A student asks how many distinct ways letters of a word (with repeats) can be rearranged — Oindrila needs to count that modulo the prime too. Given a string with possibly repeated letters, print the number of DISTINCT permutations of it, mod (10^9+7).
Input
One string S.
Output
Number of distinct permutations mod (10^9+7).
Constraints
1 ≤ |S| ≤ 10^6
Sample Input
aab
Sample Output
3
main.c
Loading editor…
Write C, then Run (custom I/O) or Submit (sample tests). ⌘/Ctrl+Enter submits.