Many Paths, Many Costs

Alice and Bob are visiting Byteland. They are observing the map of this country. Surprisingly, the map of Byteland forms a tree. A tree is a connected graph without cycles. After finding this out, Alice has fixed the starting and ending city of her journey. But Bob is super confused and can’t fix his route.

After some thinking, Bob has come up with a scheme. Let’s say Alice’s starting city is $u$ and ending city is $v$. Then Bob will choose two different cities $a$ and $b$ such that both $a$ and $b$ lie on the simple path between city $u$ and city $v$. A simple path is the path that visits each city at most once. Soon Bob finds out that there are still many options. So, he is considering all possible options. For each option of choosing two different cities $a$ and $b$, he calculates the cost of the simple path between cities $a$ and $b$ and appends it to the list $K$. After appending the costs of all options, he sorts the list $K$ in ascending order. Please note that choosing cities $a, b$ and cities $b, a$ are considered as the same option.

Each edge of the tree has some weight. Bob defines the cost of a simple path as the bit-wise XOR of all the weights of the edges lying on that simple path.

Now, Bob wants to analyze the costs in $[L, R]$ subarray of the list $K$. He wants your help to analyze this task. You need to calculate the product of all the costs in $[L, R]$ subarray of the list $K$. As the answer can be very large, you need to print the answer modulo $(10^9 + 7)$. More formally, you need to print $\left( \prod\limits_{i=L}^{R} K_i \right) \mod (10^9+7)$.

The bitwise xor operation is represented with the "⊕" logic symbol, which is denoted as the "^" operator in C/C++, Java and Python.

Input

The first line of the input will contain an integer $T(1\leq T\leq 10^4)$, the number of the test cases.

In each of the test cases, the first line will contain two integers $N, Q (2\leq N\leq 10^5; 1\leq Q\leq 10^4)$, the number of cities in Byteland, and the number of queries. Each of the next $(N-1)$ lines will contain three integers $U, V, W (1\leq U, V\leq N; U\neq V; 0< W\leq10^3)$ denoting there is an undirected edge of $W$ weight between city $U$ and city $V$. Each of the next $Q$ lines will contain four integers $u, v, L, R$ $(1\leq u, v\leq N; u\neq v; 1\leq L\leq R)$, the starting and ending cities of Alice and the list $K$’s range Bob will analyze.

It is guaranteed that the given edges form a tree and the $L$, $R$ will produce a valid range.

The sum of $N$ over all test cases won’t exceed $10^5$ and the sum of $Q$ over all test cases won’t exceed $10^4$.

Output

In each query, print $\left( \prod\limits_{i=L}^{R} K_i \right) \mod (10^9+7)$ in a line.

Sample

Input	Output
1 5 2 1 2 6 2 3 13 2 5 12 3 4 5 4 5 2 4 1 3 1 3	160 858
Note: In the first query, the costs of the paths Bob will consider are: $Cost(2, 3) = 13, Cost(2, 4) = 8, Cost(2,5)=12, Cost(3,4)=5, Cost(3,5)=1, Cost(4,5)=4$. So, the list $K$ will be: $[1, 4, 5, 8, 12, 13]$. The value of $\left( \prod\limits_{i=2}^{4} K_i \right) \mod (10^9+7)$ = $(4\times 5\times 8) \mod (10^9+7)$ = $160$.