Description

去年，我们曾请你帮忙将昂贵的金属转化为铅。（你无需了解前一道题即可解答本题。）但你们国家的领导人依然贪婪地渴望获得更多的铅！

世界上已知有 $\mathbf{M}$ 种金属；在你的元素周期表上，铅是第 1 号金属。你们国家的领导人要求你利用国库中的金属，尽可能多地制造铅。

对于每种金属（包括铅），你都知道恰好有一种配方，可以消耗 1 克该金属，并各生成 1 克另外两种金属。（关于质量守恒原理，最好不要深究！）注意，第 $i$ 种金属的配方可能会生成第 $i$ 种金属本身作为产物之一。配方不能对部分克数的金属起作用。然而，只要你拥有所需金属的 1 克，你可以任意多次（或不使用）使用每种配方。

如果你做出最优选择，最终最多能获得多少克铅，或者说这个数量是否有限？如果答案有限，我们只要求你输出结果除以质数 $10^9+7$（即 $1000000007$）的余数。

Input Format

输入的第一行是测试用例数 $\mathbf{T}$。接下来有 $\mathbf{T}$ 组测试用例。每组测试用例首先有一行整数 $\mathbf{M}$，表示已知的金属种类数。接下来有 $\mathbf{M}$ 行，每行包含两个整数 $\mathbf{R_{i1}}$ 和 $\mathbf{R_{i2}}$；第 $i$ 行（从 1 开始计数）表示你可以消耗 1 克第 $i$ 种金属，生成 1 克第 $\mathbf{R_{i1}}$ 种金属和 1 克第 $\mathbf{R_{i2}}$ 种金属。最后一行包含 $\mathbf{M}$ 个整数 $\mathbf{G_1}, \mathbf{G_2}, \ldots, \mathbf{G_M}$，其中 $\mathbf{G_i}$ 表示国库中第 $i$ 种金属的克数。铅为第 1 号金属。

Output Format

对于每组测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是你最终能获得的最大铅克数。如果最大铅克数没有上限，则 $y$ 必须为 UNBOUNDED。否则，$y$ 必须是你最终能获得的最大铅克数对质数 $10^9+7$（即 $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

Hint

样例解释

在样例 1 中，你有一个配方可以将 1 克铅变为 1 克铅和 1 克第二种金属，另一个配方可以将 1 克第二种金属变为 1 克铅和 1 克第二种金属。你可以交替使用这两个配方，制造出任意多的两种金属。

样例 2 的配方与样例 1 相同，但你一开始没有任何金属！

样例 3 中，所有配方都无法帮助你制造更多的铅，因此你最终获得的铅不会超过初始拥有的数量。

数据范围

• 对所有 $i$，$1 \leq \mathbf{R_{i1}} < \mathbf{R_{i2}} \leq \mathbf{M}$。

测试点 1（7 分，公开）

• $1 \leq \mathbf{T} \leq 100$。
• $2 \leq \mathbf{M} \leq 10$。
• $0 \leq \mathbf{G_i} \leq 10$。

测试点 2（16 分，隐藏）

• $1 \leq \mathbf{T} \leq 100$。
• $2 \leq \mathbf{M} \leq 100$。
• $0 \leq \mathbf{G_i} \leq 10^9$。

测试点 3（6 分，隐藏）

• $1 \leq \mathbf{T} \leq 5$。
• $2 \leq \mathbf{M} \leq 10^5$。
• $0 \leq \mathbf{G_i} \leq 10^9$。

由 ChatGPT 4.1 翻译