eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Палиндромная строка (Hard)

Палиндромная строка (Hard)

Ліміт часу 1 секунда
Ліміт використання пам'яті 256 MiB

У девочки Ксюши есть строка s. Она стала играть с ней — переставлять буквы строки местами.

Сейчас Ксюше очень интересно, а сколько различных палиндромов она может получить, переставляя буквы строки s?

Строка называется палиндромом, если она читается одинаково, как слева направо, так и справа налево. Например, строка "ded" — палиндром.

Вхідні дані

В первой строке записана строка s (1|s|10^6). Строка состоит только из маленьких латинских букв.

Вихідні дані

Выведите единственное целое число — сколько различных палиндромов Ксюша может получить, переставляя буквы строки s. Так как ответ может быть достаточно большим, выведите его по модулю 1000000000 (10^9).

Приклад

Вхідні дані #1
aaaaa
Вихідні дані #1
1