Cho 3 số nguyên \(n,k,m\) và m bộ ba số: \(\left( l_{1},\ r_{1},x_{1} \right);\left( l_{2},r_{2},x_{2} \right);\ldots.(l_{m},r_{m},x_{m})\).

Yêu cầu của bài toán: Đếm số lượng dãy số \((a_{n})\) gồm n phần tử thỏa mãn tất cả các điều kiện sau:

• \(0 \leq a\lbrack i\rbrack < 2^{k}\ (1 \leq i \leq n)\)

• \(a\left\lbrack l_{i} \right\rbrack\ AND\ a\left\lbrack l_{i} + 1 \right\rbrack AND\ldots.AND\ a\left\lbrack r_{i} \right\rbrack = x_{i}\ (1 \leq i \leq m)\) (với AND là phép toán thao tác bit, trong C++ ta viết là &)

Hai dãy số \(\left( a_{n} \right) = \left\{ a_{1},a_{2},\ldots,a_{n} \right\}\) và \(\left( b_{n} \right) = \left\{ b_{1},b_{2},\ldots,b_{n} \right\}\) gọi là khác nhau nếu tồn tại chỉ số \(i\) thỏa mãn: \(a_{i}
eq b_{i}(1 \leq i \leq n)\)

Dữ liệu vào:

• Dòng đầu tiên gồm 3 số nguyên \(n,k,m\)

• \(m\) dòng tiếp theo, mỗi dòng gồm 3 số \(l_{i},\ r_{i},\ x_{i}(1 \leq l_{i} \leq r_{i} \leq n;0 \leq x_{i} < 2^{k})\)

Kết quả: ghi số lượng dãy số \((a_{n})\) thỏa mãn điều kiện của bài toán, chia lấy dư cho 998244353.

Chú ý:

• Trong tất cả các test: \(1 \leq n \leq 5 \times 10^{5};1 \leq k \leq 30;0 \leq m \leq 5 \times 10^{5}\)

• 20% số điểm ứng với: \(x_{i} = 2^{k} - 1\ (1 \leq i \leq m)\)

• 30% số điểm ứng với: \(n,m,k \leq 18\)

• 20% số điểm ứng với : \(n \leq 1000\)

• 30% số điểm không có điều kiện gì thêm