Description

If we use the $4$ letters a b c d to form a string, there are $4! = 24$ possibilities. If we sort them, each string corresponds to an index:

  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
  ...

Now you are given a string formed by no more than 10 pairwise distinct lowercase letters. Can you find the index of this string among all permutations?

Input Format

One line, a string.

Output Format

One line, an integer, representing the index of the given string among all strings generated by permuting its letters. Note: the smallest index is $0$.

bdca

11

cedab

70

Hint

Time limit: 1 second, 256M. Lanqiao Cup, the 5th National Finals, 2014.

Translated by ChatGPT 5