F. Отрезки И
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Даны три целых числа $$$n$$$, $$$k$$$, $$$m$$$ и $$$m$$$ условий $$$(l_1, r_1, x_1), (l_2, r_2, x_2), \dots, (l_m, r_m, x_m)$$$.

Посчитайте количество различных массивов $$$a$$$, состоящих из $$$n$$$ целых чисел, таких что:

  • $$$0 \le a_i < 2^k$$$ для всех $$$1 \le i \le n$$$;
  • побитовое И чисел $$$a[l_i] \& a[l_i + 1] \& \dots \& a[r_i] = x_i$$$ для всех $$$1 \le i \le m$$$.

Два массива $$$a$$$ и $$$b$$$ считаются различными, если существует такая позиция $$$i$$$, что $$$a_i \neq b_i$$$.

Это число может быть довольно велико, поэтому выведите его по модулю $$$998244353$$$.

Входные данные

В первой строке записаны три целых числа $$$n$$$, $$$k$$$ и $$$m$$$ ($$$1 \le n \le 5 \cdot 10^5$$$, $$$1 \le k \le 30$$$, $$$0 \le m \le 5 \cdot 10^5$$$) — длина массива $$$a$$$, значение такое, что все числа в массиве $$$a$$$ должны быть меньше, чем $$$2^k$$$, и количество условий соответственно.

В каждой из следующих $$$m$$$ строк записано одно условие $$$l_i$$$, $$$r_i$$$ и $$$x_i$$$ ($$$1 \le l_i \le r_i \le n$$$, $$$0 \le x_i < 2^k$$$) — границы отрезка условия и необходимое значение побитового И на нем.

Выходные данные

Выведите одно целое число — количество различных массивов $$$a$$$, для которых выполняются все приведенные выше условия, по модулю $$$998244353$$$.

Примеры
Входные данные
4 3 2
1 3 3
3 4 6
Выходные данные
3
Входные данные
5 2 3
1 3 2
2 5 0
3 3 3
Выходные данные
33
Примечание

Можете вспомнить, что такое побитовое И по ссылке.

В первом примере ответом являются следующие массивы: $$$[3, 3, 7, 6]$$$, $$$[3, 7, 7, 6]$$$ и $$$[7, 3, 7, 6]$$$.