Count the Grid

You get a grid of h rows and w columns. Rows are numbered 1, 2, 3, ... , h from top to bottom while columns are numbered 1, 2 , 3, ... , w from left to right. Each cell can be represented by a pair of numbers (x, y), which means this cell is located at row x column y.
You fill the every cell with an integer ranging from 1 to m.
Then you start to play with the gird. Every time you chose a rectangle whose upper left cell is (x1, y1) and lower right cell is (x2, y2), finally you calculate the maximum value v of this rectangle.
After you played n times, you left. When you return, you find that the grid is disappeared. You only remember n rectangles and their corresponding maximum value. You are wondering how many different gird can satisfy your memory. Two grids are different if there is a cell filled different integer.
Give your answer modulo ($10^9 + 7$).
Your memory may have some mistakes so that no grid satisfies it, in this case just output 0.

Multiple test cases. In the first line there is an integer T, indicating the number of test cases. For each test case. First line contain 4 integers h, w, m, n. Next are n lines, each line contain 5 integers x1, y1, x2, y2, v.
($T = 55, 1 \leq h, w, m \leq 10^4, 1 \leq x1 \leq x2 \leq h,1 \leq y1 \leq y2 \leq w,1 \leq v \leq m,1 \leq n \leq10$, there are i test cases for n = i)

For each test case, please output one line. The output format is "Case #x: ans", x is the case number, starting from 1.

2
3 3 2 2
1 1 2 2 2
2 2 3 3 1
4 4 4 4
1 1 2 3 3
2 3 4 4 2
2 1 4 3 2
1 2 3 4 4

Case #1: 28
Case #2: 76475

2015 ACM/ICPC Asia Regional Shanghai Online