H. Turtle and Nediam 2time limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard 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.InputEach 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$$$. OutputFor each test case, output a single integer — the number of binary sequences that can be obtained, modulo $$$10^9 + 7$$$.ExampleInput5511111610001190001110001411001111111000160010000110100011Output4
8
30
114
514
NoteIn 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]$$$.