Colin recently received a gift from Eva: - a mysterious ascending random number sequence generator! You only need to input a positive integer $n$, and the generator will return an ascending sequence to you! After repeated experiments, Colin figured out how the generator works.

Initially, the generator will create a new empty sequence and select a number $k$ from $\{1, 2, \cdots, n\}$ with equal probability.

Then, the generator will select a number $x$ from $\{1, 2, \cdots, n\}$ with equal probability as the first element of the sequence.

Next, the generator will repeat the following process:

• If the maximum element in the sequence is greater than or equal to $k$, the generator will stop running immediately and return the current sequence that has already been generated.
• Otherwise, if the maximum element in the sequence is $y$, then the generator will select a number $x$ from $\{y + 1, y + 2, \cdots, n\}$ with equal probability and append $x$ to the end of the sequence.

Now Colin wants to know, for a given $n$, what the expected length of the sequence returned by the generator is?

Input

A single integer $n$ ($1 \le n \le 10^7$).

Output

A single integer, representing the expected length modulo $998244353$.

Examples

Input 1

3

Output 1

55458021

Note

• If $k = 1$, the expected length is $1$.
• If $k = 2$, the expected length is $1 \times \frac{2}{3} + 2 \times \frac{1}{3} = \frac{4}{3}$.
• If $k = 3$, the expected length is $1 \times \frac{1}{3} + 2 \times (\frac{1}{3} + \frac{1}{3} \times \frac{1}{2}) + 3 \times \frac{1}{3} \times \frac{1}{2} = \frac{11}{6}$.

Thus, the answer is $(1 + \frac{4}{3} + \frac{11}{6})/3 = \frac{25}{18}$.

The inverse of $18$ modulo $998244353$ is $720954255$, so the output result is $25 \times 720954255 \bmod 998244353 = 55458021$.