[Tjoi2016&Heoi2016]求和

时间限制:40s      空间限制:128MB

题目描述

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


输入格式

输入只有一个正整数


输出格式

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


样例输入

3

样例输出

87

提示

没有写明提示


题目来源

没有写明来源

Menuappsclose