题目描述

$0$ 以上 $2^N$ 未満の非負整数からなる集合 $S$ のうち、以下の条件を満たすものの個数を $998244353$ で割ったあまりを出力してください。

• $S$ の空でない部分集合 $T$ は以下のどちらかを満たす。
  • $T$ の要素数が奇数
  • $T$ の全要素の $\mathrm{XOR}$ が $0$ でない

$\mathrm{XOR}$ とは 非負整数 $A,\ B$ のビット単位 $\mathrm{XOR}$ 、$A\ \oplus\ B$ は、以下のように定義されます。

• $A\ \oplus\ B$ を二進表記した際の $2^k$ ($k\ \geq\ 0$) の位の数は、$A,\ B$ を二進表記した際の $2^k$ の位の数のうち一方のみが $1$ であれば $1$、そうでなければ $0$ である。

例えば、$3\ \oplus\ 5\ =\ 6$ となります (二進表記すると: $011\ \oplus\ 101\ =\ 110$)。
一般に $k$ 個の整数 $p_1,\ p_2,\ p_3,\ \dots,\ p_k$ のビット単位 $\mathrm{XOR}$ は $ (\dots\ ((p_1\ \oplus\ p_2)\ \oplus\ p_3)\ \oplus\ \dots\ \oplus\ p_k) $ と定義され、これは $p_1,\ p_2,\ p_3,\ \dots\ p_k$ の順番によらないことが証明できます。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$

输出格式

答えを出力せよ。

题目大意

题面

请输出满足下述条件的集合 $S \in \{0,1,2,\ldots,2^N-1\}$ 的个数对 $998244353$ 取模后的结果。

• 对于所有 $S$ 的非空子集 $T$，均满足下列条件之一：

  • $\lvert T \rvert$ 为奇数；

  • $T$中所有元素的异或和不为 $0$。

何为异或?

输入

一行一个整数 $N$。

输出

一行一个整数，表示答案对 $998244353$ 取模后的结果。

数据范围&限制

$1 \le N \le 2 \times 10^5$，保证输入数据全为整数。

2

15

146

743874490

提示

制約

• $1\ \le\ N\ \le\ 2\ \times\ 10^5$
• 入力は全て整数である。

Sample Explanation 1

$\lbrace\ 0,2,3\ \rbrace$ や $\lbrace\ 1\ \rbrace$ や $\lbrace\ \rbrace$ は条件を満たします。 $\lbrace\ 0,1,2,3\ \rbrace$ は条件を満たしません。 なぜなら、$\lbrace\ 0,1,2,3\ \rbrace$ は部分集合 $\lbrace\ 0,1,2,3\ \rbrace$ が要素数が偶数であり、全要素の $\mathrm{XOR}$ が $0$ であるからです。