explaination of why Luca's thm.
Intuitionso i think the problem is clear, we recognised a pattern (nth row of pascal's triangle) and we need to get that row and multiply its elements with the
# Intuition
so i think the problem is clear, we recognised a pattern (nth row of pascal's triangle) and we need to get that row and multiply its elements with the corresponding digits in the string and get the sum.

This pattern can also be recognised by simply dry running. (check the comment at the bottom of my code)

The issue we face is to calculate nCr for such huge numbers and modulo it with 10.

1. 10 isnt prime -> fix: break 10 into 2 x 5 and merge the results of individual nCr of each.
How?
if ncr mod 2 is 0 -> the value is even
thus is ncr mod 5 is 0, 1, 2, 3, 4 => the ncr mod 10 will be 0, 6, 2, 8, 4 respectively

similarly for the case where ncr mod 2 is 1

2. our traditional methods of calculating ncr could be DP (not viable because n * n is too big) and using inverse modulo (which we compute using fermat's little theorem)
-> we cant using inverse modulo (ncr = factorial(n) * inverse_factorial(n - r) * inverse_factorial(r)) because fermat's little theorem makes an assumption that p (the prime number that needs to be modded) and the value (here factorial) are both co-prime.. if not, then the inverse modulo doesnt exist. for this reason we cant precompute inverse factorial mod 2 and mod 5.

Thus we are left with Luca's theorem which also leverages the fact that p is very small. 

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

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

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

# Code
```cpp []
#define ll long long
class Solution {
public:
    int fact[10];
    int nCrSmall(ll n, ll r, ll p) { 
        if (n < r)
            return 0;
        else
            return (fact[n] / (fact[n - r] * fact[r])) % p; 
    }

    int nCrModpLuca(int n, int r, int p) 
    { 
        if (r==0) 
            return 1; 

        int ni = n % p, ri = r % p; 
        
        return (nCrModpLuca(n / p, r / p, p) * nCrSmall(ni, ri, p)) % p;
    } 

    ll nCrMod10(int n, int r) {
        ll mod2 = nCrModpLuca(n, r, 2);
        ll mod5 = nCrModpLuca(n, r, 5);

        if(mod5 == 0) 
            return mod2 ? 5 : 0;
        else if(mod5 == 1) 
            return mod2 ? 1 : 6;
        else if(mod5 == 2)
            return mod2 ? 7 : 2;
        else if(mod5 == 3)
            return mod2 ? 3 : 8;
        else
            return mod2 ? 9 : 4;
    }


    bool hasSameDigits(string s) {
        fact[0] = 1;
        for(int i = 1; i < 10; i++)
            fact[i] = fact[i - 1] * i;

        ll d1 = 0, d2 = 0;
        for(int i = 0; i < s.size() - 1; i++){
            int ncr10 = nCrMod10(s.size() - 2, i);
            d1 = (d1 + (s[i] - '0') * ncr10) % 10;
            d2 = (d2 + (s[i + 1] - '0') * ncr10) % 10;
        }

        // cout << d1 << " " << d2 << "\n";

        return d1 == d2;
    }
};

/*
3 4 7 8 9
3+4 4+7 7+8 8+9
3+4+4+7 4+7+7+8 7+8+8+9
3+4+4+7+4+7+7+8 4+7+7+8+7+8+8+9
(pascal triangle)


0761
737
00
*/
```
['C++']