Busy Beaver 居住在一条未染色的道路上，该道路由从左到右编号为 $1, 2, \dots, N$ 的 $N$ 块瓷砖组成。所有瓷砖的初始颜色均为出厂默认的 $0$，但 Busy Beaver 想要改变这一点！在接下来的几天里，Busy Beaver 计划重新粉刷整条道路。

具体来说，Busy Beaver 写下了一份包含 $Q$ 个计划的清单，其中第 $i$ 个计划表示在第 $d_i$ 天（$0 \le d_i \le 2^K - 1$），Busy Beaver 将用颜色 $c_i$ 重新粉刷区间 $[x_i, y_i]$ 内的所有瓷砖，覆盖它们之前的颜色。Busy Beaver 每天最多安排一个粉刷计划，他想知道在所有粉刷完成后，所有瓷砖最终颜色的总和。

然而，Busy Beaver 并不知道，他实际上是第一只生活在量子计算机中的海狸！不幸的是，这意味着宇宙的运行方式与他想象的不同。在夜里，当没有人观察时，量子比特会经历一次随机变换：选择一个介于 $0$ 和 $2^K - 1$ 之间的整数 $z$，原本安排在第 $i$ 天的每个计划都会被移动到第 $i \oplus z$ 天，其中 $\oplus$ 表示按位异或。

对于给定的 $z$，计划将按照它们（偏移后的）天数升序执行，每次粉刷操作都会覆盖 $x_i$ 到 $y_i$ 之间瓷砖的颜色。令 $F(z)$ 表示在使用偏移量 $z$ 执行计划后，所有瓷砖最终颜色的总和。

请计算 $\sum_{z=0}^{2^K-1} F(z)$。由于答案可能非常大，请将其对 $10^9 + 7$ 取模后输出。

输入格式

每个测试点包含多个测试用例。第一行包含测试用例的数量 $T$（$1 \le T \le 150$）。接下来是每个测试用例的描述。

每个测试用例的第一行包含三个整数 $N$、$K$ 和 $Q$（$1 \le N \le 2 \cdot 10^5$，$0 \le K \le 60$，$1 \le Q \le \min(2^K, 2 \cdot 10^5)$）。

接下来的 $Q$ 行中，第 $i$ 行包含四个整数 $d_i$、$x_i$、$y_i$ 和 $c_i$（$0 \le d_i < 2^K$，$1 \le x_i \le y_i \le N$，$0 \le c_i \le 10^9$）。

保证所有测试用例中 $N$ 的总和不超过 $4 \cdot 10^5$，所有测试用例中 $Q$ 的总和不超过 $4 \cdot 10^5$，且在同一个测试用例中，所有的 $d_i$ 两两不同。

输出格式

对于每个测试用例，单独输出一行一个整数：Busy Beaver 原本的问题在所有 $2^K$ 种可能的偏移量下的答案之和，对 $10^9 + 7$ 取模后的结果。

子任务

本题共有五个子任务。

• （10 分）：所有测试用例中 $N$、$2^K$ 和 $Q$ 的总和分别小于或等于 $5 \cdot 10^3$。注意，这指的是每个指标各自的总和，而不是它们的累加和。此外，对于所有 $i$，满足 $c_i \le 5 \cdot 10^3$。
• （20 分）：对于所有测试用例，满足 $N = 1, Q \le 2$。
• （20 分）：对于所有测试用例，满足 $N = 1$。
• （20 分）：对于所有测试用例，满足 $K \le 18$。
• （30 分）：无其他限制。

样例

输入样例 1

3
6 4 6
6 3 5 4
12 2 2 3
4 1 4 2
5 3 3 4
14 1 1 3
13 1 6 4
6 4 4
4 1 2 0
3 2 6 4
2 2 2 2
5 3 5 0
4 4 6
8 2 4 2
11 1 3 2
9 3 4 4
10 3 3 2
2 3 4 3
3 1 4 5

输出样例 1

332
184
220

输入样例 2

3
5 4 4
9 1 2 2
12 1 3 1
10 4 5 3
14 1 5 4
6 4 4
5 2 4 3
14 5 6 2
10 3 6 3
1 4 6 5
6 4 5
11 2 4 5
13 1 2 4
14 4 6 5
10 1 6 3
15 2 6 0

输出样例 2

224
272
276