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