Cho một lưới ô vuông gồm dòng và cột. Các dò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 ở vị trí dòng và cột của lưới được gọi là ô và khi đó, được gọi là tọa độ dòng còn được gọi là tọa độ cột của ô này. Trên ô của lưới ghi số nguyên dương . Trên lưới đã cho, từ ô ta có thể di chuyển đến ô nếu và một trong các điều kiện sau đây được thỏa mãn:
và (đi xuống dưới).
và (đi sang phải).
Ta gọi một cách di chuyển từ mép trái sang mép phải của lưới là cách di chuyển bắt đầu từ một ô có tọa độ cột bằng qua các ô của lưới theo qui tắc di chuyển đã nêu và kết thúc ở một ô có tọa độ cột bằng .
Yêu cầu: Tính số cách di chuyển từ mép trái lưới sang mép phải lưới.
Dữ liệu vào:
Dòng đầu gồm hai số nguyên dương và được ghi cách nhau một dấu cách.
dòng tiếp theo, dòng thứ chứa số nguyên dương , hai số liên tiếp được ghi cách nhau một dấu cách.
Dữ liệu ra:
Một số nguyên dương duy nhất là số cách di chuyển từ mép trái lưới sang mép phải lưới (do số này có thể rất lớn nên chỉ lấy phần nguyên khi chia cho 1000000007).
