C++ || FACTORIAL AND THEIR INVERSE (Mathematics) (Easy to Understand)
Explanation:\nAns is multiplication of nos of different permutations of all words in the given string\n\nExample:\n\nsuppose the given string is "abc bcd ffa"\n
Explanation:\nAns is multiplication of nos of different permutations of all words in the given string\n\nExample:\n\nsuppose the given string is "abc bcd ffa"\nwe can write abc in 6 ways\nbcd in 6 ways\nsimilarly ffa in 3 ways (ffa,faf,aff)\ntotal no of different strings that can be produced\nwe have 3 positions\n"___ ___ ___"\nTotal 6 * 6 * 3 ways (Fundamental Principle of Counting) or can say observation.\n\nTo find individual way of writing a word we can do\nFactorial of length of that word divide by\n(Multiplication of factorial of count of [\'a\',\'z\'] in that word).\n\nBut here factorials value are large so we can\'t perform divide instead we can multiply with their inverse.\n\nHope You understand the solutoin.\nFor clarification comment down.\n\n**Complexity**\n\n**Time complexity:** O(logn+n+(no of words*(length of word + 26)) )\n**Space complexity:** O(n)\n\n**Code**\n```\n\n\n\nclass Solution\n{\npublic:\n#define ll long long\n    const int mod = 1e9 + 7;\n\n    vector<ll> fact, invfact;\n\n    ll binpow(ll a, ll b, ll p)\n    {\n        ll res = 1;\n        a %= p;\n        while (b)\n        {\n            if (b & 1)\n                res = (res * a) % p;\n            a = (a * a) % p;\n            b >>= 1;\n        }\n        return res;\n    }\n\n    void precompute()\n    {\n        ll n = 100000;\n\n        fact.resize(n + 1);\n        invfact.resize(n + 1);\n\n        fact[0] = 1;\n        for (int i = 1; i <= n; ++i)\n            fact[i] = (fact[i - 1] * i) % mod;\n\n        invfact[n] = binpow(fact[n], mod - 2, mod);\n        for (int i = n - 1; i >= 0; --i)\n            invfact[i] = (invfact[i + 1] * (i + 1)) % mod; // computing all factorial inverses in O(N)\n    }\n\n    int countAnagrams(string s)\n    {\n        precompute();\n        vector<string> S;\n        stringstream ss(s);\n        string SS;\n        while (ss >> SS)\n            S.push_back(SS); // Getting all words from the main string ( we can do normal for loop also)\n        int ans = 1;\n        for (auto x : S)\n        {\n            ans = (ans * fact[x.size()]) % mod;\n            map<char, int> mp;\n            for (auto y : x)\n                mp[y]++;\n            for (auto counts : mp)\n                ans = (ans * invfact[counts.second]) % mod;\n\n        }\n\n        return ans;\n    }\n};\n```
['Math', 'String', 'Combinatorics']