← 返回题目列表

Codeforces · 1266/G

G. 排列串联

中文机器翻译题面 查看原题

令 $$$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$$$ 的子数组。

你得到了$$$n$$$。求 $$$P$$$ 的不同子数组的数量。由于这个数字可能很大,因此输出它对 $$$998244353$$$(质数)取模。

输入

唯一一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 10^6$$$),如问题陈述中所述。

输出

输出一个整数 - 不同子数组的数量,以 $$$998244353$$$ 为模。

示例

输入 #1

2

输出 #1

8

输入 #2

10

输出 #2

19210869

注意

在第一个示例中,序列 $$$P = [1, 2, 2, 1]$$$。它有八个不同的子数组:$$$[1]$$$、$$$[2]$$$、$$$[1, 2]$$$、$$$[2, 1]$$$、$$$[2, 2]$$$、$$$[1, 2, 2]$$$、$$$[2, 2, 1]$$$ 和 $$$[1, 2, 2, 1]$$$。