On vous donne une chaîne de bits $s_{1\dots N}$ de longueur $N$ ($2\le N\le 10^9$). En une opération, vous pouvez inverser une plage $s_{l\dots r}$ si les conditions suivantes sont remplies :

1. La taille de la plage est paire.
2. La première moitié de la plage est constituée d'un seul caractère (soit $0$, soit $1$), et la seconde moitié contient le caractère opposé.
3. Soit $l = 1$, soit $s_{l-1} \neq s_l$.
4. Soit $r = N$, soit $s_{r+1} \neq s_r$.

Trouvez le nombre minimum d'opérations pour déplacer tous les $1$ au début, ou indiquez si c'est impossible. S'il est possible de le faire, affichez également le nombre de séquences d'opérations atteignant ce minimum, modulo $10^9+7$.

Entrée

La première ligne contient $T$ ($1 \leq T \leq 2026$), le nombre de tests indépendants. Chaque test est spécifié dans le format suivant :

La chaîne de bits est donnée dans un format compressé. La première ligne contient $R$, le nombre de segments dans la chaîne ($2\le R\le 800$), et le premier caractère de la chaîne (soit $0$, soit $1$).

La ligne suivante contient $R$ entiers séparés par des espaces $l_1,l_2,l_3,\ldots l_R$ ($0< l_i< 10^9$), les longueurs des blocs consécutifs maximaux de caractères identiques dans $s$. Il est garanti que $N=\sum_{i=1}^Rl_i\le 10^9$.

De plus, il est garanti que la somme des $R^2$ sur tous les tests ne dépasse pas $1,5\cdot 10^6$.

Sortie

Pour chaque cas de test, affichez le nombre minimum d'opérations pour déplacer tous les $1$ au début ou $-1$ si c'est impossible, ainsi que le nombre de séquences d'opérations atteignant ce minimum modulo $10^9+7$.

Exemples

Entrée 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

Sortie 1

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

Voici la séquence de deux opérations pour le cinquième cas de test : $010110 \to 100110 \to 111000.$

Entrée 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

Sortie 2

0 1
1 1
2 1
3 3
4 9

Dans tous ces cas de test, le nombre minimum d'opérations est égal à $R/2-1$.

Voici les trois séquences possibles de trois opérations pour le quatrième cas de test :

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

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

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

Sous-tâches

• Entrée 3 : $N \leq 10$, tous les tests sont distincts.
• Entrée 4 : $R\le 10$.
• Entrées 5-8 : $R\le 100$, la somme des $R^2$ sur tous les tests ne dépasse pas $10^5$, le nombre minimum d'opérations est garanti égal à $R/2-1$.
• Entrées 9-12 : $R\le 100$, la somme des $R^2$ sur tous les tests ne dépasse pas $10^5$.
• Entrées 13-16 : Aucune contrainte supplémentaire.

Crédits du problème : Sujay Konda