A. Eminor Array
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Gew is looking for "Eminor" sequences $$$[a_1, a_2, \ldots, a_m]$$$ which have the following properties:

  • The sequence is not empty ($$$m \geq 1$$$);
  • $$$1 \leq a_i \leq 2^n-1$$$;
  • The array is strictly increasing ($$$a_i \lt a_{i+1}$$$, for each $$$i\leq m-1$$$);
  • There are no three consecutive elements with their bitwise XOR equal to zero ($$$a_i \oplus a_{i+1} \neq a_{i+2}$$$, for each $$$i\leq m-2$$$. Here $$$\oplus$$$ denotes the bitwise XOR operation).

Now, Gew is curious about how many "Eminor" sequences there are. Since there may be a large number of "Eminor" sequences, you only need to output the answer modulo $$$998\,244\,353$$$.

Input

The input contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^6$$$).

Output

Output a single integer, denoting the number of "Eminor" sequences, modulo $$$998\,244\,353$$$.

Examples
Input
1
Output
1
Input
2
Output
6
Input
3
Output
91
Note

For the second testcase, the following are $$$6$$$ possible "Eminor" sequences.

  • $$$[1]$$$
  • $$$[2]$$$
  • $$$[3]$$$
  • $$$[1,2]$$$
  • $$$[1,3]$$$
  • $$$[2,3]$$$

Irrelevent: Originating from an incorrect problem reading https://mirror.codeforces.com/gym/102956/problem/C XD