Fast modulo of Pascal triangle || Python O(n) || WUCG
IntuitionLetnbe the number of digit ins.The first element was the digit given by the following∑k=0n−1​(nk​)int(s[k])And the second element was the digit given b
# Intuition

Let $n$ be the number of digit in `s`.

The first element was the digit given by the following $$
\sum_{k=0}^{n-1} \begin{pmatrix}n\\k\end{pmatrix}int(s[k])
$$

And the second element was the digit given by the following $$
\sum_{k=1}^n \begin{pmatrix}n\\k\end{pmatrix}int(s[k])
$$
<!-- Describe your first thoughts on how to solve this problem. -->

Remember that in modular arithmetic $(a\cdot b)\mod 10=(a\mod 10)\cdot (c\mod 10)$

# Approach
<!-- Describe your approach to solving the problem. -->

The key is to build modular of $$\begin{pmatrix}n\\k\end{pmatrix}\mod 10$$ quickly, here, we use the solution from 

[fast modulo](https://stackoverflow.com/questions/76357846/numbers-of-combinations-modulo-m-efficiently) 

to help us compute the desired result in $$O(n)$$

# Complexity
- Time complexity: $$O(n)$$ for the modulo
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: $$O(n)$$ for storing array and results
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```python3 []
class Solution:
    def hasSameDigits(self, s: str) -> bool:
        n=len(s)
        # generic approach for checking, no modular.
        # p = []
        # for k in range(n-2):
        #     p.append(p[k] * (n-2-k) // (k+1))

        # fast modulo: https://stackoverflow.com/questions/76357846/numbers-of-combinations-modulo-m-efficiently
        def fast(n, m):
            res=[1]
            c = 1
            G = 1
            for k in range(n):

                mul = n - k
                while (g := gcd(mul, m)) > 1:
                    mul //= g
                    G *= g

                div = k + 1
                while (g := gcd(div, m)) > 1:
                    div //= g
                    G //= g

                # build modular inverse use pow(div, -1, m)
                c = c * mul * pow(div, -1, m) % m
                res.append(c * G % m)
            return res
        p = fast(n-2, 10)
        # print(p)
        a,b=0,0
        for i,e in enumerate(s[:n-1]):
            # print(min(i+1,n-i-1),i+1,n-i-1)
            a=(a+int(e)*p[i])%10
        for i,e in enumerate(s[1:]):
            b=(b+int(e)*p[i])%10
        # print(a,b)
        return a==b
```

Please upvote if you find the solution helpful so that more people can get inspirations from it, Thanks! :)
['Math', 'Python3']