H. Черепаха и Недиам 2
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

LGR-205-Div.1 C Черепаха и Недиам

Вам дана бинарная последовательность $$$s$$$ длины $$$n$$$, которая состоит только из $$$0$$$ и $$$1$$$.

Вы можете выполнить следующую операцию не более $$$n - 2$$$ раз (возможно, ноль):

  • Пусть $$$m$$$ обозначает текущую длину $$$s$$$. Выберите целое число $$$i$$$ такое, что $$$1 \le i \le m - 2$$$.
  • Пусть медиана$$$^{\text{∗}}$$$ подмассива $$$[s_i, s_{i + 1}, s_{i + 2}]$$$ равна $$$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$$$) — длина бинарной последовательности.

Вторая строка каждого набора входных данных содержит строку $$$s$$$ длины $$$n$$$, состоящую только из $$$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]$$$.