output_description: Print the number of different directed paths of length K in G, modulo 10^9 +
  7.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N K
      a_{1, 1} \ldots a_{1, N}
      :
      a_{N, 1} \ldots a_{N, N}
attempt: N, K = map(int, input().split())
  A = [[] for i in range(0, N)]
  for i in range(0, N):
      A[i] = list(map(int, input().split()))
  
  mod = 10**9 + 7
  
  dp = [[[0 for i in range(0, N)] for j in range(0, N)] for k in range(0, 62)]
  
  for j in range(0, N):
      for k in range(0, N):
          dp[0][j][k] = A[j][k]
  
  for i in range(1, 62):
      for j in range(0, N):
          for k in range(0, N):
              dp[i][j][k] = (
                  sum(dp[i - 1][j][l] * dp[i - 1][l][k] for l in range(0, N)) % mod
              )
  
  ans = [[[0 for i in range(0, N)] for j in range(0, N)] for k in range(0, 63)]
  
  for i in range(0, N):
      ans[0][i][i] = 1
  
  for k in range(0, 62):
      if K >> k & 1 == 1:
          for i in range(0, N):
              for j in range(0, N):
                  ans[k + 1][i][j] = (
                      sum(dp[k][i][l] * ans[k][l][j] for l in range(0, N)) % mod
                  )
  
      else:
          for i in range(0, N):
              for j in range(0, N):
                  ans[k + 1][i][j] = ans[k][i][j]
  
  print(sum(ans[62][i][j] for i in range(0, N) for j in range(0, N)) % mod)
  
problem_description: Statement
  
  There is a simple directed graph G with N vertices, numbered 1, 2, \ldots, N.
  
  For each i and j (1 \leq i, j \leq N), you are given an integer a_{i, j} that
  represents whether there is a directed edge from Vertex i to j. If a_{i, j} =
  1, there is a directed edge from Vertex i to j; if a_{i, j} = 0, there is not.
  
  Find the number of different directed paths of length K in G, modulo 10^9 + 7.
  We will also count a path that traverses the same edge multiple times.
samples: [{"input": "4 2\n    0 1 0 0\n    0 0 1 1\n    0 0 0 1\n    1 0 0 0", "output": "6\n    \n\nG is drawn in the figure below:\n\n![](https://img.atcoder.jp/dp/paths_0_muffet.png)\n\nThere are six directed paths of length 2:\n\n  * 1 \u2192 2 \u2192 3\n  * 1 \u2192 2 \u2192 4\n  * 2 \u2192 3 \u2192 4\n  * 2 \u2192 4 \u2192 1\n  * 3 \u2192 4 \u2192 1\n  * 4 \u2192 1 \u2192 2\n\n* * *"}, {"input": "3 3\n    0 1 0\n    1 0 1\n    0 0 0", "output": "3\n    \n\nG is drawn in the figure below:\n\n![](https://img.atcoder.jp/dp/paths_1_muffet.png)\n\nThere are three directed paths of length 3:\n\n  * 1 \u2192 2 \u2192 1 \u2192 2\n  * 2 \u2192 1 \u2192 2 \u2192 1\n  * 2 \u2192 1 \u2192 2 \u2192 3\n\n* * *"}, {"input": "6 2\n    0 0 0 0 0 0\n    0 0 1 0 0 0\n    0 0 0 0 0 0\n    0 0 0 0 1 0\n    0 0 0 0 0 1\n    0 0 0 0 0 0", "output": "1\n    \n\nG is drawn in the figure below:\n\n![](https://img.atcoder.jp/dp/paths_2_muffet.png)\n\nThere is one directed path of length 2:\n\n  * 4 \u2192 5 \u2192 6\n\n* * *"}, {"input": "1 1\n    0", "output": "0\n    \n\n* * *"}, {"input": "10 1000000000000000000\n    0 0 1 1 0 0 0 1 1 0\n    0 0 0 0 0 1 1 1 0 0\n    0 1 0 0 0 1 0 1 0 1\n    1 1 1 0 1 1 0 1 1 0\n    0 1 1 1 0 1 0 1 1 1\n    0 0 0 1 0 0 1 0 1 0\n    0 0 0 1 1 0 0 1 0 1\n    1 0 0 0 1 0 1 0 0 0\n    0 0 0 0 0 1 0 0 0 0\n    1 0 1 1 1 0 1 1 1 0", "output": "957538352\n    \n\nBe sure to print the count modulo 10^9 + 7."}]