给定一个长度为 $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$（字符串中连续相同字符块的数量，$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

第五个测试用例的两次操作序列为： $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：无额外限制。

题目来源：Sujay Konda