¡Oci-kun es un gran fanático de las joyas! Delante de él hay un laberinto de ~n \times n~ lleno de cofres y obstáculos. Oci-kun se encuentra actualmente en la celda superior izquierda del laberinto y, moviéndose solo hacia abajo y hacia la derecha, viajará a la celda inferior derecha. La celda en la que se encuentra Oci-kun actualmente no contiene un obstáculo.

En cada celda, hay un obstáculo o un cofre con una joya que tiene un número escrito en ella. Oci-kun recogerá todas las joyas que encuentre en su viaje (incluyendo la joya en el primer y último cofre) y luego multiplicará todos los números en ellas.

Oci-kun sabe que su número favorito es ~k~ y quiere que el producto de los números en las joyas que ha recogido sea divisible por ~k~. Él quiere saber cuántos caminos de este tipo existen. Debido a que ese número puede ser enorme, está interesado en él módulo ~998244353~.

Entrada

La primera línea contiene dos enteros ~n~ y ~k~ (~1 \leq n \leq 500~, ~1 \leq k \leq 10^6~), que denotan el tamaño del campo y el número favorito de Iva.

En cada una de las siguientes ~n~ líneas, hay ~n~ números que describen la i-ésima fila del campo (~-1 \leq a_{i,j} \leq 10^6~). Si ~a_{i,j} = -1~, entonces esa celda contiene un obstáculo, de lo contrario ~1 \leq a_{i,j} \leq 10^6~ esa celda contiene una joya con ese número.

Salida

Imprime una sola línea con el número requerido de la tarea.

Subtareas

• Subtarea 1 [11 puntos]: ~n, k, a_{i,j} \leq 20~
• Subtarea 2 [15 puntos]: ~n, k \leq 20~
• Subtarea 3 [30 puntos]: ~k \leq 20~
• Subtarea 4 [44 puntos]: No hay restricciones adicionales

Ejemplo #1 de Entrada

2 2
3 2
1 4

Ejemplo #1 de Salida

2

Ejemplo #2 de Entrada

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

Ejemplo #2 de Salida

3