回文子序列种类数

给出一个字符串s,s的长度为n<=1e3,求 s有多少个不同的回文子序列

给输出的答案取模 1e9+7 

例如 aa 一共有3个回文子序列 a,aa {}空子序列   答案就是 3%(1000000007)==3 

单组数据，仅包含一行，代表输入的字符串。建议使用scanf().否则可能读到多余的\r

输出一个整数代表结果

abba

7
hint：
空串
a
aa
aba
abba
b
bb