Problem
A binary string is said to be beautiful, if the count of “0101” substrings in the string is equal to that of “1010” substrings.
Chef has a binary string �S. Chefina asked him to find the count of non-empty beautiful subsequences of the string �S. Since the answer can be huge, print it modulo 109+7109+7.
Note that, a subsequence is obtained by deletion of several (possibly zero) characters from the string by maintaining the order of the remaining characters. Two subsequences are considered different if the set of indices deleted to obtain them aren’t identical. See Sample test case 2 for more clarification.
Input Format
- The first line of input will contain a single integer �T, denoting the number of test cases. The description of test cases follows.
- The first line of each test case contains an integer �N, the length of string �S.
- The second line of each test case contains a binary string �S.
Output Format
For each test case, print the count of non-empty beautiful subsequences of the string �S, modulo (109+7)(109+7).
Constraints
- 1≤�≤1051≤T≤105
- 1≤�≤1061≤N≤106
- �S consists of 00 and 11 only.
- The sum of �N over all test cases won’t exceed 106106.
Sample 1:
Input
Output
4 2 10 3 110 5 11111 8 10100110
2 4 31 122
Explanation:
Test case 11 : Following are the non-empty subsequences of string �S:
- 11 : number of 0101 substrings =0=0, number of 1010 substrings =0=0.
- 00 : number of 0101 substrings =0=0, number of 1010 substrings =0=0.
- 1010 : number of 0101 substrings =0=0, number of 1010 substrings =1=1.
Hence, 11 and 00, are beautiful subsequences.
Test case 22 : The beautiful subsequences are {1,1,0,11}{1,1,0,11}. Note that the subsequence 11 can be generated using index 11 as well as index 22. That is why, it is considered twice.
