Cô bé hái nấm

Mỗi ngày một cô bé đi qua khu rừng để thăm bà. Khu rừng là một lưới \(n\) hàng, \(m\) cột; ô ở hàng \(i\), cột \(j\) ký hiệu \((i, j)\). Trong lưới:

• ô \((1,1)\) là nhà cô bé và ô \((n,m)\) là nhà bà, cả hai đều có giá trị \(0\) (không có nấm);
• mọi ô còn lại có giá trị \(-1\) (nấm độc, không được bước vào) hoặc một số \(t \in \{1, 2, 3\}\) (đúng một cây nấm ăn được loại \(t\); khi bước vào ô, cô bé hái loại nấm đó).

Cô bé đi từ \((1,1)\) đến \((n,m)\), mỗi bước chỉ sang phải hoặc xuống dưới. Để nấu súp, đường đi phải hái được ít nhất hai loại nấm ăn được khác nhau (trong ba loại \(1, 2, 3\)).

Đếm số đường đi thoả mãn (không đi qua nấm độc và hái được ít nhất hai loại nấm). Vì kết quả có thể rất lớn, in ra phần dư khi chia cho \(10^7\) (in số nguyên bình thường, không thêm số \(0\) ở đầu).

Input

• Dòng đầu chứa hai số nguyên \(n\) và \(m\).
• \(n\) dòng tiếp theo, mỗi dòng \(m\) số nguyên mô tả lưới.

Output

• In ra một số nguyên: số đường đi thoả mãn, chia lấy dư cho \(10^7\).

Constraints

• \(1 \le n, m \le 500\)
• Ô \((1,1)\) và \((n,m)\) có giá trị \(0\); các ô khác có giá trị thuộc \(\{-1, 1, 2, 3\}\).

Sample Input 1

3 4
0 2 -1 1
2 2 2 3
1 3 2 0

Sample Output 1

5

Sample Input 2

4 5
0 3 1 -1 -1
1 1 -1 2 2
-1 2 2 2 -1
3 1 -1 1 0

Sample Output 2

2