H. Turtle and Nediam 2
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

LGR-205-Div.1 C Turtle and Nediam

You are given a binary sequence $$$s$$$ of length $$$n$$$ which only consists of $$$0$$$ and $$$1$$$.

You can do the following operation at most $$$n - 2$$$ times (possibly zero):

  • Let $$$m$$$ denote the current length of $$$s$$$. Choose an integer $$$i$$$ such that $$$1 \le i \le m - 2$$$.
  • Let the median$$$^{\text{∗}}$$$ of the subarray $$$[s_i, s_{i + 1}, s_{i + 2}]$$$ be $$$x$$$, and let $$$j$$$ be the smallest integer such that $$$j \ge i$$$ and $$$s_j = x$$$.
  • Remove $$$s_j$$$ from the sequence and concatenate the remaining parts. In other words, replace $$$s$$$ with $$$[s_1, s_2, \ldots, s_{j - 1}, s_{j + 1}, s_{j + 2}, \ldots, s_m]$$$.

Note that after every operation, the length of $$$s$$$ decreases by $$$1$$$.

Find how many different binary sequences can be obtained after performing the operation, modulo $$$10^9 + 7$$$.

$$$^{\text{∗}}$$$The median of an array of odd length $$$k$$$ is the $$$\frac{k + 1}{2}$$$-th element when sorted.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$3 \le n \le 2 \cdot 10^6$$$) — the length of the binary sequence.

The second line of each test case contains a string $$$s$$$ of length $$$n$$$, consisting of only $$$0$$$ and $$$1$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^6$$$.

Output

For each test case, output a single integer — the number of binary sequences that can be obtained, modulo $$$10^9 + 7$$$.

Example
Input
5
5
11111
6
100011
9
000111000
14
11001111111000
16
0010000110100011
Output
4
8
30
114
514
Note

In the first test case, the following binary sequences can be obtained: $$$[1, 1]$$$, $$$[1, 1, 1]$$$, $$$[1, 1, 1, 1]$$$, $$$[1, 1, 1, 1, 1]$$$.

In the second test case, the following binary sequences can be obtained: $$$[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]$$$. For example, to obtain $$$[0, 1, 1]$$$, you can:

  • Choose $$$i = 2$$$. The median of $$$[0, 0, 0]$$$ is $$$0$$$. Remove $$$s_2$$$. The sequence becomes $$$[1, 0, 0, 1, 1]$$$.
  • Choose $$$i = 1$$$. The median of $$$[1, 0, 0]$$$ is $$$0$$$. Remove $$$s_2$$$. The sequence becomes $$$[1, 0, 1, 1]$$$.
  • Choose $$$i = 1$$$. The median of $$$[1, 0, 1]$$$ is $$$1$$$. Remove $$$s_1$$$. The sequence becomes $$$[0, 1, 1]$$$.