#2280. 「FJOI2017」矩阵填数

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: l0nl1f3

题目描述

给定一个 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