Endurance is very careful about selecting and taking care of its intern. They are now going to select n interns from DA-IICT and they will take them to their headquarters where surprisingly exactly n people work.

There is weird condition which says that an ith intern can enter the building only if there are at least i employees of endurance who have already entered the building. So for example, 4th intern can enter if number of employees in building is greater than equal to 4.

You have to determine the number of ways in which people can enter the building.

As the answer can be very big, print answer%1000000007

Note: Endurance does not discriminate between people at same position. So all interns are identical and all employees are identical

Input
First line contains t test cases, t<=1000
Each test case contains a single line denoting n, number of employees and number of internsn<=10^6

Output
Output number of ways in which people can enter the building on new line for each test case.

Setter : Akshay Miterani