配点 : $300$ 点

問題文

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

都市 $1$ を出発し、全ての都市をちょうど $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}$

出力

答えを整数で出力せよ。

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

2

都市 $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$

の $6$ 通りがあります。それぞれの移動時間は、$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

24

どのような順で都市を訪問しても、移動時間の合計は $5$ になります。