Basics 0/103

Modular arithmetic · 2 of 2 Advanced

Combinatorics

Compute binomial coefficients with Pascal's rule, and modulo a prime with factorial and inverse-factorial tables.

1,563 words · 7 min read

Part 1 of 5 Binomial coefficients

Count the ways to choose

Counting problems often ask in how many ways kk items can be chosen out of nn when the order of the chosen items does not matter. From the five items 1, 2, 3, 4 and 5, for example, there are ten ways to choose two:

{1,2}, {1,3}, {1,4}, {1,5}, {2,3},{2,4}, {2,5}, {3,4}, {3,5}, {4,5}\begin{gathered} \{1, 2\},\ \{1, 3\},\ \{1, 4\},\ \{1, 5\},\ \{2, 3\}, \\ \{2, 4\},\ \{2, 5\},\ \{3, 4\},\ \{3, 5\},\ \{4, 5\} \end{gathered}

The pair {2,1}\{2, 1\} is the same choice as {1,2}\{1, 2\}, so it appears once. This count is the binomial coefficient (nk)\binom{n}{k}, read "nn choose kk", so (52)=10\binom{5}{2} = 10. Two values hold for every nn: (n0)=1\binom{n}{0} = 1, since there is one way to choose nothing, and (nn)=1\binom{n}{n} = 1, since there is one way to take everything.

Binomial coefficients grow quickly ((10050)\binom{100}{50} has 30 digits), so judges ask for them modulo a prime:

Answer nn questions. Each gives integers aa and bb; print (ab)\binom{a}{b} modulo 109+710^9 + 7.

The first line holds nn, and each of the next nn lines holds aa and bb.

Constraints

  • 1≤n≤1051 \le n \le 10^5
  • 0≤b≤a≤1060 \le b \le a \le 10^6

Sample · Input

3
5 3
8 1
9 5

Output

10
8
126

There are two ways to compute them. Pascal's rule computes binomial coefficients with additions only and is enough when nn is at most a few thousand. The factorial formula, with its divisions done by modular inverses, handles nn up to a million.