Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM-ICPC竞赛训练》暑期课面向全球招生。容量有限,报名从速!
Language:
Escape
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 1979Accepted: 638

Description

Hamilton, the famous thief, plans a bank robbery in L.A. When searching for the escape route, he takes two main factors into consideration. First, he cannot pass through any intersection twice since the police will set up force at any intersection after he passes it for the first time. Second, as, in America, vehicles are driven on the right side, it is too risk for Hamilton to take a left turn at intersections when escaping. So he will always drive straight ahead or turn right when he comes to a intersection.

Hamilton is planning his escape route. He pays you, his partner, to calculate the number of different ways which leads him to his shelter. He gives you the map of the city, which looks like grids, with only streets leading in East-West direction and South-North direction. His starting position is (0, 0) which is the South-West corner of the city and his shelter is located at (x, y) which stands for the intersection of the (x+1)th South-North direction street and the (y+1)th East-West direction street. Moreover, when he starts at (0, 0), he is heading north, and of course, he can make a right turn there as well.

As the total number of different ways might be very large, you are asked to give the number's residue modulo 100000007.

Input

The first line of input contains N(N<=100), the number of test cases. Each of the following lines describes one test case. Each line consists of four integers, X, Y, x, y(0<X,Y≤2000, 0≤x≤X, 0≤y≤Y), which (X, Y) is the North-East corner of the city and (x, y) is the location of Hamilton's shelter. The famous thief, of course, cannot driver out of the city.

Output

For each test case, print one line with a single integer which is the corresponding answer.

Sample Input

3
3 4 0 0
3 4 1 0
3 4 1 1

Sample Output

1
13
16

Source

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator