HDU 5651 xiaoxin juju needs help組合せ

xiaoxin juju needs help
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 293    Accepted Submission(s): 87
Problem Description
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 .
 
Sample Input

   
   
   
   

    
    
    
    3
aa
aabb
a
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    1
2
1
   
   
   
   

 
Source
BestCoder Round #77 (div.2)
 まず答えが0の場合、1より大きい文字の個数が奇数であれば、答えは0です.1つの文字の答えが1であれば、1つの文字の半分を取って並べるだけで、後ろの半分を補うだけで文が形成されるので、ポイントは配列の個数を求めることです.配列の個数は、実は重複する要素がある全配列の個数=tot!/(a!*b!*...*z!)、ここでa,b,.,zは対応する文字の個数の半分を表し、totも総和の半分を表す.過程は逆元を求める必要がある.

/****************
*PID:hdu5651
*Auth:Jonariguez
*****************
*/
#define lson k*2,l,m
#define rson k*2+1,m+1,r
#define rep(i,s,e) for(i=(s);i<=(e);i++)
#define For(j,s,e) For(j=(s);j<(e);j++)
#define sc(x) scanf("%d",&x)
#define In(x) scanf("%I64d",&x)
#define pf(x) printf("%d",x)
#define pfn(x) printf("%d
",(x))
#define Pf(x) printf("%I64d",(x))
#define Pfn(x) printf("%I64d
",(x))
#define Pc printf(" ")
#define PY puts("YES")
#define PN puts("NO")
#include <stdio.h>
#include <string.h>
#include <string>
#include <math.h>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
typedef long long Ll;
const int maxn=1000+10;
const int MOD=1e9+7;
Ll quick_pow(Ll a,Ll b){a%=MOD;Ll res=1;while(b){if(b&1)res=(res*a)%MOD;b/=2;a=(a*a)%MOD;}return res;}

char str[maxn];
int vis[30];
LL fact[maxn];

int main()
{
    int i,j,n,m,T;
    fact[0]=1;
    for(i=1;i<=1001;i++)
        fact[i]=(fact[i-1]*i)%MOD;  //     
    scanf("%d",&T);
    while(T--){
        scanf("%s",str+1);
        n=strlen(str+1);
        int f=0;
        memset(vis,0,sizeof(vis));
        for(i=1;i<=n;i++)
            vis[str[i]-'a']++;
        int cnt1=0;
        for(i=0;i<26;i++){
            if(vis[i]) cnt1++;
            if(vis[i]&1){
                if(f) break;
                f=i+1;
            }
        }
        if(i<26){
            puts("0");
            continue;
        }
        if(cnt1==1){
            puts("1");continue;
        }
        LL res=1;
        int cnt=0;
        for(i=0;i<26;i++){
            if(vis[i]){
                cnt+=(vis[i]/2);
            }
        }
        res=fact[cnt];
        for(i=0;i<26;i++){
            if(vis[i]){
                LL inv=quick_pow(fact[vis[i]/2],MOD-2); //          
                res=(res*inv)%MOD;
            }
        }
        printf("%I64d
",res);
    }
    return 0;
}