Vương quốc Inversland
Đề bài
Mô tả
Vương quốc Inversland phát hành mệnh giá tiền, mệnh giá thứ có giá trị đô la. Để việc đổi tiền càng thêm rắc rối, tất cả các giá trị đều là các số nguyên tố đôi một phân biệt.
Một nhược điểm của bộ mệnh giá này là trong một số trường hợp, để trả một khoản tiền nhất định, người trả và người nhận buộc phải trao đổi tiền qua lại. Ví dụ, với và , để trả đô la, người trả có thể đưa hai tờ và nhận lại một tờ tiền thối. Có thể chứng minh rằng không có cách nào trả đô la mà người nhận không phải thối lại tiền. Ngược lại, để trả đô la, người trả có thể đưa một tờ và một tờ mà không cần nhận tiền thối.
Để đánh giá mức độ nghiêm trọng của nhược điểm này, chính phủ muốn đếm số khoản tiền thỏa mãn đồng thời hai điều kiện:
- có thể trả khoản tiền đó bằng các mệnh giá hiện có, và
- không thể trả khoản tiền đó mà người nhận không phải thối lại tiền.
Cho mệnh giá, chính phủ nhờ bạn, một đội lập trình đã giành quyền thi khu vực, đếm số khoản tiền như vậy và in ra kết quả theo modulo . Nếu có vô số khoản tiền như vậy, hãy thông báo điều đó.
Dữ liệu vào
Dòng đầu tiên chứa số nguyên (): số bộ test. Mỗi bộ test gồm:
- Dòng đầu tiên chứa số nguyên (): số mệnh giá.
- Dòng thứ hai chứa số nguyên tố phân biệt () mô tả bộ mệnh giá.
Tổng trên tất cả các bộ test không vượt quá .
Dữ liệu ra
Với mỗi bộ test, nếu có vô số khoản tiền thỏa mãn, in ra infinity. Ngược lại, in ra số khoản tiền thỏa mãn theo modulo .
Ràng buộc
- , tổng không vượt quá
- , các là số nguyên tố đôi một phân biệt
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 2 3 5 10 941 947 953 967 971 977 983 991 997 998244341 |
4 679849251 |
Bộ test thứ nhất: mọi khoản tiền dạng với nguyên dương đều trả được bằng các tờ và . Trong đó các khoản không thể trả mà không cần thối tiền. |
| 2 3 2 3 5 2 2 7 |
15 3 |
Bộ test thứ hai: các khoản cần thối tiền là . |
Bình luận