题目描述

Last year, we asked you to help us convert expensive metals into lead. (You do not need to know anything about the previous problem to solve this one.) But your country's leader is still greedy for more lead!

There are $\mathbf{M}$ metals known in the world; lead is metal number 1 on your periodic table. Your country's leader has asked you to use the metals in the treasury to make as much lead as possible.

For each metal (including lead), you know exactly one formula that lets you destroy one gram of that metal and create one gram each of two metals. (It is best not to think too much about the principle of mass conservation!) Note that it is possible that the formula for the i-th metal might produce the i-th metal as one of the products. The formulas do not work with partial grams. However, you can use each formula as often as you would like (or not at all), as long as you have a gram of the required ingredient.

If you make optimal choices, what is the largest number of grams of lead you can end up with, or is it unbounded? If it is not unbounded: since the output can be a really big number, we only ask you to output the remainder of dividing the result by the prime $10^9+7$ (that is, $1000000007$).

输入格式

The first line of the input gives the number of test cases, $\mathbf{T}$. $\mathbf{T}$ test cases follow. Each begins with one line with an integer $\mathbf{M}$: the number of metals known in the world. Then there are $\mathbf{M}$ more lines with two integers $\mathbf{R_{i1}}$ and $\mathbf{R_{i2}}$ each; the i-th of these lines, counting starting from 1, indicates that you can destroy one gram of metal i to create one gram of metal $\mathbf{R_{i1}}$ and one gram of metal $\mathbf{R_{i2}}$. Finally, there is one line with $\mathbf{M}$ integers $\mathbf{G_1}$, $\mathbf{G_2}$, ..., $\mathbf{G_M}$; $\mathbf{G_i}$ is the number of grams of metal i in the treasury. Lead is metal 1.

输出格式

For each test case, output one line containing Case #x: y where $x$ is the test case number (starting from 1). If there is no bound on the maximum amount of lead that can be produced, $y$ must be UNBOUNDED. Otherwise, $y$ must be the largest amount of lead, in grams, that you can end up with, modulo the prime $10^9+7$ (that is, $1000000007$).

3
2
1 2
1 2
1 0
2
1 2
1 2
0 0
4
2 4
3 4
2 4
2 3
10 10 10 10

Case #1: UNBOUNDED
Case #2: 0
Case #3: 10

提示

Sample Explanation

In Sample Case #1, you have one formula that turns 1 gram of lead into 1 gram of lead and 1 gram of the second metal, and another formula that turns 1 gram of the second metal into 1 gram of lead and 1 gram of the second metal. You can alternate between these formulas to produce as much of both metals as you want.

Sample Case #2 has the same formulas as Sample Case #1, but you have no metals to start with!

In Sample Case #3, none of the formulas help you produce more lead, so you cannot end up with more lead than you started with.

Limits

• $1 \leq \mathbf{R_{i1}} < \mathbf{R_{i2}} \leq \mathbf{M}$, for all $i$.

Test set 1 (7 Pts, Visible)

• $1 \leq \mathbf{T} \leq 100$.
• $2 \leq \mathbf{M} \leq 10$.
• $0 \leq \mathbf{G_i} \leq 10$, for all $i$.

Test set 2 (16 Pts, Hidden)

• $1 \leq \mathbf{T} \leq 100$.
• $2 \leq \mathbf{M} \leq 100$.
• $0 \leq \mathbf{G_i} \leq 10^9$, for all $i$.

Test set 3 (6 Pts, Hidden)

• $1 \leq \mathbf{T} \leq 5$.
• $2 \leq \mathbf{M} \leq 10^5$.
• $0 \leq \mathbf{G_i} \leq 10^9$, for all $i$.