Good Subsequences
Tag(s):

## Algorithms, Easy, 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
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in Challenge Name

February Easy' 19

OTHER PROBLEMS OF THIS CHALLENGE
• Basic Programming > Implementation
• Algorithms > Searching
• Basic Programming > Implementation
• Data Structures > Advanced Data Structures
• Algorithms > Graphs