题目描述

给定一个长度为 $N$ 的 01 字符串 $s_{1\ldots N}$（$2 \leq N \leq 10^9$）。在一次操作中，你可以反转区间 $s_l \ldots s_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$），表示独立测试用例的数量。每个测试用例按以下格式给出：

01 字符串以压缩格式给出。第一行包含两个整数 $R$（表示字符串中连续段的个数，$2 \leq R \leq 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 \leq 10^9$。

此外，保证所有测试用例的 $R^2$ 之和不超过 $1.5 \cdot 10^6$。

输出格式

对于每个测试用例，输出一行两个整数：将所有的 $1$ 移动到最前面所需的最少操作次数（若不可能则输出 $-1$），以及达到该最少操作次数的操作序列个数对 $10^9 + 7$ 取模的结果。

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 解释

对于第 5 个测试用例，两次操作的一种可行顺序为：$010110 \to 100110 \to 111000$。

样例 2 解释

在这些测试用例中，最少操作次数均为 $R/2-1$。

下面是第 4 个测试用例所有 3 种三次操作的操作序列：

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

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

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

计分规则

• 输入 $3$：$N \le 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$：无额外限制。

翻译由 DeepSeek V4 Pro 完成