Problems
Number by permutation of letters
Number by permutation of letters
The permutations of the letters of the string S are all distinct strings obtained from it by a permutation of the letters.
Naturally, all permutations of letters can be ordered lexicographically as strings. For example, for the string abba, the list of ordered permutations of letters would look like this: aabb, abab, abba, baab, baba, bbaa.
Find the lexicographic number of the string in the set of all permutations of its letters (numbering starts from zero).
Input data
The string S, consisting of no more than 20 lowercase Latin letters.
Output data
Print the number of the string in the set of permutations of its letters.
Examples
Input example #1
abab
Output example #1
1