Fermat Little Theorem , Anagrams

/*
https://leetcode.com/problems/count-anagrams/

You are given a string s containing one or more words. Every consecutive pair of words is separated by a single space ' '.

A string t is an anagram of string s if the ith word of t is a permutation of the ith word of s.

For example, "acb dfe" is an anagram of "abc def", but "def cab" and "adc bef" are not.
Return the number of distinct anagrams of s. Since the answer may be very large, return it modulo 109 + 7.



Example 1:

Input: s = "too hot"
Output: 18
Explanation: Some of the anagrams of the given string are "too hot", "oot hot", "oto toh", "too toh", and "too oht".
Example 2:

Input: s = "aa"
Output: 1
Explanation: There is only one anagram possible for the given string.


Constraints:

1 <= s.length <= 10^5
s consists of lowercase English letters and spaces ' '.
There is single space between consecutive words.
*/

class Solution {
public:
    int MOD=1000000007;
    int dp[100001];

    long long int binaryExponentiation(long long int x, int pow){
        long long int res=1;
        while(pow>0){
            if(pow%2==0){
                x=(x*x)%MOD;
                pow/=2;
            }
            else{
                res=(res*x)%MOD;
                pow--;
            }
        }
        return res;
    }

    long long int factorial(int n){
        if(n==1){
            return 1;
        }
        if(dp[n]!=-1){
            return dp[n];
        }
        return dp[n]=(n*factorial(n-1))%MOD;
    }

    long long int Arrangements(vector<int> &freq){
        int n=accumulate(freq.begin(),freq.end(),0);
        long long int total=factorial(n);
        for(int i=0;i<26;i++){
            if(freq[i]==0){
                continue;
            }
            long long int Fx=factorial(freq[i]);
            total=(total*binaryExponentiation(Fx,MOD-2))%MOD;
        }
        return total;
    }

    int countAnagrams(string s) {
        memset(dp,-1,sizeof(dp));
        int n=s.size();
        long long int res=1;
        for(int i=0;i<n;i++){
            vector<int> freq(26,0);
            while(i<n && s[i]!=' '){
                freq[s[i]-'a']++;
                i++;
            }
            res=(res*Arrangements(freq))%MOD;
        }
        return res;
    }
};


/*
THOUGHT PROCESS-

Some important concepts links-
https://drive.google.com/file/d/1ER7_yAp9u_nmcYGRRTnJVQFxVMojVwj4/view?usp=sharing
https://drive.google.com/file/d/1-OfhISGw5tP7w7PsShR6WlTMM-i5X2Lq/view?usp=sharing

See, it is quite simple, you can easily find the total number of ways simply by multiplying the total distinct anagrams of each word.
So in short, it is like
long long res=1;
for(int i=0;i<words.size();i++){  res=res * arrangements(word);  }

The real problem though, is not in just solving. But rather handling the modulo and power raised to a number.

Please go through the above google drive links before proceeding furthur.

So by now, you have realized getting the answer of a factorial is not that difficult, as we do simple MOD while multiplying, but remember since you do modulo operation, the general laws of division would not apply here because you are using modulo and modulo changes the actual answer if overflowing. So, simple a/b would not work and a is not correct a!, but (a! % mod), same goes for b!, and dividing these will result in wrong answer, and that is why to overcome this issue we use inverse factorial AKA FERMAT LITTLE THEOREM. And since fermat theorem needs us to do base-power calculation, so to speed it up, we use binary exponentiation
*/