Description:


在2016年,佳媛姐姐刚刚学习了第二类斯特林数,非常开心。
现在他想计算这样一个函数的值:

\[f(n)=\sum_{i=0}^n\sum_{j=0}^i S(i, j)\times 2^j\times (j!)\]

\(S(i, j)\) 表示第二类斯特林数,递推公式为:

\[S(i, j) = j \times S(i - 1, j) + S(i - 1, j - 1), 1\le j\le i -1\]

边界条件为:

\[S(i, i) = 1 (0\le i), S(i, 0) = 0(1 \le i)\]

你能帮帮他吗?

Input:


输入只有一个正整数

Output:


输出 \(f(n)\) 。由于结果会很大,输出 \(f(n)\)\(998244353(7 \times 17 \times 2^{23} + 1)\) 取模的结果即可。
\(1\le n\le 100000\)

Sample Input:


Sample Output:


题解:


对第二类斯特林数不太熟悉,通项公式是这样的:

这个还是比较好理解的。
然后带进去:

\(g(x)=\frac{(-1)^x}{x!},h(n)=\frac{x^{n+1}-1}{(x-1)\times x!}\)

\[f(n) = \sum_{j=0}^n 2^j \times j! \sum_{k=0}^j g(k)\times h(j-k)\]

然后用NTT计算一下卷积。