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$.

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]$.