У вас есть одномерный пазл, все элементы которого нужно сложить в один ряд, соединяя друг с другом. Все элементы пазла полностью белые и отличимы друг от друга, только если имеют разную форму.
Каждый элемент имеет прямые границы сверху и снизу, а слева и справа имеет соединения, каждое из которых может быть выступом или углублением. Вращать элементы нельзя.
Можно заметить, что существует ровно $$$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$$$.
111 1 1 11 2 5 104 6 100 200900000 900000 900000 9000000 0 0 00 0 566 2391 0 0 0100 0 100 00 0 0 45 5 0 25 4 0 5
4 66 0 794100779 1 0 1 0 1 36 126
| Codeforces Round 925 (Div. 3) |
|---|
| Закончено |
