K. Kosmos
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Machado, a renowned researcher at the BRUTE Space Agency, invented a device he believes can reveal important patterns for the trajectory of planetary orbits. This device, named "Kosmos", produced a revolutionary numeric sequence, but since it was programmed in pure C, a memory leak occurred which led to the device's self-destruction. After discovering this, Machado immediately started programming everything in Rust. Now, shaken by the loss of his invention, the only thing he remembers is that the sequence produced by the device was defined by the following recursive formula:

$$$F(0) = 1$$$

$$$F(1) = 2$$$

$$$F(n) = F(n-1) \cdot F(n-2)$$$, if $$$n \geq 2$$$

Kosmos had enough computational power to compute any term of this sequence from $$$1$$$ to $$$10^{18}$$$. Since the value of the term can be enormous, Machado is only interested in the remainder of this number modulo $$$998244353$$$. However, without Kosmos, Machado has no idea how to compute the $$$N$$$-th term of this sequence if $$$N$$$ is that large. Therefore, he has asked for your help.

Input

The input consists of a single line with an integer $$$N$$$ $$$(0 \leq N \leq 10^{18})$$$.

Output

Print the $$$N$$$-th term of the sequence generated by Kosmos. Since this value can be very large, print it modulo $$$998244353$$$.

Examples
Input
0
Output
1
Input
1
Output
2
Input
5
Output
32
Input
123456789123456789
Output
433257388
Input
998244353
Output
470934745