← 返回题目列表

Codeforces · 2084/H

H. 海龟和 Nediam 2

中文机器翻译题面 查看原题

LGR-205-Div.1 C 海龟和 Nediam

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

您可以进行以下操作 最多 $$$n - 2$$$ 次 (可能为零):

  • 让 $$$m$$$ 表示 $$$s$$$ 的当前长度。选择一个整数 $$$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$$$ 为模。

示例

输入
复制

5
5
11111
6
100011
9
000111000
14
11001111111000
16
0010000110100011

输出
复制

4
8
30
114
514

注意

在第一个测试用例中,可以获得以下二进制序列:$$$[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]$$$。