题目分析：
最大值为 \(v\) 的限制显然可以转化为 \(\le v\) 的方案数减去 \(\le v-1\) 的方案数。
因为这里有很多个这种限制所以直接容斥就好了，具体来说就是枚举哪些条件取 \(\le v-1\) 那么剩下的就取 \(\le v\)，取 \(n=1\) 手算一下就可以得到容斥系数为 \((-1)^{|S|}\)。
因为 \(n \le 10\) 所以其实对于某一种情况求方案直接暴力就可以了，我们可以将矩阵离散化，这样会用到的点就只有 \(O(n)\) 个，我们可以对于每一个位置求一下其取值范围，下界显然就是 \(1\) 了，而对于上界我们其实就可以将这些限制从紧到松去取，也就是从小到大排序，然后每次进行一个矩阵赋值和矩阵求和，这样限制出来显然是正确的。
代码：
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 105;
const int MOD = 1e9+7;
struct node{
int l1,l2,r1,r2,v;
}a[N],b[N];
int cnt[N][N],l[N],r[N];
bool vis[N][N];
int mod(int x){
return x % MOD;
}
int power(int a,int b){
int res = 1;
while(b){
if(b & 1) res = mod(res * a);
a = mod(a * a);
b >>= 1;
}
return res;
}
bool cmp(node a,node b){
return a.v < b.v;
}
int calc(int l1,int r1,int l2,int r2){
int res = 0;
for(int i=l1; i<l2; i++){
for(int j=r1; j<r2; j++){
if(!vis[i][j]){
res += cnt[i][j];
vis[i][j] = true;
}
}
}
return res;
}
signed main(){
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int T;scanf("%lld",&T);
while(T--){
memset(cnt,0,sizeof(cnt));memset(vis,false,sizeof(vis));
int n,m,limit,h;scanf("%lld%lld%lld%lld",&n,&m,&limit,&h);
int cnt1 = 0,cnt2 = 0;
l[++cnt1] = 1;l[++cnt1] = n+1;
r[++cnt2] = 1;r[++cnt2] = m+1;
for(int i=1; i<=h; i++){
scanf("%lld%lld%lld%lld%lld",&a[i].l1,&a[i].r1,&a[i].l2,&a[i].r2,&a[i].v);
a[i].l2++,a[i].r2++;
l[++cnt1] = a[i].l1;l[++cnt1] = a[i].l2;
r[++cnt2] = a[i].r1;r[++cnt2] = a[i].r2;
}
sort(l+1,l+cnt1+1);sort(r+1,r+cnt2+1);
cnt1 = unique(l+1,l+cnt1+1) - l - 1;
cnt2 = unique(r+1,r+cnt2+1) - r - 1;
for(int i=1; i<=h; i++){
a[i].l1 = lower_bound(l+1,l+cnt1+1,a[i].l1) - l;
a[i].r1 = lower_bound(r+1,r+cnt2+1,a[i].r1) - r;
a[i].l2 = lower_bound(l+1,l+cnt1+1,a[i].l2) - l;
a[i].r2 = lower_bound(r+1,r+cnt2+1,a[i].r2) - r;
}
for(int i=1; i<cnt1; i++){ //我们将每一个点代表它右下角的这一块
for(int j=1; j<cnt2; j++){
cnt[i][j] = mod((l[i+1] - l[i]) * (r[j+1] - r[j]));
}
}
int ans = 0;
for(int S=0; S<(1<<h); S++){
for(int i=1; i<cnt1; i++){
for(int j=1; j<cnt2; j++){
vis[i][j] = false;
}
}
int res = 1;
for(int i=1; i<=h; i++){
b[i] = a[i];
if((S >> (i-1)) & 1) b[i].v--;
}
sort(b+1,b+h+1,cmp);
for(int i=1; i<=h; i++) res = mod(res * power(b[i].v,calc(b[i].l1,b[i].r1,b[i].l2,b[i].r2)));
for(int i=1; i<cnt1; i++){
for(int j=1; j<cnt2; j++){
if(vis[i][j]) continue;
res = mod(res * power(limit,cnt[i][j]));
}
}
if(__builtin_parity(S)) ans = mod(ans + (MOD-1) * res);
else ans = mod(ans + res);
}
printf("%lld\n",ans);
}
return 0;
}
