P3734 [HAOI2017] Number of Plans

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

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 a single integer, the required answer.

[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