错了一行

题目描述

小L有一个数列arr，是1到n的一个全排列，他想用下列算法在不消耗新空间的情况下将数列从小到大排序

for(int i=1; i<=n; i++) while(arr[i] != i)
    swap(arr[i], arr[arr[i]]);

这个代码既简洁又漂亮，小L高兴极了

但他在写代码时错了一行，变成了：

for(int i=1; i<=n; i++)
    swap(arr[i], arr[arr[i]]);

最后竟然答案还是对的！

小L想知道，对于所有的长度为n的全排列，其中有多少个全排列是可以在写错代码的时候仍然能成功排序的。

你能帮帮他吗？

输入格式

输入一行一个正整数 n。

输出格式

输出一行一个正整数，表示情况总数。

由于答案太大，你需要对998244353取模。

样例 #1

样例输入 #1

3

样例输出 #1

6

样例 #2

样例输入 #2

4

样例输出 #2

21

样例解释

当n=3时，所有排列都能复原，答案是$n!=6$

当n=4时，有三种情况不能复原，分别为

$2341$变为$3214$

$3421$变为$2134$

$4312$变为$2134$

其余所有全排列都能复原为$1234$

数据范围

第一个数据点，$n=8$

第二个数据点，$n=12$

第三个数据点，$n=14$

第四到九个数据点，$n\le5000$

第十个数据点，$n=50000$

数据加强 第十一个数据点，$n\le200000$