题目描述

译自 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$，表示这个格子中糖果上写的数字。

输出格式

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

2 2
3 2
1 4

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$

数据范围与提示

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