给定一个 h×wh \times wh×w 的矩阵，矩阵的行编号从上到下依次为 1,…,h1,\ldots,h1,…,h，列编号从左到右依次 1,…,w1,\ldots,w1,…,w。
在这个矩阵中你需要在每个格子中填入 1,…,m1,\ldots,m1,…,m 中的某个数。给这个矩阵填数的时候有一些限制，给定 nnn 个该矩阵的子矩阵，以及该子矩阵的最大值 vvv，要求你所填的方案满足该子矩阵的最大值为 vvv。
现在，你的任务是求出有多少种填数的方案满足这 nnn 个限制。
两种方案是不一样的当且仅当两个方案至少存在一个格子上有不同的数。由于答案可能很大，你只需要输出答案 mod1000000007。
输入数据的第一行为一个数 TTT，表示数据组数。对于每组数据，第一行为四个数 h,w,m,nh,w,m,nh,w,m,n。接下来 nnn 行，每一行描述一个子矩阵的最大值 vvv。每行为五个整数 x1,y1,x2,y2,vx_1,y_1,x_2,y_2,vx1,y1,x2,y2,v，表示一个左上角为 (x1,y1)(x_1,y_1)(x1,y1)，右下角为 (x2,y2)(x_2,y_2)(x2,y2) 的子矩阵的最大值为 vvv（1≤x1≤x2≤h, 1≤y1≤y2≤w1\leq x_1\leq x_2\leq h,\ 1\leq y_1\leq y_2\leq w1≤x1≤x2≤h, 1≤y1≤y2≤w）。
对于每组数据输出一行，表示填数方案 mod1000000007 后的值。
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≤2n \leq 2n≤2。另有 20% 的数据：1≤h,w≤501 \leq h, w\leq 501≤h,w≤50。对于 100%的数据：T≤5,1≤h,w,m≤10000,1≤v≤m,1≤n≤10T \leq 5,1 \leq h, w, m \leq 10000,1 \leq v \leq m, 1 \leq n \leq 10T≤5,1≤h,w,m≤10000,1≤v≤m,1≤n≤10。