Counting Equivalent Anagrams

In this problem, you are given $Q$ strings consisting of the characters (a), (b), and (c). For each string, you need to count the number of non-empty strings (over the same alphabet ({a,b,c})) that are equivalent to it. Two strings are considered equivalent if they have the same multiset of characters (i.e. they are anagrams of each other). In other words, for a given string (S) with length (n) and character frequencies (f_a, f_b, f_c), you must compute the number of distinct permutations of (S), which is given by the formula: [ \frac{n!}{f_a!, f_b!, f_c!} \mod (10^9+7). ] Note that the answer can be very large, so you are required to take the answer modulo (10^9+7).

inputFormat

The first line contains an integer (Q) (the number of queries). Each of the next (Q) lines contains a non-empty string consisting only of the characters a, b, and c.

outputFormat

For each query, output a single integer: the number of non-empty strings equivalent to the given string, modulo (10^9+7).

sample

1
abc

6