C. Quantum Beaver
time limit per test
6 s
memory limit per test
512 megabytes
input
standard input
output
standard output

Busy Beaver lived on an unpainted sidewalk consisting of $$$N$$$ individual tiles numbered $$$1,2,\dots,N$$$ from left to right. The tiles all start with the factory-standard color $$$0$$$, but Busy Beaver is looking to change that! Over several days of painting, Busy Beaver aims to repaint the entire sidewalk.

Specifically, Busy Beaver wrote down a list of $$$Q$$$ plans, the $$$i$$$-th of which states that on day $$$d_i$$$ ($$$0 \le d_i \le 2^K-1$$$), Busy Beaver will repaint all tiles in the range $$$[x_i, y_i]$$$ with color $$$c_i$$$, overwriting their previous colors. Busy Beaver has at most one painting plan scheduled for each day, and he is interested in the sum of the final colors of all tiles after all the repaintings.

Unbeknownst to Busy Beaver, he is, in fact, the first Beaver to live in a Quantum Computer! This unfortunately means that the universe does not operate as he thinks it does. During the night, while no one is watching, the qubits undergo a random transformation: an integer $$$z$$$ between $$$0$$$ and $$$2^K - 1$$$ is selected, and every plan originally scheduled for day $$$i$$$ is instead moved to day $$$i \oplus z$$$, where $$$\oplus$$$ denotes bitwise XOR.

For a given $$$z$$$, the plans are then executed in increasing order of their (shifted) day, and each repaint operation overwrites the colors of the tiles between $$$x_i$$$ and $$$y_i$$$. Let $$$F(z)$$$ be the sum of the final colors of all tiles after applying the plans with shift $$$z$$$.

Compute $$${\large \sum_{z=0}^{2^K - 1}} F(z)$$$. Since the answer may be enormous, output it modulo $$$10^9+7$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$T$$$ ($$$1\leq T\leq 150$$$). The description of the test cases follows.

The first line of each test case contains three integers $$$N$$$, $$$K$$$, and $$$Q$$$ ($$$1\leq N\leq 2\cdot10^5$$$, $$$0\leq K\leq60$$$, $$$1\leq Q\leq \min(2^K,2\cdot 10^5)$$$).

The $$$i$$$-th of the next $$$Q$$$ lines contains four integers $$$d_i$$$, $$$x_i$$$, $$$y_i$$$, and $$$c_i$$$ ($$$0\leq d_i \lt 2^K$$$, $$$1\leq x_i\leq y_i\leq N$$$, $$$0\leq c_i\leq10^9$$$).

It is guaranteed that the sum of $$$N$$$ across all test cases is at most $$$4\cdot10^5$$$, the sum of $$$Q$$$ across all test cases is at most $$$4\cdot10^5$$$, and all $$$d_i$$$'s within a test case are distinct.

Output

For each test case, output one integer on its own line: the sum of the answers to Busy Beaver's original question over all $$$2^K$$$ possible shifts, modulo $$$10^9+7$$$.

Scoring

There are five subtasks for this problem.

  • ($$$10$$$ points): The sum of $$$N$$$, $$$2^K$$$, and $$$Q$$$ over all test cases are each less than or equal to $$$5 \cdot 10^3$$$. Note that this refers to each of the individual sums, not the cumulative sum of all of them. Also, $$$c_i \le 5 \cdot 10^3$$$ for all $$$i$$$.
  • ($$$20$$$ points): For all test cases, $$$N=1, Q \le 2$$$.
  • ($$$20$$$ points): For all test cases, $$$N=1$$$.
  • ($$$20$$$ points): For all test cases, $$$K\leq 18$$$.
  • ($$$30$$$ points): No further constraints.
Examples
Input
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
Output
332
184
220
Input
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
Output
224
272
276