Iva is a big fan of candy! In front of her is an \(n\) times \(n\) field filled with candy and
obstacles. Iva is currently in the upper left cell of the field and by moving only
down and right she will travel to the lower right cell. The cell Iva is currently in
does not contain an obstacle.
In every cell, there is either an obstacle or a piece of candy with a number written
on it. Iva will eat all the candy she gets her hands on during her trip (including
the candy in the first and last cell) and then multiply all the numbers on them.
Iva knows her favourite number is \(k\) and she wants the product of the numbers on the candy she has eaten
to be divisible by \(k\). She wants to know how many such paths there are. Because that number can be
huge, she is interested in it modulo 998 244 353.

Subtask 1 (13 points): n, k, ai,\(j \le 20\)

Subtask 2 (17 points): n, \(k \le 20\)

Subtask 3 (33 points): \(k \le 20\)

Subtask 4 (47 points): No additional constraints

The first line contains two integers \(n\) and \(k\) (\(1 \le n \le 500\), \(1 \le k \le 10^{6}\)), which denote the size of the field
and Iva’s favourite number.
In each of the next \(n\) lines, there are \(n\) numbers describing the \(i-th\) row of the field (−\(1 \le a\)i,\(j \le 10^{6}\)). If
\(a\)i,j = −1, then that cell contains an obstacle, otherwise \(1 \le a\)i,\(j \le 10^{6}\) and that cell contains a piece of
candy with that number.

Print a single line with the required number from the task.

생성자가 기록되지 않았습니다.

출처 COCI 2022/2023 Contest 3