eolymp
bolt
Try our new interface for solving problems
Problems

Number by permutation of letters

Number by permutation of letters

Time limit 1 second
Memory limit 128 MiB

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