Есть неизвестный массив \(a\) длины \(n\), состоящий только из \(1\) и \(-1\). Пусть \(p\) — массив префиксных сумм массива \(a\). Более формально, \(p\) — это массив длины \(n\), в котором \(p_i = a_1 + a_2 + \ldots + a_i\). После этого массив \(p\) сортируется в неубывающем порядке. Например, если \(a = [1, -1, -1, 1, 1]\), то \(p = [1, 0, -1, 0, 1]\) до сортировки и \(p = [-1, 0, 0, 1, 1]\) после сортировки.
Вам дан массив префиксных сумм \(p\) после сортировки, но вы не знаете, чему был равен массив \(a\). Ваша задача — посчитать количество исходных массивов \(a\), для которых в результате сортировки массива префиксных сумм получается заданный массив \(p\). Поскольку это число может быть большим, от вас требуется только найти его по модулю \(998\,244\,353\).
Выходные данные
Для каждого набора входных данных выведите ответ по модулю \(998\,244\,353\).
Примечание
В первых двух наборах входных данных единственными возможными массивами \(a\) для \(n = 1\) являются \(a = [1]\) и \(a = [-1]\). Соответствующие им отсортированные массивы префиксных сумм \(p\) — \(p = [1]\) и \(p = [-1]\). Следовательно, не существует массива \(a\), который может привести к отсортированному массиву префиксных сумм \(p = [0]\). Но существует ровно \(1\) массив \(a\), который может привести к отсортированному массиву префиксных сумм \(p = [1]\).
В третьем наборе входных данных можно доказать, что не существует массива \(a\), который мог бы привести к отсортированному массиву префиксных сумм \(p = [-1, 1, 2]\).
В четвертом наборе входных данных существует \(3\) возможных массива \(a\), которые могут привести к отсортированному массиву префиксных сумм \(p = [-1, 0, 0, 1, 1]\).
- \(a = [1, -1, 1, -1, -1]\). Массив префиксных сумм до сортировки равен \(p = [1, 0, 1, 0, -1]\), а после сортировки \(p = [-1, 0, 0, 1, 1]\).
- \(a = [1, -1, -1, 1, 1]\). Массив префиксных сумм до сортировки равен \(p = [1, 0, -1, 0, 1]\), а после сортировки \(p = [-1, 0, 0, 1, 1]\).
- \(a = [-1, 1, 1, -1, 1]\). Массив префиксных сумм до сортировки равен \(p = [-1, 0, 1, 0, 1]\), а после сортировки \(p = [-1, 0, 0, 1, 1]\).
Для пятого набора входных данных единственным возможным массивом \(a\), который может привести к отсортированному массиву префиксных сумм \(p = [-4, -3, -3, -2, -1]\), является \(a = [-1, -1, -1, -1, 1]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1
0
1
1
3
-1 1 2
5
-1 0 0 1 1
5
-4 -3 -3 -2 -1
|
0
1
0
3
1
|