输入数据的第一行为一个数 $T$，表示数据组数。
对于每组数据，第一行为四个数 $h,w,m,n$。
接下来 $n$ 行，每一行描述一个子矩阵的最大值 $v$。每行为五个整数 x1,y1,x2,y2,vx_1,y_1,x_2,y_2,vx​1​​,y​1​​,x​2​​,y​2​​,v，表示一个左上角为 (x1,y1)(x_1,y_1)(x​1​​,y​1​​)，右下角为 (x2,y2)(x_2,y_2)(x​2​​,y​2​​) 的子矩阵的最大值为 $v$（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≤x​1​​≤x​2​​≤h, 1≤y​1​​≤y​2​​≤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\le 2$。
另有 20% 的数据：$1\le h,w\le 50$。
对于 100%的数据：$T\le 5,1\le h,w,m\le 10000,1\le v\le m,1\le n\le 10$。