题目描述

有 $N$ 个城市，编号为 $1, 2, \dots, N$ 。城市之间两两相连，从城市 $i$ 到城市 $j$ 的旅行时间为 $T_{i,j}$ 。

现在你从 城市 1 出发，计划访问其余 $N-1$ 个城市 恰好一次，最后返回 城市 1 。

目标： 请计算总旅行时间恰好等于 $K$ 的不同路径数量。

输入格式

输入第一行包含两个整数 $N$ 和 $K$ 。 接下来的 $N$ 行，每行包含 $N$ 个整数。第 $i$ 行的第 $j$ 个整数表示 $T_{i,j}$ 。

输出格式

输出一个整数，表示满足条件的路径总数。

样例

4 7
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0

6

样例解释

解释：由于 $N=4$，除了起点 $1$ 以外，剩下的 $\{2, 3, 4\}$ 有 $3! = 6$ 种排列，每种排列的路径长度都是 $1+1+1+1=4$。但在这个例子中，如果 $K=4$，输出就是 $6$。

数据范围