def bin_pow(n, k, d):
    if k == 0:
        return 1
    if k % 2 == 0:
        return bin_pow(n, k // 2, d) ** 2 % d
    return (bin_pow(n, (k - 1) // 2, d) ** 2 % d * n % d) % d


def get_primary_products(n):
    array = [0] + [1 for _ in range(n)]
    primaries = eratosthenes(n)
    for prime_number in primaries:
        prime_number_index = prime_number
        i = 0
        while True:
            i += 1
            prime_number = bin_pow(prime_number_index, i, 10**6)
            if prime_number <= n:
                array[prime_number] -= 1
            else:
                array[prime_number_index] = i - 1
                break
    return array


def eratosthenes(n):
    array = list(range(n + 1))
    array[1] = 0
    for i in array:
        if i > 1:
            for j in range(2*i, len(array), i):
                array[j] = 0
    return list(filter(lambda x: x, array))


def get_binomial_coef(n, k):
    numerator_products = get_primary_products(n)
    denumerator_products = get_primary_products(n - k if n - k > k else k)
    for i, elem in enumerate(get_primary_products(k if n - k > k else n - k)):
        denumerator_products[i] += elem
    for i in range(len(denumerator_products)):
        numerator_products[i] -= denumerator_products[i]
    return numerator_products