Перестановкой букв строки S называются все различные строки, получающиеся из нее перестановкой букв.

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

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

Входные данные

Строка S, состоящая не более чем из 20 букв латинского алфавита нижнего регистра.

Выходные данные

Выведите номер строки во множестве перестановок её букв.