P16572 [USACO26Open] Arranging Cows

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

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