Fermat's Little Theorem || P&C
Intuition\nThis problem can be simply treated as basic P&C type of qs.We have to just calculate all the possible premutations of each word and multiply them.Onl
# Intuition\nThis problem can be simply treated as basic P&C type of qs.We have to just calculate all the possible premutations of each word and multiply them.Only thing we have to consider is that the calculation of permutations of words with duplicate letters.\nFor eg - aabb -> fact(4)/fact(2)*fact(2)\n\n# Approach\nHere the constraints while taking factorial and multiplying stuff can lead to overflow case so we have to use/apply modular arithmetic.Another thing which makes this qs interesting is (a/b)%M.In order to calculate this we should be aware of Fermat\'s little theorem in order to calculate modular multiplicative inverse(MMI).We have to calculate MMI of denominator stuff and then perform modulo as mod_mul(num,MMI(den)).For clear understanding of MMI you can refer youtube videos and GFG articles.\n\n# Complexity\n- Time complexity:\nIt can be said to be O(N)\nMMI calculation needs binary exponentiation which takes log(n) time(base 2).\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nconst int M = 1e9+7;\n#define ll long long\nclass Solution {\npublic:\nll mod_add(ll a,ll b,ll mod=M){\n\treturn (a%mod + b%mod)%mod;\n}\nll mod_sub(ll a,ll b,ll mod=M){\n\treturn (a%mod - b%mod + mod)%mod;\n}\nll mod_mul(ll a,ll b,ll mod=M){\n\treturn ((a%mod) * (b%mod))%mod;\n}\nll binaryExpo(ll a,ll b){\n\tll ans = 1;\n\twhile(b){\n\t\tif(b&1){\n\t\t\tans = mod_mul(ans,a,M);\n\t\t}\n\t\ta = mod_mul(a,a,M);\n\t\tb >>= 1;\n\t}\n\treturn ans;\n}\nll MMI(ll n){\n\treturn binaryExpo(n,M-2); //Using Fermats Little Thm\n}\n    int countAnagrams(string s) {\n        vector<string>words;\n        string temp;\n        int ans = 1;\n        int i = 0;\n        int n = s.length();\n        int maxi = INT_MIN;\n        while(1){\n            if(i==n) break;\n            if(s[i] == \' \'){\n                words.push_back(temp);\n                int n = temp.size();\n                maxi = max(maxi,n);\n                temp = "";\n                i++;\n                continue;\n            }\n            temp.push_back(s[i]);\n            i++;\n        }\n        if(temp != ""){\n            int n = temp.size();\n            maxi = max(maxi,n);\n            words.push_back(temp);\n        }\n        vector<ll>fact(maxi+1,0);\n\t    fact[0] = fact[1] = 1;\n        for(ll i = 2;i<=maxi;++i){\n            fact[i] = mod_mul(fact[i-1],i,M);\n        }\n        for(auto it:words){\n            unordered_map<char,int>mpp;\n            for(auto it1:it){\n                mpp[it1]++;\n            }\n            ll num = fact[it.size()];\n            ll den = 1;\n            for(auto x:mpp){\n                den = mod_mul(den,fact[x.second]);\n            }\n            ll mmi = MMI(den);\n            ans = mod_mul(ans,mod_mul(num,mmi));\n        }\n        // for(auto it:s){\n        //     if(it == \' \'){\n        //         words.push_back(temp);\n        //         temp = "";\n        //         continue;\n        //     }\n        //     temp.push_back(it);\n        // }\n        // for(auto it:words) cout<<it<<" ";\n        return ans;\n    }\n};\n```
['C++']