CF1614C.Divan and bitwise operations

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

Divan 曾对一个由 $n$ 个非负整数组成的序列 $a_1, a_2, \ldots, a_n$ 进行如下分析：他考虑该序列 $a$ 的每一个非空子序列，计算其所有元素的按位异或（XOR），然后将所有这些异或值求和，得到序列 $a$ 的舒适度（coziness）。

序列 $c$ 是序列 $d$ 的一个子序列，当且仅当 $c$ 可通过从 $d$ 中删除若干（可能为零个或全部）元素而得到。例如，$[1, \, 2, \, 3, \, 4]$、$[2, \, 4]$ 和 $[2]$ 都是 $[1, \, 2, \, 3, \, 4]$ 的子序列，但 $[4, \, 3]$ 和 $[0]$ 不是。

Divan 对自己的分析非常自豪，但现在他丢失了原始序列 $a$，也忘记了舒适度的值！不过，Divan 记得序列 $a$ 的 $m$ 个连续子段各自的按位或（OR）值。并且，原始序列的每个元素都至少被这 $m$ 个子段中的某一个所覆盖。

Divan 请求你利用他所记得的信息，帮助他还原出序列 $a$ 的舒适度。如果存在多种可能的舒适度值，输出任意一个即可。

由于结果可能非常大，请将答案对 $10^9 + 7$ 取模后输出。

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

第一行包含一个整数 $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$。

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

对于每个测试用例，输出任意一个满足条件的序列 $a$ 的“舒适度”对 $10^9 + 7$ 取模的结果。

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

在第一个例子中，一个满足约束条件的序列是 $[0, 2]$。考虑它的所有非空子序列：

• $[0]$：该子序列的按位异或（XOR）结果为 $0$；
• $[2]$：该子序列的按位异或（XOR）结果为 $2$；
• $[0, 2]$：该子序列的按位异或（XOR）结果为 $2$。

所有结果之和为 $4$，因此答案为 $4$。

在第二个例子中，一个满足约束条件的序列是 $[0, \, 5, \, 5]$。

在第三个例子中，一个满足约束条件的序列是 $[5, \, 6, \, 7, \, 0, \, 2]$。