eolymp
bolt
Try our new interface for solving problems
Məsələlər

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

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

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

У девочки Ксюши есть строка 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