Bạn được cho một chuỗi nhị phân $s_{1\dots N}$ có độ dài $N$ ($2\le N\le 10^9$). Trong một thao tác, bạn có thể đảo ngược một đoạn $s_{l\dots r}$ nếu các điều kiện sau đây được thỏa mãn:

1. Độ dài của đoạn là số chẵn.
2. Nửa đầu của đoạn bao gồm một loại ký tự (hoặc $0$ hoặc $1$), và nửa sau chứa ký tự ngược lại.
3. Hoặc $l = 1$ hoặc $s_{l-1} \neq s_l$.
4. Hoặc $r = N$ hoặc $s_{r+1} \neq s_r$.

Hãy tìm số lượng thao tác tối thiểu để đưa tất cả các số $1$ về phía trước, hoặc thông báo rằng điều đó là không thể. Nếu có thể thực hiện, hãy in ra số lượng các chuỗi thao tác đạt được giá trị tối thiểu này, theo modulo $10^9+7$.

Dữ liệu vào

Dòng đầu tiên chứa $T$ ($1 \leq T \leq 2026$), số lượng bộ test độc lập. Mỗi bộ test được xác định theo định dạng sau:

Chuỗi nhị phân được cho dưới dạng nén. Dòng đầu tiên chứa $R$, số lượng các đoạn liên tiếp trong chuỗi ($2\le R\le 800$), và ký tự đầu tiên của chuỗi (hoặc $0$ hoặc $1$).

Dòng tiếp theo chứa $R$ số nguyên cách nhau bởi dấu cách $l_1,l_2,l_3,\ldots l_R$ ($0< l_i< 10^9$), là độ dài của các khối liên tiếp cực đại của các ký tự giống nhau trong $s$. Đảm bảo rằng $N=\sum_{i=1}^Rl_i\le 10^9$.

Ngoài ra, đảm bảo rằng tổng của $R^2$ trên tất cả các bộ test không vượt quá $1.5\cdot 10^6$.

Dữ liệu ra

Với mỗi bộ test, in ra số lượng thao tác tối thiểu để đưa tất cả các số $1$ về phía trước hoặc $-1$ nếu không thể, cùng với số lượng các chuỗi thao tác đạt được giá trị tối thiểu này theo modulo $10^9+7$.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 1

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

Ghi chú

Dưới đây là chuỗi hai thao tác cho bộ test thứ năm: $010110 \to 100110 \to 111000.$

Dữ liệu vào 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

Dữ liệu ra 2

0 1
1 1
2 1
3 3
4 9

Trong tất cả các bộ test này, số lượng thao tác tối thiểu bằng $R/2-1$.

Dưới đây là tất cả ba chuỗi thao tác có thể cho bộ test thứ tư:

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

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

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

Nhiệm vụ con

• Input 3: $N \leq 10$, tất cả các bộ test đều khác nhau.
• Input 4: $R\le 10$.
• Inputs 5-8: $R\le 100$, tổng của $R^2$ trên tất cả các bộ test không vượt quá $10^5$, số lượng thao tác tối thiểu được đảm bảo bằng $R/2-1$.
• Inputs 9-12: $R\le 100$, tổng của $R^2$ trên tất cả các bộ test không vượt quá $10^5$.
• Inputs 13-16: Không có ràng buộc bổ sung.