CF2246C.0mar and Alternating Sums

Define the alternating sum of an array $b$ of length $k$ to be $\sum_{i = 1}^{k}(-1)^{i+1}b_i$.

You are given a non-decreasing$^{\text{∗}}$ array $a$ of length $n$ such that for all $1 \le i \le n,$ either $a_i = -1$ or $a_i$ is a positive integer. Find the number of sequences $1 \le i_1 \lt i_2 \lt \ldots \lt i_k \le n$ such that the alternating sum of the sequence $a_{i_1}, a_{i_2}, \ldots, a_{i_k}$ is $0.$ Since this number may be large, output it modulo $10^9+7$.

Two sets $i_1, \ldots, i_{k_1}$ and $i'_1, \ldots, i'_{k_2}$ of indices are considered different if $k_1 \neq k_2$ or there exists a $j$ such that $i_j \neq i'_j.$

$^{\text{∗}}$A sequence $a_1, \ldots, a_n$ is non-decreasing if $a_1 \le a_2 \le \ldots \le a_n$.

定义数组 $b$（长度为 $k$）的交错和为 $\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$ 取模的结果。

若两个下标集合 $i_1, \ldots, i_{k_1}$ 与 $i'_1, \ldots, i'_{k_2}$ 满足 $k_1 \neq k_2$，或存在某个 $j$ 使得 $i_j \neq i'_j$，则认为它们是不同的。

$^{\text{∗}}$ 序列 $a_1, \ldots, a_n$ 称为非递减，当且仅当 $a_1 \le a_2 \le \ldots \le a_n$。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n \, (1 \le n \le 2 \cdot 10^5)$ — the length of the array.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ — the elements of the array where $\mathbf{a_i = -1}$ or $\mathbf{1 \leq a_i \leq 10^9}$. It is guaranteed that the array is non-decreasing.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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}$ 或 $\mathbf{1 \leq a_i \leq 10^9}$。保证该数组是非递减的。

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

For each testcase, output a single integer — the number of subsequences that have an alternating sum of zero modulo $10^9 +7$. A subsequence of length $0$ is considered to have an alternating sum of zero.

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

In the first example, the following subsequences have an alternating sum of zero:

$\bullet$

$[],$

$\bullet$

$[a_2,a_3] = [1,1]$,

$\bullet$

$[a_1, a_2, a_4] = [-1,1,2]$,

$\bullet$

$[a_1, a_3, a_4] = [-1,1,2]$,

$\bullet$

$[a_1, a_4, a_5] = [-1,2,3]$,

$\bullet$

$[a_1,a_2,a_3,a_4,a_5] = [-1,1,1,2,3].$

In the second example, only the empty subsequence $[]$ has an alternating sum of zero.

在第一个例子中，以下子序列的交替和为零：

$\bullet$

$[],$

$\bullet$

$[a_2,a_3] = [1,1]$,

$\bullet$

$[a_1, a_2, a_4] = [-1,1,2]$,

$\bullet$

$[a_1, a_3, a_4] = [-1,1,2]$,

$\bullet$

$[a_1, a_4, a_5] = [-1,2,3]$,

$\bullet$

$[a_1,a_2,a_3,a_4,a_5] = [-1,1,1,2,3].$

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