Cho 3 số nguyên \(n, k, m\) và \(m\) bộ ba số: \((l_1, r_1, x_1), (l_2, r_2, x_2), \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[i] < 2^k \quad (1 \leq i \leq n)\)
• \(a[l_i] \,\text{AND}\, a[l_i + 1] \,\text{AND} \ldots \,\text{AND}\, a[r_i] = x_i \quad (1 \leq i \leq m)\)

(Với AND là phép toán thao tác bit, trong C++ viết là &)

Hai dãy số \((a_n) = \{a_1, a_2, \ldots, a_n\}\) và \((b_n) = \{b_1, b_2, \ldots, b_n\}\) gọi là khác nhau nếu tồn tại chỉ số \(i\) sao cho \(a_i \ne b_i\).

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ố nguyên \(l_i, r_i, x_i\) (\(1 \leq l_i \leq r_i \leq n\); \(0 \leq x_i < 2^k\))

Dữ liệu ra:

• Ghi số lượng dãy số \((a_n)\) thỏa mãn điều kiện của bài toán, chia dư cho 998244353.

Input 1

4 3 2
1 3 3
3 4 6

Output 1

3

Input 2

5 2 3
1 3 2
2 5 0
3 3 3

Output 2

33

Chú ý:

• Trong tất cả các test: \(1 \leq n \leq 5 \cdot 10^5\), \(1 \leq k \leq 30\), \(0 \leq m \leq 5 \cdot 10^5\)
• 20% số điểm ứng với: \(x_i = 2^k - 1\)
• 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 còn lại: không có điều kiện gì thêm