C0630 [TJOI/HEOI2016]求和

在 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)$

你能帮帮她吗?

样例输入 1

3

样例输出 1

87