Bob is a famous magician who needs to use a magical compass to perform his fantasy magic. Before each performance, Bob must inject magic power into the magical compass. He can only successfully perform the fantasy magic if the magic values on the compass meet certain requirements.

The magical compass has $h \times w$ magic collection points, which can be viewed as an $h \times w$ matrix ($h$ rows and $w$ columns). When Bob injects magic power into the compass, the magic value collected at position $(i, j)$ is $X(i, j)$, where $X(i, j)$ is randomly chosen from the $m$ positive integers $1$ to $m$. For given values of $h, w, m$, the matrix $X$ is called a magic matrix.

To successfully perform the fantasy magic, the magic values must satisfy $n$ conditions: the $i$-th condition is that the maximum magic value in a rectangular region (a sub-compass) of the magical compass must be $v_i$. The ratio of magic matrices that satisfy these $n$ conditions among all possible magic matrices is the probability that Bob can successfully perform the fantasy magic. If the probability that Bob can successfully perform the fantasy magic is $A$, it is guaranteed that $A \times m^{h \times w}$ is a positive integer.

The Magician Problem asks for the value of $A \times m^{h \times w} \pmod{1,000,000,007}$.

Input

The first line contains a positive integer $T$, representing the number of test cases.

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

The next $n$ lines each contain five integers $x_1, y_1, x_2, y_2, v_i$, representing that the maximum magic value in the sub-compass with the top-left corner at $(x_1, y_1)$ and the bottom-right corner at $(x_2, y_2)$ must be $v_i$. $1 \le x_1 \le x_2 \le h$, $1 \le y_1 \le y_2 \le w$.

Output

For each test case, output the answer on a single line.

Examples

Input 1

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

Output 1

9
32593

Constraints

• For 20% of the data: $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 10000$, $1 \le v_i \le m$, $1 \le n \le 10$.