NCR || Pascal triangle sequence || O(n.logn) || Simple
Complexity
Time complexity:
O(nlogn)
Space complexity:
O(n)Code

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
$$O(nlogn)$$
- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
$$O(n)$$
# Code
```java []
class Solution {
     static int nCrMod10(int n, int r) {
        int mod2 = nCrMod2(n, r);
        int mod5 = nCrMod5(n, r);
        return (5 * mod2 + 6 * mod5) % 10;
    }
    
    static int nCrMod2(int n, int r) {
        return ((n & r) == r) ? 1 : 0;
    }
    
    static int nCrMod5(int n, int r) {
        if (r > n) return 0;
        int[] fact = {1, 1, 2, 1, 4};
        int[] invFact = new int[5];
        for (int i = 0; i < 5; i++) {
            invFact[i] = modInverse5(fact[i]);
        }
        int anss = 1;
        while (n > 0 || r > 0) {
            int n_i = n % 5;
            int r_i = r % 5;
            n /= 5;
            r /= 5;
            if (r_i > n_i) return 0;
            int term = fact[n_i];
            term = (int) (((long) term * invFact[r_i]) % 5);
            term = (int) (((long) term * invFact[n_i - r_i]) % 5);
            anss = (anss * term) % 5;
        }
        return anss;
    }
    
    static int modInverse5(int x) {
        return power(x, 3, 5);
    }
    
    static int power(int x, int y, int mod) {
        int res = 1;
        while (y > 0) {
            if ((y & 1) == 1)
                res = (res * x) % mod;
            x = (x * x) % mod;
            y >>= 1;
        }
        return res;
    }
    
    static boolean hasSameDigits(String s) {
        char[] nums = s.toCharArray();
        int n = nums.length;
        int x = n - 2, y = 0;
        int ans = 0;
        for (int i = 0; i < n - 1; i++) {
            int val = nCrMod10(x, y++);
            ans = (ans + ((int)(nums[i] - '0') * val)) % 10;
        }
        int temo = ans;
        y = 0;
        int one = 0;
        for (int i = 1; i < n; i++) {
            int val = nCrMod10(x, y);
            one = (one + ((int)(nums[i] - '0') * val)) % 10;
            y++;
        }
        return temo == one;
    }
}
```
['Math', 'Java']