UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#4555. [Tjoi2016&Heoi2016]求和

统计 下载数据

Description

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

现在他想计算这样一个函数的值:
S(i, j)表示第二类斯特林数,递推公式为:
S(i, j) = j ∗ S(i − 1, j) + S(i − 1, j − 1), 1 <= j <= i − 1。
边界条件为:S(i, i) = 1(0 <= i), S(i, 0) = 0(1 <= i)
你能帮帮他吗?

Input

输入只有一个正整数

Output

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

Sample Input

3

Sample Output

87

Hint

Source