Description

Define a relation $\subseteq$ on non-negative integers: if $a \subseteq b$, then $a \land b = a$, where $\land$ denotes the bitwise AND.

Consider an infinite space. You start at $(0, 0, 0)$, and you have three types of moves:

1. $(x, y, z) \to (x', y, z)$ if $x \subseteq x'$.
2. $(x, y, z) \to (x, y', z)$ if $y \subseteq y'$.
3. $(x, y, z) \to (x, y, z')$ if $z \subseteq z'$.

Due to a mysterious force, some points are blocked, i.e., you cannot pass through them. Find the number of ways to reach the point $(n, m, r)$. Output the answer modulo $998244353$.

Input Format

The first line contains three integers $n, m, r$.

The next line contains a single integer $o$, the number of obstacles.

Each of the next $o$ lines contains three integers $x, y, z$ giving the coordinates of an obstacle, where $0 \le x \le n$, $0 \le y \le m$, $0 \le z \le r$. No obstacle is at $(0, 0, 0)$ or $(n, m, r)$, and obstacles are pairwise distinct.

Output Format

Output a single integer, the required answer.

1 1 1
0

6

Hint

[Sample explanation]

There are 8 states: $(0, 0, 0)$, $(0, 0, 1)$, $(0, 1, 0)$, $(0, 1, 1)$, $(1, 0, 0)$, $(1, 0, 1)$, $(1, 1, 0)$, $(1, 1, 1)$. The corresponding numbers of ways are $1, 1, 1, 2, 1, 2, 2, 6$.

[Constraints]

• For $20\%$ of the testdata: $n, m, r \le 100$.
• For $50\%$ of the testdata: $n, m, r \le 10^6$.
• For another $20\%$ of the testdata: $o \le 10$.
• For $100\%$ of the testdata: $n, m, r \le 10^{18}$, $o \le 10^4$.

Translated by ChatGPT 5