5659번 - Buy Your House 다국어

You are going to buy a house and hence communicated with a real estate development company, which has just started their business and you are going to be the first buyer. So they are offering you something special.

The real estate company has a rectangular shaped land of width W and height H. They are using co-ordinate system for measuring lands. (0, 0) is the lower left corner of their land and any point which has distance x from lower edge of the land and distance y from left edge of the land is known as (x, y) in the co-ordinate system.

The real estate company has already built some houses in that piece of land. All of them are rectangular shaped and their edges are parallel to edges of the main land. The location of a house can be addressed by four integers x1, y1, x2, y2. Where (x1, y1) is the lower left corner and (x2, y2) upper right corner of the house.

The special offer is that you can choose any rectangular shaped region that contains exactly one house with any amount of adjacent open space. You may not have enough money to afford open space and choose to buy only the region that a house occupies. If you have enough money, you can keep open space in front of your house for gardening!

But still there are some restrictions. For the ease of their future use of rest of their land you can only choose a rectangular shaped region and the edges of which are parallel to the edges of the main land. The corners of your selected region should be integer coordinates. It can be (3, 2) but cannot be (3.5, 2). You cannot chose a region for which part of a house is inside the region and another part of that house is outside the region. You cannot choose a region having more than one house and a region having no house. How many ways you can choose your land following the above rules?

Input will start with an integer T (T is around 500), the number of test cases. Each of the test cases starts with two integers W and H (1 ≤ W, H ≤ 1000000000), width and height of the land and the next line contains an integer N (1 ≤ N ≤ 50), the number of houses in the land. Each of the next N lines will contain four integer x1, y1, x2, y2 (0 ≤ x1 < x2 ≤ W and 0 ≤ y1 < y2 ≤ H), which describes the location of the house. Note that no house can overlap with another house and all the given coordinates will be non negative integers.

For each input, print a single line of the form “Case #: W”, where ‘#’ will be replaced by the case number and W will be replaced by the number of ways you can choose your land. Here W can be very large, so you should print the number of ways modulo 1000000007 as W.