LVADER  Luke vs. Darth Vader
You know one of the most dangerous villain of all time, it's Darth Vader. It's time to stop him and Master Luke is looking forward to fight against him. They both are in an infinite twodimensional grid. Each cell is denoted by (x, y). Here x denotes the row number and y denotes the column number of that cell. Please have a look on that picture of 5*7 grid to understand.
0,0 
0,1 
0,2 
0,3 
0,4 
0,5 
0,6 
1,0 






2,0 






3,0 






4,0 






Luke stays at a cell (x1, y1) and Vader stays at another cell (x2, y2). It is guaranteed that x1<=x2 and y1<=y2. Master Luke need to reach to the Vader’s cell. Each time Luke can move one step below horizontally or vertically or diagonally. That means, if his position is (x, y) then he can move to (x+1, y) or (x, y+1) or (x+1, y+1) cell in a single move. Given Luke and Vader’s position you have to determine in how many ways Luke can reach to the Vader’s cell. As the answer can be very large output the solution modulo 10^9 + 7.
Input
Input starts with an integer (T<=50) which denotes the number of test case. Each test case consists four integer x1, y1, x2, y2 (0<=x1<=x2<=100000 and 0<=y1<=y2<=100000), the position of Luke and Vader.
Output
For each test case, print the number of ways Luke can reach to the Vader’s cell modulo 10^9 + 7.
Example
Input:3
1 2 2 3
2 2 3 3
3 4 3 5 Output:Case 1: 3
Case 2: 3
Case 3: 1
Explanation:
In the first case he can move from (1, 2) to (2, 3) in the following 3 ways,
(1, 2) > (1, 3) > (2, 3)
(1, 2) > (2, 2) > (2, 3)
(1, 2) > (2, 3)
hide comments
Waseem Ahmed:
20210730 03:57:11
TLE? Use closed form of obtaining the Delannoy Number. 

yash200:
20170621 16:16:57
just grid concept :) 

julkas:
20170322 09:09:32
Theory  https://en.wikipedia.org/wiki/Delannoy_number 
Added by:  Akash 
Date:  20170125 
Time limit:  1s2s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU 
Resource:  Intra KUET programming contest 2016 