ICC - Sir and The ICC Ratings

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 45o (increasing) or -45o (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^9+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

Added by:Aaquib Javed
Date:2013-10-08
Time limit:1.129s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own Problem used in LiveWire 2k13 MNNIT

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.