Две версии этой задачи отличаются друг от друга. Возможно, вы захотите прочитать обе версии. Вы сможете делать взломы, только если обе версии решены.
Вам дан массив \(a\) длины \(n\). Изначально \(c = 0\). Для каждого \(i\) от \(1\) до \(n\) (в порядке возрастания) выполните ровно одно из следующих действий:
- Вариант \(1\): сделать \(c\) равным \(c + a_i\).
- Вариант \(2\): сделать \(c\) равным \(|c + a_i|\), где \(|x|\) — абсолютное значение \(x\).
Пусть максимальное возможное конечное значение \(c\) после описанной выше процедуры равно \(k\). Найдите количество уникальных процедур, в результате которых получается \(c = k\). Две процедуры различны, если при каком-либо индексе \(i\) одна процедура выбрала вариант \(1\), а другая — вариант \(2\), даже если после этого хода значение \(c\) для обеих процедур одинаково.
Поскольку ответ может быть большим, выведите его по модулю \(998\,244\,353\).
Выходные данные
Для каждого набора входных данных выведите одно целое число — количество уникальных процедур, в результате которых получается \(c = k\), по модулю \(998\,244\,353\).
Примечание
В первом наборе входных данных можно показать, что максимальное конечное значение \(c\) равно \(3\). Существует \(12\) способов достичь этого, потому что для получения \(3\) мы должны взять абсолютное значение при индексах \(2\) или \(4\), или при обоих, что дает \(3\) способа. Для двух других индексов значение не меняется от того, берем мы абсолютное значение или нет, поэтому для них у нас есть \(2 \cdot 2 = 4\) способа. Итого, у нас есть \(3 \cdot 4 = 12\) способов.
Во втором наборе входных данных взятие абсолютного значения ничего не изменит, поэтому мы можем либо брать абсолютное значение, либо нет, для каждого индекса. Это дает нам \(2^8 = 256\) возможных способов.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
4
2 -5 3 -3
8
1 4 3 4 1 4 3 4
3
-1 -2 -3
4
-1000000000 1000000000 1000000000 1000000000
4
1 9 8 4
|
12
256
1
8
16
|