定义 $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)$。