Thanos does not like traditional sorting algorithms.

For a sequence $a_1, a_2, \dots, a_m$ of length $m$, define a "Thanos sort" operation as follows:

• If the current sequence is already strictly increasing, meaning $a_1 < a_2 < \dots < a_m$, the algorithm terminates immediately.
• Otherwise, choose exactly $\lfloor m / 2 \rfloor$ of the $m$ positions in the current sequence uniformly at random and delete them, preserving the relative order of the remaining elements. Then continue applying the same process to the remaining sequence.

Note that $m$ in the deletion operation above refers to the current sequence length, rather than the initial length. In other words, if $m$ elements remain at the start of a round and the sequence is not yet sorted, that round randomly deletes $\lfloor m / 2 \rfloor$ of them.

Now, first generate a permutation $p_1, p_2, \dots, p_N$ of length $N$ uniformly at random, and then apply Thanos sort to it.

Let $X$ be the final number of remaining elements. You need to calculate $\mathbb{E}[X]$ and output the answer modulo $998244353$.

Input

The input consists of a single line containing an integer $N$ $(1 \le N \le 10^6)$, denoting the length of the initial permutation.

Output

Output a single integer on one line: $\mathbb{E}[X]$ modulo $998244353$.

More formally, if the reduced fractional representation of $\mathbb{E}[X]$ is $\dfrac{P}{Q}$, output $P \cdot Q^{-1} \bmod 998244353$, where $Q^{-1}$ denotes the multiplicative inverse of $Q$ modulo $998244353$.

It can be proved that this inverse always exists within the constraints of this problem.

Examples

Input 1

2

Output 1

499122178

Input 2

4

Output 2

83187031

Note

• A "permutation" is a sequence consisting of the $N$ distinct integers $1, 2, \dots, N$.
• All random choices are uniform over all valid possibilities.
• After elements are deleted, the relative order of the remaining elements is preserved.

There are only two permutations of length $2$:

• $[1, 2]$: the sequence is already sorted, so the final number of remaining elements is $2$.
• $[2, 1]$: the sequence is not sorted, so $1$ element must be deleted at random. Whichever one is deleted, the remaining sequence has length $1$ and is necessarily sorted, so the final number of remaining elements is $1$.

Therefore, $\mathbb{E}[X] = \frac{2 + 1}{2} = \frac{3}{2}$.

Modulo $998244353$, $\frac{3}{2} \equiv 3 \cdot 2^{-1} \equiv 499122178 \pmod{998244353}.$