the-one-with-the-walk-2

Consider an NXN matrix on which the possible moves from a given block (i,j), is either one upward (i+1, j), or one rightward (i, j+1) or one  diagonally up (i+1, j+1). 
As shown in figure:
  

assuming that the numbering of rows and columns starts from 1.

You have to tell number of ways one can reach from block [a][b] to block [c][d]. 
Since this number may be huge print your answer modulo 1000000007.  

Input:

     First line T, the number of test cases

     T lines containing four space separated integers a,b,c,d.

Output:

      T lines with required answer Modulo 1000000007 for each test case.

Constraints:

      1 ≤ T ≤ 100000

      1 ≤ a ,b ≤ c,d ≤ 1004

SAMPLE INPUT
3
1 1 1 2
1 1 2 2
1 2 2 3

SAMPLE OUTPUT
1
3
3

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions: