GRID11


Submit solution

Points: 20
Time limit: 1.0s
Memory limit: 512M

Problem type

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

There are no comments at the moment.