Combination

Time limit: 0.4s Memory limit: 128MB Input: combination.in Output: combination.out

Task

You are given qq queries. For each of the queries you are given two integers, nn and kk. Calculate Cnk mod (109+7)C_n^k \text{ mod } (10^9+7), where CnkC_n^k represents the number of ways to choose kk values from a set of nn (nn choose kk).

Input data

On the first line of the input file combination.in you have qq, the number of queries. On each of the following qq lines you will have nn and kk.

Output data

For each of the qq questions we will print the answer in the output file combination.out. Because these numbers can be very large, you will need to print them modulo 109+710^9+7.

Constraints and clarifications

  • 109+710^9 + 7 is a prime number.
  • 0≤q≤1050 \leq q \leq 10^5
  • 0≤k≤n≤1050 \leq k \leq n \leq 10^5
# Points Constraints
0 0 Example
1 20 0≤n,q≤5⋅1030 \leq n, q \leq 5 \cdot 10^3
2 40 0≤n,q≤1040 \leq n, q \leq 10^4
3 40 No additional constraints

Example

combination.in

11
7 5
35 20
85 40
67 40
44 7
76 69
60 35
44 43
28 20
44 13
93 17

combination.out

21
247943139
221670461
845448992
38320568
186189386
610920233
44
3108105
915526075
419070982

Explanation

C75 mod (109+7)=21C_7^5 \text{ mod } (10^9+7)= 21.

Log in or sign up to be able to send submissions!