题目描述
给出一个字符串S，问S有多少个不同的回文子序列。答案模1000000007。
例如"bdf"是"abcdefg"的子序列，"abc"是"abc"的子序列，但"abbc"不是"abc"的子序列，"ca"也不是"abc"的子序列。注意：即使子序列字符串相同，但如果位置不同，也被认为是不同的子序列，具体看样例。所谓的回文子序列，就是指子序列的字符串从前往后读和从后往前读是一样的。
输入
一个字符串S，长度不超过100，全部有大写英文字母构成。
输出
一个整数。
样例输入输出
提示
【样例2解释】
共5个不同的回文子序列："A"、"B"、"A"、"AA"、"ABA"。第1个"A"和第3个"A"是不同的子序列，因为位置不同。
【样例解释3】
除了空串不行，其他的子序列都可以，2^3-1=7。