Palindrome Row (Hard)

Ksyusha has a string (s). 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 (s).

A string is considered a palindrome if it reads the same forwards and backwards. For example, the string "(ded)" is a palindrome.

Input

The first line contains the string (s) ((1 $\le$ |s| $\le$ 10^6)). The string consists solely of lowercase Latin letters.

Output

Output a single integer — the number of distinct palindromes Ksyusha can form by rearranging the letters of the string (s). Since the result can be very large, provide it modulo (1000000000) ((10^9)).

Examples