【题目描述】

定义一个大小为$n \times n$的矩阵A是“好”的矩阵，当且仅当其满足如下条件：

1. 矩阵中每个数均是整数

2. $\forall j, \prod_{i=1}^n i=1 A_{i,j} = x$

3. $\forall j, \prod_{i=1}^n i=1 A_{j,i} = x$

现在有T组询问，每组询问的形式是：有多少个大小为$n \times n$的“好”的矩阵，

满足条件。这个答案可能很大，请你求出对998244353取模的结果。

【输入数据】

第一行一个整数x和一个非负整数T表示询问组数。 接下来T行，每行一个正整数n表示询问。

【输出数据】

输出T行，每一行输出询问对应的答案对998244353取模的结果。

【数据范围】

数据标号	T ≤	x =	max{n} ≤
1		12	5
2		30	5
3		1
4		1
5		1
6		147203573614806055
7		371216956151518818
8		834586893457709917
9	10	1147387575560213988	2000
10		608358758975305374	2000
11		710701671428663075	2000
12		714115052266263644	2000
13	10	979573735390975739	300000
14		640807389338647549	300000
15		598480316906172486	300000
16		203522456999371050	300000
17		421206431991626060
18		595630806517176908
19		573010858348910652
20		812626144076193076

对于全部数据，有

$0 \le T \le 200000$

$1\le n \le 5000000$