『MdOI R1』Epic Convolution

小 Q 是神仙，尤其喜欢多项式。 这天小 K 问了道题： 给定长度 $n$ 的序列 $g,h$，求 $f$ 满足 $f_n=\sum\limits_{k=0}^{n}g_kh_{n-k}$。 小 Q 对小 K 说：你这个菜鸡，这不随便卷一下就行了吗，你 FFT 怎么学的了。 然后小 K 花了一个月学习 FFT 和 NTT。又跑过去问小 Q 一道题： 给定长度 $n$ 的序列 $g,h$，求 $f$ 满足 $f_n=\sum\limits_{k=0}^{n}\binom{n}{k}g_kh_{n-k}$。 小 Q 对小 K 说：你这个菜鸡，这不随便卷一下就行了吗，你 FFT 怎么学的了。 然后小 K 又花了一个月学习 FFT 和 NTT。又跑过去问小 Q 一道题： 给定长度 $n$ 的序列 $g,h$，求 $f$ 满足 $f_n=\sum\limits_{k=0}^{n}k^ng_kh_{n-k}$。 小 Q 对小 K 说：你这个菜鸡，这不随便卷一下就行了吗，你 FFT 怎么学的了。 然后他仔细看了一遍，傻眼了，发现他不会这道题。 为了吊打小 K，你需要告诉他 $4$ 个特殊情况的做法。

给定特定的序列 $g,h$，求 $f_n$ 满足 $f_n=\sum\limits_{k=0}^{n}k^ng_kh_{n-k}$。 本题有五个子任务，前四个子任务给定不同形式的 $g,h$，需要求出 $f_n$，第五个子任务不依赖于这个等式，但是形式上与此相似。 **注意，本题所有输出请对 $998244353$（$119\times 2^{23}+1$，一个质数）取模。** --- **Subtask 1（4 pts）：** 给定一个 $n$，你需要回答 $q$ 组询问，每组询问给定一个整数 $m$。 每组询问的 $g$ 和 $h$ 如下所示（$0\leq k\leq n$）： $$g_k=\begin{cases}1,&k<m\\0,&k\geq m\end{cases}$$ $$h_k=1$$ 你需要回答出 $f_n$ 的值。 --- **Subtask 2,3（16,16 pts）：** 这两个子任务给定的序列 $g,h$ 形式相同，但数据范围不同，请仔细阅读数据范围。 你需要回答 $q$ 组询问，每组询问给定两个整数 $n,m$。 每组询问的 $g$ 和 $h$ 如下所示（$0\leq k\leq n$）： $$g_k=\frac{1}{(k+m+1)!}$$ $$h_k=\begin{cases}0,&k<m\\\frac{(-1)^{k-m}}{(k-m)!},&k\geq m\end{cases}$$ 你需要回答出 $f_n$ 的值。 --- **Subtask 4（32 pts）：** 你需要回答 $q$ 组询问，每组询问给定两个整数 $n,m$。 每组询问的 $g$ 和 $h$ 如下所示（$0\leq k\leq n$）： $$g_k=\frac{k^m}{k!}$$ $$h_k=\frac{(-1)^k}{k!}$$ 你需要回答出 $f_n$ 的值。 --- **Subtask 5（32 pts）：** 你需要回答 $q$ 组询问，每组询问给定两个整数 $n,m$。 **注意下面 $n,m$ 的含义，不要看反。** $$\sum\limits_{k=0}^{m}(k+1)^m\dfrac{(k+1)^{n+1}}{(k+1)!}\sum\limits_{i=0}^{m-k}\dfrac{\binom{2n+1}{i}(-1)^{m-k}}{(m-k-i)!(k+1)^i}$$ 你需要回答出上面这个式子的值。 与前四个 Subtask 相似之处是，求和的一开始是幂的形式。

第一行一个整数 $op$，表示子任务编号。 若 $op=1$： 第二行一个整数 $n$，第三行一个整数 $q$； 接下来 $q$ 行，每行一个整数 $m$。 若 $op\in \{2,3,4,5\}$： 第二行一个整数 $q$； 接下来 $q$ 行：每行两个整数 $n,m$。 所有变量含义见题目描述。

对于每组询问，一行一个整数，表示答案。

1
5
2
2
3

1
33

2
2
4 2
18 7

440891256
841247136

4
2
4 2
20 9

65
429844531

5
2
4 2
30 12

58
475486366

### 样例解释 1 在这组样例中，需要解决第一个子任务，$n=5,\ \ q=2$。 第一组询问中，$m=2$，则（省略了 $0$ 的加数项）： $$[g_0\ \ g_1\ \ g_2\ \ g_3\ \ g_4\ \ g_5]=[1\ \ 1\ \ 0\ \ 0\ \ 0\ \ 0] $$ $$[h_0\ \ h_1\ \ h_2\ \ h_3\ \ h_4\ \ h_5]=[1\ \ 1\ \ 1\ \ 1\ \ 1\ \ 1] $$ $$f_5=1^5\times g_1h_4=1$$ 第二组询问中，$m=3$，则： $$[g_0\ \ g_1\ \ g_2\ \ g_3\ \ g_4\ \ g_5]=[1\ \ 1\ \ 1\ \ 0\ \ 0\ \ 0]$$ $$[h_0\ \ h_1\ \ h_2\ \ h_3\ \ h_4\ \ h_5]=[1\ \ 1\ \ 1\ \ 1\ \ 1\ \ 1]$$ $$f_5=1^5\times g_1h_4+2^5\times g_2h_3=33$$ ------ ### 样例解释 2 在这组样例中，需要解决第二个子任务，$q=2$。 第一组询问中，$n=4,\ \ m=2$，则： $$[g_0\ \ g_1\ \ g_2\ \ g_3\ \ g_4]=[\dfrac{1}{6}\ \ \dfrac{1}{24}\ \ \dfrac{1}{120}\ \ \dfrac{1}{720}\ \ \dfrac{1}{5040}] $$ $$[h_0\ \ h_1\ \ h_2\ \ h_3\ \ h_4]=[0\ \ 0\ \ 1\ \ -1\ \ \dfrac{1}{2}] $$ $$f_5=1^4\times g_1h_3+2^4\times g_2h_2=\dfrac{11}{120} $$ $f_5=\dfrac{11}{120}$ 对 $998244353$ 取模后等于 $440891256$。 第二组询问范围过大，不进行样例解释。 ------ ### 样例解释 3 在这组样例中，需要解决第四个子任务，$q=2$。 第一组询问中，$n=4,\ \ m=2$，则： $$[g_0\ \ g_1\ \ g_2\ \ g_3\ \ g_4]=[0\ \ \ 1\ \ \ 2\ \ \ \dfrac{3}{2}\ \ \dfrac{2}{3}] $$ $$[h_0\ \ h_1\ \ h_2\ \ h_3\ \ h_4]=[1\ \ -1\ \ \dfrac{1}{2}\ \ -\dfrac{1}{6}\ \ \dfrac{1}{24}] $$ $$f_5=1^4\times g_1h_3+2^4\times g_2h_2+3^4\times g_3h_1+4^4\times g_4h_0=65 $$ 第二组询问范围过大，不进行样例解释。 --- ### 样例解释 4 在这组样例中，需要解决第五个子任务，$q=2$。 第一组询问中，$n=4,\ \ m=2$，则枚举 $k,i$： $$k=0,\ \ i=0:\ \ (k+1)^m\dfrac{(k+1)^{n+1}}{(k+1)!}\dfrac{\binom{2n+1}{i}(-1)^{m-k}}{(m-k-i)!(k+1)^i}=\dfrac{1}{2} $$ $$k=0,\ \ i=1:\ \ (k+1)^m\dfrac{(k+1)^{n+1}}{(k+1)!}\dfrac{\binom{2n+1}{i}(-1)^{m-k}}{(m-k-i)!(k+1)^i}=9 $$ $$k=0,\ \ i=2:\ \ (k+1)^m\dfrac{(k+1)^{n+1}}{(k+1)!}\dfrac{\binom{2n+1}{i}(-1)^{m-k}}{(m-k-i)!(k+1)^i}=36 $$ $$k=1,\ \ i=0:\ \ (k+1)^m\dfrac{(k+1)^{n+1}}{(k+1)!}\dfrac{\binom{2n+1}{i}(-1)^{m-k}}{(m-k-i)!(k+1)^i}=-64 $$ $$k=1\ \ i=1:\ \ (k+1)^m\dfrac{(k+1)^{n+1}}{(k+1)!}\dfrac{\binom{2n+1}{i}(-1)^{m-k}}{(m-k-i)!(k+1)^i}=-288 $$ $$k=2\ \ i=0:\ \ (k+1)^m\dfrac{(k+1)^{n+1}}{(k+1)!}\dfrac{\binom{2n+1}{i}(-1)^{m-k}}{(m-k-i)!(k+1)^i}=\dfrac{729}{2} $$ 全部相加，结果为 $58$。 第二组询问范围过大，不进行样例解释。 --- ### 数据范围 **本题采用捆绑测试，不同 Subtask 的题意不同。** | 子任务编号 | $q\leq$ | $n\leq$ | $m\leq$ | 分值 | | :--------: | :------------: | :------------: | :------------: | :--: | | 1 | $5\times 10^5$ | $10^5$ | $\min(10^5,n)$ | 4 | | 2 | $5\times 10^5$ | $2\times 10^5$ | $20$ | 16 | | 3 | $20$ | $998244352$ | $20$ | 16 | | 4(31-40) | $5\times 10^5$ | $2\times 10^5$ | $10$ | 32 | | 4(51-60) | $20$ | $10^{10^5}$ | $10$ | 32 | | 5 | $5\times 10^5$ | $2\times 10^3$ | $2\times 10^3$ | 32 | 所有输入均为正整数。