public class Solution { public int findRank(String A) { int p = 1000003, n = A.length(); long ans = 1L; //storing fact values in array long factModArray[] = factMod(n); // storing inv mod fact values in array long factInverseModArray[] = factInvMod(n); //frequency array int[] freqArray = findingFreqArray(A); for(int i = 0; i < n; i++){ int idx = (A.charAt(i) < 91) ? A.charAt(i) - 65 : A.charAt(i) - 71; long num = 1, dem = 1, temp = 0L; for(int j = 0; j < idx; j++){ num = factModArray[n - i - 1]; for(int k = 0; k < idx; k++){ if(freqArray[k]>1){ if(j == k) dem = (dem % p * factInverseModArray[freqArray[k] - 1]) % p; else dem = (dem % p * factInverseModArray[freqArray[k]]) % p; } } // System.out.println( idx * dem > 1L); temp = (num * dem)%p; } System.out.println(i+" "+ans+" "+num+" "+dem); ans = (ans % p + temp) % p; freqArray[idx]--; } return (int)(ans % p); } public int[] findingFreqArray(String A){ int[] output = new int[52]; for(int i = 0; i < n; i++){ if(A.charAt(i) < 91) output[A.charAt(i)-65]++; else output[A.charAt(i)-71]++; } return output; } public long[] factInvMod(int n){ long[] output = new long[n]; for(int i = 0; i < n; i++){ output[i] = powerMod(i, 1000001, 1000003); } return output; } public long powerMod(long A, int n, int p ){ if(n == 0 ) return 1; long temp = powerMOd(A, n/2, p); if((n & 1) == 1) return (temp % p * temp % p * A % p)% p; return (temp % P * temp % p) % p; } public long[] factMod(int n){ int p = 1000003; long[] output = new long[n]; output[0] = 1L; for(int i = 1; i < n; i++ ){ output[i] = (output[i-1] % p * i % p ) % p; } return output; } }