def choose(n, k):
    if k > n:
        return 0
    elif n < MOD:
        return (fact[n]/fact[n-k]/fact[k])%MOD
    else:
        prod = 1
        while n > 0:
            prod *= choose(n%MOD, k%MOD)
            prod %= MOD
            n /= MOD
            k /= MOD
        return prod