时间限制：0.5秒　　内存限制：256M

---

【问题描述】

　　给定字符串 \(S\)，求它的回文子序列个数。内容相同位置不同的子序列算不同的子序列。例如字符串aba中，回文子序列为"a", "a", "aa", "b", "aba"，共5个。

【输入格式】

　　第一行包含一个整数 \(T\)，即数据组数。接下来的 \(T\) 行，每行是一个仅含英文字母且长度不超过1000的字符串。

【输出格式】

　　对每组数据，输出结果对 10007 取余。

【输入输出样例】

　Input

4
a
aaaaa
goodafternooneveryone
welcometoooxxourproblems

　Output

1
31
421
960

【数据限制】

　　100%的数据满足：\(1≤T≤50\)。

【来源】

　　Mr.he