A. Ascending Random Number Sequence
time limit per test
1 second
memory limit per test
128 megabytes
input
standard input
output
standard output

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$$$.

Example
Input
3
Output
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$$$.