For a derangement $p$ of $1 \sim n$, define an undirected graph $G(p) = (V, E)$ as follows: $V = \{1, 2, \dots, n\}$, $E = \{(i, p_i) \mid 1 \le i \le n\}$.

Define the weight $f(G)$ of an undirected graph $G$ as the sum of the squares of the sizes of all connected components in $G$. For all derangements $p$ of $1 \sim n$, calculate the sum of $f(G(p))$ modulo $998244353$.

Input

A single positive integer $n$, representing the length of the derangement.

Output

A single non-negative integer representing the answer modulo $998244353$.

Examples

Input 1

2

Output 1

4

Subtasks

For all test cases, $2 \le n < 998244353$.