Question
Lexicographic Beauty Count
Bhavya is given a string S of length N. A non-empty string Y is considered beautiful if it satisfies both of the given conditions:
- Let f(c,X) denote the frequency of character c in string X. For every character c present in string Y, f(c,Y) ≤ f(c,S).
- String Y should be lexicographically smallest among all possible strings obtained by rearranging the characters of Y.
Find the number of unique beautiful strings. As the answer can be huge, print it modulo 109 + 7.
Note: A string A is lexicographically smaller than a string B if in the first position where A and B differ, string A has a letter that appears earlier in the alphabet than the corresponding letter in B.
If the first min(A.length, B.length) characters do not differ, then the shorter string is the lexicographically smaller one.
Input
The first line of input contains a single integer T, denoting the number of test cases.
Each test case consists of two lines of input.
The first line of each test case contains an integer N - the length of string S.
The next line contains the string S, made only of lowercase English letters.
Constraints
1 ≤ T ≤ 105
1 ≤ N ≤ 105
String S contains only lowercase English alphabets.
The sum of N over all test cases won't exceed 105.
Each test case consists of two lines of input.
The first line of each test case contains an integer N - the length of string S.
The next line contains the string S, made only of lowercase English letters.
Constraints
1 ≤ T ≤ 105
1 ≤ N ≤ 105
String S contains only lowercase English alphabets.
The sum of N over all test cases won't exceed 105.
Output
For each test case, output on a new line, a single integer, representing the number of unique beautiful strings. As the answer can be huge, print it modulo 109 + 7.
Example
Sample Input
2
2
ju
3
aba
Sample Output
3
5
Explanation
Test case 1: All possible beautiful strings are {j, u, ju}. Note that uj is not beautiful because, if we rearrange the characters, we will get ju, which is lexicographically smaller than uj, violating the second condition.
Test case 2: All possible beautiful strings are {a, b, aa, ab, aab}.
2
2
ju
3
aba
Sample Output
3
5
Explanation
Test case 1: All possible beautiful strings are {j, u, ju}. Note that uj is not beautiful because, if we rearrange the characters, we will get ju, which is lexicographically smaller than uj, violating the second condition.
Test case 2: All possible beautiful strings are {a, b, aa, ab, aab}.