← 返回题目列表

Codeforces · 1485/F

F. 复制或前缀总和

中文机器翻译题面 查看原题

给定一个整数数组 $$$b_1, b_2, \ldots, b_n$$$。

如果对于每个 $$$i$$$ ($$$1 \leq i \leq n$$$) 至少满足以下条件之一,则整数数组 $$$a_1, a_2, \ldots, a_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$$$ 的数量。

示例

输入 #1

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

输出 #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]$$$。