D. UFC
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Tima and Batyr are playing a series of matches in the game UFC. The game has $$$n$$$ fighters, numbered in order of their strength from $$$1$$$ (weakest) to $$$n$$$ (strongest).

It is planned to hold $$$n$$$ matches in such a way that each player plays exactly once with each fighter. Before the start of the series, Tima and Batyr choose the order in which they will play with their fighters.

In each match, the winner is determined by the strength of the fighter chosen by the player. If both players choose the same fighter, the match is considered a draw, and Tima is declared the winner due to his age.

If at any point in the series Batyr wins more matches than Tima, he declares himself the stronger player and goes home. However, if all $$$n$$$ matches are played and Batyr has not gone home, he acknowledges Tima's strength.

As the most loyal fan of Tima, you became interested: how many ways are there to choose the order of fighters for the players so that Tima beats Batyr? Since the answer can be very large, calculate it modulo $$$998\, 244\, 353$$$.

Input

The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — the number of fighters and, correspondingly, matches.

Output

Print a single number — the number of ways modulo $$$998\, 244\, 353$$$.

Examples
Input
1
Output
1
Input
2
Output
3
Input
3
Output
22
Input
4
Output
310
Note

In the second example, there are only $$$4$$$ possible ways to choose the order of fighters. The only one where Batyr wins is the one where Batyr chooses the order of fighters $$$(2, 1)$$$ and Tima chooses the order of fighters $$$(1, 2)$$$. In this case, Batyr wins the first match, immediately declares himself the winner and goes home.

In the fourth example, there are $$$576$$$ possible ways to choose the order of fighters. If Batyr chooses the order of fighters $$$(1, 4, 3, 2)$$$ and Tima chooses the order of fighters $$$(1, 3, 2, 4)$$$, then the series will proceed as follows:

  1. Batyr and Tima both chose fighter $$$1$$$, so Tima wins due to his age;
  2. Batyr chose fighter $$$4$$$ and Tima chose fighter $$$3$$$, so Batyr wins;
  3. Batyr chose fighter $$$3$$$ and Tima chose fighter $$$2$$$, so Batyr wins. At this point, Batyr has already won more matches than Tima ($$$2$$$ to $$$1$$$), so Batyr declares himself the winner and goes home.