Description：

一个 $n\times m$ 的矩阵，每个位置填入 $[1,k]$ ，给出 $q$ 个限制，要求某个子矩阵的最大值为 $v$ ，问方案数。

$1\leqslant n,m,k\leqslant 10^4,1\leqslant q\leqslant 10$

Solution：

一看一道计数题， $q$ 这么小显然是容斥。

子矩阵的限制相当于子矩阵内所有的数都 $\leqslant v$ ，但是有一个 $=v$ ，那就对每个位置求一下它的范围 $[1,k']$ ，发现最后得到的只有值域相同的点之间才会相互影响，如果两个值域不同，就一定没有类似“两个中一定有一个 $=v$ ”这样的限制。

于是可以分别计数，然后用乘法原理乘起来，首先不考虑必须有 $=v$ 的限制，设满足这个值域的格子数为 $S_i$ ，那么答案为 $v^{|S_i|}$ ，然后就要容斥，减去第一个集合没有的，减去第二个集合没有的，加上第一个和第二个集合都没有的，以此类推。

交集大小很好预处理，并集大小可以暴力容斥。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m,v,q;

#define MAXN 20

int siz[1 << MAXN];

int in[1 << MAXN],un[1 << MAXN];

#define MOD 1000000007

int power(int a,int b)

{

	int res = 1;

	while(b > 0)

	{

		if(b & 1)res = 1ll * res * a % MOD;

		a = 1ll * a * a % MOD;

		b = b >> 1;

	}

	return res;

}

struct rect

{

	int xl,xr,yb,yt,v;

	friend rect operator & (rect a,rect b)

	{

		rect res;

		res.xl = max(a.xl,b.xl);

		res.xr = min(a.xr,b.xr);

		res.yb = max(a.yb,b.yb);

		res.yt = min(a.yt,b.yt);

		return res;

	}

	friend bool operator < (const rect &a,const rect &b)

	{

		return a.v < b.v;

	}

	int siz()

	{

		if(xr < xl || yt < yb)return 0;

		return (xr - xl + 1) * (yt - yb + 1);

	}

}r[MAXN];

void work()

{

	memset(un,0,sizeof(un));

	memset(in,0,sizeof(in));

	scanf("%d%d%d%d",&n,&m,&v,&q);

	for(int i = 1;i <= q;++i)

	{

		scanf("%d%d%d%d%d",&r[i].xl,&r[i].yb,&r[i].xr,&r[i].yt,&r[i].v);

	}

	sort(r + 1,r + 1 + q);

	for(int i = 1;i < (1 << q);++i)

	{

		rect t;t.xl = 1;t.xr = m;t.yb = 1;t.yt = n;

		for(int k = 1;k <= q;++k)if(i & (1 << (k - 1)))t = t & r[k];

		in[i] = t.siz();

	}

	for(int i = 1;i < (1 << q);++i)

	{

		for(int k = i;k;k = (k - 1) & i)

		{

			if(siz[k] & 1)un[i] += in[k];

			else un[i] -= in[k];

		}

	}

	int tot = 0,last = 0;

	int ans = 1;

	for(int i = 1;i <= q;++i)

	{

		tot |= (1 << (i - 1));

		if(i != q && r[i].v == r[i + 1].v)continue;

		int area = un[tot | last] - un[last];

		int res = power(r[i].v,area);

		for(int k = tot;k;k = (k - 1) & tot)

		{

			int s = un[k | last] - un[last];

			if(siz[k] & 1)res = (res - 1ll * power(r[i].v,area - s) * power(r[i].v - 1,s) % MOD + MOD) % MOD;

			else res = (res + 1ll * power(r[i].v,area - s) * power(r[i].v - 1,s) % MOD) % MOD;

		}

		last |= tot;tot = 0;

		ans = 1ll * ans * res % MOD;

	}

	cout << 1ll * ans * power(v,n * m - un[(1 << q) - 1]) % MOD << endl;

	return;

} 

int main()

{

	for(int i = 1;i < (1 << MAXN);++i)siz[i] = siz[i >> 1] + (i & 1);

	int testcases;

	scanf("%d",&testcases);

	while(testcases--)work();

	return 0;

}