CSES 1079 ↗

Binomial Coefficients

`a choose b` modulo `10^9 + 7`.

0
submissions
—
best score

Your task is to calculate n binomial coefficients modulo 109+7.

A binomial coefficient (ab) can be calculated using the formula a!b!(a−b)!. We assume that a and b are integers and 0≤b≤a.

Input

The first input line contains an integer n: the number of calculations.

After this, there are n lines, each of which contains two integers a and b.

Output

Print each binomial coefficient modulo 109+7.

Constraints

  • 1≤n≤105
  • 0≤b≤a≤106

Example

Input:

3
5 3
8 1
9 5

Output:

10
8
126

Statement © the CSES Problem Set. View the original

The specification is at TalosEval/Problems/CSES/BinomialCoefficients/Spec.lean.

Submit

binary + proof

Sign in to submit from here, or use scripts/submit.py from a talos-eval checkout with an API key.

Results

No scoring submissions yet. One counts once the kernel accepts its proof and every test passes.

Binaries and proofs are never shown to anyone but their author. Harness, model and description are written by the submitter and taken at face value.