Di chuyển trên lưới ước chung

Cho một bảng gồm \(m\) hàng và \(n\) cột. Ô ở hàng \(i\), cột \(j\) (hàng đếm từ trên xuống, cột đếm từ trái sang) được ký hiệu \((i, j)\) và chứa một số nguyên dương \(a_{i,j}\).

Một bước đi từ ô \((i, j)\) đến ô \((p, q)\) được phép khi và chỉ khi:

• \(j < n\), \(i \le p\), \(j \le q\) và \((p, q) \ne (i, j)\) (tức \(i + j < p + q\));
• \(\gcd(a_{i,j}, a_{p,q}) > 1\).

Một hành trình là dãy các ô, bắt đầu từ một ô bất kỳ nằm ở cột \(1\), mỗi bước là một bước đi được phép, và kết thúc ở một ô nằm ở cột \(n\). Hai hành trình khác nhau nếu dãy ô khác nhau.

Hãy đếm số hành trình từ mép trái sang mép phải của bảng. In kết quả theo modulo \(10^9\).

Input

• Dòng đầu chứa hai số nguyên dương \(m\) và \(n\).
• \(m\) dòng tiếp theo, mỗi dòng gồm \(n\) số nguyên \(a_{i,1}, \dots, a_{i,n}\).

Output

• In ra một số nguyên: số hành trình modulo \(10^9\).

Constraints

• \(1 \le m \le 100\)
• \(2 \le n \le 100\)
• \(1 \le a_{i,j} \le 3000\)

Sample Input

3 3
6 9 3
4 15 12
10 5 8

Sample Output

15

Explanation

Ví dụ, hành trình \((1,1) \to (1,2) \to (1,3)\) hợp lệ vì \(\gcd(6,9)=3\) và \(\gcd(9,3)=3\); hành trình \((2,1) \to (3,3)\) hợp lệ vì \(\gcd(4,8)=4\) và \(3 < 6\). Tổng cộng có \(15\) hành trình.