2672. [HAOI 2017]方案数

【题目描述】

考虑定义非负整数间的“$\subseteq$”，如果 $a\subseteq b$，那么 $a \land b = a$，其中 $\land$ 表示二进制下的“与”操作。

考虑现在有一个无限大的空间，现在你在 $(0,0,0)$，有三种位移操作。

一、$(x,y,z)\to(x',y,z)$ if $x\subseteq x'$

二、$(x,y,z)\to(x,y',z)$ if $y\subseteq y'$

三、$(x,y,z)\to(x,y,z')$ if $z\subseteq z'$

由于来自东方的神秘力量，有些点被屏蔽了，也就是不能经过了。现在问你到某个点 $(n,m,r)$ 的方案数，答案对 $998244353$ 取模。

【输入格式】

第一行三个整数 $n,m,r$。

接下来一行一个整数$o$，表示障碍物的数量。

接下来 $o$ 行，每行三个整数 $x,y,z$ 表示障碍物的坐标，$0\leq x\leq n,0\leq y\leq m,0\leq z\leq r$，且障碍物不在 $(0,0,0)$ 和 $(n,m,r)$ 上，障碍物不会重复。

【输出格式】

一行一个整数，代表要求的答案。

【样例输入】

1 1 1
0

【样例输出】

6 

【样例解释】

有8种状态（0,0,0),(0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1),分别方案数为 1,1,1,2,1,2,2,6。

【数据规模喝约定】

对于 20% 的数据，满足：$n, m, r \leq 100$

对于 50% 的数据，满足：$n, m, r \leq 10^6$

对于另外 20% 的数据，满足：$o \leq 10$

对于 100% 的数据，满足：$n, m, r \le 10^{18}, o \le 10^4$

【来源】

HAOI 2017