Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

while 1:
	stack = []
	
	try:
		for s in raw_input().split():
			if s == "-":
				stack.append(stack.pop(-2) - stack.pop())
			elif s == "+":
				stack.append(stack.pop(-2) + stack.pop())
			elif s == "/":
				stack.append(stack.pop(-2) / stack.pop())
			elif s == "*":
				stack.append(stack.pop(-2) * stack.pop())
			elif s == "%":
				stack.append(stack.pop(-2) % stack.pop())
			else:
				stack.append(int(s))
	
		print "%.6f" % (stack[0])
	except:
		pass

### FIXED CODE ###

while 1:
	try:
		stack = []
		for s in raw_input().split():
			if s == "-":
				stack.append(stack.pop(-2) - stack.pop())
			elif s == "+":
				stack.append(stack.pop(-2) + stack.pop())
			elif s == "/":
				stack.append(stack.pop(-2) / stack.pop())
			elif s == "*":
				stack.append(stack.pop(-2) * stack.pop())
			else:
				stack.append(float(s))
	
		print "%.6f" % (stack[0])
	except:
		break
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N, M, L = map(int, input().split())

distance = [[float('inf')]*N for _ in range(N)]
for i in range(N):
    distance[i][i] = 0
for _ in range(M):
    a, b, c = map(int, input().split())
    distance[a-1][b-1] = c
    distance[b-1][a-1] = c

for k in range(N):
    for i in range(N):
        for j in range(N):
            distance[i][j] = min(distance[i][j], distance[i][k]+distance[k][j])

stoke = [[1 if distance[i][j] <= L else float('inf') for j in range(N)] for i in range(N)]
for i in range(N):
    stoke[i][i] = 0
for k in range(N):
    for i in range(N):
        for j in range(N):
            stoke[i][j] = min(stoke[i][j], stoke[i][k]+stoke[k][j])

Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    ans = stoke[s-1][t-1]-1
    if ans is float('inf'):
        ans = -1
    print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline

N, M, L = map(int, input().split())

distance = [[float('inf')]*N for _ in range(N)]
for i in range(N):
    distance[i][i] = 0
for _ in range(M):
    a, b, c = map(int, input().split())
    distance[a-1][b-1] = c
    distance[b-1][a-1] = c

for k in range(N):
    for i in range(N):
        for j in range(N):
            distance[i][j] = min(distance[i][j], distance[i][k]+distance[k][j])

for i in range(N):
    for j in range(N):
        if i == j:
            distance[i][j] = 0
        elif distance[i][j] <= L:
            distance[i][j] = 1
        else:
            distance[i][j] = float('inf')

for k in range(N):
    for i in range(N):
        for j in range(N):
            distance[i][j] = min(distance[i][j], distance[i][k]+distance[k][j])

Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    ans = distance[s-1][t-1]-1
    if ans is float('inf'):
        ans = -1
    print(ans)
### BUGGY CODE ###

n = int(input())
ans = 1
for i in range(n):
    ans = ans * (i+1)
print(ans % (10**9+7))


### FIXED CODE ###

n = int(input())
ans = 1
for i in range(2, n+1):
    ans = ans * i % (10**9+7)
print(ans % (10**9+7))
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))

import math
total=1
for i in range(n):
    total*=a[i]

if  total>pow(10,18):
    print(-1)
else:
    print(total)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))

if a.count(0)>0:
    print(0)
    exit(0)

total=1
for i in a:
    total *=i

    if total>10**18:
        print(-1)
        exit(0)
    
print(total)
### BUGGY CODE ###

N, X, Y = map(int, input().split())

dis = dict(zip(range(1, N), [0 for _ in range(1, N)]))

for i in range(1, N):
    for j in range(i + 1, N + 1):
        d1 = abs(i - j)
        d2 = abs(i - X) + 1 + abs(j - Y)
        d3 = abs(i - Y) + 1 + abs(j - X)
        d = min(d1, d2, d3)

        dis[d] += 1

for k in range(1, N):
    print(dis[k])

### FIXED CODE ###

N, X, Y = map(int, input().split())

dis = [0 for _ in range(N)]
for i in range(1, N):
    for j in range(i + 1, N + 1):
        d = min(abs(i - j),
                abs(i - X) + 1 + abs(j - Y),
                abs(i - Y) + 1 + abs(j - X))
        dis[d] += 1

for k in range(1, N):
    print(dis[k])
### BUGGY CODE ###

N = int(input())
j = 0
for i in range(1,N):
    j += i
print(j)

### FIXED CODE ###

N = int(input())
j = N*(N-1)//2
print(int(j))
### BUGGY CODE ###

N,K = map(int,input().split(' '))

H = sorted(list(map(int,(input() for i in range(N)))))
ans = float('inf')
for i in range(N-K+1):
  frag = H[i:i+K]
  ans = min(ans,frag[-1] - frag[0])
  
print(ans)



### FIXED CODE ###

N,K = map(int,input().split(' '))

H = [int(input()) for i in range(N)]
H.sort()
  
print(min(H[i+K-1] - H[i] for i in range(N-K+1)))
### BUGGY CODE ###

n = int(input())
a = [int(input()) for i in range(n)]

max_number = max(a)

for i in range(n):
    if a[i] == max_number:
        print(max(a[0:i]+a[i+1:]))
    else:
        print(max_number)

### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]

max_number = max(a)
max_number2 = sorted(a)[-2]

for i in range(n):
    if a[i] == max_number:
        print(max_number2)
    else:
        print(max_number)
### BUGGY CODE ###

n = int(input())
l = list(map(int,input().split())) 
ans=0
for i in range(n):
    for j in range(i+1,n):
        ans += l[i]*l[j]
        
print(ans%(10**9 + 7))

### FIXED CODE ###

n = int(input())
l = list(map(int,input().split())) 

totalsqr = (sum(l))**2

individualsqrsum=0
for i in l:
    individualsqrsum += i**2

ans = (totalsqr  - individualsqrsum)  // 2 
ans = ans%(10**9 + 7)
print(ans)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
q=int(input())

d=[0]*(10**6)

for i in a:
    d[i-1]+=i

for _ in range(q):
    b,c=map(int,input().split())
    ans=0
    k=d[b-1]//b
    d[c-1]+=c*k
    d[b-1]=0

    print(sum(d))


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
q=int(input())

s=sum(a)
d=[0]*(10**5+1)
for i in a:
    d[i-1]+=1

for _ in range(q):
    b,c=map(int,input().split())
    tmp=0
    k=d[b-1]
    d[c-1]+=k
    d[b-1]=0

    tmp = k*c-k*b
    s+=tmp
    print(s)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
ma = max(A)
xma = 1
for i in range(20):
    xma = xma  * 2
    if xma >= ma:
        break
ans = 0
a = 0
max_flag = False
for l in range(N):
    a = A[l]
    x = A[l]
    if max_flag:
       ma = max(A[l:N])
       xma = 1
       for i in range(20):
           xma = xma  * 2
           if xma >= ma:
               break
    if ma == A[l]:
        max_flag =True
    for j in range(l+1,N):
        a += A[j]
        x = x ^ A[j]
        if a == x:
            ans += 1
        elif a >= xma:
            break
print(ans + N)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
ans = 0
num = 0
a = 0
x = 0
k = 0
for l in range(N):
    for j in range(k,N):
        a += A[j]
        x =  x ^ A[j]
        if a  != x:
            ans += j - l
            k = j
            x = x ^ A[l] ^ A[j]
            a = a - A[l] - A[j]
            break
        elif j == N-1:
            ans += N-l
            k = j
            x = x ^ A[l] ^ A[j]
            a = a - A[l] - A[j]
print(ans )
### BUGGY CODE ###

while True:
    n,k=map(int,raw_input().split())
    if n==k==0:break
    L=[input() for i in range(n)]
    ma=0
    for i in range(n-k+1):
        ma=max(sum(L[i:i+k]),ma)
    print ma

### FIXED CODE ###

while True:
    n,k=map(int,raw_input().split())
    if n==k==0:break
    L=[input() for i in range(n)]
    maxInt=-10000000
    temp=sum(L[:k])
    for i in range(k,n):
        maxInt=max(maxInt,temp)
        temp=temp+L[i]-L[i-k]
    print maxInt
### BUGGY CODE ###

n=int(input())
s=list(map(int,input().split()))
t=list(map(int,input().split()))
f=list(map(int,input().split()))
g=list(map(int,input().split()))
ans=[n*[0]for _ in range(n)]
for b in range(64):
  u=[a&1<<b for a in f]
  v=[a&1<<b for a in g]
  q=[[(u[i]&v[j])|(0if s[i]else u[i])|(0if t[j]else v[j])for j in range(n)]for i in range(n)]
  for i in range(n):
    if s[i]*u[i]*(u[i]not in q[i]):
      for j in range(n):
        if(t[j]^1)*([k[j]for k in q].count(0)>1):q[i][j]=u[i];break
  for j in range(n):
    if t[j]*v[j]*(v[j]not in[k[j]for k in q]):
      for i in range(n):
        if(s[i]^1)*(q[i].count(0)>1):q[i][j]=v[j];break
  h=q[0][:]
  w=[i[0]for i in q]
  for i in range(n):
    for j in range(n):
      if s[i]:w[i]|=q[i][j]
      else:w[i]&=q[i][j]
      if t[j]:h[j]|=q[i][j]
      else:h[j]&=q[i][j]
      ans[i][j]|=q[i][j]
  if(v!=h)|(u!=w):print(-1);exit() 
for i in ans:print(*i)

### FIXED CODE ###

n=int(input())
s=list(map(int,input().split()))
t=list(map(int,input().split()))
u=list(map(int,input().split()))
v=list(map(int,input().split()))
ans=[n*[0]for _ in range(n)]
ss=[u[i]if s[i]==0 else 0 for i in range(n)]
tt=[v[i]if t[i]==0 else 0 for i in range(n)]
son=[[]for _ in range(n)]
ton=[[]for _ in range(n)]
sno=[[n-1]*64 for _ in range(n)]
tno=[[n-1]*64 for _ in range(n)]
for i in range(n):
  for j in range(n):
    ans[i][j]=u[i]&v[j]
    if s[i]==0:
      ans[i][j]|=u[i]
      ss[i]&=ans[i][j]
    else:
      ss[i]|=ans[i][j]
    if t[j]==0:
      ans[i][j]|=v[j]
      tt[j]&=ans[i][j]
    else:
      tt[j]|=ans[i][j]
    if s[i]==0 or t[i]==0:
      for k in range(64):
        if ans[i][j]&1<<k:
          if s[i]==0:sno[i][k]-=1
          if t[j]==0:tno[j][k]-=1
    if j==n-1:
      if s[i]==1:
        if ss[i]|u[i]>u[i]:print(-1);exit()
        if ss[i]!=u[i]:
          for k in range(64):
            if u[i]&1<<k:
              if (ss[i]&1<<k)==0:
                son[i].append(k)
          ss[i]=1
        else:ss[i]=0
      else:
        if ss[i]!=u[i]:print(-1);exit()
        else:ss[i]=2
    if i==n-1:
      if t[j]==1:
        if tt[j]|v[j]>v[j]:print(-1);exit()
        if tt[j]!=v[j]:
          for k in range(64):
            if v[j]&1<<k:
              if (tt[j]&1<<k)==0:
                ton[j].append(k)
          tt[j]=1
        else:tt[j]=0
      else:
        if tt[j]!=v[j]:print(-1);exit()
        else:tt[j]=2
for i in range(n):
  for k in son[i]:
    for j in range(n):
      if t[j]==0:
        if tno[j][k]>0:
          ans[i][j]|=1<<k
          tno[j][k]-=1
          break
      if j==n-1:print(-1);exit()
for j in range(n):
  for k in ton[j]:
    for i in range(n):
      if s[i]==0:
        if sno[i][k]>0:
          ans[i][j]|=1<<k
          sno[i][k]-=1
          break
      if i==n-1:print(-1);exit()
for i in range(n):
  if s[i]==0:uu=ans[i][0]
  else:uu=0
  for j in range(n):
    if s[i]==0:uu&=ans[i][j]
    else:uu|=ans[i][j]
  if uu!=u[i]:print(-1);exit()
for j in range(n):
  if t[j]==0:vv=ans[0][j]
  else:vv=0
  for i in range(n):
    if t[j]==0:vv&=ans[i][j]
    else:vv|=ans[i][j]
  if vv!=v[j]:print(-1);exit()
for i in ans:print(*i)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
Xs,Ys,Xg,Yg=map(int,input().split())

N=int(input())

L=[[Xs,Ys,0]]
for i in range(N):
    x,y,r=map(int,input().split())
    L.append([x,y,r])
L.append([Xg,Yg,0])

C=[-1 for i in range(len(L))]
C[0]=0

X=Xs
Y=Ys
R=0
Q=[]
import heapq
heapq.heapify(Q)
Z=[]
for i in range(1,len(L)):
    if C[i]==-1:
        heapq.heappush(Q,[max(0,((X-L[i][0])**2+(Y-L[i][1])**2)**0.5-(R+L[i][2])),i,0])
        Z.append([max(0,((X-L[i][0])**2+(Y-L[i][1])**2)**0.5-(R+L[i][2])),i,0])
#print(Z)
        
for j in range(10**7):
    if len(Q)==0:
        break
    else:
        if C[Q[0][1]]!=-1:
            qq=heapq.heappop(Q)
            
        else:
            q=heapq.heappop(Q)
            C[q[1]]=q[0]
            X=L[q[1]][0]
            Y=L[q[1]][1]
            R=L[q[1]][2]
            for i in range(1,len(L)):
                if C[i]==-1:
                    heapq.heappush(Q,[max(0,((X-L[i][0])**2+(Y-L[i][1])**2)**0.5-(R+L[i][2]))+C[q[1]],i,q[1]])
                    Z.append([max(0,((X-L[i][0])**2+(Y-L[i][1])**2)**0.5-(R+L[i][2])),i,q[1]])
    if C[-1]!=-1:
        break
    #print(C)
    #print(Z)
print(C[-1])
#print(C)

### FIXED CODE ###

import sys
input=sys.stdin.readline

Xs,Ys,Xg,Yg=map(int,input().split())
N=int(input())
L=[]
L.append([Xs,Ys,0])
for i in range(N):
    x,y,r=map(int,input().split())
    L.append([x,y,r])
L.append([Xg,Yg,0])
cost=[[-1 for i in range(N+2)]for j in range(N+2)]
for i in range(N+2):
    for j in range(i,N+2):
        cost[i][j]=max(0,((L[i][0]-L[j][0])**2+(L[i][1]-L[j][1])**2)**0.5-L[i][2]-L[j][2])
        cost[j][i]=cost[i][j]
#print(cost)


def jdijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d

#print(jdijkstra(0,N+2,(N+2)**2,cost))
ans=jdijkstra(0,N+2,(N+2)**2,cost)
print(ans[-1])
### BUGGY CODE ###

from math import factorial
n = int(input())
ans = 0

for c in range(1, n):
    x = n - c
    for b in range(1, x+1): ans += int(x % b == 0)

print(int(ans))


### FIXED CODE ###

n = int(input())
ans = 0

for a in range(1, n):
    ans += (n-1)//a

print(int(ans))
### BUGGY CODE ###

S = input()
Q = int(input())
T = 0
for i in range(Q):
    q = list(input().split())
    if q[0] == "1":
        T = (T+1) % 2
    elif (T == 0 and q[1] == "1") or (T == 1 and q[1] == "2"):
        S = q[2] + S
    else:
        S = S + q[2]
if T == 0:
    print(S)
else:
    s = S[::-1]
    print(s)

### FIXED CODE ###

S = input()
Q = int(input())
T = 0
s = ""
for i in range(Q):
    q = list(input().split())
    if q[0] == "1":
        T = (T+1) % 2
    elif (T == 0 and q[1] == "1") or (T == 1 and q[1] == "2"):
        s += q[2]
    else:
        S += q[2]
if T == 0:
    S = s[::-1] + S
    print(S)
else:
    S = S[::-1] + s
    print(S)
### BUGGY CODE ###

def solve():
    MOD = 10**9 + 7

    N = int(input())
    Ass = [tuple(map(int, input().split())) for _ in range(N)]

    dp = [[0]*(1<<N) for _ in range(N+1)]
    dp[0][0] = 1
    for iM in range(N):
        for S in range(1<<N):
            if dp[iM][S]:
                dp[iM][S] %= MOD
                for iW in range(N):
                    if S & (1<<iW) == 0 and Ass[iM][iW]:
                        S2 = S ^ (1<<iW)
                        dp[iM+1][S2] += dp[iM][S]

    print(dp[-1][-1] % MOD)


solve()


### FIXED CODE ###

MOD = 10**9 + 7

N = int(input())
As = [int(input().replace(' ', ''), 2) for _ in range(N)]

patWsList = [[] for _ in range(N+1)]
for patW in range(2**N):
    num1 = sum([(patW >> i) & 1 for i in range(N)])
    patWsList[num1].append(patW)

dp = [0] * (2**N)
dp[-1] = 1
for iM, (A, patWs) in enumerate(zip(As, reversed(patWsList))):
    for patW in patWs:
        A2 = A & patW
        dpNow = dp[patW]
        for iW in range(N):
            if A2 & (1 << iW):
                dp[patW ^ (1 << iW)] += dpNow
                dp[patW ^ (1 << iW)] %= MOD

print(dp[0])
### BUGGY CODE ###

import sys

H, W, D = map(int, sys.stdin.readline().split())
num = {}
for j in range(H):
    tmp = map(int, sys.stdin.readline().split())
    for i, n in enumerate(tmp):
        num[n] = (i, j)

# Dで分類した累積和
# S[initial % D][j], n = r + D*j
S = [[0 for _ in range(H*W//D+D)] for _ in range(D)]
for i in range(D):
    for j in range(H*W // D):
        if i == 0 and j == 0:
            continue
        if i + (j+1)*D > H*W:
            break

        x, y = num[i + (j+1)*D]
        a, b = num[i + j*D]
        S[i][j+1] = S[i][j] + abs(x - a) + abs(y - b)
# print(S)
Q = int(sys.stdin.readline())
for _ in range(Q):
    L, R = map(int, sys.stdin.readline().split())
    r = L % D
    print(S[r][R // D] - S[r][L // D])

### FIXED CODE ###

import sys

H, W, D = map(int, sys.stdin.readline().split())
num = {}
for j in range(H):
    tmp = map(int, sys.stdin.readline().split())
    for i, n in enumerate(tmp):
        num[n] = (i, j)

# Dで分類した累積和
# S[initial % D][j], n = r + D*j
S = [0 for _ in range(H*W+D)]
for i in range(D+1, H*W+1):
    x, y = num[i]
    a, b = num[i-D]
    S[i] = S[i-D] + abs(x - a) + abs(y - b)
# print(S)
Q = int(sys.stdin.readline())
for _ in range(Q):
    L, R = map(int, sys.stdin.readline().split())
    r = L % D
    print(S[R] - S[L])
### BUGGY CODE ###

n = int(input())

def j(b):
    print(b)
    i = input()[0]
    if i == "V": exit()
    return b, i

def q(l, r, t):
    m, rm = j((l + r + 1) // 2)
    if (m - b)%2 == (rm != t):
        q(m, r, rm)
    else:
        q(l, m-1, t)

_, s = j(0)
q(0, n-1, s)

### FIXED CODE ###

n = int(input())
q = lambda i:input('%d\n'%i)
i, j = 0, n - 1
a, b = q(i), q(j)
while True:
  k = (j - i + 1) // 2 + i
  c = q(k)
  if (k - i)%2 == (a==c):
    j = k
  else:
    a = c
    i = k
### BUGGY CODE ###

#どっちで出すか注意, rstrip注意
#提出前に見返すこと！
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter
    from functools import lru_cache
    #inf = 10**17
    #mod = 10**9 + 7

    N = int(input())
    A = list(map(int, input().split()))
    @lru_cache(maxsize=None)
    def gcd(a, b):
        if b == 0:
            return a
        else:
            return gcd(b, a % b)
    
    def gcd_group(arr):
        g = gcd(arr[0], arr[1])
        for i in range(2, len(arr)):
            g = gcd(g, arr[i])
        return g
    
    def lcm(a, b):
        g = gcd(a, b)
        return (a*b)//g
    
    def lcm_group(arr):
        l = lcm(arr[0], arr[1])
        for i in range(2, len(arr)):
            l = lcm(l, arr[i])
        return l
    
    if len(A) == 2:
        print(max(A))
        exit()
    res = 0
    for i in range(N):
        arr = A[:i] + A[i+1:]
        res = max(res, gcd_group(arr))
    print(res)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#どっちで出すか注意, rstrip注意
#提出前に見返すこと！
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter
    #inf = 10**17
    #mod = 10**9 + 7

    N = int(input())
    A = list(map(int, input().split()))

    def gcd(a, b):
        if b == 0:
            return a
        else:
            return gcd(b, a % b)
    
    def gcd_group(arr):
        g = gcd(arr[0], arr[1])
        for i in range(2, len(arr)):
            g = gcd(g, arr[i])
        return g
    
    def lcm(a, b):
        g = gcd(a, b)
        return (a*b)//g
    
    def lcm_group(arr):
        l = lcm(arr[0], arr[1])
        for i in range(2, len(arr)):
            l = lcm(l, arr[i])
        return l
    
    l = [0]
    for i in range(N-1):
        l.append(gcd(l[-1], A[i]))
    r = [0]
    for i in range(N-1, 0, -1):
        r.append(gcd(r[-1], A[i]))
    
    res = 0
    for i in range(N):
        res = max(res, gcd(l[i], r[-(i+1)]))
    print(res)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)

N = int(input())
B = list(map(int,input().split()))

mem = {}
def rec(arr):
    if len(arr)==1:
        if arr[0] == 1:
            return [1]
        else:
            return False
    h = hash(tuple(arr))
    if h in mem:
        return mem[h]
    for i,a in enumerate(arr):
        if i+1 == a:
            res = rec(arr[:i] + arr[i+1:])
            if res:
                res.append(i+1)
                mem[h] = res
                break
    else:
        mem[h] = False
    return mem[h]

ans = rec(B)
if ans:
    print(*ans,sep='\n')
else:
    print(-1)

### FIXED CODE ###

N = int(input())
B = list(map(int,input().split()))

ans = []
while B:
    for i,a in reversed(list(enumerate(B))):
        if i+1 == a:
            ans.append(a)
            del B[i]
            break
    else:
        print(-1)
        exit()
print(*ans[::-1], sep='\n')
### BUGGY CODE ###

N, K = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]

MOD = 10**9+7

def dot(A, B):
    N = len(A)
    K = len(A[0])
    assert len(B) == K
    M = len(B[0])
    C = [[0] * M for _ in range(N)]
    for i in range(N):
        for j in range(M):
            for k in range(K):
                C[i][j] += A[i][k] * B[k][j]
            C[i][j] %= MOD
    return C



def mp(A, n):
    assert len(A) == len(A[0])
    B = [[0] * len(A) for _ in range(len(A))]
    for i in range(len(A)):
        B[i][i] = 1

    while n:
        n, i = divmod(n, 2)
        if i:
            B = dot(A, B)
        A = dot(A, A)

    return B


ans = sum([sum(r) % MOD for r in mp(A, K)]) % MOD
print(ans)


### FIXED CODE ###

N, K = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]

MOD = 10**9+7

def dot(A, B):
    N = len(A)
    K = len(A[0])
    assert len(B) == K
    M = len(B[0])
    C = [[0] * M for _ in range(N)]
    for i in range(N):
        for j in range(M):
            for k in range(K):
                C[i][j] += A[i][k] * B[k][j]
            C[i][j] %= MOD
    return C



def mp(A, n):
    assert len(A) == len(A[0])
    B = [[0] * len(A) for _ in range(len(A))]
    for i in range(len(A)):
        B[i][i] = 1

    while n:
        n, i = divmod(n, 2)
        if i:
            B = dot(A, B)
        A = dot(A, A)

    return B


ans = sum([sum(r) % MOD for r in mp(A, K)]) % MOD
print(ans)
### BUGGY CODE ###

N = int(input())
dic, rst = {}, []
for i in range(N):
    s = input()
    if s in dic:
        dic[s] += 1
    else:
        dic[s] = 1
rst = [ key for key, val in dic.items() if val == max(dic.values()) ]
[ print(i) for i in sorted(rst) ]

### FIXED CODE ###

N = int(input())
dic, rst = {}, []
for i in range(N):
    S = input()
    if S in dic:
        dic[S] += 1
    else:
        dic[S] = 1
max_val = max(dic.values())
[ rst.append(key) for key, val in dic.items() if val == max_val ]
[ print(i) for i in sorted(rst) ]
### BUGGY CODE ###

mod = 2019
l,r = [int(i) for i in input().split()]

minimum = 2018

for i in range(l,r):
    for j in range(l+1,r+1):
        if (i*j)%mod < minimum:
            minimum = (i*j)%mod
    if minimum == 0:
        break
    
print(minimum)

### FIXED CODE ###

mod = 2019
l,r = [int(i) for i in input().split()]

minimum = 2018

for i in range(l,r):
    for j in range(l+1,r+1):
        if minimum == 0:
            break
        elif (i*j)%mod < minimum:
            minimum = (i*j)%mod
        else:
            pass      
    if minimum == 0:
        break
    
print(minimum)
### BUGGY CODE ###

def dfs(s, stack):
    visited[s] = 1
    if s in stack:
        print(1)
        exit()
    else:
        stack.append(s)
        for t in adj[s]:
            dfs(t, stack)
        stack.remove(s)

nv, ne = map(int, input().split(' '))
adj = [[] for _ in range(nv)]
visited = [0] * nv

for _ in range(ne):
    s, t = map(int, input().split(' '))
    adj[s].append(t)

while sum(visited) < nv:
    r = 0
    while visited[r]: r += 1
    dfs(r, [])

print(0)

### FIXED CODE ###

def dfs(s):
    if not visited[s]:
        visited[s] = True
        stack[s] = True
        for t in adj[s]:
            if stack[t]:
                print(1)
                exit()
            else:
                dfs(t)
    stack[s] = False

nv, ne = map(int, input().split(' '))
adj = [[] for _ in range(nv)]
visited = [False] * nv
stack = [False] * nv

for _ in range(ne):
    s, t = map(int, input().split(' '))
    adj[s].append(t)

for i in range(nv):
    dfs(i)

print(0)