题目背景

可能对您无用的提示：

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