题目描述

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

输入格式

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

输出格式

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

说明/提示

数据规模与约定

所有输入数据保证：

• $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$；
• 输入中的所有值均为整数。