问题描述

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

输入格式

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

输出格式

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

样例输入 1

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

样例输出 1

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

说明：每个相邻城市时间均为 $1$，$n=5$ 时路径时间 $= 5$，任何访问顺序均满足，排列数 $4! = 24$。

评测数据规模

对于所有数据，保证：

• $2 \le n \le 8$

• $t_{i,i}=0$，$t_{i,j}=t_{j,i}$，$1 \le t_{i,j} \le 10^8$（$i \ne j$）

• $1 \le k \le 10^9$