C++ | Easy Approach after learning Binary Exponentiation and Modular Multiplicative Inverse
Intuition\n    Total number of permutations of a word without duplicate letters Formula: N!\n\n    Total number of permutations of a word with duplicate letters
# Intuition\n    Total number of permutations of a word without duplicate letters Formula: N!\n\n    Total number of permutations of a word with duplicate letters Formula: N! / ma! * mb! * .... * mz! where N is the total number of letters and ma, mb are the occurrences of repetitive letters in the word\n\n# Approach\n    Next (a / b) % mod will not be equal to (a % mod) / (b % mod) as it is large number we tend to take mod for every multiplication we do and we cannot calculate the final a / b to arrive at total permutations. So we make use of Modular Multiplicative Inverse\n    \n    (a / b) % mod != (a % mod) / (b % mod)\n    By applying Fermat\'s Little Theorem\n    By Conclusion we have\n    (a / b) % mod = a * (b ^ -1) % mod\n    (b ^ -1) % mod = b ^ (mod - 2) --> O(N)\n\n    But now the Time Complexity if O(N * N) which is quadratic\n    So to reduce we can use Binary Exponentiation which is O(logN)\n\n# Complexity\n- Time complexity:\n    # O(NlogN)\n\n- Space complexity:\n    # O(N)\n\n# Code\n```\nclass Solution {\nprivate:\n    const int mod = 1e9 + 7;\n    long long fact[100005];\n\n    void factorial(int n) {\n        fact[0] = 1;\n        for(int i = 1;i <= n;i++) {\n            fact[i] = (fact[i - 1] * i) % mod;\n        }\n    }\n    \n    long long getFactorial(long long n) {\n        return fact[n];\n    }\n\n    long long binExp(long long a, long long b) {\n        long long res = 1;\n        while(b) {\n            if(b & 1) {  // set bit \n                res = (res * a) % mod;\n            }\n            a = (a * a) % mod;\n            b >>= 1;\n        }\n        return res;\n    }\n\n    long long modMul(long long a, long long b) {\n        return ((a % mod) * (b % mod)) % mod;\n    }\n\n    long long getPermuation(string &word) {\n        int mp[26] = {0};\n        long long pro = 1;\n        long long n = word.size();\n\n        for(auto &ch : word) {\n            mp[ch - \'a\']++;\n        }\n        \n        long long totalFact = getFactorial(n);\n        long long fact;\n\n        for(int i = 0;i < 26;i++) {\n            if(mp[i] > 0) {\n                fact = getFactorial(mp[i]);\n                pro = (pro * fact) % mod;\n            }\n        }\n\n        long long a = totalFact;\n        long long b = binExp(pro, mod - 2);\n\n        return modMul(a, b);\n    }\npublic:\n    int countAnagrams(string s) {\n        long long total = 1;\n        int n = s.size();\n        factorial(n);\n\n        stringstream ss(s);\n        string word;\n\n        while(getline(ss, word, \' \')) {\n            total = (total * getPermuation(word)) % mod;\n        }\n\n        return total % mod;\n    }\n};\n```
['C++']