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

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

Для некоторых промежутков времени известны ограничения. Каждое ограничение задаётся тройкой l, r, x и означает следующее:

• если рассмотреть все слоты с номерами от l до r, то побитовое OR всех значений на этом отрезке равно x.

То есть должно выполняться:

a_l OR a_{l+1} OR ... OR a_r = x

Назовём сеансом наблюдения любой непустой набор временных слотов. Значение сеанса равно побитовому XOR всех чисел a_i, входящих в этот набор.

Требуется для каждого набора ограничений определить сумму значений по всем непустым сеансам наблюдения.

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

Формат входных данных

В первой строке содержится целое число t — количество наборов данных.

Далее следуют описания наборов данных.

Для каждого набора данных:

• в первой строке записаны два целых числа n и m — количество временных слотов и количество ограничений;
• в следующих m строках записаны по три целых числа l, r, x, описывающих очередное ограничение.

Гарантируется, что существует хотя бы один массив a, удовлетворяющий всем ограничениям.

Формат выходных данных

Для каждого набора данных выведите одно целое число — сумму XOR по всем непустым сеансам наблюдения по модулю 10^9 + 7.

Пример

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

2
3 1
1 3 5
4 2
1 2 3
3 4 1

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

20
24

Пояснение к примеру

В первом наборе общий набор возможных битов определяется числом 5. Тогда искомая сумма по всем непустым наборам слотов равна 5 * 2^(3-1) = 20.

Во втором наборе общий побитовый OR по всем ограничениям равен 3. Тогда ответ равен 3 * 2^(4-1) = 24.

Ограничения

• 1 <= t <= 10^4
• 1 <= n, m <= 2 * 10^5
• 1 <= l <= r <= n
• 0 <= x < 2^30
• сумма всех n по всем наборам данных не превосходит 2 * 10^5
• сумма всех m по всем наборам данных не превосходит 2 * 10^5