题目背景

小 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		$2\times 10^5$	$20$	16
3	$20$	$998244352$
4(31-40)	$5\times 10^5$	$2\times 10^5$	$10$	32
4(51-60)	$20$	$10^{10^5}$
5	$5\times 10^5$	$2\times 10^3$

所有输入均为正整数。