C. LOCO - Nhảy lò cò

Cho ô (đánh số thứ tự từ đến ), Hải Dương sẽ nhảy lò cò từ ô số và kết thúc tại ô . Tại mỗi bước nhảy, nếu Hải Dương đang ở ô số thì Hải Dương có thể:

• Chọn một số nguyên dương bất kỳ từ tập số nguyên dương ;
• Nhảy đến ô .

Yêu cầu: Đếm số cách khác nhau để Hải Dương có thể nhảy từ ô số đến ô số theo modulo .

Ghi chú: Hai dãy số và được gọi là khác nhau nếu:

• hoặc

Dữ liệu vào:

• Dòng đầu tiên chứa hai số nguyên dương ;
• Dòng tiếp theo chứa số nguyên dương . Các số trên một dòng được ghi cách nhau bởi dấu cách.

Dữ liệu ra:

• Ghi ra một số nguyên duy nhất là số cách khác nhau để Hải Dương có thể nhảy từ ô số đến ô số theo modulo .

Ví dụ:

Dữ liệu vào:

3 4
1 2 2 2

Dữ liệu ra:

3

Giải thích:

• Có ba cách sau:

Dữ liệu vào:

3 4
2 2 2 2

Dữ liệu ra:

0