#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
typedef long long ll;

struct sa {
	int x1,y1,x2,y2,v;
};
sa a[20];
ll f[1100],g[1100];

ll cal(ll x,ll y) {
	if (y==0) return 1;
	if (y==1) return x;
	ll t=cal(x,y/2);
	ll ret=t*t%mod;
	if (y%2==1) ret=ret*x%mod;
	return ret;
}

int main() {
	int tt;
	scanf("%d",&tt);
	for (int te=1;te<=tt;te++) {
		int h,w,n,m;
		scanf("%d%d%d%d",&h,&w,&m,&n);
		vector<int> X,Y;
		X.push_back(0);
		X.push_back(h);
		Y.push_back(0);
		Y.push_back(w);
		for (int i=0;i<n;i++) {
			scanf("%d%d%d%d%d",&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2,&a[i].v);
			a[i].x1--;
			a[i].y1--;
			X.push_back(a[i].x1);
			X.push_back(a[i].x2);
			Y.push_back(a[i].y1);
			Y.push_back(a[i].y2);
		}
		sort(X.begin(),X.end());
		X.erase(unique(X.begin(),X.end()),X.end());
		sort(Y.begin(),Y.end());
		Y.erase(unique(Y.begin(),Y.end()),Y.end());
		memset(f,0,sizeof(f));
		f[0]=1;
		for (int i=0;i+1<X.size();i++)
			for (int j=0;j+1<Y.size();j++) {
				memcpy(g,f,sizeof(f));
				memset(f,0,sizeof(f));
				int u=m;
				for (int k=0;k<n;k++)
					if (a[k].x1<=X[i] && X[i+1]<=a[k].x2 && a[k].y1<=Y[j] && Y[j+1]<=a[k].y2) u=min(u,a[k].v);
				int mask=0;
				for (int k=0;k<n;k++)
					if (a[k].x1<=X[i] && X[i+1]<=a[k].x2 && a[k].y1<=Y[j] && Y[j+1]<=a[k].y2 && a[k].v==u) mask|=1<<k;
				ll t1=cal(u-1,(Y[j+1]-Y[j])*(X[i+1]-X[i]));
				ll t2=cal(u,(Y[j+1]-Y[j])*(X[i+1]-X[i]));
				for (int r=0;r<(1<<n);r++) if (g[r]) {
					f[r]=(f[r]+g[r]*t1)%mod;
					f[r|mask]=(f[r|mask]+g[r]*(t2-t1))%mod;
				}
			}
		printf("Case #%d: %lld\n",te,(f[(1<<n)-1]+mod)%mod);
	}
}