Problem Description

There are $n$ sets. The $i$-th set has $a_i$ elements. There are $2m$ pairwise distinct elements in total ($\sum a_i = 2m$). Each element belongs to exactly one set.

In each round of operation, we randomly match all elements into $m$ pairs. For each pair, we randomly choose one element, remove it from its original set, and move it into the set that the matched element belongs to. Ask for the expected number of rounds of operations until all elements belong to one set.

Output the answer modulo $998244353$.

Input Format

The first line contains an integer $T$ ($1 \le T \le 100$), the number of testcases.

Then for each testcase:

Line $1$ contains two integers $n, m$ ($1 \le n \le 2m \le 400$), representing the initial number of sets and the number of pairs matched in each round.

Line $2$ contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 2 \times m$, $\sum a_i = 2 \times m$), where $a_i$ denotes the number of elements in the $i$-th set.

It is guaranteed that over all testdata, $\sum n \le 800$ and $\sum m \le 400$.

Output Format

For each testcase, output one integer per line representing the answer modulo $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

Hint

For Sample $1$:

• Testcase 1: We represent the initial state as $[1,1]$. There is only $1$ possible matching, and no matter which of the $2$ elements is chosen, after one round the state becomes $[2]$. Therefore the expected answer is $1$.
• Testcase 2: We represent the initial state as $[2,2]$. There are $3$ possible matchings. For each matching, there are $4$ ways to choose elements, so there are $12$ different operations in total. Among them, $4$ operations lead to state $[4]$, and the other $8$ operations lead to state $[2,2]$. That is, with probability $\frac{1}{3}$, after the operation only one set remains; otherwise the state does not change. Therefore the expectation is $3$.
• Testcase 3: We represent the initial state as $[1,3]$. There are $12$ different operations in total. Among them, $6$ operations lead to state $[4]$, and the other $6$ operations lead to state $[2,2]$. Therefore the expectation is $1+\frac{1}{2}\times 3=\frac{5}{2}$, which is $499122179$ modulo $998244353$.
• Testcase 4: We represent the initial state as $[1,1,2]$. There are $12$ different operations in total. Among them, $2$ operations lead to state $[4]$, and the other $10$ operations lead to state $[2,2]$. Therefore the expectation is $1+\frac{5}{6}\times 3=\frac{7}{2}$, which is $499122180$ modulo $998244353$.

Translated by ChatGPT 5