定好了难度，雄心勃勃的吉米多出题斯基开始寻找智慧的神犇星球的居民出题。

然而吉米多出题斯基没有料到，神犇星球的居民告诉吉米多出题斯基：“今年神犇星球经济不景气，大家都想宅在家里，哪有心思出来出题呢？”

为了挽救这一局面，吉米多出题斯基决定为神犇星球建一些高速传送通道促进该星球各地区之间交流题目。

神犇星球有 $n$ 座小城。对于任意两座小城 $v,u$（$v\ne u$），吉米多出题斯基想在 $v,u$ 之间建立一个传送时间为 $w(v,u)$ 的无向传送通道，其中 $w(v,u)$ 为不超过 $k$ 的非负整数。建成后，神犇星球的居民可从一座小城出发经过一个或若干个传送通道到达另一座小城交流题目，花费的时间为所有经过的传送通道的传送时间之和。

吉米多出题斯基还没有决定每一个传送通道的传送时间取值，只是对于任意两座小城 $v,u$，决定了从 $v$ 出发到达 $u$ 的最短时间要恰好等于 $d(v,u)$。但吉米多出题斯基日理万机，于是他找到了你 —— 风璃殇做不出题耶维奇，请你帮助吉米多出题斯基数一数有多少种不同的满足条件的传送通道建设方案吧！

由于方案数可能很大，你只用输出方案数对 $998244353$（$7\times 17\times 2^{23}+1$，一个质数）取模后的结果。

输入

第一行两个整数 $n,k$。保证 $n\ge 1,k\ge 0$。

接下来 $n$ 行，每行有 $n$ 个非负整数，第 $i$ 行的 第 $j$ 个数表示 $d(i,j)$ 的值。

输出

输出一行，一个整数，表示方案数对 $998244353$ 取模的结果。如果无解，则方案数为 $0$。

样例一

input

3 3
0 2 1
2 0 3
1 3 0

output

1

样例二

input

3 5
0 3 4
3 0 1
4 1 0

output

2

样例三

见样例数据下载，限制与约定跟子任务 3 相同。

样例四

见样例数据下载，限制与约定跟子任务 3 相同。

限制与约定

对于所有数据，有 $1\le n\le 400,0\le k\le {10}^9,0\le d(u,v)\le {10}^9$

时间限制：$1\mathtt{\text{s}}$

空间限制：$256\mathtt{\text{MB}}$

下载

样例数据下载