Giải bài trực tuyến

Cho một lưới ô vuông gồm m dòng và n cột. Các dòng được đánh số từ 1 đến m từ trên xuống dưới, các cột được đánh số từ 1 đến n từ trái qua phải. Ô nằm ở vị trí dòng i và cột j của lưới được gọi là ô (i, j) và khi đó, i được gọi là tọa độ dòng còn j được gọi là tọa độ cột của ô này. Trên ô (i, j) của lưới ghi số nguyên dương a_ij, i = 1, 2, …, m; j = 1, 2, …, n. Trên lưới đã cho, từ ô (i, j) ta có thể di chuyển đến ô (p, q) nếu các điều kiện sau đây được thỏa mãn:

• j < n; i ≤ p; j ≤ q và i + j < p + q;
• a_ij và a_pq có ước số chung lớn hơn 1.

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 1 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 n.

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 tiên ghi 2 số nguyên dương m, n.
• Dòng thứ i trong số m dòng tiếp theo ghi n số nguyên dương a_i1, a_i2, …, a_in là các số trên dòng thứ i của lưới, i = 1, 2, …, m.

Hai số liên tiếp trên cùng một dòng được ghi cách bởi ít nhất một dấu cách.

Kết qủa

Ghi ra 1 số nguyên là phần dư của số lượng cách di chuyển tìm được cho 10⁹.

Hạn chế

Trong tất cả các test: 1 < m, n ≤ 100; a_ij ≤ 30000, i=1,2,…,m;j=1,2,…,n. Có 50% số lượng test với m, n ≤ 50.

Ví dụ

Dữ liệu mẫu
2 2
2 4
6 8

Kết qủa
4

Dữ liệu mẫu
2 2
2 5
6 7

Kết qủa
0