CF1091D New Year and the Permutation Concatenation

给定一个整数 $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$ 取模。

在第一个样例中，总共有 $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$。 由 ChatGPT 4.1 翻译