[HEOI2016/TJOI2016]求和

题目描述

在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)$ 你能帮帮他吗?

输入输出格式

输入格式


输入只有一个正整数

输出格式


输出f(n)。由于结果会很大,输出f(n)对998244353(7 × 17 × 223 + 1)取模的结果即可。

输入输出样例

输入样例 #1

3

输出样例 #1

87

说明

对于50%数据1 ≤ n ≤5000 对于100%数据1 ≤ n ≤ 100000