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: import numpy as np
  N,K=map(int,input().split())
  a=[[int(i) for i in input().split()] for _ in range(N)]
  a=np.array(a,dtype=np.int64)
  MOD=10**9+7
  
  def matmul(A,B,MOD):
      N=len(A)
      C=np.zeros(N,dtype=np.int64)
      for i in range(N):
          for j in range(N):
              for k in range(N):
              C[i][j] += A[i][k]B[k][j]%MOD
      return C
  
  def mat_power(A,k,MOD):
      N=len(A)
      D=np.identity(N,dtype=np.int64)
      while k:
          if k & 1:
              D=matmul(D,A,MOD)
          A = matmul(A,A,MOD)
          k >>= 1
  
      return D
  
  A=mat_power(a,K,MOD)
  ans=0
  for i in range(N):
      for j in range(N):
          ans=(ans+A[i][j])%MOD
  
  print(ans)
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."}]