xiaoxin巨从小就喜欢字符串，六年级的时候他就知道了什么是回文串。这时，xiaoxin巨说到：如果一个字符串 $S$ 是回文串，那么该字符串从前往后看和从后往前看是一样一样的。 六年级的暑假，xiaoxin很快就做完了暑假作业，然后到腾讯做起了实习生。这日，leader给了xiaoxin一个字符串，请xiaoxin帮忙写一个函数来生成所有可能的回文串，可以任意改变字符串的顺序但是不可以扔掉某个字符。并且leader告诉xiaoxin，每生成一个不一样的回文串就可以得到一颗西瓜糖。 请你帮忙计算xiaoxin的leader最多需要买多少颗西瓜糖呢？
多组测试数据。第一行包含一个整数 $T(T\leq 20)$ 表示组数。每组测试数据给出一个只包含小写字母的字符串 $S(1\leq length(S)\leq 1,000)$
对于每组测试数据，输出一个数, 表示leader需要买的西瓜糖的个数，结果对 $1,000,000,007$ 取模。
3 aa aabb a
1 2 1