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

Назовем последовательность целых чисел самопродуцируемой, если для каждого $$$i$$$ ($$$1 \le i \le n$$$) выполняется хотя бы одно из следующих условий:

  • $$$a_i$$$ равно сумме элементов слева (т. е. $$$a_i = \displaystyle\sum\limits_{j = 1}^{i - 1} a_j$$$);
  • $$$a_i$$$ равно сумме элементов справа (т. е. $$$a_i = \displaystyle\sum\limits_{j = i + 1}^{n} a_j$$$).

Обратите внимание, что $$$0$$$ в начале/конце последовательности также считается допустимым.

Вам дан массив целых чисел $$$a$$$ размером $$$n$$$. Ваша задача — посчитать количество самопродуцируемых подпоследовательностей массива $$$a$$$. Поскольку ответ может быть большим, выведите его по модулю $$$998244353$$$. Две подпоследовательности различны, если индексы выбранных элементов различны.

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

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^9$$$).

Дополнительное ограничение на входные данные: сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

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

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

Пример
Входные данные
5
3
1 1 2
2
0 0
5
0 1 0 1 0
6
1 0 2 2 1 1
11
2 0 3 1 0 0 2 3 0 3 2
Выходные данные
2
4
12
8
41