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

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

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