У вас есть одномерный пазл, все элементы которого нужно сложить в один ряд, соединяя друг с другом. Все элементы пазла полностью белые и отличимы друг от друга, только если имеют разную форму.
Каждый элемент имеет прямые границы сверху и снизу, а слева и справа имеет соединения, каждое из которых может быть выступом или углублением. Вращать элементы нельзя.
Можно заметить, что существует ровно \(4\) типа элементов. Два элемента можно соединить, если правое соединение левого элемента противоположно левому соединению правого элемента.
Все возможные типы элементов. Пазл содержит \(c_1, c_2, c_3, c_4\) элементов каждого типа. Пазл считается собранным, если вам удалось объединить все элементы в одну длинную цепочку. Вы хотите узнать, сколькими способами это можно сделать.
Выходные данные
Для каждого набора входных данных выведите одно целое число — количество возможных способов собрать пазл.
Два способа считаются различными, если существует \(i\), такое, что типы элементов на \(i\)-й позиции в этих способах различаются.
Так как ответ может быть очень большим, выведите его по модулю \(998244353\).
Если пазл собрать невозможно, выведите \(0\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|