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 \(10^9 + 7\).
In other words, determine the length \(X\) of the longest good subsequence and the number of good subsequences of length \(X\) modulo \(10^9 + 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 \(10^9 + 7\).
Answer for each test case should come in a new line.
Input Constraints
\(1 \le T \le 10\)
\(1 \le |S| \le 10^5\)
3 aaa abba abcd
3 4 1
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.
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor