Câu lạc bộ Ocean
Đề bài
Mô tả
Bi rất thích loạt phim Ocean trên kênh HBO. Vì quá yêu thích, Bi đã lập một câu lạc bộ Ocean của riêng mình trong lớp. Để luyện kỹ năng giống các nhân vật trong phim, Bi đưa ra một bài toán cho các thành viên luyện tập như sau.
Câu lạc bộ Ocean của Bi có thành viên, số nhà của họ lần lượt là (các số đôi một khác nhau). Quy tắc liên lạc của câu lạc bộ là: thành viên ở nhà số có thể chuyển tin trực tiếp cho thành viên ở nhà số khi và chỉ khi và , nguyên tố cùng nhau ().
Bi yêu cầu các thành viên tính nhanh: để chuyển tin từ nhà số tới nhà số sao cho tin đi qua đúng người (tính cả người gửi ở nhà và người nhận ở nhà ), tức là tin được chuyển trực tiếp đúng lần, thì có bao nhiêu cách?
Các thành viên câu lạc bộ chưa giỏi việc này, nên Bi nhờ bạn tính giúp.
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên (): số thành viên.
- Dòng thứ hai chứa số nguyên đôi một khác nhau (): danh sách số nhà.
- Dòng thứ ba chứa số nguyên (): số câu hỏi Bi đưa ra.
- dòng tiếp theo, mỗi dòng chứa ba số nguyên (; ; ).
Dữ liệu ra
In ra dòng, dòng thứ là đáp án của câu hỏi thứ . Vì kết quả có thể rất lớn, hãy in ra phần dư của nó khi chia cho .
Ràng buộc
- , , các đôi một khác nhau
- ; ;
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 7 2 3 4 5 6 7 8 1 2 8 3 |
3 | Có cách chuyển tin từ nhà tới nhà qua đúng người: , và . |
| 4 9 2 5 4 4 2 9 1 2 9 2 2 2 1 4 9 1 |
1 1 0 1 |
Các cách: (một lần chuyển); (hai lần chuyển). Không thể chuyển từ nhà tới chính nó. Từ nhà tới nhà có cách . |
Bình luận