给定一个整数数组 $$$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]$$$。