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 sys
  
  sys.setrecursionlimit(10**6)
  input = sys.stdin.readline
  from math import floor, sqrt, factorial, hypot, log  # log2ないｙｐ
  from heapq import heappop, heappush, heappushpop
  from collections import Counter, defaultdict, deque
  from itertools import (
      accumulate,
      permutations,
      combinations,
      product,
      combinations_with_replacement,
  )
  from bisect import bisect_left, bisect_right
  from copy import deepcopy
  from fractions import gcd
  from random import randint
  import numpy
  
  
  def ceil(a, b):
      return (a + b - 1) // b
  
  
  inf = float("inf")
  mod = 10**9 + 7
  
  
  def pprint(*A):
      for a in A:
          print(*a, sep="\n")
  
  
  def INT_(n):
      return int(n) - 1
  
  
  def MI():
      return map(int, input().split())
  
  
  def MF():
      return map(float, input().split())
  
  
  def MI_():
      return map(INT_, input().split())
  
  
  def LI():
      return list(MI())
  
  
  def LI_():
      return [int(x) - 1 for x in input().split()]
  
  
  def LF():
      return list(MF())
  
  
  def LIN(n: int):
      return [I() for _ in range(n)]
  
  
  def LLIN(n: int):
      return [LI() for _ in range(n)]
  
  
  def LLIN_(n: int):
      return [LI_() for _ in range(n)]
  
  
  def LLI():
      return [list(map(int, l.split())) for l in input()]
  
  
  def I():
      return int(input())
  
  
  def F():
      return float(input())
  
  
  def ST():
      return input().replace("\n", "")
  
  
  # mint
  class ModInt:
      def __init__(self, x):
          self.x = x % mod
  
      def __str__(self):
          return str(self.x)
  
      __repr__ = __str__
  
      def __add__(self, other):
          if isinstance(other, ModInt):
              return ModInt(self.x + other.x)
          else:
              return ModInt(self.x + other)
  
      __radd__ = __add__
  
      def __sub__(self, other):
          if isinstance(other, ModInt):
              return ModInt(self.x - other.x)
          else:
              return ModInt(self.x - other)
  
      def __rsub__(self, other):
          if isinstance(other, ModInt):
              return ModInt(other.x - self.x)
          else:
              return ModInt(other - self.x)
  
      def __mul__(self, other):
          if isinstance(other, ModInt):
              return ModInt(self.x * other.x)
          else:
              return ModInt(self.x * other)
  
      __rmul__ = __mul__
  
      def __truediv__(self, other):
          if isinstance(other, ModInt):
              return ModInt(self.x * pow(other.x, mod - 2, mod))
          else:
              return ModInt(self.x * pow(other, mod - 2, mod))
  
      def __rtruediv(self, other):
          if isinstance(other, self):
              return ModInt(other * pow(self.x, mod - 2, mod))
          else:
              return ModInt(other.x * pow(self.x, mod - 2, mod))
  
      def __pow__(self, other):
          if isinstance(other, ModInt):
              return ModInt(pow(self.x, other.x, mod))
          else:
              return ModInt(pow(self.x, other, mod))
  
      def __rpow__(self, other):
          if isinstance(other, ModInt):
              return ModInt(pow(other.x, self.x, mod))
          else:
              return ModInt(pow(other, self.x, mod))
  
  
  def main():
      N, K = MI()
      A = LLIN(N)
  
      B = [[ModInt(0)] * N for _ in range(N)]
      for a, vec in enumerate(A):
          for b, boo in enumerate(vec):
              if boo:
                  B[a][b] = 1
      C = numpy.matrix(B)
      ans_mat = C**K
  
      ans = 0
      for i in range(N):
          for j in range(N):
              ans += ans_mat[i, j].x
      print(ans % mod)
  
  
  if __name__ == "__main__":
      main()
  
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."}]