GRID11
Một bảng hình chữ nhật kích thước là \(M\) x \(N\), trong đó các dòng được đánh số thứ tự từ 1 tới \(M\), các cột được đánh số thứ tự từ 1 tới \(N\). Trên mỗi ô ghi một số nguyên dương \(C[i,j]\) gọi là độ cao của ô \((i,j)\).
Một Robot cần đi từ vị trí có tọa độ \((1,1)\) tới vị trí có tọa độ \((M,N)\). Từ một ô \((i,j)\) Robot có thể di chuyển sang ô \((i+1,j)\) hoặc ô \((i,j+1)\), sao cho chênh lệnh độ cao giữa hai ô đó là một số nguyên tố.
Yêu cầu: Tính số lượng cách di chuyển Robot từ ô \((1,1)\) tới ô \((M,N);\)
INPUT:
Dòng 1 ghi 2 số nguyên \(M\) và \(N (1 ≤ M, N ≤ 100)\).
M dòng tiếp theo, mỗi dòng ghi \(N\) số nguyên dương \(C[i,j] (C[i,j] ≤ 100)\)
OUTPUT
- Một dòng duy nhất chứa số cách di chuyển từ (1,1) đến \((M,N)\) (lấy phần dư của phép chia cho \(10^9+7\))
Sample Input
5 6
1 4 8 6 2 9
6 9 12 15 8 4
8 12 2 4 13 4
7 5 7 9 11 9
8 6 8 9 14 16
Sample Output
12
Comments