Se le proporciona una cadena de bits de longitud ~N~, ~s_{1...N}~. En una sola operación, puede invertir un rango ~s_{l...r}~ si se cumplen las siguientes condiciones:

1. El tamaño del rango es par.
2. La primera mitad del rango consta de un carácter ~(0~ ó ~1)~, y la segunda mitad contiene el carácter opuesto.
3. ~l=1~ o ~s_{l-1} \neq s_l~.
4. ~r=N~ o ~s_{r+1} \neq s_r~.

Encuentre el número mínimo de operaciones para mover todos los ~1~ al principio, o indique que es imposible. Si es posible, muestre también el número de secuencias de operaciones que alcanzan este mínimo, módulo ~10^9+7~.

Entrada

La primera línea contiene ~T~, el número de pruebas independientes. Cada prueba se especifica en el siguiente formato:

• La cadena de bits se proporciona en formato comprimido. La primera línea contiene ~R~, el número de secuencias en la cadena, y el primer carácter de la cadena ~(0~ ó ~1)~.
• La siguiente línea contiene ~R~ enteros separados por espacios ~l_1, l_2, l_3, ... l_R~, que representan las longitudes de los bloques consecutivos máximos de caracteres iguales en ~s~. Se garantiza que ~N = \sum_{i=1}^R l_i \leq 10^9~.

Además, se garantiza que la suma de ~R^2~ en todas las pruebas no supera ~1,5 \cdot 10^6~.

Salida

Para cada caso de prueba, imprimir el número mínimo de operaciones necesarias para mover todos los ~1~ al principio o ~-1~ si es imposible, así como el número de secuencias de operaciones que alcanzan este mínimo módulo ~10^9+7~.

Restricciones

• ~2 \leq N \leq 10^9~
• ~0 < l_i < 10^9~
• ~1 \leq T \leq 2026~
• ~2 \leq R \leq 800~

Puntuación

Entrada(s)	Restricciones adicionales
3	~N \leq 10~, todas las pruebas son distintas
4	~R \leq 10~
5-8	~R \leq 100~, la suma de ~R^2~ en todas las pruebas no supera ~10^5~, el número mínimo de operaciones está garantizado, ~R/2-1~
9-12	~R \leq 100~, la suma de ~R^2~ en todas las pruebas no supera ~10^5~
13-16	Sin restricciones adicionales

Ejemplo #1 de Entrada

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

Ejemplo #1 de Salida

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

Esta es la secuencia de dos operaciones para el quinto caso de prueba: ~010110 -> 100110 -> 111000~.

Ejemplo #2 de Entrada

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

Ejemplo #2 de Salida

0 1
1 1
2 1
3 3
4 9

En todos estos casos de prueba, el número mínimo de operaciones es igual a ~R/2-1~.

Aquí están las tres secuencias posibles de tres operaciones para el cuarto caso de prueba:

(1)

10101010
-> 11001010
-> 11001100
-> 11110000

(2)

10101010
-> 10110010
-> 10001110
-> 11110000

(3)

10101010
-> 10101100
-> 11001100
-> 11110000