Iva's Candy Challenge

Iva is a candy fanatic! Before her lies an n × n grid, each cell of which contains either a candy with a positive integer value or an obstacle (represented by 0). Iva starts at the top‐left corner (which is always free of obstacles) and wants to reach the bottom‐right corner by moving only to the right or down. As she passes through a cell with a candy, she picks it up and multiplies its value to her current product (including the starting and ending cells). Iva loves the number \(k\) and she wishes the final product to be divisible by \(k\). Obstacles (cells with a 0) cannot be entered. Your task is to count the number of valid paths from the top‐left to the bottom‐right cell such that the product of the candy values is divisible by \(k\). Since the answer can be very large, output it modulo \(998244353\).

Note: A cell with 0 represents an obstacle and cannot be part of the path.

Hint: Factorize \(k\) as \(k = p_1^{r_1} \cdots p_m^{r_m}\) and use dynamic programming while keeping track of the exponents collected so far (capped at \(r_i\)).

inputFormat

The first line contains two integers \(n\) and \(k\) (1 ≤ \(n\) ≤ 100, 1 ≤ \(k\) ≤ 10⁹).

The next \(n\) lines each contain \(n\) integers. Each integer is either a positive number representing the candy value in that cell or 0 representing an obstacle. It is guaranteed that the top-left cell is not an obstacle.

outputFormat

Output a single integer: the number of valid paths from the top-left to the bottom-right cell such that the product of the candy values is divisible by \(k\), modulo \(998244353\).

sample

2 2
2 4
1 2

2