Rust | Binomial coefficients using modular inverse
ApproachI don't understand Lucas's theorem, but I was able to figure out a solution using modular inverses.Iteratively calculate all the coefficients in a row o
# Approach
I don't understand Lucas's theorem, but I was able to figure out a solution using modular inverses. 

Iteratively calculate all the coefficients in a row of pascal's triangle modulo m, while keeping track of how many multiples of m need to be divided out of each coefficient. If there's at least 1 multiple of m in the coefficient, then it's 0 mod m. 

# Code
```rust []
// Compute modular inverse using extended euclid's algorithm
// Multiply this instead of dividing when computing the binomial coefficients
// I got this off of wikipedia
pub fn modular_inverse(x: i32, m: i32) -> Option<i32> {
    let (mut t, mut newt) = (0,1);
    let (mut r, mut newr) = (m,x);
    while newr != 0 {
        let q = r / newr;
        (t, newt) = (newt, t - q * newt);
        (r, newr) = (newr, r - q * newr);
    }

    if r > 1 {
        return None;
    }
    if t < 0 {
        t = t + m;
    }
    return Some(t);
}

// Decompose n into a * m^b
pub fn decomp(mut n: i32, m: i32) -> (i32,i32) {
    let mut r = 0;
    if n == 0 || m == 0 {
        return (0,0);
    }
    while (n % m == 0) {
        n /= m;
        r += 1;
    }
    return (n,r);
}

// Get the nth row of pascal's triangle mod m
pub fn pascal_row(n: i32,m: i32) -> impl Iterator<Item=i32> {
    return (0..(n+1)).scan(
        // Keep track of the number of multiples of m are in the prime factorization,
        // As well as the remainder mod m, after dividing out the multiples
        (0,1),
        move |&mut (ref mut multiples,ref mut rem),i| {
            if i > 0 {
                // Break down the numerator and denominator into x_p * m^x
                let (num,num_p) = decomp(n+1-i,m);
                let (denom,denom_p) = decomp(i,m);
                *multiples = &*multiples + num_p - denom_p;
                // Call unwrap here because we should be dividing out any factors of m beforehand
                let top = num%m;
                let bottom = modular_inverse(denom%m,m).unwrap(); 
                // Multiplicative formula for n choose k, from wikipedia
                *rem = (&*rem * top * bottom) % m;
            }
            assert!(*multiples >= 0, "The prime factorization can't have a negative exponent");
            // If the number of multiples in this coefficient > 0, then the coefficient is 0 mod m
            if *multiples > 0 {
                return Some(0);
            }
            return Some(*rem);
        }
    );
}
pub fn atoi_byte(c: u8) -> i32 {
    return c as i32 - 48;
}

// Return the digit that we'd get from the string s after applying the whole process, mod m (where m is prime)
pub fn get_final_digit(s: &str,m:i32) -> i32 {
    let row = pascal_row(s.len() as i32-1,m);
    return s
            .as_bytes()
            .iter()
            .zip(row)
            .map(|(&digit,coeff)| atoi_byte(digit)*coeff)
            .fold(0,|a,x|(a+x)%m);
}

impl Solution {
    pub fn has_same_digits(s: String) -> bool {
        // Use chinese remainder theorem -- if it works for both mod 2 and mod 5, then it should work for mod 10
        let mod_2 = get_final_digit(&s[..s.len()-1],2) == get_final_digit(&s[1..], 2);
        let mod_5 = get_final_digit(&s[..s.len()-1],5) == get_final_digit(&s[1..], 5);
        return mod_2 && mod_5;
    }
}
```
['Rust']