There are $n$ sets, where the $i$-th set contains $a_i$ elements. In total, there are $2m$ distinct elements across all sets ($\sum a_i = 2m$), and each element belongs to exactly one set.

In each round of operations, we randomly partition all elements into $m$ pairs. For each pair, we randomly select one element and move it from its original set to the set of the other element in the pair. What is the expected number of rounds until all elements belong to a single set?

Input

There are multiple test cases. The first line contains an integer $T$ ($1 \le T \le 100$), representing the number of test cases. For each test case:

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

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 2m$, $\sum a_i = 2m$), where $a_i$ is the number of elements in the $i$-th set.

It is guaranteed that the sum of $n$ over all test cases does not exceed 800, and the sum of $m$ does not exceed 400.

Output

For each test case, output a single integer representing the answer modulo 998244353.

It can be proven that the answer is a rational number $\frac{P}{Q}$. You need to output the value of $PQ^{-1} \pmod{998244353}$, where $Q^{-1}$ is the integer satisfying $QQ^{-1} \equiv 1 \pmod{998244353}$.

Examples

Input 1

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

Output 1

1
3
499122179
499122180

Input 2

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

Output 2

347465837
225202828
437065763

Note

For Example 1:

• First test case: We represent the initial state as $[1, 1]$. There is only 1 possible matching, and regardless of which of the 2 elements is chosen, the state becomes $[2]$ after one round. Thus, the expected value is 1.
• Second test case: We represent the initial state as $[2, 2]$. There are 3 possible matchings, and each matching has 4 ways to select elements, resulting in 12 different operations. Among these, 4 operations result in the state $[4]$, and the remaining 8 operations result in the state $[2, 2]$. This means there is a $\frac{1}{3}$ probability of having only one set remaining after the operation, otherwise the state remains unchanged. Thus, the expected value is 3.
• Third test case: We represent the initial state as $[1, 3]$. There are 12 different operations, among which 6 result in the state $[4]$, and the remaining 6 result in the state $[2, 2]$. Thus, the expected value is $1 + \frac{1}{2} \times 3 = \frac{5}{2}$, which is $499122179$ modulo 998244353.
• Fourth test case: We represent the initial state as $[1, 1, 2]$. There are 12 different operations, among which 2 result in the state $[4]$, and the remaining 10 result in the state $[2, 2]$. Thus, the expected value is $1 + \frac{5}{6} \times 3 = \frac{7}{2}$, which is $499122180$ modulo 998244353.