Tesoro OCI.
¡Oci-kun es un gran fanático de las joyas! Delante de él hay un laberinto de 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 y quiere que el producto de los números en las joyas que ha recogido sea divisible por . É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 .
Entrada
La primera línea contiene dos enteros y (, ), que denotan el tamaño del campo y el número favorito de Iva.
En cada una de las siguientes líneas, hay números que describen la i-ésima fila del campo (). Si , entonces esa celda contiene un obstáculo, de lo contrario 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]:
- Subtarea 2 [15 puntos]:
- Subtarea 3 [30 puntos]:
- 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
El modulo en el problema a deberia ser 998244353 no 99824435