Good Bye 2018 |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

combinatorics

dp

math

*1700

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. New Year and the Permutation Concatenation

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputLet $$$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).

Input

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

Output

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

Examples

Input

3

Output

9

Input

4

Output

56

Input

10

Output

30052700

Note

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

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/09/2023 03:52:24 (k2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|