#P4555. [Tjoi2016&Heoi2016]求和

    ID: 2021 传统题 1000ms 128MiB 尝试: 1188 已通过: 659 难度: 8 上传者: 标签>CF2400提高+/省选-第二类 Stirling 数指数生成函数交换求和顺序多项式求逆多项式牛顿迭代NTT阶乘逆元预处理

[Tjoi2016&Heoi2016]求和

题目描述

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

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

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

其中 S(i,j)S(i,j) 表示第二类斯特林数,递推公式为:

$$S(i,j) = j \times S(i − 1, j) + S(i − 1, j − 1) \tag {$1 \le j \le i − 1$}$$

特别的,在边界 S(i,i)=1S(i,i)=1(0≤i0 \leq i),S(i,0)=0S(i,0)=0(1≤i1\leq i)。

你能帮帮他吗?

输入格式

第一行,输入一个正整数 nn。

输出格式

输出 f(n)f(n)。

由于结果会很大,输出 f(n)f(n) 对 998244353998244353 取模的结果即可。

3
87

数据规模与约定

对于 100%100\% 的数据,1≤n≤1051\le n \le 10^5。