컨트랜스뮤테이션

지난 대회에서 여러분에게 값비싼 금속을 납으로 바꾸는 일을 도와 달라고 부탁했습니다. 이 문제를 푸는 데 이전 문제에 대한 지식은 필요 없습니다. 그런데 나라의 지도자는 여전히 납을 더 원합니다!

세상에는 $M$개의 금속이 알려져 있으며, 주기율표에서 납은 1번 금속입니다. 지도자는 국고에 있는 금속을 써서 납을 최대한 많이 만들라고 요청했습니다.

각 금속(납 포함)마다 공식이 하나씩 정해져 있습니다. 공식은 그 금속 1그램을 없애고, 두 금속을 각각 1그램씩 만듭니다. (질량 보존 법칙은 깊이 생각하지 않는 편이 좋습니다!) $i$번째 금속의 공식은 생성물 중 하나로 $i$번째 금속 자체를 내놓을 수도 있습니다. 공식은 그램 미만 단위로는 적용할 수 없습니다. 필요한 재료가 1그램 이상 있으면 각 공식을 원하는 만큼(또는 전혀 쓰지 않고) 쓸 수 있습니다.

최적으로 선택했을 때 얻을 수 있는 납의 최대 그램 수는 얼마입니까? 상한이 없을 수도 있습니까? 값이 유한하면 결과가 매우 클 수 있으므로, 소수 $10^9+7$로 나눈 나머지를 구합니다.

입력의 첫 줄에 테스트 케이스의 개수 $T$가 주어집니다. 이어서 $T$개의 테스트 케이스가 주어집니다. 각 테스트 케이스는 세상에 있는 금속의 수 $M$을 나타내는 정수 한 개가 적힌 줄로 시작합니다. 그 다음 $M$개의 줄에 정수 두 개 $R_{i1}$과 $R_{i2}$가 주어집니다. 이 줄들 중 i번째 줄은 금속 $i$ 1그램을 없애고 금속 $R_{i1}$ 1그램과 금속 $R_{i2}$ 1그램을 만들 수 있다는 뜻입니다. 마지막 줄에는 정수 $M$개 $G_1, G_2, \ldots, G_M$이 주어지며, $G_i$는 국고에 있는 금속 $i$의 그램 수입니다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄을 출력합니다. 여기서 $x$는 1부터 시작하는 테스트 케이스 번호입니다. 얻을 수 있는 납의 양에 상한이 없으면 $y$는 UNBOUNDED입니다. 그렇지 않으면 $y$는 얻을 수 있는 납의 최대 그램 수를 $10^9+7$로 나눈 나머지입니다.

모든 $i$에 대해 $1 \le R_{i1} < R_{i2} \le M$입니다.

테스트 케이스 1에는 납 1그램을 납 1그램과 2번 금속 1그램으로 바꾸는 공식과, 2번 금속 1그램을 납 1그램과 2번 금속 1그램으로 바꾸는 공식이 있습니다. 두 공식을 번갈아 쓰면 두 금속을 원하는 만큼 얻을 수 있습니다.

테스트 케이스 2는 테스트 케이스 1과 같은 공식을 가지지만, 시작할 때 금속이 없습니다.

테스트 케이스 3에서는 납을 늘리는 공식이 없으므로, 처음보다 많은 납을 얻을 수 없습니다.