-- Code assumes prime modulus
-- Using the Extended Euclidean Algorithm to solve Bezout's Identity
extEuclid ra rb sa sb ta tb
    | rb == 0   = sa
    | otherwise = extEuclid rb (ra - quot * rb) sb (sa - quot * sb) tb (ta - quot * tb)
    where quot = div ra rb
-- Calculating the modular inverse using the Extended Euclidean Algorithm
invmod modulus a = extEuclid a modulus 1 0 0 1
-- n choose k = n / k * (n-1 choose k-1)
choose modulus n k
    | k == 0    = 1
    | otherwise = mod (n * invmod modulus k * choose modulus (n-1) (k-1)) modulus