The Uncountable Ways

All submissions for this problem are available.
Little Chef loves mathematics.Every day, he solves some mathematical problems to improve his skill.
A few days ago, he found a popular problem about turtles. The problem is as follows. Little Chef is given R rectangles, numbered 1 through R. The width and height of the ith rectangle are N_{i} and M_{i} unit respectively. There is a turtle located on the topleft corner of each rectangle. For each rectangle, count the number of ways the turtle can reach the bottomright corner, if each turtle can only move right or down 1 unit at any time.The turtle is not allowed to move outside the rectangle, but, of course, the turtle can move on the boundary of the rectangle.
In less than one second, this problem was solved for all rectangles.He felt that the problem was too easy. This morning, Little Chef wanted more challenges. Thus, for each rectangle i, he cut and removed a rectangle of A_{i} × B_{i} unit from the topright corner. See the following figure for detail.
He could not solve this new version of the problem easily. Help him count the number of ways each turtle can reach the bottomright corner using the same rule as before.
Input
The first line of the input contains a single integer R. The description of R rectangles follows. Each description consists of a single line containing four spaceseparated integers N_{i}, M_{i}, A_{i}, and B_{i}.
Output
For each rectangle, output a single line containing the number of ways, modulo 1,000,000,007.
Constraints
1 ≤ R ≤ 10
2 ≤ N_{i}, M_{i} ≤ 400,000
1 ≤ A_{i} < N_{i}
1 ≤ B_{i} < M_{i}
Example
Input: 1 2 2 1 1 Output: 5
Explanations:
In the sample case, there are 5 ways the turtle can reach the bottom right corner as follows:
Author:  ballon_ziq 
Tester:  laycurse 
Editorial  http://discuss.codechef.com/problems/CNTWAYS 
Tags  ballon_ziq, combinatorics, dec12, easymedium 
Date Added:  12102012 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, JAVA, PYTH, PYTH 3.5, 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, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions