D. Четная строка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы бы хотели построить строку $$$s$$$, состоящую из строчных латинских букв, для которой выполняется следующее условие:

  • Для каждой пары индексов $$$i$$$ и $$$j$$$, таких что $$$s_{i} = s_{j}$$$, разность этих индексов четная, то есть $$$|i - j| \bmod 2 = 0$$$.

Построить какую-нибудь строку — слишком легкая задача, поэтому вам будет дан массив $$$c$$$ из $$$26$$$ чисел — необходимое количество вхождений каждой отдельной буквы в строку $$$s$$$. То есть для каждого $$$i \in [1, 26]$$$ количество вхождений $$$i$$$-й буквы латинского алфавита в строку должно быть в точности равно $$$c_i$$$.

Ваша задача заключается в том, чтобы посчитать количество различных строк $$$s$$$, удовлетворяющих всем этим условиям. Поскольку ответ может быть огромным, выведите его по модулю $$$998\,244\,353$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^{4}$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Каждый набор данных содержит $$$26$$$ целых чисел $$$c_{i}$$$ ($$$0 \le c_{i} \le 5 \cdot 10^{5}$$$) — элементы массива $$$c$$$.

Дополнительные ограничения на входные данные:

  • сумма $$$c_{i}$$$ для каждого набора входных данных положительна;
  • сумма $$$c_{i}$$$ по всем наборам входных данных не превышает $$$5 \cdot 10^{5}$$$.
Выходные данные

Для каждого набора входных данных выведите одно целое число — количество подходящих строк $$$s$$$, взятое по модулю $$$998\,244\,353$$$.

Пример
Входные данные
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
Выходные данные
4
960
0
1
789493841
Примечание

В первом наборе входных данных существует $$$4$$$ подходящие строки: «abak», «akab», «baka» и «kaba».