Məsələlər
Палиндромная строка (Hard)
Палиндромная строка (Hard)
У девочки Ксюши есть строка s. Она стала играть с ней — переставлять буквы строки местами.
Сейчас Ксюше очень интересно, а сколько различных палиндромов она может получить, переставляя буквы строки s?
Строка называется палиндромом, если она читается одинаково, как слева направо, так и справа налево. Например, строка "ded" — палиндром.
Giriş verilənləri
В первой строке записана строка s (1 ≤ |s| ≤ 10^6). Строка состоит только из маленьких латинских букв.
Çıxış verilənləri
Выведите единственное целое число — сколько различных палиндромов Ксюша может получить, переставляя буквы строки s. Так как ответ может быть достаточно большим, выведите его по модулю 1000000000 (10^9).
Nümunə
Giriş verilənləri #1
aaaaa
Çıxış verilənləri #1
1