Read problems statements in Mandarin Chinese and Russian.

Devu is learning Combinatorics in his college. He find it very interesting to calculate number of ways of going to point (c,d) from point (a,b) in co-ordinate plane. We can take horizontal and vertical steps only and can not visit at a point twice. In a step, you can move one unit only. We have to reach to the point (c,d) from the point (a,b) using abs(a-c)+ abs(b-d) steps only.

Devu has two sets of points. Set A contains points having X co-ordinate 0 and Y co-ordinates varying from 1 to N(both inclusive). Set B contains points having X co-ordinate K and Y co-ordinates varying from 1 to N(both inclusive). Both sets contains N number of integral points. He wants to calculate the sum of number of ways to going to the each point of set B from the each point of set A .

As the answer can be large, print it modulo 1000000007.

------ Input ------

First line of input contains an integer T denoting number of test cases.
Next T lines will contain pair of integers N and K

------ Output ------

For each test case, print a single integer representing the answer of that test case.

------ Constraints ------

Subtask #1: 10 points

$1 ≤ T  ≤ 20, 1 ≤ N ,K ≤ 1000$

Subtask #1: 10 points

$1 ≤ T  ≤ 20, 1 ≤ N ,K ≤ 10^{6}$

Subtask #3: 80 points

$1 ≤ T  ≤ 10000, 1 ≤ N,K  ≤ 10^{6}$

----- Sample Input 1 ------
2

2 2

4 5
----- Sample Output 1 ------
8

236
----- explanation 1 ------

For the first sample case,
ways[(0,1)->(2,1)]= 1
ways[(0,2)->(2,2)]= 1
ways[(0,1)->(2,2)]= 3
ways[(0,2)->(2,1)]= 3

So, the total number of ways = 8.

见题面

见题面