E. XGCD

Khi nghiên cứu về lý thuyết dãy số, Nam đã tìm ra một đặc trưng cho dãy số nguyên dương. Cụ thể, với dãy số gồm phần tử, xét lần lượt các phần tử từ đến , với phần tử , Nam tính được số bằng (ký hiệu để chỉ ƯCLN của các số ). Dãy số được gọi là dãy đặc trưng của dãy số . Dễ nhận thấy rằng một dãy số chỉ có duy nhất một dãy đặc trưng, tuy nhiên, có thể có nhiều dãy số khác nhau nhưng có cùng một dãy đặc trưng.

Bẵng đi một thời gian, một hôm, Nam tìm lại được một file văn bản ghi một dãy số là một dãy đặc trưng của một dãy số khác. Nam muốn tính số lượng dãy số mà có dãy đặc trưng là .

Yêu cầu: Cho dãy số ), gọi là số lượng dãy số có dãy đặc trưng là dãy , hãy tính mod .

Chú ý:

• với mọi ;
• Ước chung lớn nhất (gcd) của hai số là số nguyên dương lớn nhất mà hai số cùng chia hết cho số đó.

Dữ liệu:

• Dòng đầu tiên gồm hai số nguyên dương ;
• Dòng thứ hai gồm số nguyên dương , dãy đảm bảo luôn có dãy thỏa mãn.

Kết quả:

• Một số nguyên duy nhất là giá trị mod .

Ví dụ:

Dữ liệu:

3 5
4 2 1

Kết quả:

3

Giới hạn:

• Subtask ( số điểm): ;
• Subtask ( số điểm): ;
• Subtask ( số điểm): .