7999: CodeChef BSTRING - Beautiful Strings
[Creator : ]
Description
A binary string is said to be beautiful, if the count of "01" substrings in the string is equal to that of "10" 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 $10^9+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.
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 $10^9+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
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.
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
For each test case, print the count of non-empty beautiful subsequences of the string S, modulo $10^9+7$.
Constraints
1≤T≤105
$1≤N≤10^6$
S consists of 0 and 1 only.
The sum of N over all test cases won't exceed $10^6$.
$1≤N≤10^6$
S consists of 0 and 1 only.
The sum of N over all test cases won't exceed $10^6$.
Sample 1 Input
4
2
10
3
110
5
11111
8
10100110
Sample 1 Output
2
4
31
122
Test case 1 : Following are the non-empty subsequences of string S:
Test case 2 : The beautiful subsequences are {1,1,0,11}. Note that the subsequence 1 can be generated using index 1 as well as index 2. That is why, it is considered twice.
- 1 : number of 01 substrings =0, number of 10 substrings =0.
- 0 : number of 01 substrings =0, number of 10 substrings =0.
- 10 : number of 01 substrings =0, number of 10 substrings =1.
Test case 2 : The beautiful subsequences are {1,1,0,11}. Note that the subsequence 1 can be generated using index 1 as well as index 2. That is why, it is considered twice.