問題文

$\lfloor(1+\sqrt{2})^N\rfloor$を $998244353$ で割ったあまりを求めてください. ただし, $\lfloor x\rfloor$ で$x\geq n$ を満たす最大の整数 $n$ を表します.

制約

• $0 \leq N \leq 10^{18}$

入力

入力はすべて整数である。

出力

計算結果を一行に出力せよ。

サンプル

2

5

$(1+\sqrt{2})^2=5.82842712...$ なので $\lfloor(1+\sqrt{2})^2\rfloor=5$ です.

0

1

$(1+\sqrt{2})^0=1$ なので $\lfloor(1+\sqrt{2})^0\rfloor=1$ です.

100

235855606