分数: 4 点
问题陈述
给你一个整数 N.
考虑排列 p = (p_1, p_2, \dots, p_N) of (1, 2, \dots, N).
计算有多少个这样的排列满足以下条件,并输出结果模 998244353.
- 对于每个整数 i 这样 1 \leq i \leq N-1,它必须保持 \max(p_1, p_2, \dots, p_i) \neq i.
约束
- 1 \leq N \leq 2.5 \times 10^5
- N 是一个整数
输入
输入由标准输入给出,格式如下:
N
输出
打印答案。
示例输入 1
3
示例输出 1
3
以下 3 排列 p 满足条件:
- (2,3,1)
- (3,1,2)
- (3,2,1)
示例输入 2
123456
示例输出 2
923416117