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 $ .

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 $ .

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.

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.