Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

NKPATH - Đường đi trên lưới

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/nkpath


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 aij, 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;
  • aij và apq 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 ai1, ai2, …, ain 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 109.

Hạn chế

Trong tất cả các test: 1 < m, n ≤ 100; aij ≤ 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

Được gửi lên bởi:Jimmy
Ngày:2007-12-27
Thời gian chạy:5s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:Đề thi quốc gia 2006

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.