AT_abc183_c [ABC183C] Travel

[problemUrl]: https://atcoder.jp/contests/abc183/tasks/abc183_c $ N $ 個の都市があります。都市 $ i $ から都市 $ j $ へ移動するには $ T_{i,j} $ の時間がかかります。 都市 $ 1 $ を出発し、全ての都市をちょうど $ 1 $ 度ずつ訪問してから都市 $ 1 $ に戻るような経路のうち、移動時間の合計がちょうど $ K $ になるようなものはいくつありますか？

入力は以下の形式で標準入力から与えられる。 > $ N $ $ K $ $ T_{1,1} $ $ \ldots $ $ T_{1,N} $ $ \vdots $ $ T_{N,1} $ $ \ldots $ $ T_{N,N} $

答えを整数で出力せよ。

### 制約 - $ 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 $ - 入力はすべて整数 ### Sample Explanation 1 都市 $ 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 $ 通りです。 ### Sample Explanation 2 どのような順で都市を訪問しても、移動時間の合計は $ 5 $ になります。