If you're already familiar with Permutations, here's a slight variation to add some difficulty: how many unique strings can we create
from the string ABCDEF just by rearranging the letters? Because n=k then we can calculate that n! / (n - k)! = 6! / 0! = 720.
However, what about the string ABBCCC? Since we now have some repeated identical elements within our set, the problem becomes a bit
more complicated.
But only just a little more complicated! if we instead take the set A B1 B2, we can start to pick apart what's going on. Here we can see
that for every permutation, there exists some sister-permutations where the identical values are in a different order. For example
A B1 B2 and A B2 B1, or B2 A B1 and B1 A B2. Thus for each element with n occurences in the set, there exists n! identical
sister-permutations. So in order to calculate the final value, we must divide our total number of permutations by the factorials of
the frequencies of each unique element.
Input Data
First line contains Q, the quantity of testcases.
Q lines will follow each containing string of capital letters.
Answer
Should contain Q space-separated values, corresponding to the number of unique permutations possible for each given string.
Report all answers modulo 1000000007.
Example
input data:
3
ABCDEF
ABBCCC
VBDKSWOVHXKANVMLDHSVHDODHFBJKCNKVJHUC
answer:
720 60 571668606