問題文

寝癖くんは不思議な植物の種を買ってきました。今日から自分の家で育てようとしています。

今日を $0$ 日目として、この植物は $1$ 日経つごとに、次のルールで成長していきます。

• $0$ 日目、植物の先端は $2$ 次元平面上の原点 $(0,0)$ にある。
• $i\ (\ge0)$ 日目の植物の先端の座標を $(x,y)$ としたとき、$i+1$ 日目の植物の先端の座標は $(x+1,y),(x+1,y+1),(x,y+1),(x-1,y+1),(x-1,y)$ のいずれかである。すなわち、右、右上、上、左上、左のいずれかの方向に伸びる。
• $i,i+1,i+2$ 日目の植物の先端の位置を $P_i,P_{i+1},P_{i+2}$ とすると、$\angle P_iP_{i+1}P_{i+2}>90^\circ$ を満たす。すなわち鋭角や直角に折れ曲がることはない。
• 伸びる方向は可能なすべての方向から等確率で独立に選ばれるとする。

寝癖くんは自分の家の天井の低さに悩まされており、この植物がどのくらいの高さまで伸びるのかをとても気にしています。

育て始めてから $N$ 日目の植物の高さ（すなわち先端の $y$ 座標）の期待値を ${\rm mod}\ 998244353$ で求めてください。

入力

$N$

• $1\le N\le 2\times 10^5$
• $N$ は整数

出力

$N$ 日目の植物の高さの期待値 ${\rm mod}\ 998244353$ を一行で出力してください。

サンプル

1

798595483

2

465847366

3

277290100