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]$。显然，$p$的长度为$n$·$n!$。 把任意满足$1\leq i \leq j \leq n$·$n!$ 的序列 $(p_i,p_{i+1},...,p_{j-1},p_j)$称为$p$的子列，其长度定义为$j-i+1$，其和定义为所有元素的总和，即 $\sum_{k=i}^j p_k$。 给定整数$n$，求出有多少个长度为$n$、和为$n(n+1)/2$的$p$的子列，答案对素数$998244353$取模。

题目描述

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).

输入输出格式

输入格式

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

输出格式

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

输入输出样例

输入样例 #1

3

输出样例 #1

9

输入样例 #2

4

输出样例 #2

56

输入样例 #3

10

输出样例 #3

30052700

说明

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

题意翻译

设$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]$。显然，$p$的长度为$n$·$n!$。 把任意满足$1\leq i \leq j \leq n$·$n!$ 的序列 $(p_i,p_{i+1},...,p_{j-1},p_j)$称为$p$的子列，其长度定义为$j-i+1$，其和定义为所有元素的总和，即 $\sum_{k=i}^j p_k$。 给定整数$n$，求出有多少个长度为$n$、和为$n(n+1)/2$的$p$的子列，答案对素数$998244353$取模。