M=10**9+7

(n,k),*a=[list(map(int,t.split()))for t in open(0)]

r=a if k&1else[[i==j for j in range(n)]for i in range(n)]

d=a

for i in range(1,k.bit_length()):

  p=[]

  for y in d:

    q=[0]*n

    for x,s in zip(y,d):

      for j,t in enumerate(s):

        q[j]+=t*x%M

    p+=q,

  d=p

  if 1<<i&k:

    p=[]

    for y in r:

      q=[0]*n

      for x,s in zip(y,d):

        for j,t in enumerate(s):

          q[j]+=t*x%M

      p+=q,

    r=p

print((sum(t for s in r for t in s)%M))
from numpy import*

(n,k),*a=[list(map(int,t.split()))for t in open(0)]

a=matrix(a,'O')

M=10**9+7

s=1

while k:s*=~k%2or a;k//=2;a=a*a%M

print((sum(s)%M))
M = 10**9 + 7
(n, k), *a = [list(map(int, t.split())) for t in open(0)]
r = a if k & 1 else [[i == j for j in range(n)] for i in range(n)]
d = a
for i in range(1, k.bit_length()):
    p = []
    for y in d:
        q = [0] * n
        for x, s in zip(y, d):
            for j, t in enumerate(s):
                q[j] += t * x % M
        p += (q,)
    d = p
    if 1 << i & k:
        p = []
        for y in r:
            q = [0] * n
            for x, s in zip(y, d):
                for j, t in enumerate(s):
                    q[j] += t * x % M
            p += (q,)
        r = p
print((sum(t for s in r for t in s) % M))

from numpy import *

(n, k), *a = [list(map(int, t.split())) for t in open(0)]
a = matrix(a, "O")
M = 10**9 + 7
s = 1
while k:
    s *= ~k % 2 or a
    k //= 2
    a = a * a % M
print((sum(s) % M))

+from numpy import * + +(n, k), *a = [list(map(int, t.split())) for t in open(0)] +a = matrix(a, "O") -(n, k), *a = [list(map(int, t.split())) for t in open(0)] -r = a if k & 1 else [[i == j for j in range(n)] for i in range(n)] -d = a -for i in range(1, k.bit_length()): -    p = [] -    for y in d: -        q = [0] * n -        for x, s in zip(y, d): -            for j, t in enumerate(s): -                q[j] += t * x % M -        p += (q,) -    d = p -    if 1 << i & k: -        p = [] -        for y in r: -            q = [0] * n -            for x, s in zip(y, d): -                for j, t in enumerate(s): -                    q[j] += t * x % M -            p += (q,) -        r = p -print((sum(t for s in r for t in s) % M)) +s = 1 +while k: +    s *= ~k % 2 or a +    k //= 2 +    a = a * a % M +print((sum(s) % M))