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

The string S, consisting of no more than 20 lowercase Latin letters.

Output

Print the number of the string in the set of permutations of its letters.

Examples