Number of Ways

All submissions for this problem are available.
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 coordinate 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(ac)+ abs(bd) steps only.
Devu has two sets of points. Set A contains points having X coordinate 0 and Y coordinates varying from 1 to N(both inclusive). Set B contains points having X coordinate K and Y coordinates 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
 1 ≤ T ≤ 20, 1 ≤ N ,K ≤ 1000
 1 ≤ T ≤ 20, 1 ≤ N ,K ≤ 10^{6}
 1 ≤ T ≤ 10000, 1 ≤ N,K ≤ 10^{6}
Output
For each test case, print a single integer representing the answer of that test case.
Constraints
Subtask #1: 10 points
Subtask #1: 10 points
Subtask #3: 80 points
Example
Input: 2 2 2 4 5 Output: 8 236
Explanation
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.
Author:  amitpandeykgp 
Tester:  xcwgf666 
Editorial  http://discuss.codechef.com/problems/NWAYS 
Tags  amitpandeykgp, combinatorics, easy, ltime24 
Date Added:  4052015 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions