All Tracks Algorithms String Algorithms Basics of String Manipulation Problem

Good Subsequences
/

Algorithms, String, String Manipulation

Problem
Editorial
Analytics

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\)

SAMPLE INPUT
3
aaa
abba
abcd
SAMPLE OUTPUT
3
4
1
Explanation

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.

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems

Contributors

This Problem was Asked in

Initializing Code Editor...
Notifications
View All Notifications

?