CF2084H.Turtle and Nediam 2

LGR-205-Div.1 C Turtle and Nediam

给定一个长度为 $n$ 的二进制序列 $s$，仅由 $0$ 和 $1$ 组成。

你可以进行最多 $n - 2$ 次（可以是零次）以下操作：

• 设当前序列 $s$ 的长度为 $m$。选择一个整数 $i$ 满足 $1 \le i \le m - 2$。
• 设子数组 $[s_i, s_{i + 1}, s_{i + 2}]$ 的中位数 $^{\text{∗}}$ 为 $x$，并令 $j$ 为满足 $j \ge i$ 且 $s_j = x$ 的最小整数。
• 从序列中移除 $s_j$ 并将剩余部分拼接。换句话说，将 $s$ 替换为 $[s_1, s_2, \ldots, s_{j - 1}, s_{j + 1}, s_{j + 2}, \ldots, s_m]$。

注意每次操作后，序列 $s$ 的长度会减少 $1$。

求经过若干次操作后，可以得到的不同二进制序列的数量，结果对 $10^9 + 7$ 取模。

$^{\text{∗}}$ 长度为奇数 $k$ 的数组的中位数是指排序后的第 $\frac{k + 1}{2}$ 个元素。

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$3 \le n \le 2 \cdot 10^6$）——二进制序列的长度。
第二行包含一个长度为 $n$ 的字符串 $s$，仅由 $0$ 和 $1$ 组成。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^6$。

对于每个测试用例，输出一个整数——可以得到的二进制序列的数量，对 $10^9 + 7$ 取模。

• 在第一个测试用例中，可以得到以下二进制序列：$[1, 1]$、$[1, 1, 1]$、$[1, 1, 1, 1]$、$[1, 1, 1, 1, 1]$。

• 在第二个测试用例中，可以得到以下二进制序列：$[0, 1]$、$[0, 1, 1]$、$[1, 0, 1]$、$[1, 0, 0, 1]$、$[1, 0, 1, 1]$、$[1, 0, 0, 0, 1]$、$[1, 0, 0, 1, 1]$、$[1, 0, 0, 0, 1, 1]$。例如，要得到 $[0, 1, 1]$，可以：

  • 选择 $i = 2$。子数组 $[0, 0, 0]$ 的中位数为 $0$。移除 $s_2$，序列变为 $[1, 0, 0, 1, 1]$。
  • 选择 $i = 1$。子数组 $[1, 0, 0]$ 的中位数为 $0$。移除 $s_2$，序列变为 $[1, 0, 1, 1]$。
  • 选择 $i = 1$。子数组 $[1, 0, 1]$ 的中位数为 $1$。移除 $s_1$，序列变为 $[0, 1, 1]$。

翻译由 DeepSeek V3 完成