[C++] Division with prime modulo 10^9+7 Solution Explained.
Formula for factorial\n4! = 1 x 2 x 3 x 4\n\nFormula for permutations.\nFor permutations of "cccbhbq", "c" is repeated 3 times and "b" is repeated 2 times. Ther
**Formula for factorial**\n4! = `1 x 2 x 3 x 4`\n\n**Formula for permutations.**\nFor permutations of "cccbhbq", "c" is repeated 3 times and "b" is repeated 2 times. There are 7 total characters. Therefore, calculation for the permutations is `7! / (3! * 2!)`.\n\n**For dividing with prime modulo:**\n`a / b` == `a * b^(-1)`\n`b^(-1) mod m` == `b^(modulo - 2)` \n\n**Time complexity**\nO(N log N). Loop through each character in the string thus `O(N)`. For every word, there is a `O(log N)` calculation of denominator to the power of `mod-2`.\n```\nclass Solution {\npublic:\n    int mod = 1000000007;\n    int countAnagrams(string s) {\n\t\t// preprocess factorial calculations\n\t\tvector<long> factorial {1};\n        for (int i = 1; i <100004; ++i) {\n            long curr = (factorial[factorial.size()-1] * i);\n            curr %= mod;\n            factorial.push_back(curr);\n        }\n\t\t\n        vector<int> freq(26); \n        int prev = 0;\n        long permutations = 1;\n        for (int i = 0; i <= s.size(); ++i) {\n            if (i != s.size() && s[i] != \' \') {\n                freq[s[i]-\'a\']++;\n            } else {\n\t\t\t\t// calculate according to permutation formula\n                long num = factorial[i-prev];\n                long denom = 1;\n                for (long val : freq) { // multiply factorial of repeated characters to denominator\n                    if (val <= 1) continue;\n                    denom *= factorial[val];\n                    denom %= mod;\n                }\n                permutations *= (num * (fastpow(denom, mod-2) % mod)) % mod;\n                permutations %= mod;\n                \n\t\t\t\t// reset hash map and previous index\n                freq.assign(26, 0);\n                prev = i+1;\n            }\n        }\n        \n        return permutations;\n    }\n    \n\t// fast pow function i found online o(logn)\n    long long fastpow(long long b, long long ex){\n        if (b==1)return 1;\n        long long r = 1;\n        while (ex ){\n            if (ex&1)r=(r * b)%mod;\n            ex = ex >> 1;\n            b = (b * b)%mod;}\n        return r;\n    }\n};\n```
[]