長さ $N$ のビット文字列 $s_{1\dots N}$ ($2\le N\le 10^9$) が与えられます。以下の条件を満たす場合、1回の操作で範囲 $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}^R l_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

注記

5番目のテストケースにおける2回の操作手順は以下の通りです。 $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$ と等しくなります。

4番目のテストケースにおける3回の操作手順として考えられる全3通りは以下の通りです。

(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: 追加の制約なし。