[Python] Linear-time Modular Inverse 3-liner in with Explanation, The Best
Intuition\nThe number of permutations of word w with possible letter repetitions is given by C_w = \dfrac{n_w!}{\prod_{c\in w} n_c!}, where n_c are counts of ea
# Intuition\nThe number of permutations of word $$w$$ with possible letter repetitions is given by $$C_w = \\dfrac{n_w!}{\\prod_{c\\in w} n_c!}$$, where $$n_c$$ are counts of each letter $$c \\in w$$. We need to compute $$\\prod_{w\\in s} C_w$$ for words $$w\\in s$$.\n\nThus, the final result is $$\\prod_{w\\in s} \\dfrac{n_w!}{\\prod_{c\\in w} n_c!} \\bmod M$$, where $$M = 10^9+7$$, a prime number.\n\n# Approach\nThe result must be computed in $$\\mathbb{Z}_M$$. Also note that computing the full $$n! \\in \\mathbb{Z}$$ may take too long. We can therefore compute numerator and denominator parts of the result separately in $$\\mathbb{Z}_M$$ and then divide them in $$\\mathbb{Z}_M$$ by computing the modular inverse of the denominator, which is possible since $$M$$ is prime.\n\nThe Best!\n\n# Complexity\n- Time complexity: $$O(\\lvert s\\rvert)$$\n- Space complexity: $$O(\\lvert s\\rvert)$$ due to word splitting, can be reduced to $$O(1)$$ by manually parsing $$s$$\n\n# Code\n```python\ndef countAnagrams(self, s: str) -> int:\n    words, M, mul, fact = s.split(), 1000000007, lambda a, b: a*b % M, lambda n: functools.reduce(mul, range(2, n+1), 1)\n    denom = functools.reduce(mul, (fact(count) for w in words for count in collections.Counter(w).values()), 1)\n    return mul(functools.reduce(lambda t, w: mul(t, fact(len(w))), words, 1), pow(denom, -1, M))\n```\n\nFor comparison, here is a solution in imperative style:\n```python\ndef countAnagrams(self, s: str) -> int:\n    def fact(n):\n        product = 1\n        for num in range(2, n + 1):\n            product = (product * num) % M\n        return product\n\n    M = 1000000007\n    numerator, denominator = 1, 1\n\n    for word in s.split():\n        numerator = (numerator * fact(len(word))) % M\n        for count in collections.Counter(word).values():\n            denominator = (denominator * fact(count)) % M\n\n    return (numerator * pow(denominator, -1, M)) % M\n```
['Python3']