Divan and bitwise operations

题意翻译

#### 题面描述 ​ 一天，Divan 研究了一个由 n 个非负整数构成的序列，$a_1,a_2,...a_n$，他选出了这个序列 $a$ 的所有非空子序列，计算出所有子序列的异或 `XOR` 值，然后把这些子序列的异或值加起来，得到了这个序列的 `conziness` 值。 $$ \text{conziness}=\sum(\sum _1 ^{\rm{size}} a_{k_1} \oplus a_{k_2}...\oplus a_{k_{\rm size}}), \mathrm{size}\leq \rm n $$ ​ 一个子序列的定义是从原序列中任意删除几个数(零，一，…，所有)，剩下的元素按照原来的顺序写在一起，得到一个新的序列，即原序列的子序列。 ​ Divan 对他的研究感到非常骄傲，但是他现在不小心把序列 $a$ 给弄丢了，当然 `conziness` 值也弄丢了！但是，Divan 知道 m 个子串的同或 `OR ` 值，并且，原序列的每个元素都至少在这 m 个子串中出现过一次。 ​ Divan 想让你帮忙找出 $a$ 序列的 `conziness` 值，如果有多种可能，任意输出一种即可。 ​ 由于答案可能特别大，请将最后的答案对 $10^9 + 7$ 取模。 #### 输入 ​ 第一行包含一个整数 $t(1\leq t\leq 10^3)$，表示数据的组数。 ​ 接下来每一个测试数据包含两个整数 n 和 m $(1\leq n,m \leq 2 \cdot 10^5)$. 意义已在上文给出。 ​ 接下来 m 行描述 m 个子串的异或值，每一行描述一个子串。每个子串由三个整数来描述 $l, r$ 和 $x$ $(1 \leq l \leq r \leq n, 0 \leq x\leq 2^{30} -1)$。分别代表这段子串的左端点，右端点，以及这段子串 $a_l, a_{l+1},...,a_{r}$ 的同或值。 ​ 保证存在一个序列，满足上述条件。 ​ 保证所有数据的 $n$ 之和以及 $m$ 之和不超过 $2\cdot 10^5$.

题目描述

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](https://en.wikipedia.org/wiki/Bitwise_operation#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](https://en.wikipedia.org/wiki/Bitwise_operation#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 $ .

输入输出格式

输入格式

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

输出格式

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

输入输出样例

输入样例 #1

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

输出样例 #1

4
20
112

说明

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