409014: GYM103415 F Cactus

Memory Limit:512 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

F. Cactustime limit per test1 secondmemory limit per test512 megabytesinputstandard inputoutputstandard 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$$$.

ExampleInput
2
Output
1
Note

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

加入题单

上一题 下一题 算法标签: