給定一個長度為 $N$ 的位元字串 $s_{1\dots 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$，即字串中連續區段（runs）的數量 ($2\le R\le 800$)，以及字串的第一個字元（$0$ 或 $1$）。

下一行包含 $R$ 個以空白分隔的整數 $l_1, l_2, l_3, \dots, 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

說明

第五個測試資料的兩次操作序列如下： $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：無額外限制。