CF1327F AND Segments

You are given three integers $ n $ , $ k $ , $ m $ and $ m $ conditions $ (l_1, r_1, x_1), (l_2, r_2, x_2), \dots, (l_m, r_m, x_m) $ . Calculate the number of distinct arrays $ a $ , consisting of $ n $ integers such that: - $ 0 \le a_i < 2^k $ for each $ 1 \le i \le n $ ; - bitwise AND of numbers $ a[l_i] \& a[l_i + 1] \& \dots \& a[r_i] = x_i $ for each $ 1 \le i \le m $ . Two arrays $ a $ and $ b $ are considered different if there exists such a position $ i $ that $ a_i \neq b_i $ . The number can be pretty large so print it modulo $ 998244353 $ .

The first line contains three integers $ n $ , $ k $ and $ m $ ( $ 1 \le n \le 5 \cdot 10^5 $ , $ 1 \le k \le 30 $ , $ 0 \le m \le 5 \cdot 10^5 $ ) — the length of the array $ a $ , the value such that all numbers in $ a $ should be smaller than $ 2^k $ and the number of conditions, respectively. Each of the next $ m $ lines contains the description of a condition $ l_i $ , $ r_i $ and $ x_i $ ( $ 1 \le l_i \le r_i \le n $ , $ 0 \le x_i < 2^k $ ) — the borders of the condition segment and the required bitwise AND value on it.

Print a single integer — the number of distinct arrays $ a $ that satisfy all the above conditions modulo $ 998244353 $ .

You can recall what is a bitwise AND operation [here](https://en.wikipedia.org/wiki/Bitwise_operation#AND). In the first example, the answer is the following arrays: $ [3, 3, 7, 6] $ , $ [3, 7, 7, 6] $ and $ [7, 3, 7, 6] $ .