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