Bạn được cho một xâu bit \(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 đoạn \(s_{l\dots r}\) nếu các điều kiện sau được thỏa mãn:

1. Độ dài của đoạn là số chẵn.
2. Nửa đầu của đoạn chỉ gồm một ký tự (hoặc \(0\) hoặc \(1\)), và nửa sau chứa ký tự còn 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ố thao tác ít nhất để đưa tất cả các ký tự \(1\) lên đầu xâu, hoặc cho biết điều đó là không thể. Nếu có thể, hãy đồng thời in ra số dãy thao tác đạt được số thao tác ít nhất này, lấy modulo \(10^9+7\).

Dữ liệu vào

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

Xâu bit được cho dưới dạng nén. Dòng đầu tiên chứa \(R\), là số đoạn liên tiếp gồm các ký tự giống nhau trong xâu (\(2\le R\le 800\)), và ký tự đầu tiên của xâu (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 gồm các ký tự giống nhau trong \(s\). Đảm bảo rằng \(N=\sum_{i=1}^R l_i\le 10^9\).

Ngoài ra, đảm bảo rằng tổng \(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ố thao tác ít nhất để đưa tất cả các ký tự \(1\) lên đầu xâu, hoặc \(-1\) nếu điều đó là không thể, cùng với số dãy thao tác đạt được số thao tác ít nhất này lấy modulo \(10^9+7\).

Ví dụ

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
0 1
0 1
-1 0
2 1
-1 0
4 7
3 1
4 1

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

0 1
1 1
2 1
3 3
4 9

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

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

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

Phân nhóm

• Input 3: \(N\leq 10\), tất cả các bộ test đôi một khác nhau.
• Input 4: \(R\le 10\).
• Inputs 5-8: \(R\le 100\), tổng \(R^2\) trên tất cả các bộ test không vượt quá \(10^5\), và đảm bảo số thao tác ít nhất bằng \(R/2-1\).
• Inputs 9-12: \(R\le 100\), tổng \(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.

Nguồn

USACO 2026 US Open, Open Division — Arranging Cows. Tác giả: Sujay Konda.
https://usaco.org/index.php?page=viewproblem2&cpid=1602