去年，我们曾请求你帮助我们将昂贵的金属转化为铅。（你不需要了解上一个问题的任何信息来解决这个问题。）但你们国家的领导人仍然贪得无厌，想要更多的铅！

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

对于每种金属（包括铅），你都确切地知道一个公式，该公式允许你消耗 1 克该金属，并创造出另外两种金属各 1 克。（最好不要过多考虑质量守恒定律！）注意，第 $i$ 种金属的公式可能会产生第 $i$ 种金属作为产物之一。这些公式不能处理不足 1 克的情况。然而，只要你有 1 克所需的原料，你就可以根据需要多次使用每个公式（或者完全不用）。

如果你做出最优选择，你最终能得到的铅的最大克数是多少？或者这个数量是无限的吗？如果不是无限的：由于输出可能是一个非常大的数字，我们只要求你输出结果除以质数 $10^9+7$（即 $1000000007$）的余数。

输入格式

输入的第一行给出了测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例的第一行包含一个整数 $M$：世界上已知的金属数量。接下来有 $M$ 行，每行包含两个整数 $R_{i1}$ 和 $R_{i2}$；从 1 开始计数，第 $i$ 行表示你可以消耗 1 克金属 $i$ 来创造 1 克金属 $R_{i1}$ 和 1 克金属 $R_{i2}$。最后一行包含 $M$ 个整数 $G_1, G_2, \dots, G_M$；$G_i$ 是国库中金属 $i$ 的克数。铅是金属 1。

输出格式

对于每个测试用例，输出一行，包含 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始）。如果产生的铅的最大数量没有上限，则 $y$ 必须为 UNBOUNDED。否则，$y$ 必须是你最终能得到的铅的最大克数，对质数 $10^9+7$（即 $1000000007$）取模。

数据范围

$1 \le R_{i1} < R_{i2} \le M$，对于所有 $i$。 时间限制：每个测试集 20 秒。 内存限制：1GB。

测试集 1（可见） $1 \le T \le 100$。 $2 \le M \le 10$。 $0 \le G_i \le 10$，对于所有 $i$。

测试集 2（隐藏） $1 \le T \le 100$。 $2 \le M \le 100$。 $0 \le G_i \le 10^9$，对于所有 $i$。

测试集 3（隐藏） $1 \le T \le 5$。 $2 \le M \le 10^5$。 $0 \le G_i \le 10^9$，对于所有 $i$。

样例

样例输入 1

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

样例输出 1

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

说明

在样例 1 中，你有一个公式可以将 1 克铅转化为 1 克铅和 1 克第二种金属，另一个公式可以将 1 克第二种金属转化为 1 克铅和 1 克第二种金属。你可以交替使用这些公式来根据需要生产任意数量的这两种金属。

样例 2 使用了与样例 1 相同的公式，但你初始没有任何金属！

在样例 3 中，没有任何公式能帮助你生产更多的铅，因此你最终得到的铅不会超过你开始时拥有的数量。