题目描述

在 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)$。

你能帮帮他吗?

输入格式

输入只有一个正整数 $n$。

输出格式

输出 $f(n)$。由于结果会很大，输出 $f(n)$ 对 $998244353$（$7 \times 17 \times 2^{23} + 1$）取模的结果即可。

3

87

提示

• 对于 $50\%$ 的数据，$1\leq n \leq5\times10^3$。

• 对于 $100\%$ 的数据，$1 \leq n \leq 10^5$。