Binomial Queries

Statement

You are given q queries. Each query gives n and r. Print the number of ways to choose r items from n, modulo 1000000007. If r is greater than n, the answer is 0.

Input

The first line has q. Each of the next q lines has n and r.

Output

Print q lines: the answer to each query.

Constraints

1 <= q <= 100000
0 <= n <= 1000000
0 <= r <= 1000000

Example 1

3
5 2
10 0
3 5

10
1
0

C(5, 2) = 10, C(10, 0) = 1, and you cannot choose 5 items from 3.