P16572 [USACO26Open] Arranging Cows

给定一个长度为 $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$ 取模的结果。

### 样例 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 完成