[AdditionalFile3926.zip](file://AdditionalFile3926.zip?type=additional_file)

#3926. 「COCI 2023.1」Bomboni

标签: 传统 | 时间限制: 2000 ms | 内存限制: 512 MiB |

题目描述

译自 COCI 2022/2023 Contest #3 T4「Bomboni」

Iva 十分喜欢糖！在她面前是一个 $n\times n$ 且有糖果和障碍物的网格。Iva 目前在左上角的单元格，她只能向下或向右移动到右下角单元格中。目前 Iva 处在的单元格中没有障碍物。

在每个单元格中，要么有一个障碍物，要么有一块上面写有一个数字的糖。Iva 会吃掉她经过的单元格中所有的糖（包括第一个和最后一个单元格中的），然后将糖上面的数字乘起来。Iva 知道她最喜欢的数字是 $k$，她希望她吃掉的糖上面的数字乘积可以被 $k$ 整除。她想知道有多少条满足条件的路径。因为这个数字可能很大，她想知道它对 $998\ 244\ 353$ 取模后的值。

输入格式

第一行包含两个整数 $n$ 和 $k\ (1\le n\le 500,1\le k\le 10^6)$，表示网格大小和 Iva 最喜欢的数字。

接下来 $n$ 行，每行 $n$ 个整数 $a_{i,j}\ (-1\le a_{i,j}\le 10^6)$ 描述这个网格。如果 $a_{i,j}=-1$，则这个格子中有障碍物，否则 $1\le a_{i,j}\le 10^6$，表示这个格子中糖果上写的数字。

输出格式

输出题目描述中要求的答案。

样例 1

输入

2 2
3 2
1 4

输出

2

样例 2

输入

3 6
5 2 -1
7 3 6
-1 3 1

输出

3

有三条可以被 $6$ 整除的路径：

• $5\cdot 2\cdot 3\cdot 3\cdot 1$
• $5\cdot 2\cdot 3\cdot 6\cdot 1$
• $5\cdot 7\cdot 3\cdot 6\cdot 1$

数据范围与提示

详细子任务附加限制及分值如下表所示。