Iva is a big fan of candy! In front of her is an $n$ times $n$ field filled with candy and obstacles. Iva is currently in the upper left cell of the field, and by moving only down and right, she will travel to the lower right cell. The cell Iva is currently in does not contain an obstacle.

In every cell, there is either an obstacle or a piece of candy with a number written on it. Iva will eat all the candy she gets her hands on during her trip (including the candy in the first and last cell) and then multiply all the numbers on them. Iva knows her favourite number is $k$, and she wants the product of the numbers on the candy she has eaten to be divisible by $k$. She wants to know how many such paths there are. Because that number can be huge, she is interested in it modulo $998244353$.

Input Specification

The first line contains two integers $n$ and $k$ $(1\le n\le 500,1\le k\le {10}^6)$, which denote the size of the field and Iva's favourite number.

In each of the next $n$ lines, there are $n$ numbers describing the $i$-th row of the field $(-1\le a_{i,j}\le {10}^6)$. If $a_{i,j}=-1$, then that cell contains an obstacle; otherwise, $1\le a_{i,j}\le {10}^6$ and that cell contains a piece of candy with that number.

Output Specification

Print a single line with the required number from the task.

Constraints

Subtask	Points	Constraints
$1$	$13$	$n,k,a_{i,j}\le 20$
$2$	$17$	$n,k\le 20$
$3$	$33$	$k\le 20$
$4$	$47$	No additional constraints.

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

Explanation for Sample 2

There are three possible paths such that the product is divisible by $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$.