For a valid parenthesis string $S$ of length $2n$, we want to perform $n$ operations on it. Each operation can be:

1. Delete a contiguous substring () from $S$. Different positions are considered different operations. For example, ()() → ().
2. Delete a contiguous substring )( from $S$. Different positions are considered different operations. However, the )( being deleted must be adjacent in $S$ from the very beginning!

For example, this sequence of operations is valid: ()()() → ()() → (); this sequence of operations is invalid: ()()() → ()() → ().

Clearly, after $n$ operations, $S$ will be empty. Let $f(S)$ be the number of ways to empty $S$ in $n$ operations.

For all valid parenthesis strings $S$ of length $2n$, calculate $\sum f(S) \pmod{998244353}$.

Input

The input contains only a single positive integer $n$ ($1 \le n \le 250000$).

Output

Output a single integer representing the answer.

Examples

Input 1

3

Output 1

28

Note

• ((())) has 1 way to be emptied.
• (()()) has 3 ways to be emptied.
• (())() has 5 ways to be emptied.
• ()(()) has 5 ways to be emptied.
• ()()() has 14 ways to be emptied.

Total 28 ways.