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

输入输出格式

输入格式


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

输出格式


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

输入输出样例

输入样例 #1

3

输出样例 #1

87

说明

对于 $50\%$ 的数据,$1\leq n \leq5\times10^3$。 对于 $100\%$ 的数据,$1 \leq n \leq 10^5$。