Problem G
Game of Rectangles
Time Limit : 7 seconds
 

 

Arif and Nadia are playing a two player game. The game has following rules - 

  1. Given a rectangular board of Width W, and Height H. Consider the co-ordinate of lower left corner of this board is (0,0) and co-ordinate of upper right corner is (W, H).
  2. In each turn a player can draw a rectangle in this board.
  3. The player who place the last rectangle will win.


But since the board itself is a rectangle, the first player will always win if we do not restrict in drawing any kind of and any size of rectangle.
So we will put some restriction in drawing rectangles. Here are the rules.

  1. All edges of the rectangle will be parallel to any of the edges of rectangular board.
  2. All corners of the rectangle must be a lattice point. Lattice points, are the points in two-dimensional coordinate system whose abscissa and ordinate has integer values. For example (3, 4) is a lattice point but (3, 4.5) is not a lattice point.
  3. The width of the rectangle will be at most MaxWidth and at least MinWidth.
  4. The height of the rectangle will be at most MaxHeight and at least MinHeight.
  5.  No two rectangles can overlap with each other.
     

Note that, A rectangle can be represented as (x1, y1, x2, y2), where (x1, y1) is the lower left corner and (x2, y2) is the upper right corner. So, the height of the rectangle is y2 - y1 and width of the rectangle is x2 - x1, and area of the rectangle is (y2-y1)*(x2-x1).

Predicting the winner of such a game is very hard. But your task is not that hard. At any stage of the game, Nadia wants to know how many possible moves are available to her. Your task is to help her. It might help her to win aginst Arif. You will be given a state of board. You have to calculate, how many ways Nadia can place a rectangle having this state.
 

  
  Input    
  The first line of input is an integer T(T<=100) that indicates the number of test cases. Each case will starts with a line containing two integer, W (1<=W<=1000000000) width of the board and H(1<=H<=1000000000) height of the board. Next Line will contain 4 integers, MaxWidth, MinWidth, MaxHeight, MinHeight. This line will be followed by another line containing a single integer K(0<=K<=50), the number of rectangles placed in the board. Next K line will represents one rectangle each. Each rectangle will be represented with 4 space separated integer values (x1, y1, x2, y2), as described above. There is a blank line between two test cases..
  		 
     
  Output  
  For each test case, output will be a single line containing N, the number of ways to place a rectangle in that board modulo 1000000007.  
     
  Sample Input Sample Output    
  2

20 10
2 2 5 4
2
10 5 11 6
4 4 5 5

 20 10
2 2 5 4
1
10 5 11 6
 211
229		    
 

Problem Setter: Md. Arifuzzaman Arif
Special Thanks: Istiaque Ahmed
Next Generation Contest 5