Se te da una cadena de bits $s_{1\dots N}$ de longitud $N$ ($2\le N\le 10^9$). En una operación, puedes invertir un rango $s_{l\dots r}$ si se cumplen las siguientes condiciones:

1. El tamaño del rango es par.
2. La primera mitad del rango consiste en un solo carácter (ya sea $0$ o $1$), y la segunda mitad contiene el carácter opuesto.
3. O bien $l = 1$ o $s_{l-1} \neq s_l$.
4. O bien $r = N$ o $s_{r+1} \neq s_r$.

Encuentra el número mínimo de operaciones para mover todos los $1$s al frente, o informa si es imposible. Si es posible hacerlo, imprime también el número de secuencias de operaciones que logran este mínimo, módulo $10^9+7$.

Entrada

La primera línea contiene $T$ ($1 \leq T \leq 2026$), el número de casos de prueba independientes. Cada prueba se especifica en el siguiente formato:

La cadena de bits se proporciona en un formato comprimido. La primera línea contiene $R$, el número de bloques consecutivos en la cadena ($2\le R\le 800$), y el primer carácter de la cadena (ya sea 0 o 1).

La siguiente línea contiene $R$ enteros separados por espacios $l_1,l_2,l_3,\ldots l_R$ ($0< l_i< 10^9$), las longitudes de los bloques consecutivos máximos de caracteres iguales en $s$. Se garantiza que $N=\sum_{i=1}^Rl_i\le 10^9$.

Además, se garantiza que la suma de $R^2$ sobre todas las pruebas no excede $1.5\cdot 10^6$.

Salida

Para cada caso de prueba, imprime el número mínimo de operaciones para mover todos los $1$s al frente o $-1$ si es imposible, así como el número de secuencias de operaciones que logran este mínimo módulo $10^9+7$.

Ejemplos

Entrada 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

Salida 1

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

Nota 1

Aquí está la secuencia de dos operaciones para el quinto caso de prueba: $010110 \to 100110 \to 111000.$

Entrada 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

Salida 2

0 1
1 1
2 1
3 3
4 9

Nota 2

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

Subtareas

• Entrada 3: $N \leq 10$, todas las pruebas son distintas.
• Entrada 4: $R\le 10$.
• Entradas 5-8: $R\le 100$, la suma de $R^2$ sobre todas las pruebas no excede $10^5$, el número mínimo de operaciones está garantizado que es igual a $R/2-1$.
• Entradas 9-12: $R\le 100$, la suma de $R^2$ sobre todas las pruebas no excede $10^5$.
• Entradas 13-16: Sin restricciones adicionales.