Background

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

Problem Description

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

Input Format

One integer $n$.

Output Format

One integer, the answer modulo $998244353$.

3

3

114514

430461019

Hint

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