Permutation Rank of a String

Given a string composed of no more than 10 unique lowercase letters, consider all possible permutations of these letters sorted in lexicographical order. The permutations are indexed starting from 0.

For example, when the letters are a, b, c, d, there are \(4! = 24\) permutations. The ordering starts as follows:

abcd  0
abdc  1
acbd  2
acdb  3
adbc  4
adcb  5
bacd  6
badc  7
bcad  8
bcda  9
bdac  10
bdca  11
cabd  12
cadb  13
cbad  14
cbda  15
cdab  16
cdba  17
...  

Your task is to compute the lexicographical rank of a given permutation string. The rank is defined as the number of permutations that appear before the given permutation in the sorted list.

Note: It is guaranteed that all letters in the given string are distinct.

inputFormat

The input consists of a single line containing the permutation string composed of distinct lowercase letters. The total number of letters is at most 10.

outputFormat

Output a single integer representing the rank (starting from 0) of the given permutation among all the lexicographically sorted permutations.

sample

abcd

0