题目描述

有 $N$ 座城市。从城市 $i$ 到城市 $j$ 所需的时间为 $T_{i, j}$ 。

在从城市 $1$ 出发，恰好访问一次其他所有城市，然后返回城市 $1$ 的路径中，有多少条路径的总时间恰好是 $K$ ？

输入格式

第一行输入两个空格隔开的整数 $N,K$

接下来输入一个 $N\times N$ 的矩阵 $T$，第 $i$ 行第 $j$ 列上的数为 $T_{i,j}$。

输出格式

输出一个整数

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

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

24

样例 1 解释

有六条路径以城市 $1$ 为起点，恰好访问一次其他所有城市，然后返回城市 $1$ ：

• $1\to 2\to 3\to 4\to 1$
• $1\to 2\to 4\to 3\to 1$
• $1\to 3\to 2\to 4\to 1$
• $1\to 3\to 4\to 2\to 1$
• $1\to 4\to 2\to 3\to 1$
• $1\to 4\to 3\to 2\to 1$

沿着这些路径行进所需的时间分别为 $421$ 、 $511$ 、 $330$ 、 $511$ 、 $330$ 和 $421$ ，其中有两个路径正好是 $330$ 。

数据范围

• $2\leq N \leq 8$
• 如果 $i\neq j$ , $1\leq T_{i,j} \leq 10^8$ .
• $T_{i,i}=0$
• $T_{i,j}=T_{j,i}$
• $1\leq K \leq 10^9$
• 输入值均为整数。