相当于将二进制下为 $0$ 的位置选至少 $1$ 个变成 $1$。

设 $f_{i,j,k}$ 表示在三维坐标二进制下分别改变了 $x,y,z$ 个 $0$ 的方案数。

:::warning[注意] 这里不是三维的答案相乘，因为是有改变相当于移动是有顺序的，如 $(0,0,0)\to(0,1,0)\to(1,1,0)$ 与 $(0,0,0)\to(1,0,0)\to(1,1,0)$ 是两种方案。 :::

有转移：

$$f_{i,j,k}= \sum_{x=1}^{i-1} \binom{i}{x}f_{x,j,k} +\sum_{x=1}^{j-1} \binom{j}{x}f_{i,x,k} +\sum_{x=1}^{k-1} \binom{k}{x}f_{i,j,x}$$

解释（第一项，其它的是类似的）:

对于 $i$，可以考虑少改变 $i-x$ 位得到 $x$。这些位置可以在 $i$ 个位置任选，方案数为 $\dbinom{i}{i-x}=\dbinom{i}{x}$。

由于每次移动坐标只能增大，先将所有障碍按字典序排序消除 DP 的后效性。

设 $g_i$ 为到达第 $i$ 个点且不经过前 $i-1$ 个点的方案数。

转移时考虑容斥，用全部方案数减去不合法的方案数。

对于每个 $j<i$，若满足 $x_j\subseteq x_i\wedge y_j\subseteq y_i\wedge z_j\subseteq z_i$，则可能到达 $i$。

记 $P(x)$ 表示 $x$ 二进制下 $1$ 的数量。

从 $j$ 到达 $i$ 有 $f_{P(x_i)-P(x_j),P(y_i)-P(y_j),P(z_i)-P(z_j)}$ 种方案，记为 $k$。

因此有：

$$g_{i}=f_{P(x_i),P(y_i),P(z_i)}-\sum_{j=1}^{i-1} [x_j\subseteq x_i\wedge y_j\subseteq y_i\wedge z_j\subseteq z_i]k\cdot g_j$$

为方便统计答案可以将终点也看作障碍点，由题目约束可知其排序后的位置一定在最后一个，答案即为 $g_{o+1}$。

#include<bits/stdc++.h>
#define P(x) __builtin_popcountll(x)
using namespace std;
using ll=long long;
const int V=70,N=10005,P=998244353;
struct Point{ll x,y,z;}a[N];
int n,f[N],C[V][V],vis[V][V][V];
int DP(int x,int y,int z){
	if(vis[x][y][z]) return vis[x][y][z];int res=0;
	for(int i=0;i<x;i++) res=(res+1ll*DP(i,y,z)*C[x][i])%P;
	for(int i=0;i<y;i++) res=(res+1ll*DP(x,i,z)*C[y][i])%P;
	for(int i=0;i<z;i++) res=(res+1ll*DP(x,y,i)*C[z][i])%P;
	return vis[x][y][z]=res;
}
int main(){
	vis[0][0][0]=1;for(int i=0;i<V;i++) C[i][0]=1;
	for(int i=1;i<V;i++) for(int j=1;j<=i;j++)
		(C[i][j]=C[i-1][j-1]+C[i-1][j])>P?(C[i][j]-=P):0;
	scanf("%lld%lld%lld%d",&a[0].x,&a[0].y,&a[0].z,&n);
	for(int i=1;i<=n;i++) scanf("%lld%lld%lld",&a[i].x,&a[i].y,&a[i].z);
	sort(a,a+n+1,[](Point u,Point v){return u.x^v.x?u.x<v.x:u.y^v.y?u.y<v.y:u.z<v.z;});
	auto Out=[](int x,int y){return a[x].x&a[y].x^a[y].x|a[x].y&a[y].y^a[y].y|a[x].z&a[y].z^a[y].z;};
	for(int i=0;i<=n;i++){f[i]=DP(P(a[i].x),P(a[i].y),P(a[i].z));for(int j=0;j<i;j++) if(!Out(i,j))
		f[i]=(f[i]-1ll*f[j]*DP(P(a[i].x^a[j].x),P(a[i].y^a[j].y),P(a[i].z^a[j].z)))%P;}
	return printf("%d",(f[n]+P)%P),0;
}