Bomboni

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's favourite number is $k$, and she wants the product of the numbers on the candy she has eaten to be divisible by $k$. Count how many such paths there are. Because that number can be huge, print it modulo $998\,244\,353$.

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.

Each of the next $n$ lines contains $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.

Print a single line with the required number.

Clarification of the second example:

There are three possible paths such that the product is divisible by 6: (5, 2, 3, 3, 1), (5, 2, 3, 6, 1), (5, 7, 3, 6, 1).