Counting Paths in a Bitwise Subset Lattice

We define a partial order on nonnegative integers by a ⊆ b if and only if \(a \land b = a\), where \(\land\) denotes the bitwise AND operation (in \(\LaTeX\) format). In other words, when the binary representation of \(a\) has its 1-bits in a subset of the positions where \(b\) has 1's, we say \(a \subseteq b\).

Consider an infinite 3D space. You are initially at \((0,0,0)\). In each step you are allowed to perform one of the following three types of moves:

• Move along the x-axis: \((x,y,z) \to (x',y,z)\) if \(x \subseteq x'\) and \(x \neq x'\).
• Move along the y-axis: \((x,y,z) \to (x,y',z)\) if \(y \subseteq y'\) and \(y \neq y'\).
• Move along the z-axis: \((x,y,z) \to (x,y,z')\) if \(z \subseteq z'\) and \(z \neq z'\).

However, due to a mysterious eastern force, some points in the space are blocked and cannot be visited. Given a target point \((n, m, r)\) along with a list of blocked points, count the number of valid paths from \((0,0,0)\) to \((n, m, r)\) using the allowed moves. Since the answer can be very large, output it modulo \(998244353\).

Note: A move only changes one coordinate. In each coordinate the allowed moves are exactly those jumps from the current value \(a\) to any value \(b\) (with \(b \neq a\)) such that \(a \subseteq b\) and where both \(a\) and \(b\) are bitwise subsets of the corresponding target coordinate. For example, if the target in one coordinate is \(n\), then all valid intermediate values in that coordinate are exactly those numbers that can be obtained by choosing a subset of the set bits in the binary representation of \(n\).

inputFormat

The first line contains three nonnegative integers \(n\), \(m\), and \(r\) (in \(\LaTeX\) format as the target point \((n, m, r)\)).

The second line contains a single integer \(k\), the number of blocked points.

Then \(k\) lines follow, each containing three nonnegative integers \(x\), \(y\), and \(z\) representing a blocked point. It is guaranteed that \((0,0,0)\) and \((n, m, r)\) are not blocked.

outputFormat

Output a single integer, the number of valid paths from \((0,0,0)\) to \((n, m, r)\) modulo \(998244353\).

sample

1 1 1
0

6