In 2016, Sister Jiayuan just learned about Stirling numbers of the second kind and was very happy. Now she wants to calculate the value of the following function: $$f(n) = \sum_{i=0}^{n} \sum_{j=0}^{i} S(i, j) \times 2^j \times (j!)$$ $S(i, j)$ denotes the Stirling numbers of the second kind, with the recurrence relation: $$S(i, j) = j \times S(i - 1, j) + S(i - 1, j - 1), 1 \le j \le i - 1$$ The boundary conditions are: $S(i, i) = 1 (0 \le i)$, $S(i, 0) = 0 (1 \le i)$. Can you help her?

Input

The input contains only a single positive integer $n$.

Output

Output $f(n)$. Since the result can be very large, output $f(n) \pmod{998244353}$ (where $998244353 = 7 \times 17 \times 2^{23} + 1$).

Constraints

For 50% of the data, $1 \le n \le 5000$. For 100% of the data, $1 \le n \le 100000$.

Examples

Input 1

3

Output 1

87