D. Even String
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You would like to construct a string $$$s$$$, consisting of lowercase Latin letters, such that the following condition holds:

  • For every pair of indices $$$i$$$ and $$$j$$$ such that $$$s_{i} = s_{j}$$$, the difference of these indices is even, that is, $$$|i - j| \bmod 2 = 0$$$.

Constructing any string is too easy, so you will be given an array $$$c$$$ of $$$26$$$ numbers — the required number of occurrences of each individual letter in the string $$$s$$$. So, for every $$$i \in [1, 26]$$$, the $$$i$$$-th letter of the Latin alphabet should occur exactly $$$c_i$$$ times.

Your task is to count the number of distinct strings $$$s$$$ that satisfy all these conditions. Since the answer can be huge, output it modulo $$$998\,244\,353$$$.

Input

Each test consists of several test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^{4}$$$)— the number of test cases. The description of test cases follows.

Each test case contains $$$26$$$ integers $$$c_{i}$$$ ($$$0 \le c_{i} \le 5 \cdot 10^{5}$$$)— the elements of the array $$$c$$$.

Additional constraints on the input data:

  • The sum of $$$c_{i}$$$ for every test case is positive;
  • The sum of $$$c_{i}$$$ over all test cases does not exceed $$$5 \cdot 10^{5}$$$.
Output

For each test case, print one integer — the number of suitable strings $$$s$$$, taken modulo $$$998\,244\,353$$$.

Example
Input
5
2 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0 1 0 3 0 0 0 0 0 0 0 0 0 0 0
1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 233527 233827
Output
4
960
0
1
789493841
Note

In the first test case, there are $$$4$$$ suitable strings: "abak", "akab", "baka" and "kaba".