問題文

$\lbrace 1,2,3, \dots , 2^N-1 \rbrace$ の部分集合 $X=\left \lbrace X_1, X_2, \dots, X_k \right \rbrace$ に対して、 $f(X)=X_1\ \mathrm{OR}\ X_2\ \mathrm{OR} \dots \mathrm{OR}\ X_k$ と定義します。ただし、$X$ が空集合の時は $f(X)=0$ とします。

$\lbrace 1,2,3, \dots , 2^N-1 \rbrace$ の部分集合 $S$ のうち次の条件を満たすものを良い集合と呼ぶことにします。

• $S$ の任意の部分集合 $U$, $V$ に対して、$U \neq V$ ならば $f(U) \neq f(V)$ が成り立つ。

$\lbrace 1,2,3, \dots , 2^N-1 \rbrace$ の部分集合 $S$ は $2^{2^N-1}$ 個ありますが、そのうち良い集合の個数を求め、 $998244353$ で割った余りを出力してください。

入力

$N$

出力

良い集合の個数を $998244353$ で割った余りを出力してください。

サンプル

2

5

4

98

100

457732232