TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P4026
  • Problem
  • P4026[Tjoi2016&Heoi2016]求和
    Limits : Time Limit : - MS   Memory Limit : 165536 KB
    Judgment Tips : 1s
    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 Format

    输入只有一个正整数

    Output Format

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

    Sample Input

    3

    Sample Output

    87