C. Divan и битовые операции
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Однажды Divan проанализировал последовательность $$$a_1, a_2, \ldots, a_n$$$, состоящую из $$$n$$$ целых неотрицательных чисел, следующим образом. Он рассмотрел все непустые подпоследовательности последовательности $$$a$$$, вычислил побитовое исключающее ИЛИ её элементов, после чего просуммировал все полученные результаты, получив удобство последовательности $$$a$$$.

Напомним, что последовательность $$$c$$$ является подпоследовательностью последовательности $$$d$$$, если $$$c$$$ может быть получена из $$$d$$$ путем удаления нескольких элементов (возможно, ни одного). Например, $$$[1, \, 2, \, 3, \, 4]$$$, $$$[2, \, 4]$$$ и $$$[2]$$$ являются подпоследовательностями $$$[1, \, 2, \, 3, \, 4]$$$, а $$$[4, \, 3]$$$ и $$$[0]$$$ не являются.

Divan очень гордился проведенным анализом, но теперь потерял и последовательность $$$a$$$, и значение ее удобства! Однако Divan помнит значение побитового ИЛИ на $$$m$$$ непрерывных подотрезках последовательности $$$a$$$. Оказалось, что каждый элемент последовательности входит хотя бы в один из этих $$$m$$$ отрезков.

Divan просит вас найти удобство последовательности $$$a$$$, используя информацию, которую он помнит. Если возможны несколько значений удобства, выведите любое.

Так как ответ может быть большим, выведите его по модулю $$$10^9 + 7$$$.

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

Каждый тест содержит несколько наборов входных данных.

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^3$$$) — количество наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$) — количество чисел в последовательности и количество отрезков, значения побитового ИЛИ которых смог запомнить Divan, соответственно.

Далее идут $$$m$$$ строк, в которых содержатся описания отрезков по одному в строке.

Каждый отрезок задаётся тремя целыми числами $$$l$$$, $$$r$$$ и $$$x$$$ ($$$1 \le l \le r \le n$$$, $$$0 \le x \le 2^{30} - 1$$$) — левая и правая граница отрезка, а также значение побитового ИЛИ элементов $$$a_l, a_{l + 1}, \ldots, a_r$$$, соответственно.

Гарантируется, что каждый элемент последовательности входит хотя бы в один из данных отрезков. Гарантируется, что существует последовательность, которая удовлетворяет всем данным ограничениям.

Гарантируется, что сумма значений $$$n$$$, а также сумма значений $$$m$$$ по всем наборам входных данных не превосходят $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите любое возможное удобство последовательности $$$a$$$ по модулю $$$10^9 + 7$$$.

Пример
Входные данные
3
2 1
1 2 2
3 2
1 3 5
2 3 5
5 4
1 2 7
3 3 7
4 4 0
4 5 2
Выходные данные
4
20
112
Примечание

В первом примере одной из последовательностей, которая подходит под ограничения, является $$$[0, 2]$$$. Рассмотрим все её непустые подпоследовательности:

  • $$$[0]$$$: побитовое исключающее ИЛИ равно $$$0$$$;
  • $$$[2]$$$: побитовое исключающее ИЛИ равно $$$2$$$;
  • $$$[0, 2]$$$: побитовое исключающее ИЛИ равно $$$2$$$.

Суммируя полученные числа, получаем $$$4$$$, что является ответом.

Во втором примере одной из последовательностей, которая подходит под ограничения, является $$$[0, \, 5, \, 5]$$$.

В третьем примере одной из последовательностей, которая подходит под ограничения, является $$$[5, \, 6, \, 7, \, 0, \, 2]$$$.