AT_dp_r Walk
Description
[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 $ で割った余りを求めてください。 ただし、同じ辺を複数回通るような有向パスも数えるものとします。
Input Format
N/A
Output Format
N/A
Explanation/Hint
### 制約
- 入力はすべて整数である。
- $ 1\ \leq\ N\ \leq\ 50 $
- $ 1\ \leq\ K\ \leq\ 10^{18} $
- $ a_{i,\ j} $ は $ 0 $ または $ 1 $ である。
- $ a_{i,\ i}\ =\ 0 $
### Sample Explanation 1
$ G $ は次図です。  長さ $ 2 $ の有向パスは、次の $ 6 $ 通りです。 - $ 1 $ → $ 2 $ → $ 3 $ - $ 1 $ → $ 2 $ → $ 4 $ - $ 2 $ → $ 3 $ → $ 4 $ - $ 2 $ → $ 4 $ → $ 1 $ - $ 3 $ → $ 4 $ → $ 1 $ - $ 4 $ → $ 1 $ → $ 2 $
### Sample Explanation 2
$ G $ は次図です。  長さ $ 3 $ の有向パスは、次の $ 3 $ 通りです。 - $ 1 $ → $ 2 $ → $ 1 $ → $ 2 $ - $ 2 $ → $ 1 $ → $ 2 $ → $ 1 $ - $ 2 $ → $ 1 $ → $ 2 $ → $ 3 $
### Sample Explanation 3
$ G $ は次図です。  長さ $ 2 $ の有向パスは、次の $ 1 $ 通りです。 - $ 4 $ → $ 5 $ → $ 6 $
### Sample Explanation 5
答えを $ 10^9\ +\ 7 $ で割った余りを出力することを忘れずに。