#2058. 「TJOI / HEOI2016」求和

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

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

现在他想计算这样一个函数的值:

f(n)=\sum_{i=0}^n \sum_{j=0}^i S(i, j) \cdot 2^j \cdot j!

S(i, j) 表示第二类斯特林数,递推公式为: S(i, j) = j \cdot S(i − 1, j) + S(i − 1, j − 1), \ 1 \leq j \leq i − 1

边界条件为: S(i, i) = 1(0 \leq i), \ S(i, 0) = 0(1 \leq i)

你能帮帮她吗?

输入格式

输入只有一个正整数。

输出格式

输出 f(n) 。由于结果会很大,输出 f(n) 998244353 \ (7 × 17 × 2^{23} + 1) 取模的结果即可。

样例

样例输入

3

样例输出

87

数据范围与提示

1 \leq n \leq 100000