Даны три целых числа \(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\).
Выходные данные
Выведите одно целое число — количество различных массивов \(a\), для которых выполняются все приведенные выше условия, по модулю \(998244353\).
Примечание
Можете вспомнить, что такое побитовое И по ссылке.
В первом примере ответом являются следующие массивы: \([3, 3, 7, 6]\), \([3, 7, 7, 6]\) и \([7, 3, 7, 6]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 3 2
1 3 3
3 4 6
|
3
|
|
2
|
5 2 3
1 3 2
2 5 0
3 3 3
|
33
|