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

У девочки Ксюши есть строка s. Она стала играть с ней — переставлять буквы строки местами.

Сейчас Ксюше очень интересно, а сколько различных палиндромов она может получить, переставляя буквы строки s?

Строка называется палиндромом, если она читается одинаково, как слева направо, так и справа налево. Например, строка "ded" — палиндром.

Входные данные

В первой строке записана строка s (1 ≤ |s| ≤ 10^6). Строка состоит только из маленьких латинских букв.

Выходные данные

Выведите единственное целое число — сколько различных палиндромов Ксюша может получить, переставляя буквы строки s. Так как ответ может быть достаточно большим, выведите его по модулю 1000000000 (10^9).

Примеры