#P8143. [JRKSJ R4] Stirling

[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][1,n] 的排列 pp,定义其“生成图”为:该图有 nn 个点,且 1in\forall 1\le i\le n,无向边 (i,pi)(i,p_i) 存在且仅存在这些边。

给定 nn,求有多少个 [1,n][1,n] 的排列满足其生成图恰有偶数个环(自环同样计入)。

输入格式

一个整数 nn

输出格式

一个整数,表示答案。答案对 998244353998244353 取模。

3
3
114514
430461019

提示

样例 11 解释

这些排列满足条件:

{1,3,2}\{1,3,2\} {2,1,3}\{2,1,3\} {3,2,1}\{3,2,1\}

数据规模

对于 20%20\% 的数据,n10n\le 10
对于 50%50\% 的数据,n500n\le 500
对于 100%100\% 的数据,1n1061\le n\le 10^6