题目背景

小 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$）：

你需要回答出 $f_n$ 的值。

Subtask 2,3（16,16 pts）：

这两个子任务给定的序列 $g,h$ 形式相同，但数据范围不同，请仔细阅读数据范围。

你需要回答 $q$ 组询问，每组询问给定两个整数 $n,m$。

每组询问的 $g$ 和 $h$ 如下所示（$0\leq k\leq n$）：

你需要回答出 $f_n$ 的值。

Subtask 4（32 pts）：

你需要回答 $q$ 组询问，每组询问给定两个整数 $n,m$。

每组询问的 $g$ 和 $h$ 如下所示（$0\leq k\leq n$）：

你需要回答出 $f_n$ 的值。

Subtask 5（32 pts）：

你需要回答 $q$ 组询问，每组询问给定两个整数 $n,m$。

注意下面 $n,m$ 的含义，不要看反。

你需要回答出上面这个式子的值。

与前四个 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$ 的加数项）：

第二组询问中，$m=3$，则：

样例解释 2

在这组样例中，需要解决第二个子任务，$q=2$。

第一组询问中，$n=4,\ \ m=2$，则：

$f_5=\dfrac{11}{120}$ 对 $998244353$ 取模后等于 $440891256$。

第二组询问范围过大，不进行样例解释。

样例解释 3

在这组样例中，需要解决第四个子任务，$q=2$。

第一组询问中，$n=4,\ \ m=2$，则：

第二组询问范围过大，不进行样例解释。

样例解释 4

在这组样例中，需要解决第五个子任务，$q=2$。

第一组询问中，$n=4,\ \ m=2$，则枚举 $k,i$：

全部相加，结果为 $58$。

第二组询问范围过大，不进行样例解释。

数据范围

本题采用捆绑测试，不同 Subtask 的题意不同。

所有输入均为正整数。