Задачі
Палиндромная строка (Hard)
Палиндромная строка (Hard)
У девочки Ксюши есть строка s. Она стала играть с ней — переставлять буквы строки местами.
Сейчас Ксюше очень интересно, а сколько различных палиндромов она может получить, переставляя буквы строки s?
Строка называется палиндромом, если она читается одинаково, как слева направо, так и справа налево. Например, строка "ded" — палиндром.
Вхідні дані
В первой строке записана строка s (1 ≤ |s| ≤ 10^6). Строка состоит только из маленьких латинских букв.
Вихідні дані
Выведите единственное целое число — сколько различных палиндромов Ксюша может получить, переставляя буквы строки s. Так как ответ может быть достаточно большим, выведите его по модулю 1000000000 (10^9).
Приклад
Вхідні дані #1
aaaaa
Вихідні дані #1
1