Description

Given an $h \times w$ matrix, the rows are numbered from top to bottom as $1 \sim h$, and the columns are numbered from left to right as $1 \sim w$.

You need to fill each cell in this matrix with a number from $1 \sim m$.

There are some restrictions when filling the matrix. You are given $n$ submatrices of this matrix and the maximum value $v$ for each submatrix. Your filling must satisfy that the maximum value of each given submatrix is $v$.

Now, your task is to find how many fillings satisfy the $n$ constraints.

Two fillings are different if and only if there exists at least one cell where the numbers differ between the two fillings. Since the answer may be large, you only need to output the result modulo $10 ^ 9 + 7$.

Input Format

The first line of the input contains an integer $T$, the number of test cases.

For each test case, the first line contains four integers $h,w,m,n$.

Then follow $n$ lines, each describing the maximum value $v$ of a submatrix. Each line contains five integers $x1,y1,x2,y2,v$, indicating that the submatrix with top-left corner $(x1,y1)$ and bottom-right corner $(x2,y2)$ has a maximum value of $v$. $1 \le x1 \le x2 \le h$, $1 \le y1 \le y2 \le w$.

Output Format

For each test case, output one line: the number of valid fillings modulo $1,000,000,007$.

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

28
76475

Hint

For $20\%$ of the testdata, $n \le 2$.

For another $20\%$ of the data, $1 \le h, w \le 50$.

For $100\%$ of the data, $T \le 5$, $1 \le h, w, m \le 10 ^ 4$, $1 \le n \le 10$, $1 \le v \le m$.

Translated by ChatGPT 5