C++ Euclidean algorithm modular Inverse& Factorials||12ms beats 100%
Intuition\n Describe your first thoughts on how to solve this problem. \nReal math solution is solved by Number theoretical trick, Modular Inverse.\nLet $w$ den
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nReal math solution is solved by Number theoretical trick, Modular Inverse.\nLet $w$ denote a word  in the string `s` with length $len(w)$ & frequency table\nfreq(w)=$(w_{0}, w_1\\cdots w_{25})$\nThen the answer is\n$$\nans=\\Pi_{w\\in s}\\frac{len(w)!}{w_0!w_1!\\cdots w_{25}!}\\pmod{ p=10^9+7}\n$$\nwhere $x!$ ($x\\in N$) denotes the factorial, i.e. $x=x(x-1)\\cdots(2)1.$ & $0!=1$.\n# Approach\n<!-- Describe your approach to solving the problem. -->\nWhy this formula works? The valid anagram, say $\\sigma : s\\to t$ will keep the restriction $\\sigma|_w$ being also an anagram for each word $w$ in `s`.\n\nThe number of anagrams for the word $w$ is the total number of permutaions on $w$ (considering total $len(w)$ letters with $w_0$ a, $w_1$ b$\\cdots w_{25}$ z)which is \n$$\nn(w)=\\frac{len(w)!}{w_0!w_1!\\cdots w_{25}!}.\n$$\nAccording to the multiplicative principle for counting (combinatorics), the total number of valid anagrams is the product.\n\nThe factorial $x=w_i!$ in the denominator is not computed by the usual division, but by computing its modular Inverse $x^{-1}$ ($x\\times x^{-1}\\equiv 1\\pmod{p}$) by the Euclidean algorithm, for that the existence of the modular Inverse is quaranteed by the number $p=10^9+7$ being a prime.\n\nThe idea of applying Euclidean algorithm for finding the modular Inverse is also applied for other Leetcode problems:\n[2954. Count the Number of Infection Sequences](https://leetcode.com/problems/count-the-number-of-infection-sequences/solutions/4357894/c-extended-euclidean-algorithm-modular-power-combinatorics/)\n[2400. Number of Ways to Reach a Position After Exactly k Steps](https://leetcode.com/problems/number-of-ways-to-reach-a-position-after-exactly-k-steps/solutions/4263879/c-extended-euclidean-algorthm-for-modinverse0ms-beats-100/)\n[2906. Construct Product Matrix](https://leetcode.com/problems/construct-product-matrix/solutions/4170288/cmodular-inverse-modpow-vs-prefix-product-suffix-product/)\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# C++ Code 12ms beats 100%\n```\n#pragma GCC optimize("O3", "unroll-loops")\nstatic int mod=1e9+7;\nclass Solution {\npublic:\n    vector<long long> fact;\n    void factorialMod(int n){\n        fact.assign(n+1, 1);\n        for(int i=2; i<=n; i++){\n            fact[i]=fact[i-1]*i%mod;\n        }\n    }\n    // Find x, y, d such that ax + by = d where d = gcd(a, b)\n    int modInverse(int a, int b=mod) {//mod is prime d=1\n        int x0 = 1, x1 = 0;\n        int r0 = a, r1 = b;\n        while (r1 != 0) {\n            int q = r0/r1, rr = r1, xx = x1;\n            r1 = r0-q * r1;\n            x1 = x0-q * x1;\n            r0 = rr;\n            x0 = xx;\n        }\n        if (x0 < 0) x0+= b;\n        return x0;\n    }\n    long long computePerm(array<int, 26>& freq, int wlen){\n        long long ans=fact[wlen];\n        for(int f: freq){\n            if (f!=0){\n                ans=(ans*modInverse(fact[f]))%mod;\n            }\n        }\n        return ans%mod;\n    }\n    int countAnagrams(string& s) {\n        int n=s.size();\n        factorialMod(n);\n        long long ans=1;\n        array<int, 26> freq={0};\n        int wlen=0;\n        for (int i=0; i<n; i++){\n            while(i<n && s[i]!=\' \'){\n                freq[s[i]-\'a\']++;\n                wlen++;\n                i++;\n            }\n            ans=(ans*computePerm(freq, wlen))%mod;\n            if (i<n){\n                freq.fill(0);\n                wlen=0;\n            }\n        }\n        return ans%mod;\n    }\n};\n\nauto init = []()\n{ \n    ios::sync_with_stdio(0);\n    cin.tie(0);\n    cout.tie(0);\n    return \'c\';\n}();\n```
['Math', 'Combinatorics', 'Counting', 'Number Theory', 'C++']