Divan and bitwise operations
Contest: Codeforces Round 757 (Div. 2)
Difficulty rating: 1500
Tags: bitmasks, combinatorics, constructive algorithms, dp, math

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 format:
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 format:
For each test case print the coziness any suitable sequence $$$a$$$ modulo $$$10^9 + 7$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

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]$$$.

Example 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

Example output:
4
20
112

Editorial:
Let's count for each bit how many times it will be included in the answer.
Let us now consider the $$$i$$$-th bit. Note that if no number contains the included $$$i$$$-th bit, then such a bit will never be included in the answer. Otherwise, each of the subsequences contains $$$i$$$-th bit even or odd number of times. If a bit enters an even number of times, then we should not count such a subsequence, because the bitwise exclusive OR for this bit will be zero. If the bit enters an odd number of times, then we must count such a subsequence, because the bitwise exclusive OR for this bit will be equal to one.
It is stated that the number of subsequences in which the $$$i$$$-th bit enters an odd number of times is equal to $$$2^{n - 1}$$$. Let's prove it.
Divide the numbers into two sets $$$A$$$ and $$$B$$$. In the set $$$A$$$ there will be numbers whose $$$i$$$th bit is off, in the set $$$B$$$ there will be numbers whose $$$i$$$-th bit is on.
Note that the numbers from the set $$$A$$$ do not affect the answer in any way, because $$$x\; XOR\; 0 = 1$$$. Thus, whichever subset of $$$A$$$ we take, the $$$i$$$-th bit will not change its parity. There will be $$$2^{|A|}$$$ in total of such subsets.
Let $$$k = 1$$$ if $$$|B|$$$ is even, or $$$k = 0$$$ if $$$|B|$$$ is odd. In order for the $$$i$$$-th bit to enter the subsequence an odd number of times, you need to take an odd number of elements from the set $$$B$$$. This number is equal to $$$C_{|B|}^{1} \, + \, C_{|B|}^{3} \, + \dots \, + \, C_{|B|}^{|B| - k} = 2^{|B| - 1}$$$.
Thus, the $$$i$$$-th bit is included in exactly $$$2^{|A|}\cdot 2^{|B|- 1}= 2^{n - 1}$$$ subsequences, which was required to be proved.
Then the solution to this problem turns out to be very simple: let $$$x$$$ be equal to the bitwise OR of all elements of the sequence (or, the same thing, bitwise OR of all given segments), then the answer will be equal to $$$x\cdot 2^{n - 1}$$$ modulo $$$10^9 + 7$$$.
The resulting asymptotics in time: $$$\mathcal{O}(n)$$$.