[HAOI2017]方案数

题目描述

考虑定义非负整数间的“$ \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 \le x \le n, 0 \le y \le m, 0 \le z \le r $,且障碍物不在 $ (0, 0, 0) $ 和 $ (n, m, r) $ 上,障碍物不会重复。

输出格式


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

输入输出样例

输入样例 #1

1 1 1
0

输出样例 #1

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 \le 100 $ 对于 $ 50\% $ 的数据,满足:$ n, m, r \le 10^6 $ 对于另外 $ 20\% $ 的数据,满足:$ o \le 10 $ 对于 $ 100\% $ 的数据,满足:$ n, m, r \le 10^{18}, o \le 10^4 $