P9759 [COCI 2022/2023 #3] Bomboni

Iva is a crazy candy fan! In front of her there is an $n \times n$ grid filled with candies and obstacles. Iva is currently at the top-left corner. By moving right or down, she needs to reach the bottom-right corner. The cell where Iva currently stands has no obstacle. In each cell there is a number indicating either a candy or an obstacle. Iva will eat all candies she passes through (including the candies at the start and the end) and multiply the corresponding numbers. Iva knows that her favorite number is $k$, so she wants this product to be divisible by $k$. She wants to know how many such paths there are. Since the answer may be very large, she only wants the result modulo $998244353$.

The first line contains two integers $n, k$, denoting the side length of the grid and Iva's favorite number. In the next $n$ lines, each line contains $n$ numbers describing the grid. If $a_{i,j} = -1$, then that cell is an obstacle; otherwise, that cell contains a number satisfying $1 \le a_{i,j} \le 10^6$.

Output one integer, the answer.

**Sample Explanation #2.** There are three such paths: - 5-2-3-3-1 - 5-2-3-6-1 - 5-7-3-6-1 **Constraints.** | Subtask | Points | Special Properties | | :----------: | :----------: | :----------: | | $1$ | $13$ | $n, k, a_{i,j} \le 20$ | | $2$ | $17$ | $n, k \le 20$ | | $3$ | $33$ | $k \le 20$ | | $4$ | $47$ | No special properties | For $100\%$ of the testdata, $1 \le n \le 500$, $1 \le k \le 10^6$, and $-1 \le a_{i,j} \le 10^6$. The full score for this problem is $110$ points. Translated by ChatGPT 5