[Python] lucas theorem + CRT beats 100%
The hardest part of this problem is the calculation of nCk % 10. The naive approach will take O(k) times. However we can speed it up to O(logN) time by using lu
The hardest part of this problem is the calculation of nCk % 10. The naive approach will take O(k) times. However we can speed it up to O(logN) time by using lucas theorem. For mod 2 we can use the fact that nCk % m is odd when n&k ==k.

```python3 []
class Solution:
    def lucas(self,n, k):
        res = 1
        while n or k:
            (n, n_i), (k, k_i) = divmod(n,5),divmod(k,5)
            res = (res * (comb(n_i, k_i)%5)) % 5
        return res

    def crt(self,n, k):
        r2 = n & k == k
        r5 = self.lucas(n, k)  
        
        for c in range(10):
            if c%2 == r2 and c%5 == r5:
                return c

    def hasSameDigits(self, s: str) -> bool:
        mods = [self.crt(len(s)-2,i) for i in range(len(s)-1)]
        return sum(int(c)*mods[i] for i,c in enumerate(s[:-1]))%10 == sum(int(c)*mods[i] for i,c in enumerate(s[1:]))%10
```
['Python3']