Contest Duration: - (local time) (100 minutes) Back to Home
C - Travel /

Time Limit: 2 sec / Memory Limit: 1024 MB

問題文

N 個の都市があります。都市 i から都市 j へ移動するには T_{i,j} の時間がかかります。

制約

• 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\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

6 通りがあります。それぞれの移動時間は、421,511,330,511,330,421 なので、ちょうど 330 であるようなものは 2 通りです。

入力例 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 になります。

Score : 300 points

Problem Statement

There are N cities. The time it takes to travel from City i to City j is T_{i, j}.

Among those paths that start at City 1, visit all other cities exactly once, and then go back to City 1, how many paths take the total time of exactly K to travel along?

Constraints

• 2\leq N \leq 8
• If 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
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

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


Output

Print the answer as an integer.

Sample Input 1

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


Sample Output 1

2


There are six paths that start at City 1, visit all other cities exactly once, and then go back to City 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

The times it takes to travel along these paths are 421, 511, 330, 511, 330, and 421, respectively, among which two are exactly 330.

Sample Input 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


Sample Output 2

24


In whatever order we visit the cities, it will take the total time of 5 to travel.