After running tests on samples of ore, mining engineers must [plot out the economics of extraction, transportation, and treatment in long range terms](https://youtu.be/zPbY--IXGg8?t=618s). Feasibility reports are then drafted for executive decision.

In a given Ontario town, all the extracted ore is shipped using the town's transportation network, known as its Bulk Transportation Chain (BTC). The BTC is a network of \(N\) ore processing plants, numbered from \(1\) to \(N\), with \(N-1\) roads running amongst them. The \(i\)th road allows ore to be shipped in either direction between plants \(A_i\) and \(B_i\), and has the capacity for at most \(C_i\) kilograms of ore to be shipped through it per minute. It is possible to reach any plant from any other plant by following a sequence of roads.

The *shipping capacity* for an unordered pair of processing plants is the maximum weight of ore that may be shipped between them (in either direction) per minute. This is equal to the minimum capacity of any road on the shortest sequence of roads connecting them (such a sequence is unique per pair of plants).

Mining is a dirty business, and not just among blue-collar workers. Executives of a new mining project are plotting to sabotage their rival company's presence in a given town by disrupting its transportation operations. They hope to blockade a single one of the \(N-1\) roads within the town's BTC network, preventing any ore from being shipped along it and therefore reducing its capacity to \(0\). They would like to negatively impact the shipping capacities between various pairs of processing plants as much as possible, but have yet to decide which road would best accomplish their goal, so they'll consider each of them in turn.

Let \(S_i\) be the sum of shipping capacities, in kilograms, across all \(N*(N-1)/2\) unordered pairs of processing plants if the \(i\)th road were to be blockaded. In order to reduce the size of the output, you must calculate a single integer: the product of \(S_{1..(N-1)}\). As this product may be very large, you should only compute its value modulo \(1{,}000{,}000{,}007\).

# Constraints

\(1 \le T \le 45\)
\(2 \le N \le 800{,}000\)
\(1 \le A_i, B_i \le N\)
\(1 \le C_i \le 20\)

The sum of \(N\) across all towns is at most \(4{,}000{,}000\).

# Input

Input begins with an integer \(T\), the number of towns that the execs are scoping out. For each town, there is first a line containing a single integer \(N\). Then, \(N-1\) lines will follow, the \(i\)th of which contains the \(3\) space-separated integers \(A_i\), \(B_i\), and \(C_i\).

# Output

For the \(i\)th town, output a line containing *"Case #i: "* followed by a single integer, the product of \(S_{1..(N-1)}\), modulo \(1{,}000{,}000{,}007\).

# Sample Explanation

In the first town, the BTC network looks as follows:

{{PHOTO_ID:654301598882147}}

If the single road were blockaded (with its capacity reduced to \(0\)), the shipping capacity between plants \(1\) and \(2\) would become 0. Therefore, \(S = [0]\), and the final answer is \(0\).

In the second town, the BTC network looks as follows:

{{PHOTO_ID:4343232682381910}}

If the first road were blockaded, the shipping capacity between plants \(2\) and \(3\) would be \(5\), with the shipping capacities for other pairs of plants (plants \(1\) and \(2\), and plants \(1\) and 3) reduced to \(0\). If the second road were blockaded, there would instead just be a shipping capacity of \(4\) between plants \(1\) and \(2\). Therefore, \(S = [5, 4]\), and the answer is \((5 * 4)\) modulo \(1{,}000{,}000{,}007 = 20\).

In the third town, the BTC network looks as follows:

{{PHOTO_ID:176939544513599}}

If the first road (between plants \(2\) and \(1\)) were blockaded, there would be a shipping capacity of \(5\) between plants \(1\) and \(4\), and a shipping capacity of \(1\) between plants \(1\) and \(3\) as well as between plants \(3\) and \(4\). Therefore, \(S_1 = 5 + 1 + 1 = 7\). Overall, \(S = [7, 20, 12]\), and the answer is \((7 * 20 * 12)\) modulo \(1{,}000{,}000{,}007 = 1{,}680\).

In the fourth town, \(S = [6, 4, 4, 6]\).

In the fifth town, \(S = [36, 41, 28, 21, 34, 29, 41]\).