We, the insomniacs are part time architects. The job that lies ahead of us is laying out the plan of a new country named Zigobe. The constraint requires us to use exactly n roads to connect the cities within the country. All the cities must be connected to form a closed convex shape. In other words, all the cities must lie at the perimeter of the country to form a closed figure (See the figure for clarity).
There can be only a single direct - straight road between any two cities without any curves or bends. There can however be any number of paths between any two cities.
So, given the number of roads to be laid down, there can be an arbitrary number of cities in the country such that the above constraints satisfy. It has been therefore decided that the country would not have less than k cities. Now your task is to help us find out the number of ways in which the country can be planned.
Note : The roads can overlap with each other but must not coincide.
This figure shows a possibility of planning the country with 6 cities and 8 roads connecting them.
Input Format :
First line contains number of test cases - t. The following t lines contain the individual test cases.
Each test case contains two integers n and k separated by a single space.
Output Format :
For each test case, output the number of ways in a separate line.
Give the answer modulus 1000000007
1 <= t <= 1000
3 <= n <=2000
3 <= k <= n
Sample Input :
Sample Output :
For the first case, only a single possibility of a triangle of three cities exists.
For the second case, if you plan to have 3 cities, you cannot have 4 roads connecting them such that the constraints are satisfied. So, the only case that remains is having 4 cities and all connected in a cycle to form a closed figure.