#245MediumMath & Combinatorics· Many Binomial Queries Modulo a Prime

Modular Combinations Table

A lottery office prints, for many different games, the number of ways to pick `r` numbers out of `n` without caring about the order. The numbers are enormous, so the office only prints the value modulo `1000000007`. Given a list of queries `[n, r]`, return `C(n, r) mod 1000000007` for each of them, in the same order. When `r > n` there are no ways to pick, so the answer is `0`.

Input format

`queries`: an array of pairs `[n, r]`.

Output format

An array with one integer per query: C(n, r) modulo 1000000007.

Examples

Input: queries = [[5, 2], [10, 3], [4, 4]]

Output: [10, 120, 1]

C(5,2) = 10, C(10,3) = 120 and C(4,4) = 1.

Input: queries = [[3, 5], [0, 0], [6, 0]]

Output: [0, 1, 1]

Choosing 5 out of 3 is impossible (0). C(0,0) = 1 and C(n,0) = 1 for any n.

Input: queries = [[40, 20]]

Output: [846527861]

C(40,20) = 137846528820, and 137846528820 mod 1000000007 = 846527861.

Constraints

1 <= queries.length <= 10^5
0 <= n <= 10^6
0 <= r <= 10^6

#combinatorics
#modular-arithmetic
#precomputation
#math