F. Копия или префиксная сумма
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив целых чисел $$$b_1, b_2, \ldots, b_n$$$.

Массив $$$a_1, a_2, \ldots, a_n$$$ целых чисел смешанный, если для всех $$$i$$$ ($$$1 \leq i \leq n$$$) хотя бы одно из этих двух условий выполнено:

  • $$$b_i = a_i$$$, или
  • $$$b_i = \sum_{j=1}^{i} a_j$$$.

Найдите количество смешанных массивов $$$a_1, a_2, \ldots, a_n$$$. Поскольку ответ может быть очень большим, найдите его по модулю $$$10^9 + 7$$$.

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

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

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

Во второй строке описания каждого набора входных данных находятся $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$ ($$$-10^9 \le b_i \le 10^9$$$).

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

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

Для каждого набора входных данных выведите единственное целое число: количество смешанных массивов $$$a_1, a_2, \ldots, a_n$$$ по модулю $$$10^9 + 7$$$.

Пример
Входные данные
4
3
1 -1 1
4
1 2 3 4
10
2 -1 1 -2 2 3 -5 0 2 -1
4
0 0 0 1
Выходные данные
3
8
223
1
Примечание

В первом наборе входных данных смешанные массивы — это $$$[1, -2, 1]$$$, $$$[1, -2, 2]$$$, $$$[1, -1, 1]$$$.

Во втором наборе входных данных смешанные массивы — это $$$[1, 1, 1, 1]$$$, $$$[1, 1, 1, 4]$$$, $$$[1, 1, 3, -1]$$$, $$$[1, 1, 3, 4]$$$, $$$[1, 2, 0, 1]$$$, $$$[1, 2, 0, 4]$$$, $$$[1, 2, 3, -2]$$$, $$$[1, 2, 3, 4]$$$.

В четвертом наборе входных данных единственный смешанный массив — это $$$[0, 0, 0, 1]$$$.