题目描述

小明最近想到了一道题，要来考考你。

题目是这样的：给定 $n$，$0\le i,j<2^n$，求 $i,j$ 满足 $(i \operatorname{and} j)(i \operatorname{or} j)=ij$ 的对数模 $998244353$ 的结果。

输入格式

一行一个自然数 $n$。

输出格式

输出答案。

样例 #1

样例输入 #1

2

样例输出 #1

14

样例 #2

样例输入 #2

5

样例输出 #2

454

样例 #3

样例输入 #3

114514

样例输出 #3

508206609

提示

样例 $1$ 解释：只有 $(2,3)$ 和 $(3,2)$ 不符合要求。

对于 $20\%$ 的数据：$0\le n\le10$。

对于 $100\%$ 的数据：$0\le n<2^{30}$。