#include<bits/stdc++.h>
#define rep(i,s,t) for (int i=s;i<=t;i++)
using namespace std;
const int maxn = 10001;
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<PII,PII> PPP;
typedef pair<int,PPP> PIP;
typedef pair<int,PII> PIS;
int TEMP;
const LL mod = 1e9 + 7;
LL margin;
int n;
int a1,a2,a3,a4,a5;
PIP node[22];
LL w,h,m;
int cnt;
int q1[4000], q2[4000];
set<PII> a[31][31];
map<int,int> s1, s2;
LL expMod(LL e, LL n){
	LL ret = 1;
	for (; n; n >>= 1, e = e * e % mod)
		if (n & 1)
			ret = ret * e % mod;
	return ret;
}
LL memory[2][31][31];
LL origin[31][31];
int main()
{
	int testdata;
	scanf("%d",&testdata);
	rep(_t,1,testdata)
	{
		s1.clear();
		s2.clear();
		printf("Case #%d: ", _t);
		scanf("%lld%lld%lld%d",&h,&w,&m,&n);
		s1[h+1] = 1;
		s2[w+1] = 1;
		s1[1] = 1;
		s2[1] = 1;
		rep(i,1,n)
		{
			scanf("%d%d%d%d%d", &a1,&a2,&a3,&a4,&a5);
			s1[a1] = 1;
			s1[++a3] = 1;
			s2[a2] = 1;
			s2[++a4] = 1;
			node[i] = PIP(a5, PPP(PII(a1, a2), PII(a3, a4)));
		}
		int cnt1 = 0;
		for (auto xx = s1.begin(); xx != s1.end(); xx++)
		{
			xx->second = ++cnt1;
			q1[cnt1] = xx->first;
		}
		int cnt2 = 0;
		for (auto xx = s2.begin(); xx != s2.end(); xx++)
		{
			xx->second = ++cnt2;
			q2[cnt2] = xx->first;
		}
		cnt = 0;
		rep(i,1,n)
		{
			node[i].second.first.first = s1[node[i].second.first.first];
			node[i].second.second.first = s1[node[i].second.second.first];
			node[i].second.first.second = s2[node[i].second.first.second];
			node[i].second.second.second = s2[node[i].second.second.second];
		}
		int last = 0;
		LL ans = 0;
		{
			rep(i,1,cnt1) rep(j,1,cnt2)
			{
				a[i][j].clear();
				a[i][j].insert(PII(m,0));
				origin[i][j] = m;
			}
			rep(i,1,n)
			{
				rep(j,node[i].second.first.first,node[i].second.second.first-1)
					rep(k,node[i].second.first.second,node[i].second.second.second-1)
					{
						a[j][k].insert(PII(node[i].first, i));
						origin[j][k] = min(origin[j][k], (LL)node[i].first);
					}
			}
			LL temp = 1;
			rep(i,1,cnt1-1)
				rep(j,1,cnt2-1)
				{
					memory[0][i][j] = expMod(a[i][j].begin()->first, (q1[i+1]-q1[i]) * (q2[j+1]-q2[j])) % mod;
					memory[1][i][j] = expMod(a[i][j].begin()->first - 1, (q1[i+1]-q1[i]) * (q2[j+1]-q2[j])) % mod;
				}
			rep(i,1,cnt1-1)
				rep(j,1,cnt2-1)
				{
					temp = temp * memory[0][i][j] % mod;
				}
			ans = (ans + temp) % mod;
		}
		rep(state, 1, (1<<n)-1)
		{
			int mm = (state) ^ (state >> 1);
			int stemp = mm ^ last;
			last = mm;
			int type = __builtin_popcount(mm);
			rep(i,1,n)
			if ((1 << (i-1)) & stemp)
			{
				rep(j,node[i].second.first.first,node[i].second.second.first-1)
					rep(k,node[i].second.first.second,node[i].second.second.second-1)
					{
						int p = ((1 << (i-1)) & last);
						if (p)
						{
							a[j][k].erase(PII(node[i].first, i));
							a[j][k].insert(PII(node[i].first-1, i));
						}
						else
						{
							a[j][k].erase(PII(node[i].first-1, i));
							a[j][k].insert(PII(node[i].first, i));
						}
					}
			}
			LL temp = 1;
			rep(i,1,cnt1-1)
				rep(j,1,cnt2-1)
				{
					temp = temp * memory[a[i][j].begin()->first != origin[i][j]][i][j] % mod;
				}
			ans = (ans + ((type % 2)?(-1):1) * temp) % mod;
		}
		printf("%lld\n", (ans + mod) % mod);
	}
}