CF2086D Even String

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 $ .

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} $ .

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

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