EduBrick

G. Сколько разных слов

2000 мс · 256 МБ · всё или ничего

Дано слово из строчных латинских букв. Сколько различных слов можно получить, переставляя его буквы?

Если бы все буквы были разными, ответ был бы n!n!. Одинаковые буквы переставлять между собой бессмысленно — каждая перестановка одинаковых букв даёт то же слово.

Формат ввода

Одна строка содержит слово длиной от 1 до 2⋅1052 \cdot 10^5 из строчных латинских букв.

Формат вывода

Одно число — количество различных слов по модулю 109+710^9 + 7.

Примеры

ввод
aab
вывод
3
ввод
abc
вывод
6
Войдите, чтобы отправлять решения.