Problem Statement

Neguse-kun has bought the seed of a mysterious plant. He is going to grow it at his home starting today.

Let today be day $0$. Each time $1$ day passes, this plant grows according to the following rules.

• On day $0$, the tip of the plant is at the origin $(0,0)$ of a $2$-dimensional plane.
• If the coordinates of the tip of the plant on day $i\ (\ge0)$ are $(x,y)$, then the coordinates of the tip on day $i+1$ are one of $(x+1,y),(x+1,y+1),(x,y+1),(x-1,y+1),(x-1,y)$. That is, it grows in one of the following directions: right, upper right, up, upper left, or left.
• Let $P_i,P_{i+1},P_{i+2}$ be the positions of the tip of the plant on days $i,i+1,i+2$. Then $\angle P_iP_{i+1}P_{i+2}>90^\circ$ holds. That is, the plant never bends at an acute or right angle.
• The direction of growth is chosen independently and uniformly at random from all possible directions.

Neguse-kun is troubled by the low ceiling of his home, and he is very concerned about how tall this plant will grow.

Find the expected value of the height of the plant (that is, the $y$-coordinate of its tip) on day $N$ after he starts growing it, modulo ${\rm mod}\ 998244353$.

Input

$N$

• $1\le N\le 2\times 10^5$
• $N$ is an integer.

Output

Output the expected value of the height of the plant on day $N$, ${\rm mod}\ 998244353$, on a single line.

Sample

1

798595483

2

465847366

3

277290100