题目描述

给定一个$h×w$的矩阵，矩阵的行编号从上到下依次为$1\sim h$，列编号从左到右依次$1\sim w$。 在这个矩阵中你需要在每个格子中填入$1\sim 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≤x_1≤x_2≤h，1≤y_1≤y_2≤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≤2$。 另有20%的数据：$1≤h,w≤50$。   对于100%的数据：$T≤5，1≤h,w,m≤10000，1≤v≤m，1≤n≤10$。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共8个测试点，非原站或官方原始数据。总分100分。