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 \leq p~; ~j \leq 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.

Input

• 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.

Output

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}~ .

Giới hạn

• Trong tất cả các test: ~1 < m~, ~n \leq 100~; ~a_{ij} \leq 30000~, ~i = 1~, ~2~, ..., ~m~; ~j = 1~, ~2~, ..., ~n~.
• Có ~50\%~ số lượng test với ~m~, ~n \leq 50~.

Sample Input 1

2 2
2 4
6 8

Sample Output 1

4

Sample Input 2

2 2
2 5
6 7

Sample Output 2

0