You are given a string S consisting of lowercase alphabets. A good subsequence of this string is a subsequence which contains distinct characters only.
Determine the number of good subsequences of the maximum possible length modulo 109+7.
In other words, determine the length X of the longest good subsequence and the number of good subsequences of length X modulo 109+7.
Input format
- First line: An integer T denoting the number of test cases
- Each of the next T lines: String S
Output format
For each test case, print the number of good subsequences of the maximum length modulo 109+7.
Answer for each test case should come in a new line.
Input Constraints
1≤T≤10
1≤|S|≤105
In the first testcase, any one of the a can be chosen. Hence there are 3 good subsequences of maximum length.
In the second testcase, the maximum length of a good subsequence is 2. There are 4 such subsequences (listed by indices):
- (1, 2)
- (1, 3)
- (2, 4)
- (3, 4)
In the third testcase, the maximum length of a good subsequence is 4 and there is only 1 such subsequence.
