You are given a fair coin (that is, if you flip this coin, there will be a 50% chance of heads and 50% chance of tails). You would like to use it to generate a sequence of $n$ integers $a_1, a_2, \dots, a_n$. To do that, you will repeat the following process exactly $n$ times:

• Keep tossing this coin until you get a tails-up result.
• Suppose you get $k$ times of heads-up result before you stop.
• An integer $k$ is generated and added to the end of the sequence.

For a sequence of integers $b_1, b_2, \dots, b_m$, let $\text{mex}(b_1, b_2, \dots, b_m)$ be the smallest non-negative integer $x$ such that:

• For each $1 \le i < x$, there exists $1 \le j \le m$ such that $b_j = i$.
• $b_j \neq x$ for all $1 \le j \le m$.

For example, $\text{mex}(0, 1, 0, 3) = 2$, $\text{mex}(4, 3, 2, 1, 0, 6, 7, 5) = 8$ and $\text{mex}(1, 2, 3) = 0$.

Now, you would like to calculate the expected value of $\text{mex}(a_1, a_2, \dots, a_n)$, modulo $998\,244\,353$.

Input

The first line of the input contains a single integer $n$ ($1 \le n \le 10^5$).

Output

Output a single line containing a single integer, indicating the answer modulo $998\,244\,353$.

Examples

Input 1

1

Output 1

499122177

Input 2

3

Output 2

561512450

Note

In the first example:

• If $a_1 = 0$, we have $\text{mex}(a_1) = 1$. There is a $1/2$ probability of this happening.
• Otherwise, we have $\text{mex}(a_1) = 0$.

Therefore, the answer is $1 \times \frac{1}{2} + 0 \times (1 - \frac{1}{2}) = \frac{1}{2} \equiv 499122177 \pmod{998\,244\,353}$.