O. Xor Triangle
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given a positive integer $$$N$$$.

Find the number of pairs of integers $$$(a,b)$$$ such that $$$1 \leq a,b \lt 2^N$$$ and the following condition is satisfied, modulo the prime $$$998244353$$$.

  • There exists a non-degenerate triangle whose side lengths are $$$a,b,a\oplus b$$$.

Here, for integers $$$x,y$$$, $$$x\oplus y$$$ denotes the bitwise XOR of $$$x$$$ and $$$y$$$.

Input

The first line contains an integer $$$N$$$. ($$$1 \leq N \leq 10^{18}$$$)

Output

Print the number of pairs of integers $$$(a,b)$$$ satisfying the condition, modulo the prime $$$998244353$$$.

Examples
Input
2
Output
0
Input
5
Output
390
Input
10000
Output
851087540
Note

For the second example, for instance, $$$(a,b)=(13,24)$$$ satisfies the condition. Since $$$a \oplus b = 13 \oplus 24 = 21$$$, there exists a non-degenerate triangle whose side lengths are $$$13,24,21$$$.

There are exactly $$$390$$$ pairs of integers $$$(a,b)$$$ satisfying the condition.

The bitwise XOR $$$x \oplus y$$$ of non-negative integers $$$x,y$$$ is defined as follows.

  • In the binary representation of $$$x \oplus y$$$, the digit at the $$$2^k \ (k \geq 0)$$$ place is $$$1$$$ if and only if exactly one of the digits at the $$$2^k$$$ place in the binary representations of $$$x$$$ and $$$y$$$ is $$$1$$$; otherwise, it is $$$0$$$.

For example, $$$3 \oplus 5 = 6$$$ (in binary, $$$011 \oplus 101 = 110$$$).