P8143 [JRKSJ R4] Stirling

A possibly useless hint: $$f(n)=\sum_{i=0}^n \begin{Bmatrix} n\\i\end{Bmatrix}g(i) \leftrightarrow g(n)=\sum_{i=0}^n (-1)^{n-i} \begin{bmatrix} n\\i\end{bmatrix} f(i)$$

For a permutation $p$ of $[1,n]$, define its “generated graph” as follows: the graph has $n$ vertices, and for all $1\le i\le n$, the undirected edge $(i,p_i)$ exists, and only these edges exist. Given $n$, find how many permutations of $[1,n]$ have a generated graph with exactly an even number of cycles (self-loops are also counted).

One integer $n$.

One integer, the answer modulo $998244353$.

### Explanation for Sample $1$ These permutations satisfy the condition: $$\{1,3,2\}$$ $$\{2,1,3\}$$ $$\{3,2,1\}$$ ### Constraints For $20\%$ of the testdata, $n\le 10$. For $50\%$ of the testdata, $n\le 500$. For $100\%$ of the testdata, $1\le n\le 10^6$. Translated by ChatGPT 5