Дана битовая строка $s_{1\dots N}$ длины $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$), количество независимых тестов. Каждый тест задан в следующем формате:

Битовая строка задана в сжатом виде. Первая строка содержит $R$, количество серий (блоков) в строке ($2\le R\le 800$), и первый символ строки (либо $0$, либо $1$).

Следующая строка содержит $R$ целых чисел $l_1, l_2, l_3, \ldots, l_R$ ($0< l_i< 10^9$), разделенных пробелами — длины максимальных последовательных блоков одинаковых символов в $s$. Гарантируется, что $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

Примечание 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: Дополнительных ограничений нет.