Binomial Coefficients Modulo a Prime

"n choose k" is the number of ways to pick k items out of n when order does not matter: 5 choose 2 is 10. A puzzle site receives many of these questions at once, with n up to half a million. The true answers can have more than a hundred thousand digits, so the site reports each one modulo the prime 1,000,000,007.

Write choose_mod(queries) that takes a list of pairs (n, k) and returns a list with (n choose k) % 1_000_000_007 for each pair, in the same order. When k > n there is no way to choose, so the answer is 0.

Examples

choose_mod([(5, 2), (10, 3), (4, 0)])    # returns [10, 120, 1]
choose_mod([(3, 5)])                     # returns [0]
choose_mod([(52, 5)])                    # returns [2598960]

52 choose 5 counts the different poker hands one deck can deal.

Constraints

• 1 <= len(queries) <= 100,000
• 0 <= n <= 500,000 and 0 <= k (k can be larger than n)
• Working each answer out in full is far too slow: 500,000 choose 250,000 has over 150,000 digits.