As of now you have registered for IndiaHacks 2016 which is about to begin and you want to go to the venue to participate and the map is in the form of matrix. 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 you can reach from block [a][b] i.e. your home to block [c][d] i.e Indiahacks venue. Since this number may be huge print your answer modulo 1000000007.
Still if you have not registered for the contest do it now at IndiaHacks 2016 else Tom and Jerry will fight with you at the venue.
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