题目链接http://acm.hdu.edu.cn/showproblem.php?pid=5651
题目意思我看了半天没读懂，一直以为是回文子串又没看见substring的单词最后看博客才知道是用给出的字符任意组合。
求不同的回文串个数，显然对于一个长度为奇数的串，我们可以枚举中间位置的元素，然后计算由剩余字符对半分(如果不可以就是零)之后的
排列数就好了，由于有重复字符排列数公式也会不同，偶数串的话直接计算一次就好了。
假设串长度为n，有m种不同元素，每种有ai个，则排列数就是 n！/(a1!*a2!*a3!*......am!)
接着讨论具体计算过程，
对于solve()，就是计算在当前合法状态下，对半分之后的排列总数对mod取余，公式就是
len!/(a1!*a2!*a3!......*am!)%mod,由于阶乘值会很大所以只能用同余公式和逆元进行化简，
==> (1%mod*2%mod*....*len%mod)%mod*(1/a1!)%mod*(1/a2!)*......*(1/am!)%mod //我们用fac[i]表示阶乘取模，prv[i]表示i！的逆对mod取模
//对于1/x!%mod<==>1*(1/2)%mod*(1/3)%mod*...(1/x)%mod<==> 2-1%mod*3-1%mod......*x-1%mod
==>fac[i]*prv[a1]*prv[a2]*.....*prv[am]%mod;
#include<bits/stdc++.h>
using namespace std;
#define LL long long
LL mod=1e9+;
LL a[];
LL fac[]={};
LL inv[]={,};
LL prv[]={,};
LL solve(int len)
{
int i,j,k;
LL res=fac[len];
for(i=;i<;++i)
{
if(a[i]&) return ;
a[i]/=;
res=res*prv[a[i]]%mod;
a[i]*=;
}
return res;
}
int main()
{
int t,i,j,n,m;
char str[];
for(LL i=;i<=;++i) fac[i]=fac[i-]*i%mod;
for(i=;i<=;++i) {
inv[i]=(mod-mod/i)*inv[mod%i]%mod;
prv[i]=prv[i-]*inv[i]%mod;
}
cin>>t;
while(t--){memset(a,,sizeof(a));
scanf("%s",str);
int len=strlen(str);
for(i=;i<len;++i){
a[str[i]-'a']++;
}LL ans=;
if(len&){
for(i=;i<;++i){
if(!a[i]) continue;
a[i]--;
ans=(ans+solve((len-)/))%mod;
a[i]++;
}
}
else{
ans=solve(len/);
}
cout<<ans<<endl;
}
return ;
}