题目描述
给出一个字符串S，问S有多少个不同的回文子序列。答案模1000000007。

例如"bdf"是"abcdefg"的子序列，"abc"是"abc"的子序列，但"abbc"不是"abc"的子序列，"ca"也不是"abc"的子序列。

注意：即使子序列字符串相同，但如果位置不同，也被认为是不同的子序列，具体看样例。所谓的回文子序列，就是指子序列的字符串从前往后读和从后往前读是一样的。

输入格式
一个字符串S，长度不超过100，全部有大写英文字母构成。

输出格式
一个整数。

样例

AB

2

ABA

5

ABCBA

13

样例解释
样例2：共5个不同的回文子序列："A"、"B"、"A"、"AA"、"ABA"。第1个"A"和第3个"A"是不同的子序列，因为位置不同。
样例3：除了空串不行，其他的子序列都可以，2^3-1=7。