E. Упоротый баланс
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана последовательность $$$a_1, a_2, \dots, a_n$$$ длины $$$n$$$, ваша задача посчитать число, по модулю $$$998244353$$$, способов разбить ее на несколько не пустых непрерывных подпоследовательностей так, что сумма элементов в подпоследовательностях является сбалансированной последовательностью.

Последовательность $$$s_1, s_2, \dots, s_k$$$ длины $$$k$$$ является сбалансированной, если $$$s_{i} = s_{k-i+1}$$$ для всех $$$1 \leq i \leq k$$$. Например, $$$[1, 2, 3, 2, 1]$$$ и $$$[1,3,3,1]$$$ сбалансированный, а $$$[1,5,15]$$$ нет.

Формально, каждое разбиение может быть описано последовательностью индексов $$$i_1, i_2, \dots, i_k$$$ длины $$$k$$$ и $$$1 = i_1 < i_2 < \dots < i_k \leq n$$$ такое, что

  1. $$$k$$$ является числом непустых непрерывных подпоследовательностей в разделении;
  2. Для каждого $$$1 \leq j \leq k$$$, $$$j$$$-я непрерывная подпоследовательность начинается в $$$a_{i_j}$$$, и заканчивается перед $$$a_{i_{j+1}}$$$, где $$$i_{k+1} = n + 1$$$. Значит, что $$$j$$$-я подпоследовательность это $$$a_{i_j}, a_{i_j+1}, \dots, a_{i_{j+1}-1}$$$.
Всего $$$2^{n-1}$$$ различных разбиений.

Пусть $$$s_1, s_2, \dots, s_k$$$ означает суммы элементов в подпоследовательностях относительно разбиения $$$i_1, i_2, \dots, i_k$$$. Формально, для каждого $$$1 \leq j \leq k$$$, $$$$$$ s_j = \sum_{i=i_{j}}^{i_{j+1}-1} a_i = a_{i_j} + a_{i_j+1} + \dots + a_{i_{j+1}-1}. $$$$$$ Например, разбиение $$$[1\,|\,2,3\,|\,4,5,6]$$$ последовательности $$$[1,2,3,4,5,6]$$$ задается последовательностью индексов $$$[1,2,4]$$$, и суммы элементов разбиения будут равны $$$[1,5,15]$$$.

Два разбиения $$$i_1, i_2, \dots, i_k$$$ и $$$i'_1, i'_2, \dots, i'_{k'}$$$ (описанные последовательностью индексов) являются разными, если выполнено хотя бы одно из следующих условий.

  • $$$k \neq k'$$$,
  • $$$i_j \neq i'_j$$$ для некоторого $$$1 \leq j \leq \min\left\{ k, k' \right\}$$$.
Входные данные

В первой строке задано одно целое число $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — количество наборов входных данных. Затем следуют описания наборов входных данных.

Первая строка набора входных данных содержит целое число $$$n$$$ ($$$1 \leq n \leq 10^5$$$), означающее длину последовательности $$$a$$$.

Вторая строка набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$0 \leq a_i \leq 10^9$$$), означающие элементы последовательности $$$a$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

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

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

Пример
Входные данные
6
1
1000000000
2
1 1
4
0 0 1 0
5
1 2 3 2 1
5
1 3 5 7 9
32
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Выходные данные
1
2
3
4
2
150994942
Примечание

В первом примере существует только один способ разделить последовательность длины $$$1$$$, который, разумеется, сбалансированный.

Для второго теста существует $$$2$$$ способа разделить последовательность:

  • Сама последовательность $$$[1, 1]$$$ тогда $$$s = [2]$$$ сбалансирована;
  • Разделить на две последовательности $$$[1\,|\,1]$$$, тогда $$$s = [1, 1]$$$ сбалансирована.

В третьем тесте существует $$$3$$$ способа разделить последовательность:

  • Сама последовательность $$$[0, 0, 1, 0]$$$, тогда $$$s = [1]$$$ сбалансирована;
  • $$$[0 \,|\, 0, 1 \,|\, 0]$$$, тогда $$$s = [0, 1, 0]$$$ сбалансирована;
  • $$$[0, 0 \,|\, 1 \,|\, 0]$$$, тогда $$$s = [0, 1, 0]$$$ сбалансирована.

В четвертом примере существует $$$4$$$ способа разделить последовательность:

  • Сама последовательность $$$[1, 2, 3, 2, 1]$$$, тогда $$$s = [9]$$$ сбалансирована;
  • $$$[1, 2 \,|\, 3 \,|\, 2, 1]$$$, тогда $$$s = [3, 3, 3]$$$ сбалансирована;
  • $$$[1 \,|\, 2, 3, 2 \,|\, 1]$$$, тогда $$$s = [1, 7, 1]$$$ сбалансирована;
  • $$$[1 \,|\, 2 \,|\, 3 \,|\, 2 \,|\, 1]$$$, тогда $$$s = [1, 2, 3, 2, 1]$$$ сбалансирована.

В пятом примере существует $$$2$$$ способа разделить последовательность:

  • Сама последовательность $$$[1, 3, 5, 7, 9]$$$, тогда $$$s = [25]$$$ сбалансирована;
  • $$$[1, 3, 5 \,|\, 7 \,|\, 9]$$$, тогда $$$s = [9, 7, 9]$$$ сбалансирована.

Для шестого примера любое разбиение подходит. Значит, ответ равен $$$2^{32-1} \equiv 150994942 \pmod {998244353}$$$.