← 返回题目列表

Codeforces · 1614/C

C. Divan 和按位运算

中文机器翻译题面 查看原题

一旦 Divan 分析了由 $$$n$$$ 非负整数组成的序列 $$$a_1, a_2, \ldots, a_n$$$,如下所示。他考虑了序列$$$a$$$的每个非空子序列,计算其元素的按位异或并将所有异或相加,获得序列$$$a$$$的舒适性。

序列 $$$c$$$ 是序列 $$$d$$$ 的子序列,如果 $$$c$$$ 可以通过删除几个(可能是零个或全部)元素从 $$$d$$$ 获得。例如,$$$[1, \, 2, \, 3, \, 4]$$$、$$$[2, \, 4]$$$ 和 $$$[2]$$$ 是 $$$[1, \, 2, \, 3, \, 4]$$$ 的子序列,但 $$$[4, \, 3]$$$ 和 $$$[0]$$$ 不是 $$$[0]$$$ 的子序列。

Divan 对他的分析感到非常自豪,但现在他失去了序列 $$$a$$$,还有舒适度值!然而,Divan 会记住序列 $$$a$$$ 的 $$$m$$$ 连续子段上的按位 OR 值。事实证明,原始序列的每个元素至少包含在这些 $$$m$$$ 段中的一个中。

Divan 要求你使用他记住的信息来帮助找到序列 $$$a$$$ 的舒适度。如果可能存在多个舒适度值,请打印任何一个。

由于结果可能非常大,因此打印对 $$$10^9 + 7$$$ 取模的值。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^3$$$) — 测试用例的数量。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$) — 分别是序列的长度和 Divan 记住的按位 OR 值的连续段的数量。

以下 $$$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$$$。

输出

对于每个测试用例,打印任何合适的序列 $$$a$$$ 模 $$$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

注意

在第一个示例中,符合约束的序列之一是 $$$[0, 2]$$$。考虑它的所有非空子序列:

- $$$[0]$$$:该子序列按位异或为$$$0$$$;
- $$$[2]$$$:该子序列按位异或为$$$2$$$;
- $$$[0, 2]$$$:该子序列的按位异或为 $$$2$$$。

所有结果的总和是 $$$4$$$,所以这就是答案。

在第二个示例中,符合约束的序列之一是 $$$[0, \, 5, \, 5]$$$。

在第三个示例中,符合约束的序列之一是 $$$[5, \, 6, \, 7, \, 0, \, 2]$$$。