Номер по перестановці букв

Перестановкою букв рядка S називаються усі різні рядки, які отримуються з неї перестановкою букв.

Звичайно, що усі перестановки букв можна упорядкувати лексикографічно як рядки. Наприклад, для рядка abba список упорядкованих перестановок букв буде виглядати так: aabb, abab, abba, baab, baba, bbaa.

Знайдіть лексикографічний номер рядка у множині усіх перестановок його букв (нумерація ведеться з нуля).

Вхідні дані

Рядок S, який складається не більше ніж з 20 букв латинського алфавіту нижнього регістру.

Вихідні дані

Виведіть номер рядка у множині перестановок його букв.

Приклади