Binomial coefficient - MarisaOJ: Marisa Online Judge

There are

q

$q$ queries, each of the form

(n, k)

$(n, k)$ , calculate the binomial coefficient:

(\binom{n}{k}) = \frac{n!}{k! (n - k)!}

${n\choose k}=\frac{n!}{k!(n-k)!}$ ### Input - The first line contains an integer

q

$q$ . - Each line in the next

q

$q$ lines contains 2 integers

n, k

$n, k$ . ### Output - Print each binominal coefficient modulo

10^{9} + 7

$10^9+7$ . ### Constraints -

1 \leq q \leq 10^{6}

$1 \le q \le 10^6$ . -

1 \leq k \leq n \leq 10^{6}

$1 \le k \le n \le 10^6$ . ### Example Input:

26453

$2 6 4 5 3$

Output:

1510

$15 10$

Topic

Combinatorics

Rating

1000

Solution (0)

Solution