F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister
Problem 4555. -- [Tjoi2016&Heoi2016]求和

4555: [Tjoi2016&Heoi2016]求和

Time Limit: 40 Sec  Memory Limit: 128 MB
Submit: 1147  Solved: 893
[Submit][Status][Discuss]

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

[Submit][Status][Discuss]

HOME Back