Description

In 2016, Sister Jiayuan had just learned about the Stirling numbers of the second kind and was very happy.

Now she wants to compute 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: $S(i, j) = j \times S(i - 1, j) + S(i - 1, j - 1), 1 \le j \le i - 1$.

Boundary conditions: $S(i, i) = 1 (0 \le i)$, $S(i, 0) = 0 (1 \le i)$.

Can you help her?

Input Format

The input contains a single positive integer $n$.

Output Format

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

3

87

Hint

For 50% of the testdata, $1 \le n \le 5 \times 10^3$. For 100% of the testdata, $1 \le n \le 10^5$.

Translated by ChatGPT 5