#216606. [USACO26OPEN] Arranging Cows

You are given a length- bitstring (). In one operation, you can reverse a range 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 or ), and the second half contains the opposite character
3. Either or
4. Either or

Find the minimum number of operations to move all of the 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 .

The first line contains (), 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 , the number of runs in the string (), and the first character of the string (either or ).

The next line contains space-separated integers (), the lengths of maximal consecutive blocks of equal characters in . It’s guaranteed that .

Additionally, it is guaranteed that the sum of over all tests does not exceed .

For each test case, print the minimum number of operations to move all of the s to the front or if it is impossible, as well as the number of sequences of operations achieving this minimum modulo .

样例输入 1

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 1
0 1
0 1
-1 0
2 1
-1 0
4 7
3 1
4 1

样例输入 2

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

样例输出 2

0 1
1 1
2 1
3 3
4 9

Sample 1

Here is the sequence of two operations for the fifth testcase: .

Sample 2

In all of these test cases, the minimum number of operations equals .

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 : , all tests are distinct
• Input :
• Inputs -: , the sum of over all tests does not exceed , the minimum number of operations is guaranteed to equal .
• Inputs -: , the sum of over all tests does not exceed .
• Inputs -: No additional constraints.