Xét bảng hình chữ nhật kích thước ô. Các hàng được đánh số từ đến từ trên xuống dưới, các cột được đánh số từ đến từ trái qua phải. Ô nằm trên hàng và cột được ghi một số nguyên không âm, ký hiệu . Ở góc trên trái bảng có một quân cờ. Ta phải chuyển quân cờ về ô dưới phải của bảng theo quy tắc sau:
Tại mỗi bước nhảy, chỉ được di chuyển sang phải trên cùng một hàng hoặc di chuyển xuống dưới theo cùng một cột;
Kích thước bước nhảy không được vượt quá số ghi trên ô có quân cờ hiện tại;
Chỉ được di chuyển trong phạm vi bảng đang xét;
Kích thước của bước nhảy từ ô tới ô được tính bằng giá trị .
Yêu cầu: Cho dãy và số nguyên dương . Bảng kích thước được xác định với . Hãy tính số lượng cách di chuyển quân cờ từ ô trên trái xuống ô dưới phải .
Dữ liệu vào:
Dòng đầu chứa ba số nguyên dương
Dòng thứ hai chứa số nguyên
Dòng thứ ba chứa số nguyên
Dữ liệu ra:
Ghi ra một số nguyên duy nhất là số cách di chuyển tìm được lấy theo module .
Ví dụ:
Dữ liệu vào:
3 2 1
3 4 11
2 5
Dữ liệu ra:
2
Giới hạn:
số test tương ứng số điểm có
số test khác tương ứng số điểm có
số test khác tương ứng số điểm có
số test khác tương ứng số điểm có
số test còn lại tương ứng số điểm không có ràng buộc gì thêm
