Năm ngoái, chúng tôi đã nhờ bạn giúp biến đổi những kim loại đắt tiền thành chì. (Bạn không cần biết gì về bài toán trước để giải bài này.) Nhưng nhà lãnh đạo đất nước bạn vẫn tham lam và muốn có thêm chì!

Trên thế giới có \(M\) kim loại đã được biết đến; chì là kim loại số 1 trong bảng tuần hoàn của bạn. Nhà lãnh đạo đã yêu cầu bạn dùng các kim loại trong kho bạc để tạo ra nhiều chì nhất có thể.

Với mỗi kim loại (kể cả chì), bạn biết đúng một công thức cho phép phá hủy một gram kim loại đó và tạo ra một gram của mỗi kim loại trong hai kim loại khác. (Tốt nhất đừng suy nghĩ quá nhiều về định luật bảo toàn khối lượng!) Công thức của kim loại thứ \(i\) có thể tạo ra chính kim loại thứ \(i\) làm một trong các sản phẩm. Công thức không áp dụng cho phần lẻ của một gram. Bạn có thể dùng mỗi công thức bao nhiêu lần tùy thích (hoặc không dùng), miễn là có một gram nguyên liệu cần thiết.

Nếu lựa chọn tối ưu, số gram chì lớn nhất cuối cùng bạn có thể có là bao nhiêu, hay lượng đó không bị chặn? Nếu có giới hạn, vì kết quả có thể rất lớn, chỉ cần in phần dư khi chia kết quả cho số nguyên tố \(10^9+7\) (tức \(1000000007\)).

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Tiếp theo là \(T\) bộ test. Mỗi bộ bắt đầu bằng số nguyên \(M\), là số kim loại đã biết. Sau đó có \(M\) dòng, mỗi dòng gồm hai số nguyên \(R_{i1}\) và \(R_{i2}\); dòng thứ \(i\) (đánh số từ 1) cho biết có thể phá hủy một gram kim loại \(i\) để tạo một gram kim loại \(R_{i1}\) và một gram kim loại \(R_{i2}\). Cuối cùng là một dòng gồm \(M\) số nguyên \(G_1,G_2,…,G_M\); \(G_i\) là số gram kim loại \(i\) trong kho bạc. Chì là kim loại 1.

Dữ liệu ra

Với mỗi bộ test, in một dòng dạng Case #x: y, trong đó x là số thứ tự bộ test (bắt đầu từ 1). Nếu lượng chì tối đa có thể tạo ra không bị chặn, y phải là UNBOUNDED. Nếu không, y là lượng chì lớn nhất (tính bằng gram) cuối cùng có thể có, lấy modulo \(10^9+7\) (tức \(1000000007\)).

Ràng buộc

• \(1≤ R_{i1}<R_{i2}≤ M\) với mọi \(i\).

Phân nhóm

Test Set 1 (Công khai)

• \(1≤ T≤100\).
• \(2≤ M≤10\).
• \(0≤ G_i≤10\) với mọi \(i\).

Test Set 2 (Ẩn)

• \(1≤ T≤100\).
• \(2≤ M≤100\).
• \(0≤ G_i≤10^9\) với mọi \(i\).

Test Set 3 (Ẩn)

• \(1≤ T≤5\).
• \(2≤ M≤10^5\).
• \(0≤ G_i≤10^9\) với mọi \(i\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

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

Nguồn

Google Code Jam 2019, Vòng 2, bài Contransmutation.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.