アルゴリズムとデータ構造

回文

左から右へ、また右から左へ読んでも同じになる文字列を「回文」と呼びます（例: radar、madam、racecar）。
文字列 s が与えられたとき、文字を削除して s から回文を作ることができる異なる方法の数を求めます。文字をまったく削除しなくても回文が得られる場合があります。なお、削除の順番は考慮しません。

入力

入力として、長さ |s| が 1 以上 60 以下の大文字のラテン文字のみからなる文字列 s が与えられます。

出力

文字列 s から回文を得るための異なる方法の数を出力してください。

例

Input
Output
BAOBAB
22

解説

  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue