题目描述

给定一个 $h \times w$ 的矩阵，矩阵的行编号从上到下依次为 $1,\ldots,h$，列编号从左到右依次 $1,\ldots,w$。

在这个矩阵中你需要在每个格子中填入 $1,\ldots,m$ 中的某个数。给这个矩阵填数的时候有一些限制，给定 $n$ 个该矩阵的子矩阵，以及该子矩阵的最大值 $v$，要求你所填的方案满足该子矩阵的最大值为 $v$。

现在，你的任务是求出有多少种填数的方案满足这 $n$ 个限制。

两种方案是不一样的当且仅当两个方案至少存在一个格子上有不同的数。由于答案可能很大，你只需要输出答案 $\bmod 1000000007$。

输入格式

输入数据的第一行为一个数 $T$，表示数据组数。
对于每组数据，第一行为四个数 $h,w,m,n$。
接下来 $n$ 行，每一行描述一个子矩阵的最大值 $v$。每行为五个整数 $x_1,y_1,x_2,y_2,v$，表示一个左上角为 $(x_1,y_1)$，右下角为 $(x_2,y_2)$ 的子矩阵的最大值为 $v$（$1\leq x_1\leq x_2\leq h$，$1\leq y_1\leq y_2\leq w$）。

输出格式

对于每组数据输出一行，表示填数方案 $\bmod 1000000007$ 后的值。

样例

输入

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

数据范围与提示

• 对于 $20\%$ 的数据：$n \leq 2$。
• 另有 $20\%$ 的数据：$1 \leq h, w\leq 50$。
• 对于 $100\%$ 的数据：$T \leq 5$，$1 \leq h, w, m \leq 10000$，$1 \leq v \leq m$，$1 \leq n \leq 10$。