Trên sân hình vuông có ~n \times n~ ô vuông, các dòng và cột được đánh số từ ~1~ đến ~n~. Tại mỗi ô ~(i, j)~ hoặc chứa chướng ngại vật hoặc ghi số nguyên ~a_{i, j}~ (~1 \le i, j \le n, -1 \le a_{i, j} \le 10^6~). Nếu ~a_{i, j} = -1~ thì ô đó là chướng ngại vật. Robot nhận nhiệm vụ di chuyển từ ô ~(1, 1)~ đến ô ~(n, n)~. Tại ô ~(i, j)~ robot chỉ được di chuyển sang ô ~(i, j + 1)~ hoặc ~(i + 1, j)~, không được di chuyển ra khỏi sân, không được di chuyển vào ô có chướng ngại vật. Nếu đến được đích thì điểm thưởng sẽ được tính bằng tích của tất cả các số ghi trên các ô mà nó đi qua. Để tăng độ khó, người ta yêu cầu điểm thưởng phải là bội của một số nguyên ~k~ cho trước.

Yêu cầu: Đếm số đường đi mà robot đi đến được đích sao cho điểm thưởng là bội số của một số nguyên ~k~ cho trước, kết quả lấy modulo ~998244353~.

Output

Số lượng đường đi thỏa mãn yêu cầu sau khi modulo ~998244353~.

Subtasks

Subtask 1 (~40 \%~ số điểm): ~n \le 500, k = 1~.

Subtask 2 (~15 \%~ số điểm): ~n \le 500, k = 2~.

Subtask 3 (~15 \%~ số điểm): ~n \le 100, k \le 20~.

Subtask 4 (~30 \%~ số điểm): Không có ràng buộc nào thêm.

Sample Input 1

2 2
3 6
3 2

Sample Output 1

2

Sample Input 2

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

Sample Output 2

3