Problem Statement

There is an integer $X$ written on a blackboard. You can do the operation below any number of times (possibly zero).

• Choose an integer $x$ written on the blackboard.
• Erase one $x$ from the blackboard and write two new integers $\lfloor \frac{x}{2}\rfloor$ and $\lceil \frac{x}{2}\rceil$.

Find the maximum possible product of the integers on the blackboard after your operations, modulo $998244353$.

What are $\lfloor \frac{x}{2}\rfloor$ and $\lceil \frac{x}{2}\rceil$? For a real number $x$, $\lfloor x\rfloor$ denotes the largest integer not greater than $x$, and $\lceil x\rceil$ denotes the smallest integer not less than $x$. For example, the following holds. For $x = 2$, we have $\lfloor \frac{x}{2}\rfloor = 1$ and $\lceil \frac{x}{2}\rceil = 1$. For $x = 3$, we have $\lfloor \frac{x}{2}\rfloor = 1$, $\lceil \frac{x}{2}\rceil = 2$.

Constraints

• $1\leq X \leq 10^{18}$

Input

Input is given from Standard Input from the following format:

X

Output

Print the maximum possible product of the integers on the blackboard after your operations, modulo $998244353$.