A banner is printed by arranging all the letter tiles of a given word in a row. Repeated letters are indistinguishable, so two arrangements are the same when they read as the same string. Count the number of distinct strings that can be formed by permuting all the tiles of the word. Report the count modulo 1000000007.
Input format
A single line: a non-empty word made of lowercase English letters.
Output format
A single integer: the number of distinct arrangements, modulo 1000000007.
Constraints
- 1 <= length of the word <= 64
- The word contains only lowercase English letters.