题目描述

You are given a length-$N$ bitstring $s_1 \ldots N$ ($2 \leq N \leq 10^9$). In one operation, you can reverse a range $s_l \ldots r$ if the following conditions are true:

1. The size of the range is even.
2. The first half of the range consists of one character (either $0$ or $1$), and the second half contains the opposite character
3. Either $l = 1$ or $s_{l-1} \neq s_l$
4. Either $r = N$ or $s_{r+1} \neq s_r$

Find the minimum number of operations to move all of the $1$s to the front, or report that it is impossible. If it is possible to do so, also output the number of sequences of operations achieving this minimum, modulo $10^9 + 7$.

输入格式

The first line contains $T$ ($1 \leq T \leq 2026$), the number of independent tests. Each test is specified in the following format:

The bitstring is given in a compressed format. The first line contains $R$, the number of runs in the string ($2 \leq R \leq 800$), and the first character of the string (either $0$ or $1$).

The next line contains $R$ space-separated integers $l_1, l_2, l_3, \ldots l_R$ ($0 < l_i < 10^9$), the lengths of maximal consecutive blocks of equal characters in $s$. It’s guaranteed that $N = \sum_{i=1}^{R} l_i \leq 10^9$.

Additionally, it is guaranteed that the sum of $R^2$ over all tests does not exceed $1.5 \cdot 10^6$.

输出格式

For each test case, print the minimum number of operations to move all of the $1$s to the front or $-1$ if it is impossible, as well as the number of sequences of operations achieving this minimum modulo $10^9 + 7$.

9
2 0
1 1
2 1
1 1
2 1
2 1
2 0
1 2
5 0
1 1 1 2 1
3 0
1 2 1
8 0
1 1 2 1 1 2 1 1
6 0
3 3 1 2 2 1
7 0
5 1 1 3 2 1 1

1 1
0 1
0 1
-1 0
2 1
-1 0
4 7
3 1
4 1

5
2 1
1 1
4 1
1 1 1 1
6 1
1 1 1 1 1 1
8 1
1 1 1 1 1 1 1 1
10 1
1 1 1 1 1 1 1 1 1 1

0 1
1 1
2 1
3 3
4 9

提示

Sample 1

Here is the sequence of two operations for the fifth testcase: $010110 \to 100110 \to 111000$.

Sample 2

In all of these test cases, the minimum number of operations equals $R/2-1$.

Here are all three possible sequences of three operations for the fourth test case:

(1)
   10101010
-> 11001010
-> 11001100
-> 11110000

(2)
   10101010
-> 10110010
-> 10001110
-> 11110000

(3)
   10101010
-> 10101100
-> 11001100
-> 11110000

SCORING

• Input $3$: $N \le 10$, all tests are distinct
• Input $4$: $R \le 10$
• Inputs $5$-$8$: $R \le 100$, the sum of $R^2$ over all tests does not exceed $10^5$, the minimum number of operations is guaranteed to equal $R/2 - 1$.
• Inputs $9$-$12$: $R \le 100$, the sum of $R^2$ over all tests does not exceed $10^5$.
• Inputs $13$-$16$: No additional constraints.