#4555. [Tjoi2016&Heoi2016]求和

内存限制:128 MiB 时间限制:40 Sec

题目描述

在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

数据范围与提示