Problem Statement

There is an $N×N$ matrix. Let $a_{i,j}$ denote the value in row $i$, column $j$ of this matrix.

Initially, $a_{i,i}=1$ for each positive integer $i$ satisfying $1 \le i \le N$. For all other elements, $a_{i,j}=0\ (i \neq j)$.

You may perform the following operations any number of times, $0$ or more, in any order.

• Choose a positive integer $i$ satisfying $1 \le i \le N$ and reverse row $i$. More formally, for each positive integer $j$ satisfying $1 \le j \le N$, replace $a_{i,j}$ with $a_{i,N-j+1}$.
• Choose a positive integer $j$ satisfying $1 \le j \le N$ and reverse column $j$. More formally, for each positive integer $i$ satisfying $1 \le i \le N$, replace $a_{i,j}$ with $a_{N-i+1,j}$.

Find the number of matrices that can be obtained in the end.

Since the answer can be very large, find it modulo $998244353$.

Input

$N$

• All inputs are integers.
• $1 \le N \le 10^{18}$

Output

Find the number of matrices that can be obtained in the end.

Since the answer can be very large, find it modulo $998244353$.

Sample

2

6

1 0
0 1

0 1
0 1

2021

654946506