定义 \(path(x,y,z)\) 表示 从 \((0,0,0)\) 走到 \((x,y,z)\) 的方案数。
显然的经过容斥得到，若 \(r1\le r2,c1\le c2,h1\le h2\)，则 \(ans=path(n,m,w)-path(r1,c1,h1)\times path(n-r1,m-c1,w-h1)-path(r2,c2,h2)\times path(n-r2,m-c2,w-h2)+path(r1,c1,h1)\times path(r2-r1,c2-c1,h2-h1)\times path(n-r2,m-c2,w-h2)\)
若 \(r1\ge r2,c1\ge c2,h1\ge h2\) 同理。
否则， \(ans=path(n,m,w)-path(r1,c1,h1)\times path(n-r1,m-c1,w-h1)-path(r2,c2,h2)\times path(n-r2,m-c2,w-h2)\)
那我们可以定义 \(f(x,a)\) 表示用 \(a\) 个质数走到 \(x\) 的方案数，集合 \(P\) 表示全体素数。
那我们就可以得到 \(f(x,a)=\displaystyle{\sum_{b\in P,b\le x}f(x-b,a-1)}\)。
则 \(\space path(x,y,z)\)
\(\begin{aligned} &=\displaystyle{\sum_{i\le x,j\le y,k\le z}C_{i+j+k}^i\times C_{j+k}^{j}\times f(x,i)\times f(y,j) \times f(z,k)}\\ &=\displaystyle{\sum_{i\le x,j\le y,k\le z}\frac{(i+j+k)!}{i!\times(j+k)!}\times\frac{(j+k)!}{j!\times k!}\times f(x,i)\times f(y,j) \times f(z,k)}\\ &=\displaystyle{\sum_{i\le x,j\le y,k\le z}(i+j+k)!\space\times\frac{f(x,i)}{i!}\times\frac{f(y,j)}{j!}\times\frac{f(z,k)}{k!}}\\ &=\displaystyle{\sum_{l\le x+y,i+j=l}\frac{f(x,i)}{i!}\times\frac{f(y,j)}{j!}\space\sum_{k\le z}(l+k)!\space\times \frac{f(z,k)}{k!}} \end{aligned}\)
复杂度为 \(O(n^2)\)。
#include<bits/stdc++.h>
#define int long long
#define mod 1000000007
using namespace std;
int n,m,w,r1,r2,c1,c2,h1,h2,prime[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997,10000};
int f[1005][1005],C[3005][3005],fac[3005],inv[3005];
int path(int x,int y,int z){
int ans=0;
for(int l=0;l<=x+y;l++){
int aa=0,bb=0;
for(int i=0;i<=l;i++)if(i<=x&&l-i<=y){
aa+=f[x][i]*inv[i]%mod*f[y][l-i]%mod*inv[l-i]%mod;
}
for(int k=0;k<=z;k++)bb+=fac[l+k]*f[z][k]%mod*inv[k]%mod;
aa%=mod,bb%=mod;
ans+=aa*bb%mod;
}
return ans%mod;
}
int ksm(int x,int y){
int res=1;
while(y){
if(y&1)res=res*x%mod;
x=x*x%mod;
y>>=1;
}
return res;
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
f[0][0]=1;
for(int i=1;i<=1000;i++)for(int j=1;j<=i/2;j++){
for(int k=0;;k++){
if(prime[k]>i)break;
f[i][j]+=f[i-prime[k]][j-1];
f[i][j]%=mod;
}
}
fac[0]=1;
for(int i=1;i<=3000;i++)fac[i]=fac[i-1]*i%mod;
inv[3000]=ksm(fac[3000],mod-2);
for(int i=2999;~i;i--)inv[i]=inv[i+1]*(i+1)%mod;
cin>>n>>m>>w>>r1>>c1>>h1>>r2>>c2>>h2;
n--,m--,w--,r1--,c1--,h1--,r2--,c2--,h2--;
if(r1>=r2&&c1>=c2&&h1>=h2){
swap(r1,r2);
swap(c1,c2);
swap(h1,h2);
}
if(r1<=r2&&c1<=c2&&h1<=h2){
int ans=(path(n,m,w)-path(r1,c1,h1)*path(n-r1,m-c1,w-h1)%mod-path(r2,c2,h2)*path(n-r2,m-c2,w-h2)%mod+path(r1,c1,h1)*path(r2-r1,c2-c1,h2-h1)%mod*path(n-r2,m-c2,w-h2)%mod+3ll*mod)%mod;
cout<<ans;
return 0;
}
int ans=(path(n,m,w)-path(r1,c1,h1)*path(n-r1,m-c1,w-h1)%mod-path(r2,c2,h2)*path(n-r2,m-c2,w-h2)%mod+3ll*mod)%mod;
cout<<ans;
return 0;
}