Palindromic Anagram

Time Limit : 1 sec, Memory Limit : 65536 KB

問題文

文字列 S が与えられる。S のすべてのアナグラムのうち、回文になっているものの個数を求めよ。

文字列 XY のアナグラムであるとは、XY と等しいか、X の文字を並び替えたら Y に等しくなることをいう。例えば文字列abcdに対して、abcdやcbdaなどはアナグラムであるが、abedやcabやabcddなどはアナグラムでない。

文字列 X が回文であるとは、X を逆から読んだものが X 自身と等しくなることをいう。例えばabcやabは回文でなく、aやabccbaなどは回文である。

入力

入力は以下の形式に従う。

S

制約

  • 1 \leq |S| \leq 40 ( |S| は文字列 S の長さ)
  • S は小文字の英字のみを含む。
  • 答は 2^{63} 未満であることが保証される。

出力

個数を1行に出力せよ。

Sample Input 1

ab

Output for the Sample Input 1

0

abのアナグラムはabとbaの二つがあるが、どちらも回文になっていない。

Sample Input 2

abba

Output for the Sample Input 2

2

abbaとbaabの二つの文字列が回文かつアナグラムになっている。


Source: Osaka University Programming Contest 2012 , Osaka, Japan, 2012-03-18