CF2084H Turtle and Nediam 2

[LGR-205-Div.1 C Turtle and Nediam](https://www.luogu.com.cn/problem/P11283) 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.

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

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

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