Everyone knows Sir Jadeja can alone blow the opposition away. Sir has dominated the ICC Rankings as well. One day he was going through his career rating graph on Cricinfo.com and noticed the peaks in the graph. He found these graphs interesting and decides to create many hypothetical graphs. In all his graphs, at any time  the slope of the graph is either 45^o (increasing) or -45^o (decreasing) only and takes non-negative integral values only. Since the graphs are hypothetical he starts the graph at rating 0 and end it at 0 too. In between the end points the total time covered is 2N (horizontal axis) units and there are a total of K peaks. He wants to calculate the total number of different graphs for a given N and K. Since the answer could be very large, print it modulo 10⁹+7. You too are supposed to be good at Maths, so please help Sir solve the problem.

Input

First Line denotes the number of test cases T (1 ≤ T ≤ 1000000). Each test case consists of two numbers, N and K.

1 ≤ K ≤ N ≤ 1000.

Output

Total number of such graphs modulo 1000000007.

Example

Input:
1
5 2

Output:
10