CF1091D.New Year and the Permutation Concatenation

Let $n$ be an integer. Consider all permutations on integers $1$ to $n$ in lexicographic order, and concatenate them into one big sequence $p$. For example, if $n = 3$, then $p = [1, 2, 3, 1, 3, 2, 2, 1, 3, 2, 3, 1, 3, 1, 2, 3, 2, 1]$. The length of this sequence will be $n \cdot n!$.

Let $1 \leq i \leq j \leq n \cdot n!$ be a pair of indices. We call the sequence $(p_i, p_{i+1}, \dots, p_{j-1}, p_j)$ a subarray of $p$. Its length is defined as the number of its elements, i.e., $j - i + 1$. Its sum is the sum of all its elements, i.e., $\sum_{k=i}^j p_k$.

You are given $n$. Find the number of subarrays of $p$ of length $n$ having sum $\frac{n(n+1)}{2}$. Since this number may be large, output it modulo $998244353$ (a prime number).

设 $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$（一个质数）取模的结果。

The only line contains one integer $n$ ($1 \leq n \leq 10^6$), as described in the problem statement.

唯一的一行包含一个整数 $n$（$1 \leq n \leq 10^6$），其含义如题目描述中所述。

Output a single integer — the number of subarrays of length $n$ having sum $\frac{n(n+1)}{2}$, modulo $998244353$.

输出一个整数——长度为 $n$ 且元素和为 $\frac{n(n+1)}{2}$ 的子数组的个数，对 $998244353$ 取模。

In the first sample, there are $16$ subarrays of length $3$. In order of appearance, they are:

$[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]$.

Their sums are $6$, $6$, $7$, $6$, $7$, $5$, $6$, $6$, $8$, $6$, $7$, $5$, $6$, $6$, $7$, $6$. As $\frac{n(n+1)}{2} = 6$, the answer is $9$.

在第一个样例中，共有 $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$。