Cho bảng ô vuông gồm \(n\) hàng và \(n\) cột, trên mỗi ô sẽ chứa một số nguyên dương hoặc một chướng ngại vật. Bạn cần lập trình đếm số lượng đường đi từ ô trên cùng bên trái đến ô dưới cùng bên phải, thỏa mãn các điều kiện sau:

• Không tồn tại chướng ngại vật nào trên đường đi.
• Tại mỗi bước di chuyển, chỉ được phép đi từ ô hiện tại sang một ô chung cạnh bên phải hoặc phía dưới.
• Tích các số trên các ô vuông của đường đi phải chia hết cho \(k\).

Vì kết quả có thể rất lớn nên bạn chỉ cần in ra phần dư của nó khi chia cho \(998244353\).

Input

Dòng đầu chứa hai số nguyên dương \(n\) và \(k\) (\(1\leq n\leq 500\), \(1\leq k\leq 10^6\)).

Dòng thứ \(i\) trong \(n\) dòng tiếp theo chứa \(n\) số nguyên \(a_{ij}\) mô tả một hàng của bảng ô vuông (\(-1\leq a_{ij}\leq 10^6\)). Nếu \(a_{ij}=-1\), ô vuông thứ \(j\) của hàng \(i\) đang chứa một chướng ngại vật, ngược lại, \(1\leq a_{ij}\leq 10^6\) và ô vuông đó đang chứa một số nguyên với giá trị \(a_{ij}\).

Output

In ra một số nguyên duy nhất là số lượng đường đi tìm được \(\text{mod}\) \(998244353\).

Ví dụ

Sample input 1

2 2
3 2
1 4

Sample output 1

2

Sample input 2

3 6
5 2 -1
7 3 6
-1 3 1

Sample output 2

3

Giải thích

Có đúng \(3\) đường đi thỏa mãn tích các số chia hết cho \(6\): \((5,2,3,3,1)\), \((5,2,3,6,1)\), và \((5,7,3,6,1)\).

Ràng buộc

• Subtask 1 (25 điểm): \(n,k, a_{ij}\leq 20\).
• Subtask 2 (25 điểm): \(n,k \leq 20\).
• Subtask 3 (25 điểm): \(k\leq 20\).
• Subtask 4 (25 điểm): Không có ràng buộc gì thêm.