Easy C++ || Fermat's Theorem || O(n*log(10^9))
Intuition\n Describe your first thoughts on how to solve this problem. \nFermat\'s Theorem + factorial\n\n# Approach\n Describe your approach to solving the pro
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nFermat\'s Theorem + factorial\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nFor every word, count no of distinct chars and equal chars freq(using HashMap), now use concept of permutations for every word and keep on multiplying res into "ans"\ne.g for word = "abbscs", res = 6!/(2!*2!) => 6! * $$(2!)^i$$*$$(2!)^i$$\nwhere i = -1 and inv(n) = modular inverse of n w.r.t p can be calculated using Fermat\'s Theorem:\ninv(n, p) = pow(n, p-2)%p\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(n*log(10^9))$$\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(n)$$ where n = size of fact array $$(10^5)$$\n\n# Code\n```\n#define ll long long\n#define mod 1000000007\n\nclass Solution {\npublic:\n    \n    ll bin_pow(ll a, ll n){\n        ll res = 1;\n        while(n > 0){\n            if(n&1)\n                res = (res*a)%mod;\n            \n            a = (a*a)%mod;\n            n = n>>1;\n        }\n        \n        return res;\n    }\n    \n//     ll fun(ll n, ll r){\n        \n//     }\n    \n    int countAnagrams(string s) {\n        int i, j;\n        int n = s.length();\n        int sz = 100000;\n        ll fact[sz+1];\n        fact[0] = 1;\n        \n        for(ll ind=1; ind <= sz; ind++){\n            fact[ind] = (fact[ind-1]*ind)%mod;\n        }\n        \n        ll ans = 1;\n        \n        i = 0;\n        while(i < n){\n            unordered_map<char, int> m;\n            \n            ll count = 0;\n            \n            while(i < n && s[i] != \' \'){\n                count++;\n                m[s[i]]++;\n                i++;\n            }\n            \n            ll N = fact[count];\n            \n            ll r = 1;\n            for(auto it:m){\n                r = (r*fact[it.second])%mod;\n            }\n            \n            ll val = (N*bin_pow(r, mod-2))%mod;\n            ans = (ans*val)%mod;\n            \n            i++;\n        }\n        \n        return ans;\n        \n        \n    }\n};\n```
['Math', 'Prefix Sum', 'C++']