Problem1044--#2058. 「TJOI / HEOI2016」求和

1044: #2058. 「TJOI / HEOI2016」求和

Time Limit: 1 Sec  Memory Limit: 256 MB
Submit: 0  Solved: 0
[Submit] [Status] [Web Board] [Creator:]

Description

在2016年,佳媛姐姐刚刚学习了第二类斯特林数,非常开心。

现在他想计算这样一个函数的值:

f(n)=∑i=0n∑j=0iS(i,j)⋅2j⋅j!f(n)=\sum_{i=0}^n \sum_{j=0}^i S(i, j) \cdot 2^j \cdot j!f(n)=i=0nj=0iS(i,j)2jj!

S(i,j)S(i, j)S(i,j)表示第二类斯特林数,递推公式为: S(i,j)=jS(i1,j)+S(i1,j1), 1ji1

边界条件为:S(i,i)=1(0≤i), S(i,0)=0(1≤i)S(i, i) = 1(0 \leq i), \ S(i, 0) = 0(1 \leq i)S(i,i)=1(0i), S(i,0)=0(1i)

你能帮帮她吗?

输入格式

输入只有一个正整数。

输出格式

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

样例

样例输入

3

样例输出

87

数据范围与提示

1≤n≤1000001 \leq n \leq 1000001n100000


Source/Category

 

[Submit] [Status]