Epic Convolution！
因为这道题是五合一 所以我用了 鸢一折纸 的天使来命名。
话说卡老师到底会不会 Epic Convolution II 啊，这玩意有没有被解决啊
尝试写一篇人话题解。
在做这道题之前，你需要仔细阅读 具体数学（Concrete Mathematics） 的 6.2 章节，下面列出一些之后要用到的东西：
\[m!\begin{Bmatrix}n\\m\end{Bmatrix}=\sum_k k^n\binom{m}{k}(-1)^{m-k} \] \[\begin{Bmatrix}n\\m\end{Bmatrix}=\sum_k \frac{k^n(-1)^{m-k}}{k!(m-k)!} \] \[\left\langle\begin{matrix}n\\m\end{matrix}\right\rangle=\sum_{k}\begin{Bmatrix}n\\k\end{Bmatrix}\binom{n-k}{m}(-1)^{n-k-m}k!=\sum_{k=0}^m\binom{n+1}{k}(m+1-k)^n(-1)^k \] \[\left\langle\left\langle\begin{matrix}n\\k\end{matrix}\right\rangle\right\rangle=(k+1)\left\langle\left\langle\begin{matrix}n-1\\k\end{matrix}\right\rangle\right\rangle+(2n-1-k)\left\langle\left\langle\begin{matrix}n-1\\k-1\end{matrix}\right\rangle\right\rangle \] \[\left\langle\left\langle\begin{matrix}n\\k\end{matrix}\right\rangle\right\rangle=\sum_{i=0}^k\binom{2n+1}{i}(-1)^{i}\begin{Bmatrix}n+k+1-i\\k+1-i\end{Bmatrix} \]接下来依次分析各个 Subtask。
Subtask 1
\[\begin{aligned} f_n&=\sum_{k=0}^nk^ng_kh_{n-k}\\ &=\sum_{k=0}^{m-1}k^n \end{aligned} \]由于 \(n\) 固定，预处理幂的前缀和即可。
复杂度为 \(O(n)-O(1)\)。
namespace Shemesh{
ll ans[N];
void Metatron(){
IO>>n>>q;
rep(i,1,n-1)ans[i]=(ans[i-1]+qpow(i,n))%P;
}
void Shemesh(){
while(q--){
ll m;
IO>>m;
IO<<ans[m-1]<<'\n';
}
}
}// Metatron Shemesh 绝灭天使·日轮
Subtask 2
\[f_n=\sum_{k=0}^{n}k^n\frac{1}{(k+m+1)!}\frac{(-1)^{n-k-m}}{(n-k-m)!} \]显然这里可以提一个组合数，两边乘以 \((n+1)!\) 可得
\[(n+1)!f_n=\sum_{k=0}^{n}k^n\binom{n+1}{k+m+1}(-1)^{n-k-m} \]然后这个 \(k^n\) 显然要拿去配斯特林数，我们观察一下这个式子，然后来尝试强行凑一个。
\[\begin{Bmatrix}n\\m\end{Bmatrix}=\sum_k \frac{k^n(-1)^{m-k}}{k!(m-k)!} \]那么组合数可以产生求和符号，首先可以把 \((-1)^{n-k-m}\) 拆成 \((-1)^{n-j-m}(-1)^{j-k}\)，\(j\) 是外层求和枚举的变量，然后来考虑分母怎么动，这个时候就可以把斯特林数的式子改一下变成：
\[\begin{Bmatrix}n\\j\end{Bmatrix}=\sum_k \frac{k^n(-1)^{j-k}}{k!(j-k)!} \]那么我们整一个 \(\dbinom{j}{k}\) 就可以搞出来了，下面考虑怎么把 \(\dbinom{n+1}{k+m+1}\) 搞成求和形式。
事实上根据生成函数容易证明：
\[\binom{n+1}{k+m+1}=\sum_{j}\binom{j}{k}\binom{n-j}{m} \]然后带进去就可以得到我们想要的式子：
\[\begin{aligned} \sum_{k=0}^{n}k^n\binom{n+1}{k+m+1}(-1)^{n-k-m}&=\sum_{k=0}^{n}k^n(-1)^{n-k-m}\sum_{j}\binom{j}{k}\binom{n-j}{m}\\ &=\sum_{j}(-1)^{n-j-m}\binom{n-j}{m}\sum_{k=0}^{n}k^n(-1)^{j-k}\binom{j}{k}\\ &=\sum_{j}(-1)^{n-j-m}\binom{n-j}{m}j!\begin{Bmatrix}n\\j\end{Bmatrix} \end{aligned} \]然后你就会发现和欧拉数的通项一完全一致，用通项二带进去可得
\[f_n=\frac{1}{(n+1)!}\sum_{k=0}^m\binom{n+1}{k}(m+1-k)^n(-1)^k \]预计算幂和阶乘，单次 \(O(m)\) 即可。
复杂度 \(O(nm)-O(m)\)。
namespace Malakh{
ll fac[N],invfac[N],pw[25][N];
void Metatron(ll n,ll m){
fac[0]=1;
rep(i,1,n)fac[i]=fac[i-1]*i%P;
invfac[n]=qpow(fac[n],P-2);
Rep(i,n-1,0)invfac[i]=invfac[i+1]*(i+1)%P;
rep(i,1,m){
pw[i][0]=1;
rep(j,1,n)pw[i][j]=pw[i][j-1]*i%P;
}
}
ll C(ll n,ll m){return fac[n]*invfac[m]%P*invfac[n-m]%P;}
void Malakh(){
for(IO>>q;q--;){
IO>>n>>m;
ll ans=0;
rep(k,0,m){
if(k&1^1)ans=(ans+C(n+1,k)*pw[m+1-k][n]%P)%P;
else ans=(ans+(P-C(n+1,k))*pw[m+1-k][n]%P)%P;
}
IO<<ans*invfac[n+1]%P<<'\n';
}
}
}//Metatron Mal'akh 绝灭天使·天翼
Subtask 5
因为 sub3 和 sub4 有点毁天灭地，所以先来讲 Sub5 了。
首先出题人显然把这玩意的 \(k+1\) 次幂强行拆开了，现在我们把它合起来，顺便把 \(k+1\) 转化成 \(k\)。
\[\begin{aligned} Ans&=\sum_{k=0}^{m}\sum_{i=0}^{m-k}\frac{\dbinom{2n+1}{i}(-1)^{m-k}(k+1)^{m+n+1-i}}{(m-k-i)!(k+1)!}\\ &=\sum_{k=1}^{m+1}\sum_{i=0}^{m-k+1}\frac{\dbinom{2n+1}{i}(-1)^{m-k}k^{m+n+1-i}}{(m-k+1-i)!k!}\\ \end{aligned} \]继续考虑怎么化出斯特林数。
首先观测到 \(k=0\) 时，后面的式子也是 \(0\)，所以可以把 \(k=0\) 扔进来。
天然的 \(\dfrac{k^{m+n+1-i}}{(m-k+1-i)!k!}\) 肯定不要动，那么 \(i\) 是固定的，考虑其余怎么配。
代入斯特林数的通项，我们可以发现：
\[\begin{Bmatrix}m+n+1-i\\m+1-i\end{Bmatrix}=\sum_k \frac{k^{m+n+1-i}(-1)^{m+1-k-i}}{k!(m-k+1-i)!} \]直接拆 \((-1)^{m-k}\) 为 \((-1)^{m+1-k-i}(-1)^{i-1}\) 就可以了。
于是原式化为
\[\begin{aligned} Ans&=\sum_{k=0}^{m+1}\sum_{i=0}^{m-k+1}\frac{\dbinom{2n+1}{i}(-1)^{m-k}k^{m+n+1-i}}{(m-k+1-i)!k!}\\ &=\sum_{i=0}^{m}\sum_{k=0}^{m-i+1}\frac{\dbinom{2n+1}{i}(-1)^{m-k}k^{m+n+1-i}}{(m-k+1-i)!k!}\\ &=\sum_{i=0}^{m}\dbinom{2n+1}{i}(-1)^{i-1}\sum_{k=0}^{m-i+1}\frac{(-1)^{m+1-k-i}k^{m+n+1-i}}{(m-k+1-i)!k!}\\ &=\sum_{i=0}^{m}\dbinom{2n+1}{i}(-1)^{i-1}\begin{Bmatrix}n+k+1-i\\k+1-i\end{Bmatrix} \end{aligned} \]注意到这正好是二阶欧拉数的通项，而注意到数据范围只有 \(2000\)，所以可以通过递归式 \(n^2\) dp 求得。
复杂度为 \(O(n^2)-O(1)\) 的。
namespace Satan{
ll Euler[2005][2005];
void Devil(ll n){
rep(i,0,n)Euler[i][0]=1;
rep(i,1,n)rep(j,1,i)Euler[i][j]=((j+1)*Euler[i-1][j]%P+(2*i-1-j)*Euler[i-1][j-1])%P;
}
void Satan(){
for(IO>>q;q--;){
IO>>n>>m;
IO<<Euler[n][m]<<'\n';
}
}
}//Satan 反转体 救世魔王
目前你可以得到 \(52\) 分的高分。（我目前就写了这么多）
Subtask 3
相比 Subtask 2 而言，数据范围上升到了 \(998244352\)，考虑怎么优化预处理。
快速阶乘算法我不会，所以上分块打表。
为了防止快速幂被卡，所以上分块打表。
然后这个 sub 就没了。
Subtask 4
\[f_n=\sum_{k=0}^{n}k^n\frac{k^m}{k!}\frac{(-1)^{n-k}}{(n-k)!} \]小 Q 对小 K 说：你这个菜鸡，这不显然的第二类斯特林数吗，你斯特林数怎么学的了。
然后他仔细看了一遍，
\[n\le 10^{10^5},m\le 10 \]傻眼了，发现他不会这道题。
所以我们需要用 OEIS 来解决这道题！
根据 oeis 上 formula 板块列出的列 EGF，我们可以知道：
\[F_k(x)=\exp x\times \sum_{m=0}^{k-1}\operatorname{A112493}(k-1,m)\times \frac{x^{k-1+m}}{(k-1+m)!} \]注意到 \(m\le 10\)，我们可以考虑把 A112493 的前面几行根据定义式算出来（复杂度 \(O(m^3)\)，如果你高兴可以打表），然后每次查询暴力计算就行了。
复杂度 \(O(m^3)-O(m)\)，如果不采用打表。
后面 \(n\) 的范围过大，我们考虑使用边读入边取模的方式解决。
于是这道题就做完了。