Palindrome Row (Hard)#5940
Ksyusha has a string . She enjoys rearranging the letters of this string.
Ksyusha is curious to know how many distinct palindromes she can create by rearranging the letters of the string .
A string is considered a palindrome if it reads the same forwards and backwards. For example, the string "ded" is a palindrome.
The first line contains the string (1 \leq |s| \leq 10^6). The string consists solely of lowercase Latin letters.
Output a single integer — the number of distinct palindromes Ksyusha can form by rearranging the letters of the string . Since the result can be very large, provide it modulo (10^9).
Example 1