题目描述

在 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) = j \times S(i − 1, j) + S(i − 1, j − 1) \tag {$1 \le j \le i − 1$} $$

特别的，在边界 $S(i,i)=1$（$0 \leq i$），$S(i,0)=0$（$1\leq i$）。

你能帮帮他吗?

输入格式

第一行，输入一个正整数 $n$。

输出格式

输出 $f(n)$。

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

3

87

数据规模与约定

对于 $100\%$ 的数据，$1\le n \le 10^5$。