Cho một bảng số nguyên gồm \(n\) hàng và \(n\) cột. Các hàng được đánh số thứ tự từ \(1\) đến \(n\) theo hướng từ trên xuống dưới và các cột được đánh số thứ tự từ \(1\) đến \(n\) theo hướng từ trái sang phải. Ô nằm ở hàng \(i\) cột \(j\) có tọa độ là \((i,j)\). Mỗi ô \((i,j)\) trên bảng được ghi một số nguyên \(a_{i,j}\). Trong đó:

• \(a_{i,j}=-1\) cho biết ô này bị cấm
• \(1 \le a_{i,j} \le 10^6\) cho biết ô này có thể đi qua và có giá trị là \(a_{i,j}\)

Xuất phát từ ô \((1,1)\) ta cần di chuyển đến ô \((n,n)\) theo quy tắc sau:

• Không được di chuyển vào ô cấm
• Mỗi bước di chuyển ta chỉ có thể di chuyển xuống ô kề cạnh phía dưới hoặc di chuyển sang ô kề cạnh bên phải.

Giá trị của đường đi là tích của các giá trị trong các ô đi qua. Hai đường đi được gọi là khác nhau nếu có ít nhất một ô xuất hiện trên đường đi này nhưng không xuất hiện trên đường đi còn lại.

Yêu cầu

• Hãy lập trình xác định số lượng đường đi sao cho giá trị của đường đi chia hết cho một số nguyên dương \(k\) cho trước.

Dữ liệu vào

• Dòng đầu ghi hai số nguyên dương \(n\) và \(k\) \((n \le 500, k \le 10^6)\)
• \(n\) dòng tiếp theo, mỗi dòng ghi \(n\) số nguyên cho biết bảng số
• Dữ liệu đảm bảo ô \((1,1)\) không là ô cấm.

Kết quả

• Một số là phần dư của kết quả tìm được khia chia cho \(10^9+7\)

Ràng buộc

• 20% số điểm có \(n,k,a_{i,j} \le 10\)
• 20% số điểm có \(n,k \le 10\)
• 20% số điểm có \(n \le 100, k=1\)
• 40% số điểm còn lại không có ràng buộc gì thêm.

Input 1

3 10
7 2 -1
3 5 10
-1 5 1

Output 1

3