Палиндромная строка
У девочки Ксюши есть строка s. Она стала играть с ней — переставлять буквы строки местами.
Сейчас Ксюше очень интересно, а сколько различных палиндромов она может получить, переставляя буквы строки s?
Строка называется палиндромом, если она читается одинаково, как слева направо, так и справа налево. Например, строка "ded" — палиндром.
Входные данные
В первой строке записана строка s (1 ≤ |s| ≤ 20). Состоит только из маленьких латинских букв.
Выходные данные
Выведите единственное целое число — сколько различных палиндромов Ксюша может получить, переставляя буквы строки s.
Примечание. Строка x = x_1x_2...x_p лексикографически меньше строки y = y_1y_2...y_q, если либо p < q и x_{1 }= y_1,x_{2 }= y_{2 },..., x_{p }= y_p, либо существует такое число r (r < p, r < q), что x_1 = y_1, x_2 = y_2, ..., x_r = y_r и x_{r+1} < y_{r+1}. Символы строк сравниваются как их ASCII коды.