Walk

给一张有向简单图，给出邻接矩阵，求长度为 $K$ 的路径条数，答案对 $10^9+7$ 取模。

[problemUrl]: https://atcoder.jp/contests/dp/tasks/dp_r $ N $ 頂点の単純有向グラフ $ G $ があります。 頂点には $ 1,\ 2,\ \ldots,\ N $ と番号が振られています。 各 $ i,\ j $ ($ 1\ \leq\ i,\ j\ \leq\ N $) について、頂点 $ i $ から $ j $ への有向辺の有無が整数 $ a_{i,\ j} $ によって与えられます。 $ a_{i,\ j}\ =\ 1 $ ならば頂点 $ i $ から $ j $ への有向辺が存在し、$ a_{i,\ j}\ =\ 0 $ ならば存在しません。 $ G $ の長さ $ K $ の有向パスは何通りでしょうか？ $ 10^9\ +\ 7 $ で割った余りを求めてください。 ただし、同じ辺を複数回通るような有向パスも数えるものとします。

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

$ G $ の長さ $ K $ の有向パスは何通りか？ $ 10^9\ +\ 7 $ で割った余りを出力せよ。

4 2
0 1 0 0
0 0 1 1
0 0 0 1
1 0 0 0

6

3 3
0 1 0
1 0 1
0 0 0

3

6 2
0 0 0 0 0 0
0 0 1 0 0 0
0 0 0 0 0 0
0 0 0 0 1 0
0 0 0 0 0 1
0 0 0 0 0 0

1

1 1
0

0

10 1000000000000000000
0 0 1 1 0 0 0 1 1 0
0 0 0 0 0 1 1 1 0 0
0 1 0 0 0 1 0 1 0 1
1 1 1 0 1 1 0 1 1 0
0 1 1 1 0 1 0 1 1 1
0 0 0 1 0 0 1 0 1 0
0 0 0 1 1 0 0 1 0 1
1 0 0 0 1 0 1 0 0 0
0 0 0 0 0 1 0 0 0 0
1 0 1 1 1 0 1 1 1 0

957538352

### 制約 - 入力はすべて整数である。 - $ 1\ \leq\ N\ \leq\ 50 $ - $ 1\ \leq\ K\ \leq\ 10^{18} $ - $ a_{i,\ j} $ は $ 0 $ または $ 1 $ である。 - $ a_{i,\ i}\ =\ 0 $ ### Sample Explanation 1 $ G $ は次図です。 !\[\](https://img.atcoder.jp/dp/paths\_0\_muffet.png) 長さ $ 2 $ の有向パスは、次の $ 6 $ 通りです。 - $ 1 $ → $ 2 $ → $ 3 $ - $ 1 $ → $ 2 $ → $ 4 $ - $ 2 $ → $ 3 $ → $ 4 $ - $ 2 $ → $ 4 $ → $ 1 $ - $ 3 $ → $ 4 $ → $ 1 $ - $ 4 $ → $ 1 $ → $ 2 $ ### Sample Explanation 2 $ G $ は次図です。 !\[\](https://img.atcoder.jp/dp/paths\_1\_muffet.png) 長さ $ 3 $ の有向パスは、次の $ 3 $ 通りです。 - $ 1 $ → $ 2 $ → $ 1 $ → $ 2 $ - $ 2 $ → $ 1 $ → $ 2 $ → $ 1 $ - $ 2 $ → $ 1 $ → $ 2 $ → $ 3 $ ### Sample Explanation 3 $ G $ は次図です。 !\[\](https://img.atcoder.jp/dp/paths\_2\_muffet.png) 長さ $ 2 $ の有向パスは、次の $ 1 $ 通りです。 - $ 4 $ → $ 5 $ → $ 6 $ ### Sample Explanation 5 答えを $ 10^9\ +\ 7 $ で割った余りを出力することを忘れずに。