题目描述

有 $N$ 个城市。从城市 $i$ 到城市 $j$ 的旅行时间为 $T_{i, j}$。

在所有从城市 $1$ 开始，恰好访问了所有其他城市一次，然后回到城市 $1$ 的路径中，有多少条路径的总时间正好为 $K$？

约束条件

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

输入

输入从标准输入给出，格式如下：

$N$ $K$ $T_{1,1}$ $\\ldots$ $T_{1,N}$ $\\vdots$ $T_{N,1}$ $\\ldots$ $T_{N,N}$

输出

输出一个整数作为答案。

示例输入 1

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

示例输出 1

2

有六条路径从城市 $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 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

不管以什么顺序访问城市，总旅行时间都为 $5$。