#P1561. 错了一行

错了一行

错了一行

题目描述

小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!=6n!=6

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

23412341变为32143214

34213421变为21342134

43124312变为21342134

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

数据范围

第一个数据点,n=8n=8

第二个数据点,n=12n=12

第三个数据点,n=14n=14

第四到九个数据点,n5000n\le5000

第十个数据点,n=50000n=50000

数据加强 第十一个数据点,n200000n\le200000