Consider the definition of "$\subseteq$" between non-negative integers: $a \subseteq b$ if and only if $a \land b = a$, where $\land$ denotes the bitwise AND operation.

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

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

Due to mysterious forces from the East, some points are blocked and cannot be visited. Calculate the number of ways to reach a target point $(n, m, r)$, modulo $998244353$.

Input

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

The next line contains an integer $o$, representing the number of obstacles.

The next $o$ lines each contain three integers $x, y, z$ representing the coordinates of an obstacle, where $0 \le x \le n, 0 \le y \le m, 0 \le z \le r$. Obstacles are not located at $(0, 0, 0)$ or $(n, m, r)$, and no two obstacles are at the same position.

Output

Output a single integer representing the required answer.

Examples

Input 1

1 1 1
0

Output 1

6

Note 1

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 number of ways to reach them are $1, 1, 1, 2, 1, 2, 2, 6$ respectively.

Subtasks

For $20\%$ of the data, $n, m, r \le 100$.

For $50\%$ of the data, $n, m, r \le 10^6$.

For another $20\%$ of the data, $o \le 10$.

For $100\%$ of the data, $n, m, r \le 10^{18}, o \le 10^4$.