C. Prefix Sum Array
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There's an array of size $$$10^{18}$$$ which every element of the array is $$$1$$$. After each second, Every element of the array becomes the prefix sum of it's position, it means for example at a second the array is $$$a_{1}, a_{2}, a_{3}, ....$$$ in the next second the array becomes $$$a_{1}, a_{1} + a_{2}, a_{1} + a_{2} + a_{3}, ....$$$ . Now your task is to find the $$$n_{th}$$$ element of the array after $$$k$$$ seconds.

Input

In the first line of input, You'll be given a number $$$t$$$ which shows the number of testcases.

In the next $$$t$$$ lines you'll be given two integers $$$n$$$ and $$$k$$$.

$$$1 \le t \le 10^{5}, 1 \le n \le 10^{5}, 1 \le k \le 10^5$$$.

Note that for each testcases the initial array is filled with $$$1$$$.

Output

As the answer can be large print the answer modulo $$$10^9 + 7$$$.

Example
Input
3
2 1
1 3
2 4
Output
2
1
5
Note

Testcase $$$1$$$ :

The array at second $$$0 : 1, 1, 1, 1, 1, 1, ...$$$

The array at second $$$1 : 1, 2, 3, 4, 5, 6, ...$$$

The array at second $$$2 : 1, 3, 6, 10, 15, 21, ...$$$