题目描述

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

输入格式

一个整数 $n$。

输出格式

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

样例

3

3

114514

430461019