Matrix Filling with Submatrix Maximum Constraints

You are given a matrix of size \(h \times w\) with rows numbered \(1 \ldots h\) (from top to bottom) and columns numbered \(1 \ldots w\) (from left to right). You have to fill each cell of the matrix with an integer chosen from \(1 \ldots m\). In addition, there are \(n\) constraints. Each constraint specifies a submatrix (by its top-left and bottom-right corners) and an integer \(v\). The constraint requires that in the specified submatrix, the maximum number among all cells is exactly \(v\). Two fillings are considered different if there exists at least one cell in which the numbers differ.

Your task is to compute the number of ways to fill the matrix so that all \(n\) constraints are satisfied. Since the answer can be large, output it modulo \(10^9+7\).

Note: A submatrix with top-left cell \((r_1, c_1)\) and bottom-right cell \((r_2, c_2)\) consists of all cells \((i,j)\) with \(r_1 \le i \le r_2\) and \(c_1 \le j \le c_2\). For a given submatrix with required maximum \(v\), all the cells within that submatrix must have values at most \(v\), and at least one cell must be exactly \(v\).

inputFormat

The first line contains four integers \(h\), \(w\), \(m\) and \(n\) representing the number of rows, the number of columns, the maximum number available, and the number of constraints, respectively.

Then \(n\) lines follow. Each of these lines contains five integers \(r_1\), \(c_1\), \(r_2\), \(c_2\) and \(v\). This means that in the submatrix defined by the top-left cell \((r_1,c_1)\) and bottom-right cell \((r_2,c_2)\), the maximum value must be exactly \(v\).

If \(n = 0\), then there are no constraint lines following.

outputFormat

Output a single integer, which is the number of valid matrix fillings modulo \(10^9+7\).

sample

2 2 3 1
1 1 2 2 2

15