如果只考虑某个子矩阵的话，其最大值为v的方案数显然是vsize-(v-1)size。问题在于处理子矩阵间的交叉情况。
如果两个交叉的子矩阵所要求的最大值不同，可以直接把交叉部分划给所要求的最大值较小的子矩阵。那么，所要求最大值不同的格子彼此间是独立的。于是现在可以只考虑要求相同的格子。
直接计算似乎很麻烦。由于n很小，考虑一个很套路的容斥：至少0个不满足限制的方案数-至少1个不满足限制的方案数+至少2个不满足限制的方案数……于是我们可以枚举哪些矩阵不满足限制，剩下的随便填（当然要在所限制的最大值之内）。
计算这些矩形的交和并也是一个有点麻烦的问题。可以离散化后暴力统计。这里离散化后应该每个位置表示一段区间比较方便，所以读入时++x2，++y2。由于数据范围实在太小怎么做都行。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int read()
{
int x=,f=;char c=getchar();
while (c<''||c>'') {if (c=='-') f=-;c=getchar();}
while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();
return x*f;
}
#define P 1000000007
#define N 13
#define y1 y3
#define y2 y4
int T,r,c,n,m,row[N<<],line[N<<],flag[N<<][N<<],ans,sum,nw,nv;
bool choose[N];
struct data
{
int x1,y1,x2,y2,v,size;
int tag[N<<][N<<];
bool operator <(const data&a) const
{
return v>a.v;
}
}a[N];
int ksm(int a,int k)
{
if (k==) return ;
int tmp=ksm(a,k>>);
if (k&) return 1ll*tmp*tmp%P*a%P;
else return 1ll*tmp*tmp%P;
}
int calc(int v)
{
memset(flag,,sizeof(flag));
for (int i=;i<=n;i++)
if (a[i].v==v&&!choose[i])
for (int j=a[i].x1;j<a[i].x2;j++)
for (int k=a[i].y1;k<a[i].y2;k++)
if (a[i].tag[j][k]) flag[j][k]=;
for (int i=;i<=n;i++)
if (choose[i])
for (int j=a[i].x1;j<a[i].x2;j++)
for (int k=a[i].y1;k<a[i].y2;k++)
if (a[i].tag[j][k]) flag[j][k]=-;
int s1=,s2=;
for (int i=;i<nw;i++)
for (int j=;j<nv;j++)
if (flag[i][j]==) s1+=(row[i+]-row[i])*(line[j+]-line[j]);
else if (flag[i][j]==-) s2+=(row[i+]-row[i])*(line[j+]-line[j]);
return 1ll*ksm(v,s1)*ksm(v-,s2)%P;
}
void dfs(int k,int s,int v)
{
if (k>n)
{
if (s&) sum=(sum-calc(v)+P)%P;
else sum=(sum+calc(v))%P;
return;
}
if (a[k].v==v) choose[k]=,dfs(k+,s+,v);
choose[k]=;dfs(k+,s,v);
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("bzoj5010.in","r",stdin);
freopen("bzoj5010.out","w",stdout);
const char LL[]="%I64d\n";
#else
const char LL[]="%lld\n";
#endif
T=read();
while (T--)
{
r=read(),c=read(),m=read(),n=read();
for (int i=;i<=n;i++)
a[i].x1=read(),a[i].y1=read(),a[i].x2=read()+,a[i].y2=read()+,a[i].v=read(),a[i].size=,memset(a[i].tag,,sizeof(a[i].tag));
int w=,v=;
for (int i=;i<=n;i++)
row[++w]=a[i].x1,row[++w]=a[i].x2,line[++v]=a[i].y1,line[++v]=a[i].y2;
row[++w]=,row[++w]=r+;line[++v]=,line[++v]=c+;
sort(row+,row+w+);sort(line+,line+v+);
nw=unique(row,row+w+)-row-,nv=unique(line,line+v+)-line-;
for (int i=;i<=n;i++)
a[i].x1=lower_bound(row+,row+nw+,a[i].x1)-row,a[i].x2=lower_bound(row+,row+nw+,a[i].x2)-row,
a[i].y1=lower_bound(line+,line+nv+,a[i].y1)-line,a[i].y2=lower_bound(line+,line+nv+,a[i].y2)-line;
sort(a+,a+n+);
memset(flag,,sizeof(flag));
for (int i=;i<=n;i++)
for (int j=a[i].x1;j<a[i].x2;j++)
for (int k=a[i].y1;k<a[i].y2;k++)
flag[j][k]=a[i].v;
for (int i=;i<=n;i++)
for (int j=;j<nw;j++)
for (int k=;k<nv;k++)
if (flag[j][k]==a[i].v) a[i].size++,a[i].tag[j][k]=;
ans=;
for (int i=;i<nw;i++)
for (int j=;j<nv;j++)
if (flag[i][j]==) ans=1ll*ans*ksm(m,(row[i+]-row[i])*(line[j+]-line[j]))%P;
for (int i=;i<=n;i++)
{
sum=;int t=i;
while (a[t+].v==a[i].v) t++;
memset(choose,,sizeof(choose));
dfs(i,,a[i].v);
ans=1ll*ans*sum%P;
i=t;
}
cout<<ans<<endl;
}
return ;
}