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

题目描述

有 $n$ 个城市，从城市 $i$ 到城市 $j$ 需要的时间为 $t_{i,j}$。请问：从城市 $1$ 开始，只访问其他城市一遍，最后返回城市 $1$ 的路径中，有多少条路径所需要的时间为 $k$？

输入格式

输入共 $(n+1)$ 行。第一行输入两个正整数 $n,k$，中间以单个空格隔开；然后输入一个 $n \times n$ 的矩阵，第 $i$ 行第 $j$ 列上的数为 $t_{i,j}$。

输出格式

输出一行一个非负整数，即满足条件的路径条数。

输入输出样例 #1

输入 #1

4 330
0 1 10 100
1 0 20 200
10 20 0 300
100 200 300 0

输出 #1

2

输入输出样例 #2

输入 #2

5 5
0 1 1 1 1
1 0 1 1 1
1 1 0 1 1
1 1 1 0 1
1 1 1 1 0

输出 #2

24

说明/提示

数据规模与约定

所有输入数据保证：

• $2 \le n \le 8$；
• 对于所有满足$1 \le i,j \le n$ 且 $i \neq j$ 的整数对 $(i,j)$，$t_{i,i}=0,t_{i,j}=t_{j,i},1 \le t_{i,j} \le 10^8$；
• $1 \le k \le 10^9$；
• 输入中的所有值均为整数。