Tesoro OCI.


Submit solution

Points: 100 (partial)
Time limit: 2.0s
Memory limit: 512M

Authors:
Problem type
Allowed languages
C, C++, Java, JS, Pascal, Python, VB

¡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

Comments


  • 1
    Marco_Escandon  commented on Jan. 24, 2024, 4:39 p.m.

    El modulo en el problema a deberia ser 998244353 no 99824435