Dany jest ciąg bitowy $s_{1\dots N}$ o długości $N$ ($2\le N\le 10^9$). W jednej operacji możesz odwrócić podciąg $s_{l\dots r}$, jeśli spełnione są następujące warunki:

1. Długość podciągu jest parzysta.
2. Pierwsza połowa podciągu składa się z jednego znaku (albo $0$, albo $1$), a druga połowa zawiera znak przeciwny.
3. Albo $l = 1$, albo $s_{l-1} \neq s_l$.
4. Albo $r = N$, albo $s_{r+1} \neq s_r$.

Znajdź minimalną liczbę operacji potrzebną do przeniesienia wszystkich $1$ na początek ciągu lub zgłoś, że jest to niemożliwe. Jeśli jest to możliwe, wypisz również liczbę ciągów operacji osiągających to minimum, modulo $10^9+7$.

Wejście

Pierwsza linia zawiera $T$ ($1 \leq T \leq 2026$), liczbę niezależnych testów. Każdy test jest określony w następujący sposób:

Ciąg bitowy jest podany w formacie skompresowanym. Pierwsza linia zawiera $R$, liczbę serii w ciągu ($2\le R\le 800$), oraz pierwszy znak ciągu (albo $0$, albo $1$).

Następna linia zawiera $R$ liczb całkowitych oddzielonych spacjami $l_1,l_2,l_3,\ldots l_R$ ($0< l_i< 10^9$), będących długościami maksymalnych spójnych bloków jednakowych znaków w $s$. Gwarantuje się, że $N=\sum_{i=1}^Rl_i\le 10^9$.

Dodatkowo gwarantuje się, że suma $R^2$ dla wszystkich testów nie przekracza $1.5\cdot 10^6$.

Wyjście

Dla każdego przypadku testowego wypisz minimalną liczbę operacji potrzebną do przeniesienia wszystkich $1$ na początek lub $-1$, jeśli jest to niemożliwe, a także liczbę ciągów operacji osiągających to minimum modulo $10^9+7$.

Przykład

Przykład 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

Wyjście 1

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

Uwagi

Oto sekwencja dwóch operacji dla piątego przypadku testowego: $010110 \to 100110 \to 111000.$

Przykład 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

Wyjście 2

0 1
1 1
2 1
3 3
4 9

We wszystkich tych przypadkach testowych minimalna liczba operacji jest równa $R/2-1$.

Oto wszystkie trzy możliwe sekwencje trzech operacji dla czwartego przypadku testowego:

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

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

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

Podzadania

• Wejście 3: $N \leq 10$, wszystkie testy są różne.
• Wejście 4: $R\le 10$.
• Wejścia 5-8: $R\le 100$, suma $R^2$ dla wszystkich testów nie przekracza $10^5$, minimalna liczba operacji jest gwarantowana jako $R/2-1$.
• Wejścia 9-12: $R\le 100$, suma $R^2$ dla wszystkich testów nie przekracza $10^5$.
• Wejścia 13-16: Brak dodatkowych ograniczeń.

Autor zadania: Sujay Konda