IMP:Rank The Permutations

#include <bits/stdc++.h>
using namespace std;
long long int f[16];
void fact(){
    f[0]=1;
    for(int i=1;i<=15;i++){
        f[i]=i*f[i-1];
        f[i]%=1000003;
    }
}
int main() {
    long long int t,cnt;
    cin>>t;
    fact();
    while(t--){
        string s;
        cin>>s;
        set<char>set(s.begin(),s.end());
        int l=s.length(),a[l];
        if(set.size()!=l){
            cout<<0<<endl;
            continue;
        }
        for(int i=0;i<l;i++){
            cnt=0;
            for(int j=i+1;j<l;j++){
                if(s[i]>s[j])cnt++;
            }
            a[i]=cnt;
        }
        cnt=1;
        for(int i=0;i<l;i++){
            cnt+=a[i]*f[l-i-1];
            cnt%=1000003;
        }
        cout<<cnt<<endl;
    }
    return 0;
}