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$