The rapid flow of rivers is an effective way to move logs in the great Canadian log drive. But as every Canadian knows, it can be a double-edged sword. If logs get stuck on the riverbanks, they'll eventually pile up and cause the river to overflow. [Sometimes you need a helping hand to keep the logs moving](https://youtu.be/7AheBqBk0iQ?t=578).

In a given river system there are \(N\) lakes, numbered from \(1\) to \(N\), and \(N-1\) rivers flowing amongst the lakes. For each lake \(i\) such that \(2 \le i \le N\), there's a river flowing from lake \(P_i\) to lake \(i\) which is \(L_i\) metres long. There are no rivers flowing into lake 1. \(P_1\) and \(L_1\) are defined to be equal to 0, but are irrelevant. It's guaranteed that each lake is accessible from lake 1 by some sequence of rivers. Each lake with no rivers flowing out of it has a log-processing plant.

Shipments of logs are often transported through these lakes and rivers. Each shipment consists of some number of logs, and is managed by a log driver with some integer carelessness value. A shipment may be transported from a lake by means of a river flowing out of it, to the lake which that river flows into. However, a number of logs will be permanently lost along the way, equal to the log driver's carelessness value multiplied by the length of the river (in metres). We can assume that shipments are always large enough that they don't risk completely running out of logs. Each shipment continues to be transported from lake to lake until reaching a log-processing plant.

Other log drivers available for hire also live by the lakes. There's a log driver living by each lake \(i\) with a carelessness of \(H_i\). Whenever a shipment of logs is at lake \(i\), the company that owns the shipment may choose to hire the log driver there to take over in place of the shipment's current log driver. The newly-hired log driver will then manage the shipment until it either reaches a log-processing plant, or another log driver is later hired to replace them.

As part of the log-istics team, you need to answer \(M\) questions, the \(i\)th of which asks: If you begin with a shipment of logs in lake \(X_i\), being managed by a log driver with a carelessness of \(Y_i\), what's the minimum number of logs which can be lost by the time the shipment reaches any log-processing plant? Please note that each question is independent of the others (for example, the same log driver may be hired as part of the answer to multiple different questions).

Let \(V_i\) be the answer to the \(i\)th question. In order to reduce the size of the output, you must calculate a single integer: the product of \((V_i + 1)\) over \(i=1..M\). As this product may be very large, you should only compute its value modulo 1,000,000,007.

In order to reduce the size of the input, the above values will not all be provided explicitly. Instead, you'll be given the first \(K\) values \(P_{1..K}\), \(L_{1..K}\), \(H_{1..K}\), \(X_{1..K}\), and \(Y_{1..K}\), as well as the five tuples of constants \((A_P, B_P, C_P)\), \((A_L, B_L, C_L, D_L)\), \((A_H, B_H, C_H, D_H)\), and \((A_X, B_X, C_X)\), \((A_Y, B_Y, C_Y, D_Y)\), and must then compute \(P_{(K+1)..N}\), \(L_{(K+1)..N}\), \(H_{(K+1)..N}\), \(X_{(K+1)..M}\), and \(Y_{(K+1)..M}\) as follows:

\(P_i = ((A_P * P_{i-2} + B_P * P_{i-1} + C_P) \text{ modulo } (i-1)) + 1\) for \(i > K\)
\(L_i = ((A_L * L_{i-2} + B_L * L_{i-1} + C_L) \text{ modulo } D_L) + 1\) for \(i > K\)
\(H_i = ((A_H * H_{i-2} + B_H * H_{i-1} + C_H) \text{ modulo } D_H) + 1\) for \(i > K\)
\(X_i = ((A_X * X_{i-2} + B_X * X_{i-1} + C_X) \text{ modulo } N) + 1\) for \(i > K\)
\(Y_i = ((A_Y * Y_{i-2} + B_Y * Y_{i-1} + C_Y) \text{ modulo } D_Y) + 1\) for \(i > K\)

# Constraints

\(1 \le T \le 85\)
\(2 \le N, M \le 1,000,000\)
\(2 \le K \le min(N, M)\)
\(0 \le A_P, B_P, C_P, A_L, B_L, C_L, A_H, B_H, C_H, A_X, B_X, C_X, A_Y, B_Y, C_Y <= 1,000,000,000\)
\(1 \le D_L, D_H, D_Y \le 1,000,000\)
\(0 \le P_i \le i-1\) (\(P_i = 0\) if and only if \(i = 1\))
\(0 \le L_i \le D_L\) (\(L_i = 0\) if and only if \(i = 1\))
\(1 \le H_i \le D_H\)
\(1 \le X_i \le N\)
\(1 \le Y_i \le D_Y\)

The sum of \(N+M\) over all \(T\) test cases is at most 10,000,000.

# Input

Input begins with an integer \(T\), the number of river systems. For each system, there are 11 lines:

The first line contains the 3 space-separated integers \(N\), \(M\), and \(K\).

The second line contains the \(K\) space-separated integers \(P_{1..K}\).

The third line contains the 3 space-separated integers \(A_P\), \(B_P\), and \(C_P\).

The fourth line contains the \(K\) space-separated integers \(L_{1..K}\).

The fifth line contains the 4 space-separated integers \(A_L\), \(B_L\), \(C_L\), and \(D_L\).

The sixth line contains the \(K\) space-separated integers \(H_{1..K}\).

The seventh line contains the 4 space-separated integers \(A_H\), \(B_H\), \(C_H\), and \(D_H\).

The eighth line contains the \(K\) space-separated integers \(X_{1..K}\).

The ninth line contains the 3 space-separated integers \(A_X\), \(B_X\), and \(C_X\).

The tenth line contains the \(K\) space-separated integers \(Y_{1..K}\).

The eleventh line contains the 4 space-separated integers \(A_Y\), \(B_Y\), \(C_Y\), and \(D_Y\).

# Output

For the \(i\)th river system, print a line containing *"Case #i: "* followed by a single integer, the product of \((V_i + 1)\) over \(i=1..M\), modulo 1,000,000,007.

# Explanation of Sample

**In the first case:**

- \(P = [0, 1, 2]\)
- \(L = [0, 2, 3]\)
- \(H = [10, 5, 50]\)
- \(X = [1, 1, 2, 3]\)
- \(Y = [2, 8, 3, 1]\)

The system of lakes and rivers looks as follows (with hireable log drivers' carelessness values indicated in circles, and lakes with log-processing plants marked in brown):

{{PHOTO_ID:896677524192910}}

- The first question deals with a shipment of logs at lake \(1\) being managed by a log driver with carelessness \(2\). It's optimal for this log driver to move the shipment to lake \(2\) (while losing \(2 * 2 = 4\) logs), and then to lake \(3\) (losing another \(3 * 2 = 6\) logs), with a total of \(10\) logs lost.
- For the second question, the log driver should move the shipment to lake \(2\) and then be replaced by the log driver living there (who has a carelessness of \(5\)), who will move it to lake \(3\). This would result in a total of \(2 * 8 + 3 * 5 = 31\) logs lost.
- For the third question, the log driver should move the shipment to lake \(3\), losing \(3 * 3 = 9\) logs along the way.
- For the fourth question, the shipment begins at a lake with a log-processing plant, meaning that no logs need to be lost.

Therefore, \(V = [10, 31, 9, 0]\), and the final answer is \(((10 + 1) * (31 + 1) * (9 + 1) * (0 + 1))\text{ modulo 1,000,000,007} = 3520\).

**In the second case:**

- \(P = [0, 1, 2, 1, 2, 4]\)
- \(L = [0, 11, 12, 13, 14, 15]\)
- \(H = [5, 4, 7, 2, 1, 3]\)
- \(X = [1, 2, 4, 1, 2, 1]\)
- \(Y = [1, 2, 3, 4, 5, 6]\)

The system of lakes and rivers looks as follows:

{{PHOTO_ID:3296189243803342}}

For the first question, the log driver should move the shipment to lake \(2\) and then to lake \(3\), losing a total of \(11 * 1 + 12 * 1 = 23\) logs along the way. Overall, \(V = [23, 24, 30, 82, 48, 95]\).

**In the third case:**

- \(P = [0, 1, 2, 2, 2, 1, 6, 5]\)
- \(L = [0, 5, 1, 8, 3, 2, 9, 8]\)
- \(H = [10, 9, 8, 7, 6, 5, 4, 3]\)
- \(X = [5, 1, 2, 1, 8, 5, 4, 1, 8, 5]\)
- \(Y = [6, 2, 9, 8, 9, 4, 9, 4, 9, 4]\)

For this case, \(V = [48, 12, 9, 48, 0, 32, 0, 24, 0, 32]\).