# 描述

As we all known, xiaoxin is a brilliant coder. He knew palindromic strings when he was only a six grade student at elementry school.

This summer he was working at Tencent as an intern. One day his leader came to ask xiaoxin for help. His leader gave him a string and he wanted xiaoxin to generate palindromic strings for him. Once xiaoxin generates a different palindromic string, his leader will give him a watermelon candy. The problem is how many candies xiaoxin’s leader needs to buy?

## Input

This problem has multi test cases. First line contains a single integer T(T≤20) which represents the number of test cases.
For each test case, there is a single line containing a string S(1≤length(S)≤1,000).

## Output

For each test case, print an integer which is the number of watermelon candies xiaoxin’s leader needs to buy after mod 1,000,000,007.

• intput

• output

# 思路

• 其实这道题难点不是推出公式，而是求解公式(吐血.jpg)。
• 设字符串为s,字符串长度为Len,字母i出现次数的二分之一为c[i](取整);
• 如果有解，就要求出现次数是奇数的字母不超过1个(废话)，然后我们只需要考虑一边的所有情况，另一边跟它一样就能构成回文序列。只考虑一边时，共有Len/2个字符,根据高中学的排列组合可知，所有的排列情况是
• 关键就是如何求解这个公式了，由题目可知，Len/2最大是500，也就是要算500!，很明显要爆精度。因为答案对(1e9+7)取摸，这里引入一个转化：
(a$\times$b)%m $\rightarrow$ (a%m $\times$ b%m )%m 显然正确,所以我们求阶乘的时候只要边乘边对(1e9+7)取模就不会爆精度。
但是 (a $\div$ b)%m $\not=$ ((a%m) $\div$ (b%m))%m,所以我们要用逆元变除法为乘法，就可以边乘边取模。
• 这道题我是用的拓展欧几里德算法求逆元，不知道的可以看我的另一篇博客数论笔记本

# 代码

-------------本文结束 感谢您的阅读-------------