题目描述

给你一个长度为 $N(N \le 1000)$ 的字符串，请你输出它所有的回文子序列的数量对10007取模的结果。

只要从字符串 $s$ 中顺序地取出一些字符（不要求连续，可以是 $s$ 本身，不能是空串），不改变他们的顺序的情况下，这个子序列是一个回文串，那么他就是一个 $s$ 的回文子序列。

输入格式

首先是一个数 $T(T \le 50)$，表示测试用例的数量。
接下来 $T$ 行，每行包含一个字符串长度不超过 $1000$ 的字符串（数据保证字符串中只包含小写英文字母）。

输出格式

对于每一个字符串，你需要输出它的回文子序列数量，输出格式要和样例输出一样（由于数据量可能会比较大，所以结果需要对 $10007$ 取模）。

4
a
aaaaa
goodafternooneveryone
welcometoooxxourproblems

Case 1: 1
Case 2: 31
Case 3: 421
Case 4: 960