問題文

$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}$

出力

答えを整数で出力せよ。

入力例 1

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

出力例 1

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$ 通りです。

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