409014: GYM103415 F Cactus
Description
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$$$.
InputA single line contains an integer $$$n$$$ ($$$1\le n\le 3\times 10^5$$$).
OutputSuppose 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$$$.
ExampleInput2Output
1Note
In the first example, $$$f_1=1,f_2=2$$$, and the answer is $$$1$$$.