令 $$$n$$$ 为整数。按字典顺序考虑整数 $$$1$$$ 到 $$$n$$$ 的所有排列,并将它们连接成一个大序列 $$$p$$$。例如,如果 $$$n = 3$$$,则 $$$p = [1, 2, 3, 1, 3, 2, 2, 1, 3, 2, 3, 1, 3, 1, 2, 3, 2, 1]$$$。该序列的长度将为$$$n \cdot n!$$$。
设 $$$1 \leq i \leq j \leq n \cdot n!$$$ 为一对索引。我们将序列 $$$(p_i, p_{i+1}, \dots, p_{j-1}, p_j)$$$ 称为 $$$p$$$ 的子数组。它的长度定义为其元素的数量,即 $$$j - i + 1$$$。它的总和是其所有元素的总和,即 $$$\sum_{k=i}^j p_k$$$。
你得到了$$$n$$$。求 $$$p$$$ 长度为 $$$n$$$ 且总和为 $$$\frac{n(n+1)}{2}$$$ 的子数组的数量。由于这个数字可能很大,因此输出它对 $$$998244353$$$(质数)取模。
输入
唯一一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 10^6$$$),如问题陈述中所述。
输出
输出一个整数 - 长度为 $$$n$$$ 且总和为 $$$\frac{n(n+1)}{2}$$$ 的子数组的数量,以 $$$998244353$$$ 为模。
示例
输入 #1
3
输出 #1
9
输入 #2
4
输出 #2
56
输入 #3
10
输出 #3
30052700
注意
在第一个示例中,有 $$$16$$$ 长度为 $$$3$$$ 的子数组。按照出现顺序,它们是:
$$$[1, 2, 3]$$$, $$$[2, 3, 1]$$$, $$$[3, 1, 3]$$$, $$$[1, 3, 2]$$$, $$$[3, 2, 2]$$$, $$$[2, 2, 1]$$$, $$$[2, 1, 3]$$$, $$$[1, 3, 2]$$$, $$$[3, 2, 3]$$$, $$$[2, 3, 1]$$$, $$$[3, 1, 3]$$$, $$$[1, 3, 1]$$$, $$$[3, 1, 2]$$$, $$$[1, 2, 3]$$$, $$$[2, 3, 2]$$$, $$$[3, 2, 1]$$$.
它们的总和为 $$$6$$$、$$$6$$$、$$$7$$$、$$$6$$$、$$$7$$$、$$$5$$$、$$$6$$$、$$$6$$$、$$$8$$$、$$$6$$$、$$$7$$$、$$$5$$$、 $$$6$$$、$$$6$$$、$$$7$$$、$$$6$$$。由于$$$\frac{n(n+1)}{2} = 6$$$,答案是$$$9$$$。