题目描述

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

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

1. $ (x, y, z) \to (x', y, z) $ 当且仅当 $ x \subseteq x' $；
2. $ (x, y, z) \to (x, y', z) $ 当且仅当 $ y \subseteq y' $；
3. $ (x, y, z) \to (x, y, z') $ 当且仅当 $ 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) $ 上，障碍物不会重复。

输出格式

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

样例

input

1 1 1
0

output

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 $。