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[i][j]\), \(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 \lt n; i \le p; j \le q\) và \(i+j \lt p+q\)
• \(a[i,j]\) và \(a[p,q]\) có ước chung lớn nhất 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 thứ nhất là hai số nguyên \(n,m\) cách nhau một khoảng trắng
• Trong \(m\) dòng tiếp theo, mỗi dòng là \(n\) số nguyên cách nhau một khoảng trắng.
• 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.

Dữ liệu ra

• 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^9\)

Ràng buộc

• \(1 \le M \le 100\)
• \(2 \le N \le 100\)
• \(1 \le a[i][j] \le 3000\)

Input 1

2 2
2 4
6 8

Output 1

4