该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

在时间尽头的逆时之塔中 , 存在着一块庞大的方形石阵

传说那是古代时间术士的试炼之地

石阵由 $\rm N \times N$ 块符石构成 , 每块符石上都刻着一个整数

其中第 $\rm i$ 行第 $\rm j$ 列上的数字为 $\rm T_{i , j}$

它们的能量以某种奇异的规律流动着

$\rm sMa$ 被困在这座塔的最底层第 $\rm N$ 行第 $\rm N$ 列

为了逃离这座塔 $\rm sMa$ 必须“逆时而行”——从塔底不断 向上 或 向左 移动 , 最终抵达塔顶的传送门 第 $\rm 1$ 行第 $\rm 1$ 列

然而通道并非随意可走：有些符石的能量早已枯竭 , 踏上去会瞬间坠落无法通行

当 $\rm sMa$ 成功踏上一条完整路径时 , 该路径的总能量 $\rm P$ 定义为所有符石数值的乘积

即

与此同时"时光之门"的核心 $\rm D$ 会对能量结构进行共鸣判定

设 $\rm D$ 质因数分解为：

若路径能量 $\rm P$ 在每个质因数上 至少拥有相同或更高的幂次

即：

则称该路径为 共鸣路径

换言之路径的能量积必须 完整覆盖 能核 $\rm D$ 的所有质因子需求 , 才能触发能量共振使传送门响应

你需要计算共有多少条路径能够得到时间之门的回应

输入格式

第一行输入两个空格分隔的正整数 $\rm N,D$

在接下来 $\rm N$ 行 , 每一行输入 $\rm N$ 个空格分隔的整数 , 表示 “时之符石” 上的整数

若数值为 $-1$ 则代表该符石能量枯竭 , 无法移动到此处

输出格式

输出一个整数表示结果

答案可能很大 $\rm mod ~ 1000000007$ 后输出

2 2
3 2
1 4

2

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

3

见 ex_bomboni1.in

见 ex_bomboni1.out

见 ex_bomboni2.in

见 ex_bomboni2.out

点此下载

样例2解释

共有三条这样的路线：

• $1 \to 3 \to 3 \to 2 \to 5$

• $1 \to 6 \to 3 \to 2 \to 5$

• $1 \to 6 \to 3 \to 7 \to 5$

数据规模

对于 $100\%$ 的数据 $\rm 1\leq N \leq 500 , 1\le D\le 10^6 , -1\le T_{i , j}\le 10^6$