G: 回文部分列 (Palindromic Subsequences)

問題

英小文字のみからなる文字列 S が与えられるので、この文字列 S の連続とは限らない部分列であって、回文であるものは何種類あるかを求めてください。

ここで、S の連続とは限らない部分列とは、元の文字列 S から 1 文字以上 |S| 文字以下を任意に選択し (選択するそれぞれの文字の位置は非連続でも良い)、それらを元の順番通りに連結させてできた文字列のことを指します。この問題において、空文字列は部分列として認められないことに注意してください。

また、文字列 X が回文であるとは、元の文字列 X と、X を反転した文字列 X’ が等しいことを指します。

さらに、異なる部分列のとりかたの結果同じ回文が生成されたとしても、それは重複して数えないことに注意してください。例えば S = acpc である場合、 2 文字目のみからなる部分列と、4 文字目のみからなる部分列はどちらも回文 c ですが、これは複数回数えず、合わせて一度だけ数えることとします。

答えは非常に大きくなることがあるので、 1,000,000,007 で割った余りを出力してください。

入力形式

S

制約

• 1 \leq |S| \leq 2,000
• S に含まれる文字は英小文字のみである

出力形式

• 答えを 1,000,000,007 で割った余りを 1 行で出力してください。

入力例1

acpc

出力例1

5

文字列 acpc の連続とは限らない部分列であって回文であるものは、 a, c, cc, cpc, p の 5 種類です。部分列の種類数を数えることに注意してください。

入力例2

z

出力例2

1

条件を満たす部分列は z のみです。空文字列は部分列として認められないことに注意してください。

入力例3

madokamagica

出力例3

28

Note

Link

 

---