Modular C(n,r)

medium

Question Solve Solutions

You have T test cases and for each test case you have been given n and r values and you need to find nCr mod 10^9+7.

Input Format

The first line contains an integer T. Next T lines contain integers n and r.

Output Format

for each query print nCr mod 10^9+7 in a line.

Constraints

1 &lt;= T &lt;= 10^6
1 &lt;= n &lt;= 3000
1 &lt;= r &lt;= n

Example

Input

Output

4
10
45

Modular Fast Exponentiation

Related Questions

medium Extended Euclidean Algorithm medium Linear Diophantine Equation hard Eulers Totient Function medium Wilsons Theorem medium Modular Fast Exponentiation hard No Max No Min medium Prime Factors Using Sieve medium All Factors Using Sieve easy Count Of Common Divisors medium Gcd Length medium I Hate 1111 medium Relatively Prime Pairs medium Sum Of Factors easy Chinese Remainder Theorem easy Monkey Tradition