[JRKSJ R4] Stirling

可能对您无用的提示： $$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)$$

对于 $[1,n]$ 的排列 $p$，定义其“生成图”为：该图有 $n$ 个点，且 $\forall 1\le i\le n$，无向边 $(i,p_i)$ 存在且仅存在这些边。 给定 $n$，求有多少个 $[1,n]$ 的排列满足其生成图恰有偶数个环（自环同样计入）。

一个整数 $n$。

一个整数，表示答案。答案对 $998244353$ 取模。

3

3

114514

430461019

### 样例 $1$ 解释 这些排列满足条件： $$\{1,3,2\}$$ $$\{2,1,3\}$$ $$\{3,2,1\}$$ ### 数据规模 对于 $20\%$ 的数据，$n\le 10$。\ 对于 $50\%$ 的数据，$n\le 500$。\ 对于 $100\%$ 的数据，$1\le n\le 10^6$。