题目描述

现有 $n$ 个集合，第 $i$ 个集合有 $a_i$ 个元素，共 $2m$ 个互不相同的元素（ $\sum a_i=2 m$ ），每个元素有一个唯一的所属集合。

对于每轮操作，我们将所有元素随机匹配为 $m$ 对，对于每对匹配，我们随机挑选一个元素，将其从原本所属的集合中取出，放入与其匹配的元素的所属集合中。请问期望操作多少轮，所有元素将属于一个集合。

输出答案在模 $998244353$ 意义下的值。

输入格式

第一行输入一个整数 $T$ ($1 \le T \le 100$) ，表示测试数据的组数。

接下来依次输入每组测试数据，对于每组测试数据：

第 $1$ 行输入两个整数 $n,m$ ($1 \le n \le 2m \le 400$)，表示初始集合的数量以及每轮操作的匹配数。

第 $2$ 行输入 $n$ 个整数 $a_1,a_2, \ldots, a_n$，($1\le a_i\le 2\times m , \sum a_i=2\times m$)，其中 $a_i$ 表示第 $i$ 个集合有 $a_i$ 个元素。

保证所有测试数据 $\sum n\le 800,\sum m\le400$ 。

输出格式

对于每组数据，输出一行一个整数表示答案在模 $998244353$ 意义下的值。

4
2 1
1 1
2 2
2 2
2 2
1 3
3 2
1 1 2

1
3
499122179
499122180

3
6 5
2 1 1 3 1 2
10 100
90 12 18 1 1 24 7 4 37 6
10 200
102 19 25 11 43 97 19 28 11 45

347465837
225202828
437065763

提示

对于样例 $1$：

• 第一组测试数据：我们将初始状态表示为 $[1,1]$ ，只有 $1$ 种可能的匹配方式，并且这 $2$ 个元素无论谁被选中，都有操作一轮后状态为 $[2]$ ，因此期望答案为 $1$ 。
• 第二组测试数据：我们将初始状态表示为 $[2,2]$ ，有 $3$ 种匹配方式，每种匹配方式有 $4$ 种挑选元素的方法，共 $12$ 种不同操作，其中有 $4$ 种操作在操作后状态为 $[4]$ ，其余的 $8$ 种操作在操作后状态为 $[2,2]$ ，即有 $\frac{1}{3}$ 的概率操作后只剩一个集合，其余情况状态不变，因此期望为 $3$ 。
• 第三组测试数据：我们将初始状态表示为 $[1,3]$ ，共有 $12$ 种不同操作，其中有 $6$ 种操作在操作后状态为 $[4]$ ，其余 $6$ 种操作在操作后状态为 $[2,2]$ ，因此期望为 $1+\frac{1}{2}\times 3=\frac{5}{2}$ ，即模 $998244353$ 意义下的 $499122179$ 。
• 第四组测试数据：我们将初始状态表示为 $[1,1,2]$ ，共有 $12$ 种不同操作，其中有 $2$ 种操作在操作后状态为 $[4]$ ，其余 $10$ 种操作在操作后状态为 $[2,2]$ ，因此期望为 $1+\frac{5}{6}\times 3=\frac{7}{2}$ ，即模 $998244353$ 意义下的 $499122180$ 。