Mai là một người rất thích kẹo! Trước mặt cô ấy là một bảng kích thước ~n \times n~ chứa các viên kẹo và chướng ngại vật. Mai hiện đang đứng ở ô góc trên bên trái của bảng, và bằng cách chỉ di chuyển xuống dưới và sang phải, cô ấy sẽ đi tới ô góc dưới bên phải. Ô mà Mai đang đứng không chứa chướng ngại vật.

Trong mỗi ô, có thể có một chướng ngại vật hoặc một viên kẹo có ghi một số trên đó. Mai sẽ ăn tất cả kẹo mà cô ấy đi qua (bao gồm cả ô đầu và ô cuối), sau đó nhân tất cả các số trên những viên kẹo đó lại với nhau.

Mai biết số ưa thích của mình là ~k~, và cô muốn tích các số trên kẹo mà cô ăn chia hết cho ~k~. Cô muốn biết có bao nhiêu đường đi thỏa mãn điều này. Vì kết quả có thể rất lớn, cô chỉ quan tâm đến kết quả theo modulo ~998244353~.

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~k~ ~(1 \le n \le 500; 1 \le k \le 10^6)~, biểu thị kích thước bảng và số yêu thích của Mai.

• Trong mỗi dòng tiếp theo (tổng cộng ~n~ dòng), có ~n~ số mô tả hàng thứ ~i~ của bảng ~(-1 \le a_{i,j} \le 10^6)~:

  • Nếu ~a_{i,j}=-1~: ô đó là chướng ngại vật;

  • Nếu ~1 \le a_{i,j} \le 10^6~: ô đó chứa một viên kẹo có số tương ứng.

Output

In ra một số nguyên duy nhất là kết quả của bài toán.

Scoring

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

Notes

Ở ví dụ thứ hai, có các đường đi sao cho tích các số chia hết cho ~6~:

• ~5 \cdot 2 \cdot 3 \cdot 3 \cdot 1~

• ~5 \cdot 2 \cdot 3 \cdot 6 \cdot 1~

• ~5 \cdot 7 \cdot 3 \cdot 6 \cdot 1~