← 返回题目列表

Codeforces · 2246/C

C. 0mar 和交替求和

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

将长度为 $$$k$$$ 的数组 $$$b$$$ 的交替和定义为 $$$\sum_{i = 1}^{k}(-1)^{i+1}b_i$$$。

给你一个非递减的$$$^{\text{*}}$$$数组$$$a$$$,长度为$$$n$$$,这样对于所有$$$1 \le i \le n,$$$要么$$$a_i = -1$$$要么$$$a_i$$$是正整数。求序列 $$$1 \le i_1 \lt i_2 \lt \ldots \lt i_k \le n$$$ 的数量,使得序列 $$$a_{i_1}, a_{i_2}, \ldots, a_{i_k}$$$ 的交替和为 $$$0。$$$ 因为这个数字可能很大,所以输出它对 $$$10^9+7$$$ 取模。

如果 $$$k_1 \neq k_2$$$ 或存在 $$$j$$$ 使得 $$$i_j \neq i'_j.$$$ ,则两组索引 $$$i_1, \ldots, i_{k_1}$$$ 和 $$$i'_1, \ldots, i'_{k_2}$$$ 被视为不同

$$$^{\text{*}}$$$如果 $$$a_1 \le a_2 \le \ldots \le a_n$$$ 则 $$$a_1, \ldots, a_n$$$ 是非递减的。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n \, (1 \le n \le 2 \cdot 10^5)$$$ — 数组的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ — 数组的元素,其中 $$$\mathbf{a_i = -1}$$$ or $$$\mathbf{1 \leq a_i \leq 10^9}$$$。保证数组是非递减的。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数 - 具有零模 $$$10^9 +7$$$ 交替和的子序列的数量。长度为 $$$0$$$ 的子序列被认为具有零的交替和。

示例

输入
复制

4
5
-1 1 1 2 3
3
1 2 3
4
1 3 5 7
14
-1 -1 -1 1 2 2 3 3 3 5 5 5 5 5

输出
复制

6
1
1
1536

注意

在第一个示例中,以下子序列的交替和为零:

$$$\项目符号$$$$$$[],$$$
$$$\项目符号$$$$$$[a_2,a_3] = [1,1]$$$,
$$$\项目符号$$$$$$[a_1, a_2, a_4] = [-1,1,2]$$$,
$$$\项目符号$$$$$$[a_1, a_3, a_4] = [-1,1,2]$$$,
$$$\项目符号$$$$$$[a_1, a_4, a_5] = [-1,2,3]$$$,
$$$\项目符号$$$$$$[a_1,a_2,a_3,a_4,a_5] = [-1,1,1,2,3].$$$

在第二个示例中,只有空子序列 $$$[]$$$ 的交替和为零。