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 two-dimensional 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 needs to reach 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)

Added by:Akash
Date:2017-01-25
Time limit:1s-2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU
Resource:Intra KUET programming contest 2016

hide comments
2021-07-30 03:57:11 Waseem Ahmed
TLE? Use closed form of obtaining the Delannoy Number.
2017-06-21 16:16:57
just grid concept :)
2017-03-22 09:09:32
Theory - https://en.wikipedia.org/wiki/Delannoy_number
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.