길이가 $N$인 비트 문자열 $s_{1\dots N}$ ($2\le N\le 10^9$)이 주어진다. 한 번의 연산으로 다음 조건이 만족될 때 범위 $s_{l\dots r}$을 뒤집을 수 있다:

1. 범위의 크기가 짝수이다.
2. 범위의 앞 절반은 한 종류의 문자($0$ 또는 $1$)로 구성되어 있고, 뒤 절반은 그와 반대되는 문자로 구성되어 있다.
3. $l = 1$ 이거나 $s_{l-1} \neq s_l$ 이다.
4. $r = N$ 이거나 $s_{r+1} \neq s_r$ 이다.

모든 $1$을 앞쪽으로 옮기기 위한 최소 연산 횟수를 구하고, 불가능한 경우 이를 보고하라. 가능하다면, 최소 연산 횟수를 달성하는 연산 순서의 수를 $10^9+7$로 나눈 나머지도 함께 출력하라.

입력

첫 번째 줄에는 독립적인 테스트 케이스의 수 $T$ ($1 \leq T \leq 2026$)가 주어진다. 각 테스트 케이스는 다음 형식으로 주어진다.

비트 문자열은 압축된 형식으로 주어진다. 첫 번째 줄에는 문자열의 런(run) 개수 $R$ ($2\le R\le 800$)과 문자열의 첫 번째 문자($0$ 또는 $1$)가 주어진다.

다음 줄에는 $s$에서 동일한 문자가 연속되는 최대 블록의 길이인 $R$개의 정수 $l_1, l_2, l_3, \ldots, l_R$ ($0< l_i< 10^9$)이 공백으로 구분되어 주어진다. $N=\sum_{i=1}^Rl_i\le 10^9$임이 보장된다.

또한, 모든 테스트 케이스에 대해 $R^2$의 합이 $1.5\cdot 10^6$을 넘지 않음이 보장된다.

출력

각 테스트 케이스에 대해 모든 $1$을 앞쪽으로 옮기기 위한 최소 연산 횟수를 출력하거나, 불가능한 경우 $-1$을 출력한다. 또한 최소 연산 횟수를 달성하는 연산 순서의 수를 $10^9+7$로 나눈 나머지를 함께 출력한다.

예제

예제 입력 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

다섯 번째 테스트 케이스에 대한 두 번의 연산 과정은 다음과 같다: $010110 \to 100110 \to 111000.$

예제 입력 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

이 모든 테스트 케이스에서 최소 연산 횟수는 $R/2-1$과 같다.

네 번째 테스트 케이스에 대한 세 번의 연산이 가능한 모든 순서는 다음과 같다:

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

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

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

서브태스크

• 입력 3: $N \leq 10$, 모든 테스트 케이스는 서로 다르다.
• 입력 4: $R\le 10$
• 입력 5-8: $R\le 100$, 모든 테스트 케이스에 대해 $R^2$의 합은 $10^5$를 넘지 않으며, 최소 연산 횟수는 $R/2-1$임이 보장된다.
• 입력 9-12: $R\le 100$, 모든 테스트 케이스에 대해 $R^2$의 합은 $10^5$를 넘지 않는다.
• 입력 13-16: 추가 제약 없음.