F. Cactus
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

An undirected connected graph is called a cactus, if and only if each edge of it belongs to at most one simple cycle. A simple cycle is a cycle that has no repeated vertices.

Now suppose there are $$$f_n$$$ cactuses of $$$n$$$ distinct vertices, and the cactuses may have parallel edges and must not have self-loops, you need to calculate $$$\sum_{i=1}^n \prod_{j\neq i} \frac{1+f_i-f_if_j}{f_i - f_j}$$$.

The sum of a zero-length sequence is $$$0$$$, and the product of a zero-length sequence is $$$1$$$.

Input

A single line contains an integer $$$n$$$ ($$$1\le n\le 3\times 10^5$$$).

Output

Suppose the reduced form of the answer is $$$\frac{x}{y}$$$, and you only need to output the value of $$$x\times y^{998244351} \bmod 998244353$$$.

Example
Input
2
Output
1
Note

In the first example, $$$f_1=1,f_2=2$$$, and the answer is $$$1$$$.