题目描述

小高计划进行一次旅行。有 $N$ 个城市，从城市 $i$ 到城市 $j$ 需要花费时间 $T_{i,j}$。在所有从城市1出发，访问其他所有城市恰好一次，然后返回城市1的路径中，总共花费时间恰好为 $K$ 的路径有多少条？

输入格式

输入格式如下：

$N \ K$

$T_{1,1} ... T_{1,N}$

$⋮$

$T_{N,1} ... T_{N,N}$

输出格式

输出一个整数表示答案。

样例

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说明】
无论以何种顺序访问城市，总花费时间都是 $5$。

数据范围

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

来源

• AtCoder ABC183C