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

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,\dots ,m$; $j=1,2,\dots ,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\le p$; $j\le 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},\dots ,a_{in}$ là các số trên dòng thứ $i$ của lưới, $i=1,2,\dots ,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.

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<m,n\le 100$.
• $1\le a_{ij}\le 30000$.

Subtasks

• Subtask 1 ($50\%$ số test): $m,n\le 50$.
• Subtask 2 ($50\%$ số test): không có ràng buộc gì thêm.

Mỗi subtask gồm nhiều test, mỗi test được chấm điểm riêng.

Ví dụ