#2277. 「HAOI2017」方案数

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: __stdcall

题目描述

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

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

  1. (x, y, z) \to (ax, y, z) 当且仅当 x \subseteq ax
  2. (x, y, z) \to (x, ay, z) 当且仅当 y \subseteq ay
  3. (x, y, z) \to (x, y, az) 当且仅当 z \subseteq az

由于来自东方的神秘力量,有些点被屏蔽了,也就是不能经过了。现在问你到某个点 (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
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 \le 100
对于 50\% 的数据, n, m, r \le 10^6
对于另外 20\% 的数据, o \le 10
对于 100\% 的数据, n, m, r \le 10^{18}, o \le 10^4