Anagrame5

/*
    Soltuie oficiala:
        Autor: Iacob Tudor.
        Complexitate: O(n+sigma)
        Punctaj: 100p
    Aceasta problema a fost gandita
    ca a doua problema din concursul
    infoleague etapa 1 dar a fost
    inlocuita.
*/
#include<bits/stdc++.h>
using namespace std;
ifstream fin("window.in");
ofstream fout("window.out");
const long long mod=666013;
long long fs[50],ft[50],r,f[100005],inv[100005],invf[100005];
char s[100005],t[100005];

//calculeaza Combinari de n luate cate k in O(1).
long long c(long long n,long long k){
    return (((f[n]*invf[k])%mod)*invf[n-k])%mod;
}

int main(){

    //dam precompte: f[i] - factorialul lui i sub modul mod
    //               inv[i] - inversul lui i sub modul mod.
    //               invf[i] inversul factorialului lui i sub modul mod.
    f[0]=f[1]=inv[0]=inv[1]=invf[0]=invf[1]=1;
    for(long long i=2;i<=100001;i++){
        f[i]=(i*f[i-1])%mod;
        inv[i]=(inv[mod%i]*(mod-mod/i))%mod;
        invf[i]=(inv[i]*invf[i-1])%mod;
    }

    cin>>s>>t;

    //calculam frecventa fiecarui caracter.
    r=1;
    long long ns(strlen(s)),nt(strlen(t));
    for(long long i=0;i<ns;i++)fs[(long long)s[i]-96]++;
    for(long long i=0;i<nt;i++)ft[(long long)t[i]-96]++;

    //iteram prin toate caracterele si calculam combinarile.
    for(long long i=1;i<=26;i++){
        if(ft[i]>fs[i]){
            cout<<0;
            return 0;
        }
        r*=c(fs[i],ft[i]);
        r%=mod;
    }

    cout<<r;
    return 0;
}