P4091 [HEOI2016/TJOI2016] 求和

在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), 1 \le j \le i - 1$。 边界条件为：$S(i, i) = 1(0 \le i), S(i, 0) = 0(1 \le i)$ 你能帮帮他吗?

无

无

对于 $50\%$ 的数据，$1\leq n \leq5\times10^3$。 对于 $100\%$ 的数据，$1 \leq n \leq 10^5$。