CF1266G.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 is $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$.

You are given $n$. Find the number of distinct subarrays of $P$. 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$ 的一个子数组。

给定 $n$，求 $P$ 中不同子数组的个数。由于该数目可能很大，请对 $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 distinct subarrays, modulo $998244353$.

输出一个整数——不同子数组的个数，对 $998244353$ 取模。

In the first example, the sequence $P = [1, 2, 2, 1]$. It has eight distinct subarrays: $[1]$, $[2]$, $[1, 2]$, $[2, 1]$, $[2, 2]$, $[1, 2, 2]$, $[2, 2, 1]$ and $[1, 2, 2, 1]$.

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