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