题目描述

Iva 是一个狂热的糖果迷！在她面前是一块填满糖果和障碍的 $n\times n$ 的土地。Iva 目前在左上角。通过向右或向下移动，她要前往右下角。Iva 目前所在的格子没有障碍。

在每个格子中写了一个数字表示此地为糖果或障碍。Iva 会吃掉所有经过的糖果（包括起点和终点的糖果）并且将糖果对应的数字相乘。Iva 知道她自己最喜欢的数字是 $k$，所以她希望这个乘积结果能被 $k$ 整除。她想知道一共有多少条这样的路径。由于答案可能很大，她只想知道答案模 $998244353$ 的结果。

输入格式

第一行两个整数 $n,k$，表示土地的边长和 Iva 的最喜欢的数字。

在接下来的 $n$ 行中，每一行 $n$ 个数字，描述这片土地。如果 $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

提示

【样例解释 #2】

共有三条这样的路线：

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

【数据范围】

对于 $100\%$ 的数据，满足 $1\leq n \leq 500,1\le k\le 10^6, -1\le a_{i,j}\le 10^6$。

本题满分 $110$ 分。