URI Online Judge | 1981

Shuffling Again

By Gabriel Duarte, UNIFESO BR Brazil

Timelimit: 1

Now you've ever helped Gabriel with the first data required for your logic game, he needs your help again.
This time he needs that your program can handle cases where words can has repeated letters.

Input

The input consists of several test cases. Each test case will have a single line with an word S (1 ≤ S ≤ 10000), composed only with characters from 'a' and 'z'. The entry ends when S = 0 and should not be processed.

Output

For each test case you should print how many different anagrams are possible to be formed with the informed characters. As the numbers can be large, print the response module 100000007.

Input Sample Output Sample

abc
abcde
abcdefg
aabb
0

6
120
5040
6