C++ || Combinatorics under modular arithmetic
Intuition\nWe can find the number of permutations for each word in the string. \nLet\'s consider the first example:\n\n\ns = "too hot"\n\n\nLet\'s find the numb
# Intuition\nWe can find the number of permutations for each word in the string. \nLet\'s consider the first example:\n\n```\ns = "too hot"\n```\n\n**Let\'s find the number of permutations of the first word**\n\nIf we were given 3 distinct characters and asked to find the number of permutations, we can use the factorial to achieve that. So we would have 3! = 6 permutations. \n\nNow what if 2 of them are the same characters. As in our first word <code>too</code>. Let\'s just think about the permutations that are made of the same two characters <code>\'o\'</code>. Well, we have 2! = 2 permutations. Namely, \'oo\' and \'oo\'. As you can see these permutations are not distinguishable, meaning that they are all the same. So in reality, we can make only one permutation out of these two characters. For our word <code>too</code>, we have 3! = 6 permutations in which we have the indistinguishable permutations of the letter <code>\'o\'</code>. So we have to get rid of them. \n\nIn general, if we have a sequence of objects of size n and we have a1 of object 1 and a2 of object 2 and ... a_n of object n where a1 + a2 + ... + a_n = n, then the permutations are calculated as follows.\n\n```\nP = (n!) / (a1! * a2! * ... * a_n!)\n```\n\nSince the answer might get very large, we have to do our calculations under modulo operation. We need to use **modular inverse** for division. You can read about it [here](https://cp-algorithms.com/algebra/module-inverse.html), [here](https://codeforces.com/blog/entry/78873). \n\n\n# Code\n```\n#define vv std::vector\n#define ll long long\n\nconst int N = 1e5;\nconst int MOD = 1e9 + 7;\nll fact[N + 1];\n\nvoid precalcFact()\n{\n    fact[0] = 1;\n    fact[1] = 1;\n    for (int i = 2; i <= N; i++)\n    {\n        fact[i] = (fact[i - 1] * i) % MOD;\n    }\n}\n\nll powmod(ll a, ll b, ll p)\n{\n    a %= p;\n    if (a == 0)\n        return 0;\n    ll prod = 1;\n    while (b > 0)\n    {\n        if (b & 1)\n        {\n            prod = (prod * a) % p;\n            --b;\n        }\n        a = (a * a) % p;\n        b >>=1;\n    }\n    return prod;\n}\n\nll inv(ll a, ll p)\n{\n    return powmod(a, p - 2, p);\n}\n\nll denominator(vv<int> &vals)\n{\n    ll res = 1;\n    for (ll i : vals)\n    {\n        res = (res * inv(fact[i], MOD)) % MOD;\n    }\n\n    return res;\n}\n\n\nclass Solution {\npublic:\n    int countAnagrams(string s) {\n\n        precalcFact();\n        ll ans = 1;\n        int i = 0;\n        int len = s.length();\n        while (i < len)\n        {\n            vv<int> cnts(26);\n            int cnt = 0;\n            while (i < len && s[i] != \' \')\n            {\n                cnts[s[i] - \'a\']++;\n                cnt++;\n                i++;\n            }\n            ll x = (fact[cnt] * denominator(cnts)) % MOD;\n            ans = (ans * x) % MOD;\n            i++;\n        }\n\n        return ans;\n    }\n};\n```
['C++']