G. Одномерный пазл
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть одномерный пазл, все элементы которого нужно сложить в один ряд, соединяя друг с другом. Все элементы пазла полностью белые и отличимы друг от друга, только если имеют разную форму.

Каждый элемент имеет прямые границы сверху и снизу, а слева и справа имеет соединения, каждое из которых может быть выступом или углублением. Вращать элементы нельзя.

Можно заметить, что существует ровно $$$4$$$ типа элементов. Два элемента можно соединить, если правое соединение левого элемента противоположно левому соединению правого элемента.

Все возможные типы элементов.

Пазл содержит $$$c_1, c_2, c_3, c_4$$$ элементов каждого типа. Пазл считается собранным, если вам удалось объединить все элементы в одну длинную цепочку. Вы хотите узнать, сколькими способами это можно сделать.

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

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 2 \cdot 10^5$$$) — количество наборов входных данных. Далее следуют описания наборов входных данных.

Описание каждого набора входных данных содержит $$$4$$$ целых числа $$$c_i$$$ ($$$0 \le c_i \le 10^6$$$) — количества элементов каждого типа соответственно.

Гарантируется, что сумма $$$c_i$$$ по всем наборам входных данных не превосходит $$$4 \cdot 10^6$$$.

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

Для каждого набора входных данных выведите одно целое число — количество возможных способов собрать пазл.

Два способа считаются различными, если существует $$$i$$$, такое, что типы элементов на $$$i$$$-й позиции в этих способах различаются.

Так как ответ может быть очень большим, выведите его по модулю $$$998244353$$$.

Если пазл собрать невозможно, выведите $$$0$$$.

Пример
Входные данные
11
1 1 1 1
1 2 5 10
4 6 100 200
900000 900000 900000 900000
0 0 0 0
0 0 566 239
1 0 0 0
100 0 100 0
0 0 0 4
5 5 0 2
5 4 0 5
Выходные данные
4
66
0
794100779
1
0
1
0
1
36
126