Description

对于 $[1,n]$ 的排列 $p$，定义其“生成图”为：该图有 $n$ 个点，且 $\forall 1\le i\le n$，无向边 $(i,p_i)$ 存在且仅存在这些边。

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

Input Format

一个整数 $n$。

Output Format

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

3

3

114514

430461019

Hint

样例 $1$ 解释

这些排列满足条件：

数据规模

对于 $20\%$ 的数据，$n\le 10$。
对于 $50\%$ 的数据，$n\le 500$。
对于 $100\%$ 的数据，$1\le n\le 10^6$。