Description

You are given a positive integer $N$.

Find the number of pairs of integers $(a, b)$ such that $1 \le a, b < 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 \le N \le 10^{18}$)

Output

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

Examples

Input 1

2

Output 1

0

Input 2

5

Output 2

390

Explanation

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 $390$ pairs of integers $(a, b)$ satisfying the condition.

Input 3

10000

Output 3

851087540

Hint

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 \ge 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$).