There are $n(\geq 3)$ white balls arranged in a circle, numbered $1, 2, \dots, n$. You need to paint all these balls black. The operation is as follows:

1. Choose a ball that has not been chosen before (either white or black) uniformly at random.
2. Paint the chosen ball and its two adjacent balls black.
3. If all white balls are painted black, the process ends.

Calculate the expected number of operations to paint all white balls black. The answer should be taken modulo 998244353.

Input

A single positive integer $n$, representing the number of white balls.

Output

A single integer representing the expected number of operations, modulo 998244353.

Examples

Input 1

4

Output 1

2

Note 1

After the first operation, only one white ball remains. Next, there are two black balls and one white ball that can be chosen; regardless of which one is chosen, all balls will be painted black.

Input 2

5

Output 2

499122179

Constraints

For $40\%$ of the data, $n \leq 10$.

For $100\%$ of the data, $n \leq 5000$.