問題文

$N×N$ の行列があります。この行列の $i$ 行 $j$ 列の値を $a_{i,j}$ とします。

初め、$1 \le i \le N$ を満たす正整数 $i$ に対し、$a_{i,i}=1$ です。それ以外の要素に対しては $a_{i,j}=0\ (i \neq j)$ です。

あなたは以下の操作を好きな順序で $0$ 回以上任意の回数行えます。

• $1 \le i \le N$ を満たす正整数 $i$ を選び、$i$ 行目を反転させる。より厳密には $1 \le j \le N$ を満たす正整数 $j$ に対して $a_{i,j}$ を $a_{i,N-j+1}$ に置き換える。
• $1 \le j \le N$ を満たす正整数 $j$ を選び、$j$ 列目を反転させる。より厳密には $1 \le i \le N$ を満たす正整数 $i$ に対して $a_{i,j}$ を $a_{N-i+1,j}$ に置き換える。

最終的に作ることが可能な行列の個数を求めてください。

ただし、解はとても大きくなることがあるので $998244353$ で割った余りを求めてください。

入力

$N$

• 入力は全て整数である。
• $1 \le N \le 10^{18}$

出力

最終的に作ることが可能な行列の個数を求めてください。

ただし、解はとても大きくなることがあるので $998244353$ で割った余りを求めてください。

サンプル

2

6

1 0
0 1

0 1
0 1

2021

654946506