Contransmutation

작년에 우리는 값비싼 금속을 납으로 변환하는 일을 도와달라고 요청했다. (이 문제를 풀기 위해 이전 문제에 관해 아무것도 알 필요는 없다.) 하지만 여러분 나라의 지도자는 여전히 더 많은 납을 탐내고 있다!

세상에는 M개의 금속이 알려져 있으며, 주기율표에서 납은 1번 금속이다. 여러분 나라의 지도자는 국고에 있는 금속을 사용해 가능한 한 많은 납을 만들라고 요청했다.

각 금속(납 포함)에 대해, 그 금속 한 그램을 없애고 두 금속을 각각 한 그램씩 생성할 수 있는 공식을 정확히 하나 알고 있다. (질량 보존의 원리에 대해서는 너무 깊이 생각하지 않는 편이 좋다!) i번째 금속의 공식이 생성물 중 하나로 i번째 금속 자체를 만들 수도 있음에 유의하라. 공식은 일 그램 미만의 양에는 적용되지 않는다. 하지만 필요한 재료가 한 그램 있는 한, 각 공식을 원하는 만큼 자주 사용할 수 있다(또는 전혀 사용하지 않아도 된다).

최적의 선택을 한다면, 최종적으로 얻을 수 있는 납은 최대 몇 그램인가? 아니면 그 양에 상한이 없는가? 상한이 있다면, 출력값이 매우 큰 수일 수 있으므로 결과를 소수 $10^{9}$+7(즉, 1000000007)로 나눈 나머지만 출력하면 된다.

제한

1 ≤ $R_{i1}$ < $R_{i2}$ ≤ M, 모든 i에 대해. 시간 제한: 테스트 세트당 20초. 메모리 제한: 1GB.

테스트 세트 1 (공개)

1 ≤ T ≤ 100. 2 ≤ M ≤ 10. 0 ≤ $G_{i}$ ≤ 10, 모든 i에 대해.

테스트 세트 2 (비공개)

1 ≤ T ≤ 100. 2 ≤ M ≤ 100. 0 ≤ $G_{i}$ ≤ $10^{9}$, 모든 i에 대해.

테스트 세트 3 (비공개)

1 ≤ T ≤ 5. 2 ≤ M ≤ $10^{5}$. 0 ≤ $G_{i}$ ≤ $10^{9}$, 모든 i에 대해.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 세상에 알려진 금속의 수를 나타내는 정수 M이 있는 한 줄로 시작한다. 그다음에는 각각 두 정수 $R_{i1}$와 $R_{i2}$가 있는 M개의 줄이 더 주어진다. 1부터 세었을 때 이 줄들 중 i번째 줄은 금속 i 한 그램을 없애 금속 $R_{i1}$ 한 그램과 금속 $R_{i2}$ 한 그램을 생성할 수 있음을 나타낸다. 마지막으로 M개의 정수 $G_{1}$, $G_{2}$, ..., $G_{M}$가 있는 한 줄이 주어진다. $G_{i}$는 국고에 있는 금속 i의 그램 수이다. 납은 금속 1이다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호이다. 생산할 수 있는 납의 최대량에 상한이 없다면, y는 UNBOUNDED여야 한다. 그렇지 않으면 y는 최종적으로 얻을 수 있는 납의 최대량을 그램 단위로 나타낸 값을 소수 $10^{9}$+7(즉, 1000000007)로 나눈 나머지여야 한다.

예제 케이스 #1에서는 납 1그램을 납 1그램과 두 번째 금속 1그램으로 바꾸는 공식 하나와, 두 번째 금속 1그램을 납 1그램과 두 번째 금속 1그램으로 바꾸는 또 다른 공식이 있다. 이 공식들을 번갈아 사용하면 두 금속 모두 원하는 만큼 많이 생산할 수 있다.

예제 케이스 #2의 공식은 예제 케이스 #1와 같지만, 처음에 가진 금속이 전혀 없다!

예제 케이스 #3에서는 어느 공식도 납을 더 많이 생산하는 데 도움이 되지 않으므로, 처음에 가진 양보다 더 많은 납을 최종적으로 얻을 수 없다.