Игра «Наборщик» проходит следующим образом: выбирается одно длинное слово, а затем игрок пытается из букв этого слова составить различные слова. Букву из исходного слова в каждом из составляемых слов можно использовать не больше раз, чем её количество в исходном слове.

По заданному слову узнайте, сколько существует вариантов составляемых слов.

Единственная строка входных данных содержит одно слово из маленьких латинских букв. Длина слова от 1 до 1000 символов.

Выведите одно целое число — количество вариантов составляемых слов.

Примеры

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

Примечание. Из слова "aab" из примера можно получить следующие 8 слов:

a, aa, ab, aab, aba, b, ba, baa.