回文
左から右へ、また右から左へ読んでも同じになる文字列を「回文」と呼びます（例: radar、madam、racecar）。
文字列 s が与えられたとき、文字を削除して s から回文を作ることができる異なる方法の数を求めます。文字をまったく削除しなくても回文が得られる場合があります。なお、削除の順番は考慮しません。
入力
入力として、長さ |s| が 1 以上 60 以下の大文字のラテン文字のみからなる文字列 s が与えられます。
出力
文字列 s から回文を得るための異なる方法の数を出力してください。
例
Input | Output |
|---|---|
BAOBAB | 22 |
解説
BAOBABBAOBABBAOBABBAOBABBAOBABBAOBABBAOBABBAOBABBAOBABBAOBABBAOBABBAOBABBAOBABBAOBABBAOBABBAOBABBAOBABBAOBABBAOBABBAOBABBAOBABBAOBAB
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB