Oh, what a big horse!

Limits: 3 sec., 512 MiB

This statement was translated automatically from Ukrainian.

Zenyk and Marichka are planning to host an excursion on their farm for the participants of the regional informatics olympiad. There are very many participants in the olympiad, so it was decided to divide them into groups. For each group of children, the excursion will be conducted separately.

On Zenyk and Marichka’s farm, there are \(n\) stallions, and all the horses have different sizes.

This year there are very, very many olympiad participants, so they will be divided into as many as \(n! = 1 \cdot 2 \cdot \dots \cdot n\) groups.

For each group of children, Zenyk will line up his \(n\) horses in a row. Moreover, the order of the horses in the row will be different for each group of children.

During the excursion, Marichka will lead the children along the row. When the children approach the first horse in the row, they will feed it a carrot and, in surprise, shout in chorus "Oh, what a big horse!". After that, Marichka will lead them further. They will feed each horse with a carrot one by one in the order of the row. Each time the horse they are feeding has a larger size than all the horses they have fed before, the children will again shout in chorus "Oh, what a big horse!".

How many times in total across all \(n!\) groups will the children shout "Oh, what a big horse!"? Since the answer can be large, output the remainder of the division of the answer by the prime number \(998244353\).

Input

The single line contains an integer \(n\) — the number of horses.

Output

Output a single integer — the remainder of the division of the answer by the prime number \(998244353\).

Constraints

\(1 \le n \le 10^6\).

Scoring consists of the following blocks:

• 1 point for each sample test from the statement,

• 6 points: \(n \le 10\),

• 11 points: \(n \le 18\),

• 31 points: \(n \le 100\),

• 22 points: \(n \le 4000\),

• 27 points: no additional constraints.

You will receive the points for a block only if your program passes all the tests in that block.

Samples

Input (stdin) сopy	Output (stdout) сopy
2	3

Input (stdin) сopy	Output (stdout) сopy
3	11

Input (stdin) сopy	Output (stdout) сopy
47	781750049

Notes

When \(n = 2\), there are two stallions on the farm — a small one and a big one. In this case, the children will be divided into \(2! = 2\) groups.

• One group will be shown a row where the small horse stands first, and the big horse stands second. The children in this group will be surprised for the first time when they see the small horse and feed it a carrot, and they will be surprised for the second time when they see the big horse.

• Another group will be shown a row where the big horse stands first, and the small horse stands second. The children will be surprised once when they see the big horse. When they feed the small horse, its size will no longer cause them excitement.

In total, the children in both groups will be surprised and shout "Oh, what a big horse!" three times.

When \(n = 3\), there are three stallions on the farm — a small one, a medium one, and a big one. The children will be divided into \(3! = 6\) groups. Marichka will show each group a row of horses in a different order. Let’s write down all possible rows and underline the horses that will cause surprise in the children.

• Small, medium, big — three surprises.

• Small, big, medium — two surprises.

• Medium, small, big — two surprises.

• Medium, big, small — two surprises.

• Big, small, medium — one surprise.

• Big, medium, small — one surprise.

In total, the children will be surprised and shout "Oh, what a big horse!" eleven times.

Don’t forget to compute the remainder modulo \(998244353\).