该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定一个字符串 S ，计算其不同的回文子序列个数，答案需对 1000000007 取模。

子序列的定义：由字符串中若干个不连续的字符按原有顺序组成的序列（例如“bdf”是“abcdefg”的子序列，“abc”是“abc”的子序列，但“abbc”“ca”均不是“abc”的子序列）。

回文子序列的定义：子序列的字符串从前往后读与从后往前读完全一致。

特别说明：即使两个子序列的字符串内容相同，只要它们在原字符串中的位置不同，也视为不同的子序列（具体见样例解释）。

输入格式

输入仅一行，为一个字符串 S 字符串仅由大写英文字母构成。 对于40%的数据 字符串长度小于10 对于100%的数据 字符串长度小于100

样例输入

ABA

样例输出

5

样例解释

该字符串共有 5 个不同的回文子序列，分别是：

1. 第1个位置的“A”
2. 第2个位置的“B”
3. 第3个位置的“A”
4. 第1和第3个位置组成的“AA”
5. 第1、2、3个位置组成的“ABA”

其中第1个“A”和第3个“A”因位置不同，视为两个不同的回文子序列。