Once Divan analyzed a sequence $a_1, a_2, \ldots, a_n$ consisting of $n$ non-negative integers as follows. He considered each non-empty subsequence of the sequence $a$, computed the bitwise XOR of its elements and added up all the XORs, obtaining the coziness of the sequence $a$.

A sequence $c$ is a subsequence of a sequence $d$ if $c$ can be obtained from $d$ by deletion of several (possibly, zero or all) elements. For example, $[1, \, 2, \, 3, \, 4]$, $[2, \, 4]$, and $[2]$ are subsequences of $[1, \, 2, \, 3, \, 4]$, but $[4, \, 3]$ and $[0]$ are not.

Divan was very proud of his analysis, but now he lost the sequence $a$, and also the coziness value! However, Divan remembers the value of bitwise OR on $m$ contiguous subsegments of the sequence $a$. It turns out that each element of the original sequence is contained in at least one of these $m$ segments.

Divan asks you to help find the coziness of the sequence $a$ using the information he remembers. If several coziness values are possible, print any.

As the result can be very large, print the value modulo $10^9 + 7$.


-----Input-----

The first line contains one integer number $t$ ($1 \le t \le 10^3$) — the number of test cases.

The first line of each test case contains two integer numbers $n$ and $m$ ($1 \le n, m \le 2 \cdot 10^5$) — the length of the sequence and the number of contiguous segments whose bitwise OR values Divan remembers, respectively.

The following $m$ lines describe the segments, one per line.

Each segment is described with three integers $l$, $r$, and $x$ ($1 \le l \le r \le n$, $0 \le x \le 2^{30} - 1$) — the first and last elements of the segment and the bitwise OR of $a_l, a_{l + 1}, \ldots, a_r$, respectively.

It is guaranteed that each element of the sequence is contained in at least one of the segments. It is guaranteed that there exists a sequence that satisfies all constraints.

It is guaranteed that the sum of $n$ and the sum of $m$ over all test cases do not exceed $2 \cdot 10^5$.


-----Output-----

For each test case print the coziness any suitable sequence $a$ modulo $10^9 + 7$.


-----Examples-----

Input
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
Output
4
20
112


-----Note-----

In first example, one of the sequences that fits the constraints is $[0, 2]$. Consider all its non-empty subsequences:

$[0]$: the bitwise XOR of this subsequence is $0$;

$[2]$: the bitwise XOR of this subsequence is $2$;

$[0, 2]$: the bitwise XOR of this subsequence is $2$.

The sum of all results is $4$, so it is the answer.

In second example, one of the sequences that fits the constraints is $[0, \, 5, \, 5]$.

In third example, one of the sequences that fits the constraints is $[5, \, 6, \, 7, \, 0, \, 2]$.

Difficulty: MEDIUM
Tags: Bit manipulation

Constructive algorithms

Combinatorics

Dynamic programming

Mathematics
Skill types: Dynamic programming

Bit manipulation

Starter code:

Solutions:
import sys
input = sys.stdin.readline

def inp():
	return int(input())

def st():
	return input().rstrip('\n')

def lis():
	return list(map(int, input().split()))

def ma():
	return map(int, input().split())
t = inp()
while t:
	t -= 1
	(n, m) = ma()
	p = 10 ** 9 + 7
	x = 0
	for i in range(m):
		(l, r, x1) = ma()
		x = x | x1
	x = x * 2 ** (n - 1)
	x %= p
	print(x)


import sys
input = sys.stdin.readline
mod = 10 ** 9 + 7
for _ in ' ' * int(input()):
	(n, m) = map(int, input().split())
	res = 0
	for _ in ' ' * m:
		(l, r, x) = map(int, input().split())
		res |= x
	print(res * pow(2, n - 1, mod) % mod)


from sys import stdin
import math
from collections import deque
from heapq import heapify, heappop, heappush
from bisect import bisect_left, bisect_right
input = stdin.readline
(power, mod) = ({}, 1000000007)

def getpower(k):
	if k == 0:
		return 1
	if k == 1:
		return 2
	if k in power:
		return power[k]
	power[k] = getpower(k // 2) * getpower(k - k // 2) % mod
	return power[k]
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	(arr, mod, easy) = ([], 1000000007, [0] * 30)
	powerval = getpower(n - 1)
	easy = 0
	for _ in range(m):
		(l, r, x) = map(int, input().split())
		easy = easy | x
	(value, total) = (1, 0)
	for i in range(30):
		if easy % 2 == 0:
			value = value * 2 % mod
			easy = easy // 2
			continue
		total += value
		total = total % mod
		value = value * 2
		value = value % mod
		easy = easy // 2
	print(total * powerval % mod)


import sys
mod = 10 ** 9 + 7
input = sys.stdin.readline
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	orx = 0
	for j in range(m):
		(l, r, orc) = map(int, input().split())
		orx = orx | orc
	print(orx * pow(2, n - 1, mod) % mod)


import sys
import bisect
import math
from collections import deque
input = lambda : sys.stdin.readline().strip()
mod = 10 ** 9 + 7

def solve():
	(n, k) = map(int, input().split())
	bits = 0
	for _t in range(k):
		(l, r, x) = map(int, input().split())
		bits |= x
	return bits * pow(2, n - 1, mod) % mod
t = 1
t = int(input())
for _ in range(t):
	print(solve())


import sys
input = sys.stdin.readline

def solve(n, m, Q):
	mo = 10 ** 9 + 7
	curr = 0
	for (l, r, x) in Q:
		curr |= x
	print(curr * pow(2, n - 1, mo) % mo)
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	Q = [tuple(map(int, input().split())) for _ in range(m)]
	solve(n, m, Q)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	xor = 0
	mod = 1000000007

	def fun(n):
		if n == 0:
			return 1
		if n == 1:
			return 2
		t = fun(n // 2)
		if n % 2 == 0:
			return t * t % mod
		return t * (t * 2) % mod % mod
	for i in range(m):
		l = list(map(int, input().split()))
		xor |= l[2]
	print(fun(n - 1) * xor % mod)


p = int(input())
for _ in range(p):
	n = input().split(' ')
	(n, k) = (int(n[0]), int(n[1]))
	m = 0
	mod = 10 ** 9 + 7
	for i in range(k):
		x = input().split()
		m = m | int(x[2])
	n = n - 1
	ans = 1
	res = 2
	while n > 0:
		if n & 1:
			ans = ans * res % mod
		res = res * res % mod
		n = n >> 1
	print(m * ans % mod)


mod = 10 ** 9 + 7

def power(a, b):
	if b == 0:
		return 1
	ax = power(a, int(b / 2))
	ax = ax * ax % mod
	if b % 2 == 1:
		ax = ax * a % mod
	return ax
p = int(input())
for _ in range(p):
	n = input().split(' ')
	(n, k) = (int(n[0]), int(n[1]))
	m = 0
	for i in range(k):
		x = input().split()
		m = m | int(x[2])
	ans = power(2, n - 1)
	print(m * ans % mod)


import math
from heapq import heappush, heappop, heapify
import random
import string
from collections import deque
from bisect import bisect, bisect_left, bisect_right, insort
import sys
input = sys.stdin.readline
S = lambda : input().rstrip()
I = lambda : int(S())
M = lambda : map(int, S().split())
L = lambda : list(M())
mod1 = 1000000000 + 7
mod2 = 998244353
for _ in range(I()):
	(n, m) = M()
	s = 0
	for i in range(m):
		(l, r, x) = M()
		s |= x
	print(s * (1 << n - 1) % mod1)


mod = 1000000007

def f():
	(n, m) = map(int, input().split())
	s = 0
	for i in range(m):
		(l, r, x) = map(int, input().split())
		s |= x
	return int(s * pow(2, n - 1, mod)) % mod
for _ in range(int(input())):
	print(f())


import itertools
import functools

def main():
	t = int(input())
	for _ in range(t):
		(n, m) = map(int, input().split())
		s = 0
		for _ in range(m):
			(l, r, x) = map(int, input().split())
			s = s | x
		print(2 ** (n - 1) * s % 1000000007)
main()


MOD = 1000000007

def solve():
	(n, m) = [int(x) for x in input().split()]
	k = 0
	for i in range(m):
		(a, b, c) = [int(x) for x in input().split()]
		k = k | c
	print(k * pow(2, n - 1, MOD) % MOD)
for i in range(int(input())):
	solve()


from collections import Counter, deque
from sys import stdout
import time
from math import factorial, log

def main():
	(n, m) = [int(i) for i in input().split()]
	global_or = 0
	for i in range(m):
		(_, __, _and) = [int(i) for i in input().split()]
		global_or |= _and
	print(global_or * pow(2, n - 1, mod) % mod)
mod = 10 ** 9 + 7
for t in range(int(input())):
	main()


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	xo = 0
	for i in range(m):
		(l, r, x) = map(int, input().split())
		xo = xo | x
	ans = pow(2, n - 1, 10 ** 9 + 7)
	ans *= xo
	print(ans % (10 ** 9 + 7))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	bits = 0
	mod = 10 ** 9 + 7
	(a, b, c) = map(int, input().split())
	ans = c
	for i in range(m - 1):
		(d, e, f) = map(int, input().split())
		ans |= f
	print(ans % mod * (pow(2, n - 1) % mod) % mod)


for _ in range(int(input())):
	(y, [n, m]) = (0, map(int, input().split()))
	for i in range(m):
		y |= [int(x) for x in input().split()][2]
	print(2 ** (n - 1) * y % (10 ** 9 + 7))


(MOD, T) = (10 ** 9 + 7, int(input()))
for CASE in range(T):
	(n, m) = map(int, input().split())
	a = 0
	for i in range(m):
		(l, r, x) = map(int, input().split())
		a = a | x
	print(a * pow(2, n - 1, MOD) % MOD)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	x = 0
	for j in range(m):
		(l, r, o) = map(int, input().split())
		x |= o
	mod = 1000000007
	c = pow(2, n - 1, mod) % mod
	c = c % mod * x % mod % mod
	print(c)


def power_of_two(base, n):
	mod = 1000000007
	if n == 1:
		return 2
	if n == 0:
		return 1
	if n % 2 == 0:
		val = power_of_two(base, n / 2)
		return val % mod * (val % mod) % mod
	else:
		val = 2 * (power_of_two(base, n - 1) % mod) % mod
		return val % mod
t = int(input())
for i in range(0, t):
	mod = 1000000007
	l1 = [int(x) for x in input().split()]
	n = l1[0]
	m = l1[1]
	or_val = 0
	for j in range(0, m):
		l2 = [int(x) for x in input().split()]
		or_val = or_val | l2[2]
	powerval = power_of_two(2, n - 1)
	ans = powerval % mod * (or_val % mod) % mod
	print(ans)


t = int(input())
mod = 1000000007
for _ in range(t):
	(n, m) = map(int, input().split())
	or_of_all = 0
	for i in range(m):
		(l, r, x) = map(int, input().split())
		or_of_all |= x
	ans = or_of_all * 2 ** (n - 1)
	print(ans % mod)


M = 10 ** 9 + 7

def xorSum(arr, n):
	bits = 0
	for i in range(len(arr)):
		bits |= arr[i]
	ans = bits * pow(2, n - 1)
	ans %= M
	return ans
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	arr = []
	for i in range(m):
		(l, r, val) = map(int, input().split())
		arr.append(val)
	print(xorSum(arr, n))


mod = 10 ** 9 + 7
for _ in range(int(input())):
	z = 0
	(n, k) = map(int, input().split())
	for i in range(k):
		(l, r, p) = map(int, input().split())
		z |= p
	print(z * pow(2, n - 1, mod) % mod)


for _ in range(int(input())):
	(n, m) = map(int, input().split(' '))
	here = 0
	mod = int(1000000000.0 + 7)
	for y in range(m):
		(l, r, x) = map(int, input().split(' '))
		here |= x
	print(pow(2, n - 1, mod) * here % mod)


t = int(input())
MOD = int(1000000000.0 + 7)
for _ in range(t):
	(n, m) = map(int, input().split())
	acc = 0
	for i in range(m):
		(_, _, x) = map(int, input().split())
		acc |= x
	print(acc * pow(2, n - 1, MOD) % MOD)


MOD = int(1000000000.0 + 7)
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	s = 0
	for i in range(m):
		(l, r, k) = map(int, input().split())
		s |= k
	print(s * pow(2, n - 1, MOD) % MOD)


I = lambda : [*map(int, input().split())]
M = 10 ** 9 + 7
for _ in [0] * I()[0]:
	(n, m) = I()
	o = 0
	for i in range(m):
		o |= I()[2]
	print(o * 2 ** (n - 1) % M)


mod = 10 ** 9 + 7
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	ans = 0
	for i in range(k):
		(a, b, c) = map(int, input().split())
		ans = ans | c
	print(pow(2, n - 1, mod) * (ans % mod) % mod)


import math
from collections import defaultdict
mod = 10 ** 9 + 7

def bexp(a, b):
	res = 1
	while b:
		if b % 2:
			res = res * a % mod
			b = b - 1
		else:
			a = a * a % mod
			b = b // 2
	return res
for cases in range(int(input())):
	(n, m) = map(int, input().split())
	xor = 0
	for i in range(0, m):
		(l, r, x) = map(int, input().split())
		xor = xor | x
	ans = bexp(2, n - 1)
	ans = ans * xor % mod
	print(ans)


t = eval(input())
for i in range(t):
	(n, m) = map(int, input().split())
	result = 0
	for j in range(m):
		(l, r, x) = map(int, input().split())
		result = result | x
	print(result * 2 ** (n - 1) % (10 ** 9 + 7))


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	X = 0
	for j in range(m):
		(l, r, x) = map(int, input().split())
		X |= x
	ans = X * 2 ** (n - 1)
	print(ans % (10 ** 9 + 7))


t = int(input())
rajawat = 10 ** 9 + 7
for test in range(t):
	(n, m) = map(int, input().split())
	temp = 0
	for k in range(m):
		lks = list(map(int, input().split()))
		temp |= lks[-1]
	print(temp * 2 ** (n - 1) % rajawat)


mod = 10 ** 9 + 7
t = int(input())
for _ in range(t):
	(n, m) = [int(i) for i in input().split(' ')]
	ans = 0
	for i in range(m):
		(l, r, x) = [int(i) for i in input().split(' ')]
		ans |= x
	print(pow(2, n - 1, mod) * ans % mod)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	oor = -1
	for i in range(m):
		(l, r, x) = map(int, input().split())
		if i == 0:
			oor = x
		else:
			oor = oor | x
	print(2 ** (n - 1) * oor % (10 ** 9 + 7))


import math
t = int(input())
for alp in range(t):
	(n, m) = [int(x) for x in input().split()]
	mx = 31
	v = []
	a = 0
	for i in range(m):
		(l, r, x) = [int(x) for x in input().split()]
		a = a | x
	mod = int(1000000000.0 + 7)
	temp = pow(2, n - 1, mod) * a % mod
	print(int(temp))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	xor = 0
	for i in range(m):
		A = list(map(int, input().split()))
		xor = xor | A[2]
	ans = 2 ** (n - 1) * xor
	print(ans % 1000000007)


def input_int():
	return int(input())

def input_multiple():
	return map(int, input().split())
t = input_int()
while t > 0:
	(n, m) = input_multiple()
	or_value = 0
	for i in range(m):
		(l, r, x) = input_multiple()
		or_value |= x
	print(or_value * 2 ** (n - 1) % 1000000007)
	t -= 1


t = int(input())
mod = 1000000007

def power(n):
	if n == 1:
		return 2
	if n == 0:
		return 1
	ans = power(n // 2)
	if n % 2 != 0:
		return ans * (ans * 2) % mod % mod
	else:
		return ans * ans % mod
while t > 0:
	(n, m) = list(map(int, input().split()))
	total_or = 0
	for i in range(m):
		tmp = list(map(int, input().split()))
		total_or |= tmp[2]
	ans = total_or * power(n - 1) % mod
	print(ans)
	t = t - 1


mod = 10 ** 9 + 7
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	k = 0
	for _ in range(m):
		(l, r, x) = map(int, input().split())
		k |= x
	print(k % mod * pow(2, n - 1, mod) % mod)


from itertools import accumulate
import functools

def solve():
	(n, m) = list(map(int, input().split()))
	X = []
	for _ in range(m):
		(l, r, x) = list(map(int, input().split()))
		X.append(x)
	or_sum = functools.reduce(lambda x, y: x | y, X)
	return or_sum * pow(2, n - 1) % (10 ** 9 + 7)
for _ in range(int(input())):
	print(solve())


for t in range(int(input())):
	(n, m) = list(map(int, input().split()))
	(l, r, xx) = list(map(int, input().split()))
	for i in range(m - 1):
		(l, r, x) = list(map(int, input().split()))
		xx = xx | x
	print(2 ** (n - 1) * xx % 1000000007)


mod = 1000000007

def inp():
	return list(map(int, input().split()))
_t = int(input())
for _ in range(_t):
	(n, m) = inp()
	bit = 0
	for i in range(m):
		(l, r, x) = inp()
		bit |= x
	ans = bit * pow(2, n - 1, mod=mod)
	print(ans % mod)


mod = 10 ** 9 + 7
for i in range(int(input())):
	(n, m) = list(map(int, input().split()))
	fullOr = 0
	for i in range(m):
		(_, _, x) = list(map(int, input().split()))
		fullOr |= x
	print(fullOr * 2 ** (n - 1) % mod)


def power(x, MOD):
	ans = 1
	for i in range(x):
		ans = ans * 2 % MOD
	return ans
t = int(input())
for _ in range(t):
	(n, k) = [int(x) for x in input().split()]
	ans = 0
	MOD = pow(10, 9) + 7
	totalOr = 0
	for j in range(k):
		(a, b, c) = [int(x) for x in input().split()]
		totalOr = c | totalOr
	temp = totalOr * power(n - 1, MOD) % MOD
	ans = (ans + temp) % MOD
	print(ans)


for iiii in range(int(input())):
	(n, m) = map(int, input().split())
	x = 0
	for i in range(m):
		(a, b, c) = map(int, input().split())
		x = x | c
	per = 1000000000 + 7
	cou = x % per
	for i in range(n - 1):
		cou = cou % per * 2 % per
	print(cou)


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split(' '))
	l = [0 for theta in range(m)]
	r = [0 for delta in range(m)]
	all_and = 0
	for j in range(m):
		(l[j], r[j], x) = map(int, input().split(' '))
		all_and = all_and | x
	p = 10 ** 9 + 7
	all_and = all_and % p
	temp = pow(2, n - 1, p)
	ans = temp * all_and % p
	print(ans)


import sys
from math import sqrt, gcd
from collections import deque
sys.setrecursionlimit(10 ** 8)
I = lambda : int(input())
S = lambda : input().strip()
M = lambda : map(int, input().strip().split())
L = lambda : list(map(int, input().strip().split()))
mod = 1000000007
for _ in range(I()):
	(n, m) = M()
	ans = 0
	for i in range(m):
		(l, r, v) = M()
		ans |= v
	print(2 ** (n - 1) * ans % mod)


t = int(input())
while t:
	t -= 1
	b = list(map(int, input().split()))
	x = 0
	for i in range(b[1]):
		a = list(map(int, input().split()))
		x = x | a[2]
	x = x % 1000000007
	y = 1
	for i in range(b[0] - 1):
		y = y * 2 % 1000000007
	print(x * y % 1000000007)


mod = 1000000007
for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	y = 0
	for i in range(m):
		(l, r, x) = list(map(int, input().split()))
		y |= x
	t = 0
	for i in range(32):
		if y & 1 << i:
			t += (1 << i) * pow(2, n - 1, mod)
	print(t % mod)


t = int(input())
while t > 0:
	(n, m) = [int(x) for x in input().split()]
	ans = 0
	for i in range(m):
		ip = [int(x) for x in input().split()]
		l = ip[0]
		r = ip[1]
		x = ip[2]
		ans = ans | x
	for i in range(n - 1):
		ans = ans % 1000000007 * 2 % 1000000007
	print(ans % 1000000007)
	t -= 1


from collections import *

def xorSum(arr, n):
	bits = 0
	for i in range(n):
		bits |= arr[i]
	ans = bits * pow(2, n - 1, mod) % mod % mod
	return ans
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	ans = 0
	mod = 1000000007
	arr = [0 for i in range(n)]
	for i in range(m):
		(l, r, x) = map(int, input().split())
		arr[r - 1] = max(x, arr[r - 1])
	print(xorSum(arr, len(arr)) % mod)


mod = 10 ** 9 + 7

def mpow(a, b):
	ans = 1
	while b:
		if b & 1:
			ans = ans * a % mod
		a = a * a % mod
		b >>= 1
	return ans
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = []
	for i in range(m):
		a.append([int(x) for x in input().split()])
	sm = 0
	for i in range(m):
		sm |= a[i][2]
	ans = mpow(2, n - 1)
	ans *= sm
	ans %= mod
	print(ans)


def hehe(n):
	res = 1
	for i in range(n - 1):
		res = res * 2 % 1000000007
	return res
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = []
	ans = 0
	for i in range(m):
		temp = list(map(int, input().split()))
		l.append(temp)
	for i in range(m):
		ans = ans | l[i][2]
	print(hehe(n) * ans % 1000000007)