Sorted Permutation Rank with Repeats

• Time : O(|A|log(mod))
• Space : O(|A|)

long long modpow(long long n, long long x, long long mod) {
    if(x == 0) return 1;
    long long res = modpow(n,x>>1,mod);
    res = (res * res) % mod;
    if(x & 1) res = (res * n) % mod;
    return res;
}

int Solution::findRank(string A) {
    vector<long long> freq(300);
    vector<long long> fact {1};
    long long mod = 1000003;
    for(int i = 0; i < A.length(); i++) {
        freq[A[i]]++;
        fact.push_back(fact.back() * (i + 1) % mod);
    }
    
    long long res = 1;
    for(int i = 0; i < A.length(); i++) {
        long long cnt = 0, d = 1;
        for(int j = 0; j < A[i]; j++) cnt += freq[j];
        for(int j = 0; j < 300; j++) d = d * fact[freq[j]] % mod;
        long long p = modpow(d,mod - 2,mod);
        res = (res + cnt * fact[A.length() - i - 1] % mod * p % mod) % mod;
        freq[A[i]]--;
    }
    return res;
}