У девочки Ксюши есть строка \textbf{s}. Она стала играть с ней --- переставлять буквы строки местами. Сейчас Ксюше очень интересно, а сколько различных палиндромов она может получить, переставляя буквы строки \textbf{s}? Строка называется палиндромом, если она читается одинаково, как слева направо, так и справа налево. Например, строка "\textbf{ded}" --- палиндром. \InputFile В первой строке записана строка \textbf{s} (\textbf{1} ≤ \textbf{|s|} ≤ \textbf{10^6}). Строка состоит только из маленьких латинских букв. \OutputFile Выведите единственное целое число --- сколько различных палиндромов Ксюша может получить, переставляя буквы строки \textbf{s}. Так как ответ может быть достаточно большим, выведите его по модулю \textbf{1000000000} (\textbf{10^9}).