You are given a length-N bitstring s1…N(2≤N≤109). In one operation, you can reverse a range sl…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 00 or 11), and the second half contains the opposite character
3.Either l=1 or sl−1≠sl
4.Either r=N or sr+1≠sr
Find the minimum number of operations to move all of the 11s 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 109+7.
INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains T (1≤T≤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≤R≤800), and the first character of the string (either 0 or 1).
The next line contains R space-separated integers l1,l2,l3,…lR (0<li<109), the lengths of maximal consecutive blocks of equal characters in s. It's guaranteed that N=
Additionally, it is guaranteed that the sum of R2 over all tests does not exceed 1.5⋅106.
OUTPUT FORMAT (print output to the terminal / stdout):
For each test case, print the minimum number of operations to move all of the 11s to the front or −1−1 if it is impossible, as well as the number of sequences of operations achieving this minimum modulo 109+7.
SAMPLE INPUT:
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
SAMPLE OUTPUT:
1 1
0 1
0 1
-1 0
2 1
-1 0
4 7
3 1
4 1
Here is the sequence of two operations for the fifth testcase: 010110→100110→111000.010110→100110→111000.
SAMPLE INPUT:
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
SAMPLE OUTPUT:
0 1
1 1
2 1
3 3
4 9
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≤10, all tests are distinct
Input 4: R≤10
Inputs 5-8: R≤100, the sum of R2 over all tests does not exceed 105, the minimum number of operations is guaranteed to equal R/2−1.
Inputs 9-12: R≤100, the sum of R2 over all tests does not exceed 105.
Inputs 13-16: No additional constraints.
Problem credits: Sujay Konda
