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$.

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.

Constraints

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

Sample Input 1

15

Sample Output 1

192

Here is a sequence of operations that makes the product of the integers on the blackboard 192.

• The initial state of the blackboard is (15).
• An operation with x = 15 changes it to (7, 8).
• An operation with x = 7 changes it to (8, 3, 4).
• An operation with x = 4 changes it to (8, 3, 2, 2).
• An operation with x = 8 changes it to (3, 2, 2, 4, 4).

Here, the product of the integers on the blackboard is $3\times 2\times 2\times 4\times 4 = 192$.

Sample Input 2

3

Sample Output 2

3

Doing zero operations makes the product of the integers on the blackboard 3.

Sample Input 3

100

Sample Output 3

824552442

The maximum possible product of the integers on the blackboard after your operations is 5856458868470016, which should be printed modulo 998244353.

见题面 Input 部分

见题面 Output 部分