C++ | Modular Inverse
Here the problem is quite straightforward, go through the observation points for intuition.\nObservations:\n1) Notice our permutation depends on every word of t
Here the problem is quite straightforward, go through the observation points for intuition.\nObservations:\n1) Notice our permutation depends on every word of the string i.e. string between two spaces.\n2) Spaces doesn\'t contribute to our final answer.\n3) Permutation of each word is the factorial of the number of charcters in that word divided by factorial of frequency of each character.\n\nEample - \n1) string - "too hot"\nanswer - (3! / (1! * 2!)) * (3! / (1! * 1! * 1!)) = 18\nExplanation - \na) "too" -  its length is 3 and here frequency of o is 2 and t is 1 so its contribution in final is (3! / (1! * 2!))\nb) "hot" - its length is 3 and here frequency of o is 1, h is 1 and t is 1 so its contribution in final is (3! / (1! * 1! * 1!))\n\n2) string - "aa"\nanswer - (2! / 2!) = 1\nExplanation - \n"aa" - its length is 2 and frequency of letter 2 is 2 so its contribution in final answer is (2! / 2!).\n\n3) string - "topppo hot"\nanswer - (6! / (1! * 2! * 3!)) * (3! / (1! * 1! * 1!)) = 360\nExplanation - \na) "topppo" -  its length is 6 and here frequency of o is 2, p is 3 and t is 1 so its contribution in final is (6! / (1! * 2! * 3!)).\nb) "hot" - its length is 3 and here frequency of o is 1, h is 1 and t is 1 so its contribution in final is (3! / (1! * 1! * 1!))\n\nNow you can observe the pattern here.\nIn this the most challenging part is to calculate mod of dividing the factorial as in the case of mod of dividing, doesn\'t yield the correct answer. So to come across this, modular inverse is used which is calculated using fermats little theorem. There are many good blogs present in internet for this theorem and modulo inverse, i recommend going through them for better understanding of the solution. I have linked them down below.\n\nModulo-Inverse - https://cp-algorithms.com/algebra/module-inverse.html\nCodeforces blog - https://codeforces.com/blog/entry/78873\n\nCode -\n```\nclass Solution {\n    long long mod = 1e9 + 7;\n    vector<long long> fact = vector<long long>(1e5 + 1);\n    long long binpow(long long a, long long b) {\n        long long res = 1; \n        a = a % mod;\n        while (b > 0) {\n            if (b & 1) res = res * a % mod; \n            a = a * a % mod; \n            b >>= 1;\n        } \n        return res;\n    }\n    long long inv(long long a) {\n        return binpow(a, mod - 2);\n    }\npublic:\n    // Constructor \n    Solution() {\n        int maxn = 1e5;\n        fact[0] = 1;\n        for(long long i = 1; i <= maxn; ++i) {\n            fact[i] = fact[i - 1] * i % mod;\n        }\n    }\n    int countAnagrams(string s) {\n        long long ans = 1;\n        int n = s.size();\n        for(int i = 0; i < n; ++i) {\n            vector<int> freq(26);\n            int ind = i;\n            while(ind < n && s[ind] != \' \') freq[s[ind++] - \'a\']++;\n            int len = ind - i;\n            long long perm = 1;\n            for(int i = 0; i < 26; ++i) {\n                perm = perm * inv(fact[freq[i]]) % mod;\n            }\n            ans = (ans * (fact[len] * perm % mod) % mod);\n            i = ind;\n        }\n        return ans;\n    }\n};\n```\n\nTC - O(100000) ```for calculating factorial``` +  O(n * 26 * log(mod)) ```for calculating inverse of each frequency```\nSC - O(100000) ```for storing factorial``` + O(26) ```for storing frequency```\n\nNote - TC can be further reduced to ->O(100000 log(mod) + O(n * 26) if we also precompute the inverse array.\n\n**Please upvote if it helps**
['C']