该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

余影排列

题目描述

给定两个整数 $n,m$，以及一个长度为 $n-1$ 的整数序列 $d_1,d_2,\dots,d_{n-1}$。

你需要计算有多少个 $1$ 到 $n$ 的排列 $p_1,p_2,\dots,p_n$，满足对于所有 $1 \le i < n$，都有：

这里 $(x\bmod m)$ 表示 $x$ 除以 $m$ 后位于 $0$ 到 $m-1$ 之间的余数。

答案对 $998244353$ 取模。

两个排列不同，当且仅当至少存在一个位置上的数不同。

输入格式

第一行输入一个整数 $T$，表示测试数据组数。

对于每组测试数据：

第一行输入两个整数 $n,m$。

第二行输入 $n-1$ 个整数 $d_1,d_2,\dots,d_{n-1}$。

数据范围

对于所有测试数据，保证：

所有测试数据的 $n+m$ 之和不超过 $2 \times 10^5$。

所有输入数据均为整数。

输出格式

对于每组测试数据，输出一行一个整数，表示满足条件的排列数量。

输入输出样例 #1

输入 #1

5
4 3
1 1 1
5 2
1 1 1 1
5 3
0 0 0 0
6 4
1 2 1 2 1
6 3
1 2 1 2 1

输出 #1

2
12
0
4
0

说明/提示

第一组中，如果 $p_1 \equiv 1 \pmod 3$，那么四个位置需要的余数依次为：

在数字 $1,2,3,4$ 中，余数 $0$ 的数有 $3$，余数 $1$ 的数有 $1,4$，余数 $2$ 的数有 $2$。数量正好匹配。

余数为 $1$ 的两个位置可以放入 $1,4$，顺序任意，所以这一种首项余数贡献 $2$ 个排列。其他首项余数不合法，因此答案为 $2$。

第二组中，数字 $1,2,3,4,5$ 在模 $2$ 意义下，奇数有 $3$ 个，偶数有 $2$ 个。

差分全为 $1$，所以位置余数会交替变化。

如果首项余数为 $0$，位置余数依次为：

这需要偶数 $3$ 个、奇数 $2$ 个，与数字 $1,2,3,4,5$ 的余数分布不匹配。

如果首项余数为 $1$，位置余数依次为：

这正好需要奇数 $3$ 个、偶数 $2$ 个，与数字 $1,2,3,4,5$ 的余数分布匹配。

因此只有一种首项余数合法。奇数桶内部有 $3!$ 种排列，偶数桶内部有 $2!$ 种排列，所以答案为：

第三组中，要求所有位置上的数模 $3$ 后余数相同，但 $1,2,3,4,5$ 不可能全部同余，所以答案为 $0$。