Bob has an empty number matrix with ~H~ rows and ~W~ columns. The rows are numbered from ~1~ to ~H~ and the columns from ~1~ to ~W~.

Bob plans to fill each cell in the matrix with an integer from ~1~ to ~M~ (inclusive). However, there are ~N~ special constraints that Bob must follow. Each constraint is defined by five integers: ~r_1~, ~c_1~, ~r_2~, ~c_2~, and ~v~. This means that in the submatrix with top-left corner ~(r_1, c_1)~ and bottom-right corner ~(r_2, c_2)~, the maximum value among all the cells must be exactly ~v~.

Bob wants to know how many valid ways there are to fill the entire matrix so that all constraints are satisfied. Since the answer may be very large, print the result modulo ~10^9 + 7~.

Input Specification

The first line of the input contains one integer ~T~ (~1 \le T \le 5~), the number of test cases.

For each test case, the first line contains four integers ~H~, ~W~, ~M~ and ~N~ (~1 \le H, W, M \le 10^4~, ~1 \le N \le 10~), the size of the number matrix, the value range of the numbers, and the number of special requirements.

Each of the following ~N~ lines contains five integers ~r_1~, ~c_1~, ~r_2~, ~c_2~ and ~v~ (~1 \le r_1 \le r_2 \le H~, ~1 \le c_1 \le c_2 \le W~, ~1 \le v \le M~), indicating a special requirement that the maximal integer in the submatrix from ~(r_1, c_1)~ to ~(r_2, c_2)~ is ~v~.

Output Specification

For each test case, print a single line — the number of valid ways to fill the matrix such that all constraints are satisfied, modulo ~10^9 + 7~.

Constraints

Subtask	Points	Additional constraints
~1~	~20~	~N \leq 2~.
~2~	~20~	~H, W \le 50~.
~3~	~60~	No additional constraints

Sample Input

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

Sample Output

28
76475