Harryxun/stf_run huggingface dataset:
def lightdot(px, py):
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    # それぞれ上、下、左、右に移動していく
    pos = deque([[px, py, 0, 0], [px, py, 1, 0], [px, py, 2, 0], [px, py, 3, 0]])
    res = 0

    while len(pos) > 0:
        x, y, direct, depth = pos.popleft()
        nx = x + dx[direct]
        ny = y + dy[direct]
        if 0 <= nx < w and 0 <= ny < h and maze[ny][nx] == '.':
            # 方向は引き継ぐ
            pos.append([nx, ny, direct, depth + 1])
        else:
            res += depth
    # 現在地点の'.'も含める
    return res + 1

for i in range(w):
    for j in range(h):
        if maze[j][i] == '.':
            ans = max(ans, lightdot(i, j))
print(ans)

### FIXED CODE ###

def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()

from collections import defaultdict, deque, Counter
from sys import exit
import heapq
import math
import copy
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

h,w = [int(i) for i in input().split()]
b = [input() for i in range(h)]

ans = [[0]*w for i in range(h)]

for i in range(h):
    res = 0
    for j in range(w):
        if b[i][j] == ".":
            ans[i][j] += res
        if b[i][j] == ".":
            res += 1
        else:
            res = 0

for i in range(h):
    res = 0
    for j in range(w-1,-1,-1):
        if b[i][j] == ".":
            ans[i][j] += res
        if b[i][j] == ".":
            res += 1
        else:
            res = 0

for j in range(w):
    res = 0
    for i in range(h):
        if b[i][j] == ".":
            ans[i][j] += res
        if b[i][j] == ".":
            res += 1
        else:
            res = 0

for j in range(w):
    res = 0
    for i in range(h-1,-1,-1):
        if b[i][j] == ".":
            ans[i][j] += res
        if b[i][j] == ".":
            res += 1
        else:
            res = 0

print(max(max(row) for row in ans) + 1)
N, M, K = map(int, input().split())

groups = [None] * N
visited = set()

# 連結成分を求める
def dfs(group, i):
  if i in visited:
    return
  
  visited.add(i)
  group.add(i)
  groups[i] = group
  # 他のノード
  for c in graph[i]:
    if not c in visited:
      dfs(group, c)
  

graph = [set() for _ in range(N)]

friends_count = [0] * N
block_count = [0] * N

for _ in range(M):
  a, b = map(int, input().split())
  a, b = a - 1, b - 1
  friends_count[a] += 1
  friends_count[b] += 1
  graph[a].add(b)
  graph[b].add(a)
  
for i in range(N):
  dfs(set(), i)
      
for _ in range(K):
  c, d = map(int, input().split())
  c, d = c - 1, d - 1
  
  # 同じ連結成分に含まれないブロック関係は無視してok
  if d in groups[c]:
    block_count[c] += 1
    block_count[d] += 1

candidates = []

for i in range(N): 
  candidates.append(
    len(groups[i]) - friends_count[i] - block_count[i] - 1
  )
    
print(' '.join(str(x) for x in candidates))

### FIXED CODE ###

import sys
sys.setrecursionlimit(2 ** 30)
N, M, K = map(int, input().split())

groups = [None] * N
visited = set()

# 連結成分を求める
def dfs(group, i):
  if i in visited:
    return
  
  visited.add(i)
  group.add(i)
  groups[i] = group
  # 他のノード
  for c in graph[i]:
    if not c in visited:
      dfs(group, c)
  

graph = [set() for _ in range(N)]

friends_count = [0] * N
block_count = [0] * N

for _ in range(M):
  a, b = map(int, input().split())
  a, b = a - 1, b - 1
  friends_count[a] += 1
  friends_count[b] += 1
  graph[a].add(b)
  graph[b].add(a)
  
for i in range(N):
  dfs(set(), i)
      
for _ in range(K):
  c, d = map(int, input().split())
  c, d = c - 1, d - 1
  
  # 同じ連結成分に含まれないブロック関係は無視してok
  if d in groups[c]:
    block_count[c] += 1
    block_count[d] += 1

candidates = []

for i in range(N): 
  candidates.append(
    len(groups[i]) - friends_count[i] - block_count[i] - 1
  )
    
print(' '.join(str(x) for x in candidates))
s=input()
n=len(s)
k=list('keyence')
ans='NO'
cnt=[0]*n
final=0
j=0
for i in range(n):
    if j==n-1:
        break
    if s[i]==k[j]:
        cnt[i]=1
        j+=1
for i in range(n-1):
    if cnt[i]!=cnt[i+1]:
        final+=1
if cnt[0]==0 and final==1:
    ans='YES'
elif cnt[0]==1 and final==2:
    ans='YES'
if n==7 and final==0:
    ans='YES'
print(ans)

### FIXED CODE ###

s=input()
n=len(s)
k='keyence'
ans='NO'
for i in range(n):
    if s[:i]+s[i+n-7:]==k:
        ans='YES'
print(ans)
import sys
input = sys.stdin.readline

a,b=map(int,input().split())

def yakusu(x,X):
    for i in range(1,int(x**0.5)+1):
        if x%i==0:
            X.append(i)
            if x!=i:
                X.append(x//i)
    
A=[]
B=[]
yakusu(a,A)
yakusu(b,B)
A.sort()
B.sort()
#print(A,B)
kouyakusu=[]
i=0
j=0
while i<len(A) and j<len(B):
    if A[i]==B[i]:
        kouyakusu.append(A[i])
        i+=1
        j+=1
    elif A[i]>B[j]:
        j+=1
    else:
        i+=1

def isPrime(x):
    if x<=1:
        return False
    for i in range(2,x):
        if x%i==0:
            return False
    return True


ans=0
for k in kouyakusu:
    if isPrime(k):
        ans+=1
print(ans+1)

### FIXED CODE ###

import sys
input = sys.stdin.readline

a,b=map(int,input().split())

def yakusu(x,X):
    for i in range(1,int(x**0.5)+1):
        if x%i==0:
            X.append(i)
            if x!=i:
                X.append(x//i)
    
A=[]
B=[]
yakusu(a,A)
yakusu(b,B)
A.sort()
B.sort()
#print(A,B)
kouyakusu=[]
i=0
j=0
while i<len(A) and j<len(B):
    if A[i]==B[j]:
        kouyakusu.append(A[i])
        i+=1
        j+=1
    elif A[i]>B[j]:
        j+=1
    else:
        i+=1

ans=0
for i in range(1,len(kouyakusu)):
    if not(kouyakusu[i]): continue
    ans+=1
    for j in range(i+1,len(kouyakusu)):
        if kouyakusu[j]%kouyakusu[i]==0:
            kouyakusu[j]=False
#print(kouyakusu)
print(ans+1)
#!/usr/bin/env python3
#import math
import fractions

def lcm(x, y):
    #return (x * y) // math.gcd(x, y)
    return (x * y) // fractions.gcd(x, y)

if __name__ == '__main__':
    a, b, c, d = list(map(int, input().split()))
    bc = b // c
    bd = b // d
    ac = (a - 1) // c
    ad = (a - 1) // d
    l = lcm(c, d)

    ans = (b - (bc + bd)) - ((a - 1) - (ac + ad)) + b // l
    print(ans)
    

### FIXED CODE ###

#!/usr/bin/env python3

if __name__ == '__main__':
    s = input()
    f = True
    for c in range(1, len(s)):
        if s[c-1] == s[c]:
            f = False

    if f:
        print("Good")
    else:
        print("Bad")
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# 問題：https://atcoder.jp/contests/abc126/tasks/abc126_d


class Graph():

    def __init__(self):
        self.adjacency_dict = {}
    
    def add_vertex(self, v):
        self.adjacency_dict[v] = []

    def add_edge(self, v1, v2):
        self.adjacency_dict[v1].append(v2)
        self.adjacency_dict[v2].append(v1)

    def get_vertexes(self):
        return self.adjacency_dict.keys()

    def get_edges(self, v):
        return self.adjacency_dict[v]

    def print_graph(self):
        print(self.adjacency_dict)

import numpy as np
n = int(input())
p = np.full((n, n), 0)

res = []
g = Graph()
for i in range(n):
    res.append(-1)
    g.add_vertex(i)

for i in range(n-1):
    u, v, w = map(int, input().strip().split())
    g.add_edge(u-1, v-1)
    p[u-1][v-1] = w % 2
    p[v-1][u-1] = w % 2

q = []
res[0] = 0
q.append(0)
while(len(q) > 0):
    v = q.pop()
    for u in g.get_edges(v):
        if res[u] != -1:
            continue
        w = p[u][v]
        res[u] = (res[v] + w) % 2
        q.append(u)

for i in range(n):
    print(res[i])


### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# 問題：https://atcoder.jp/contests/abc126/tasks/abc126_d


class Graph():

    def __init__(self):
        self.adjacency_dict = {}
        self.weight = []
    
    def add_vertex(self, v):
        self.adjacency_dict[v] = []
        self.weight.append([])

    def add_edge(self, v1, v2, w):
        self.adjacency_dict[v1].append(v2)
        self.adjacency_dict[v2].append(v1)
        self.weight[v1].append(w)
        self.weight[v2].append(w)

    def get_vertexes(self):
        return self.adjacency_dict.keys()

    def get_edges(self, v):
        return self.adjacency_dict[v], self.weight[v]

    def print_graph(self):
        print(self.adjacency_dict)

n = int(input())

res = []
g = Graph()
for i in range(n):
    res.append(-1)
    g.add_vertex(i)

for i in range(n-1):
    u, v, w = map(int, input().strip().split())
    g.add_edge(u-1, v-1, w % 2)

q = []
res[0] = 0
q.append(0)
while(len(q) > 0):
    v = q.pop()
    u_l, w_l = g.get_edges(v)
    for u, w in zip(u_l, w_l):
        if res[u] != -1:
            continue
        res[u] = (res[v] + w) % 2
        q.append(u)

for i in range(n):
    print(res[i])
n,m = map(int,input().split())
List = [input() for i in range(n)]

print("".join(sorted(List))


### FIXED CODE ###

n,m = map(int,input().split())
List = [input() for i in range(n)]

List2 = sorted(List)
print("".join(List2))
A, B ,K  = (int(x) for x in input().split())
i = 1
ans = []
while True:
    if min(A,B) < i:
        break
    if A % i == 0 & B % i == 0:
        ans.append(i)
    i = i + 1
print(ans[-K-1])

### FIXED CODE ###

A, B ,K  = (int(x) for x in input().split())
i = 1
ans = []
while True:
    if min(A,B) < i:
        break
    if (A % i == 0) & (B % i == 0):
        ans.append(i)
    i = i + 1
print(ans[len(ans)-K])
N,K=map(int,input().split())

array=map(int,input().split())

A=list(array)
A.insert(0,0)

visit=0
root=[]
visited=1
once=0
while True:
    if visit & (0b1<<visited):
        break
    root.append(visited)
    visit|=0b1<<visited
    once+=1
    visited=A[visited]

roop=root[root.index(visited):]
print(roop)
if K<=once:
    print(root[K])
else:
    order=K-once
    print(roop[order%len(roop)])

### FIXED CODE ###

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

array=map(int,input().split())

A=list(array)
A.insert(0,0)

visit=0
root=[]
visited=1
once=0
while True:
    if visit & (0b1<<visited):
        break
    root.append(visited)
    visit|=0b1<<visited
    once+=1
    visited=A[visited]

roop=root[root.index(visited):]
if K<once:
    print(root[K])
else:
    order=K-once
    print(roop[order%len(roop)])
"""everything has a cost!"""

from math import *
import random, functools, collections, sys

__author__ = 'p7x'


# sys.stdin = open('in.txt', 'r')
# sys.stdout = open('out.txt', 'w')
# sys.stderr = open('err.txt', 'w')


if __name__ == '__main__':
    n = int(input())
    print(a + a**2 + a**3)


### FIXED CODE ###

"""everything has a cost!"""

from math import *
import random, functools, collections, sys

__author__ = 'p7x'


# sys.stdin = open('in.txt', 'r')
# sys.stdout = open('out.txt', 'w')
# sys.stderr = open('err.txt', 'w')


if __name__ == '__main__':
    n = int(input())
    print(n + n**2 + n**3)
#!/usr/bin/env python3
#C
import numpy as np
import math
import re
from functools import reduce

n = int(input())

a = input()
a = re.split(" ",a)
a = list(map(int,a))
def gcd_list(numbers):
    return reduce(math.gcd, numbers)

m = 0
for i in range(n):
    s = []
    for j in range(n):
        if j != i:
            s.append(a[j])
    x = gcd_list(s)
    if(x > m):
        m = x
print(m)

### FIXED CODE ###

#!/usr/bin/env python3
#C
def gcd(a, b):
    while b > 0:
        a, b = b, a%b
    return a

N = int(input())
A = list(map(int,input().split()))
L=[0]*(N+2)
R=[0]*(N+2)
L[0] = A[0]
R[N-1] = A[N-1]
for i in range(1,N):
    L[i] = gcd(L[i-1],A[i])
for i in range(N-2,-1,-1):
    R[i] = gcd(R[i+1],A[i])

ans = 0
for i in range(N):
    ans = max(ans,gcd(L[i-1],R[i+1]))
print(ans)
#!/usr/bin/env python3

import sys
import math
import numpy as np
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

k,q = LI()
d = LI()
nxm = [LI() for _ in range(q)]

for n,x,m in nxm:
    e = [i%m for i in d]
    zero = e.count(0)
    zero = zero*((n-1)//k)
    for i in range((n-1)%k):
        if e[i] == 0:
            zero += 1
    f = list(accumulate(e))
    s = f[-1] * ((n-1)//k)
    if (n-1)%k != 0:
        s += f[(n-1)%k-1]
    tmp = (s+x%m)//m
    print(n-1-zero-tmp)

    
    


### FIXED CODE ###

#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

k,q = LI()
d = LI()
nxm = [LI() for _ in range(q)]

for n,x,m in nxm:
    e = list(map(lambda x:(x-1)%m+1,d))
    f = list(accumulate(e))
    s = f[-1] * ((n-1)//k)
    if (n-1)%k != 0:
        s += f[(n-1)%k-1]
    tmp = (s+x%m)//m
    print(n-1-tmp)
import numpy as np
def cumsum(x):
    return list(np.cumsum(x))

def cumsum_number(N,K,x):
    ans=[0]*(N-K+1)
    number_cumsum = cumsum(x)
    number_cumsum.insert(0,0)
    for i in range(N-K+1):
        ans[i]=number_cumsum[i+K]-number_cumsum[i]
    return ans
"""
int #整数
float #小数

#for
for name in fruits: #fruitの頭から操作
    print(name)

#リスト
list0 = [] #リスト生成
list0 = [1,2,3,4] #初期化
list0 = [0]*10 #[0,0,0,0,0,0,0,0,0,0]
list1= [i for i in range(10)] #>>> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
list1 = list(map(int, input().split()))　# 複数の入力をリストに入れる
number=[int(input()) for i in range(int(input()))] #複数行の入力をリストに
list1 = list1 + [6, 7, 8] #リストの追加
list2.append(34) #リストの追加　最後に（）内が足される
list.insert(3,10) #リストの追加　任意の位置（追加したい位置,追加したい値）
len(list4) #リストの要素数
max(sa) #list saの最小値
list5.count(2) #リスト(文字列も可）内の2の数
list1.sort() #並び替え小さい順
list1.sort(reverse=True)  #並び替え大きい順
set(list1) #list1内の重複している要素を削除し、小さい順に並べる
sum([2,3,   ,3]) #リストの合計

abs(a) #aの絶対値
max(a,b) min(a,b) #最大値　最小値
text1 = text1.replace("34","test") #text1内の"34"を"test"に書き換える(文字列内の文字を入れ替える)

exit(0) #強制終了

cumsum(リスト) #累積和をリストで返す
cumsum_number(N,K,x) #N個の数が含まれるリストx内のK個からなる部分和をリストで返す
"""
N,A,B=map(int,input().split())
S=N//(A+B) #SはA+Bのセット数
M=N-S*(A+B) #Mは残り
if A<=M:
    print(A+S*A)
else:
    print(M+S*A)

### FIXED CODE ###

import numpy as np
def cumsum(x):
    return list(np.cumsum(x))

def cumsum_number(N,K,x):
    ans=[0]*(N-K+1)
    number_cumsum = cumsum(x)
    number_cumsum.insert(0,0)
    for i in range(N-K+1):
        ans[i]=number_cumsum[i+K]-number_cumsum[i]
    return ans
"""
int #整数
float #小数

#for
for name in fruits: #fruitの頭から操作
    print(name)

#リスト
list0 = [] #リスト生成
list0 = [1,2,3,4] #初期化
list0 = [0]*10 #[0,0,0,0,0,0,0,0,0,0]
list1= [i for i in range(10)] #>>> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
list1 = list(map(int, input().split()))　# 複数の入力をリストに入れる
number=[int(input()) for i in range(int(input()))] #複数行の入力をリストに
list1 = list1 + [6, 7, 8] #リストの追加
list2.append(34) #リストの追加　最後に（）内が足される
list.insert(3,10) #リストの追加　任意の位置（追加したい位置,追加したい値）
len(list4) #リストの要素数
max(sa) #list saの最小値
list5.count(2) #リスト(文字列も可）内の2の数
list1.sort() #並び替え小さい順
list1.sort(reverse=True)  #並び替え大きい順
set(list1) #list1内の重複している要素を削除し、小さい順に並べる
sum([2,3,   ,3]) #リストの合計

abs(a) #aの絶対値
max(a,b) min(a,b) #最大値　最小値
text1 = text1.replace("34","test") #text1内の"34"を"test"に書き換える(文字列内の文字を入れ替える)

exit(0) #強制終了

cumsum(リスト) #累積和をリストで返す
cumsum_number(N,K,x) #N個の数が含まれるリストx内のK個からなる部分和をリストで返す
"""
N,A,B=map(int,input().split())
S=N//(A+B) #SはA+Bのセット数
M=N-S*(A+B) #Mは残り
if A<=M:
    print(A+S*A)
else:
    print(M+S*A)
MOD=10**9+7
N=int(input())

tree=[[] for _ in range(N+1)]
for _ in range(N-1):
  A,B=map(int,input().split())
  tree[A].append(B)
  tree[B].append(A)
#print(tree)

def dfs(u,par):
  visited[u]=True
  ret=1
  for v in tree[u]:
    if not visited[v]:
      ret+=dfs(v,u)

  if par>0:
    tree_dic[(u,par)]=ret
  return ret
  
visited=[False]*(N+1)
tree_dic={}
dfs(1,0)
#print(tree_dic)

bumbo=pow(2,N,MOD)
bunshi=(pow(2,N,MOD)-1-N*pow(2,N-1,MOD))%MOD
for x in tree_dic.values():
  term=(pow(2,x,MOD)-1)*(pow(2,N-x,MOD)-1)
  bunshi+=term  
  bunshi%=MOD
#print(bunshi,bumbo)

answer=bunshi*pow(bumbo,MOD-2,MOD)
answer%=MOD
print(answer)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)
MOD=10**9+7
N=int(input())

tree=[[] for _ in range(N+1)]
for _ in range(N-1):
  A,B=map(int,input().split())
  tree[A].append(B)
  tree[B].append(A)
#print(tree)

def dfs(u,par):
  visited[u]=True
  ret=1
  for v in tree[u]:
    if not visited[v]:
      ret+=dfs(v,u)

  if par>0:
    tree_dic[(u,par)]=ret
  return ret
  
visited=[False]*(N+1)
tree_dic={}
dfs(1,0)
#print(tree_dic)

bumbo=pow(2,N,MOD)
bunshi=(pow(2,N,MOD)-1-N*pow(2,N-1,MOD))%MOD
for x in tree_dic.values():
  term=(pow(2,x,MOD)-1)*(pow(2,N-x,MOD)-1)
  bunshi+=term  
  bunshi%=MOD
#print(bunshi,bumbo)

answer=bunshi*pow(bumbo,MOD-2,MOD)
answer%=MOD
print(answer)
import fractions

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

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

A.sort()

for i in range(N-1):

    if i == 0:
        now = fractions.gcd(A[0],A[1])

    else:
        now = fractions.gcd(now,A[i+1])

if K % now == 0 and K <= A[-1]:
    print ("POSSIBLE")
else:
    print ("IMPOSSIBLE")


### FIXED CODE ###

import fractions
import sys

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

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

A.sort()

if len(A) == 1:
    if A[0] == K:
        print ("POSSIBLE")
    else:
        print ("IMPOSSIBLE")
    sys.exit()

for i in range(N-1):

    if i == 0:
        now = fractions.gcd(A[0],A[1])

    else:
        now = fractions.gcd(now,A[i+1])

if K % now == 0 and K <= A[-1]:
    print ("POSSIBLE")
else:
    print ("IMPOSSIBLE")
from collections import defaultdict

N = int(input())
xy = [list(map(int,input().split())) for _ in range(N)]
if N == 1:
  print(1)
else:
  d = defaultdict(int)
  for i in range(N):
    xi,yi = xy[i]
    for j in range(N):
      if i==j:
        continue
      else:
        xj,yj = xy[j]
      d[(xj-xi,yj-yi)] += 1
max_v = max(d.values())
print(N-max_v)



### FIXED CODE ###

from collections import defaultdict

N = int(input())
xy = [list(map(int,input().split())) for _ in range(N)]
if N == 1:
  print(1)
else:
  d = defaultdict(int)
  for i in range(N):
    xi,yi = xy[i]
    for j in range(N):
      if i==j:
        continue
      else:
        xj,yj = xy[j]
      d[(xj-xi,yj-yi)] += 1
  max_v = max(d.values())
  print(N-max_v)
if W >= S :
  print ("unsafe")
if W < S :
  print("safe")

### FIXED CODE ###

S, W = map(int, input().split())
if 1 <= W <= 100 and 1 <= S <= 100 and W >= S :
  print ("unsafe")
if 1 <= W <= 100 and 1 <= S <= 100 and W < S :
  print("safe")
H,W = map(int,input().split())
A = [[] for i in range(H)]
B = [[] for i in range(H)]

for i in range(H):
	a = list(map(int,input().split()))
	A[i] = a
for i in range(H):
	b = list(map(int,input().split()))
	B[i] = b

D = [[abs(A[i][j]) - abs(B[i][j]) for j in range(W)] for i in range(H)]
R = 160*80
dp = [[[False for k in range(R)] for j in range(W)] for i in range(H)]
dp[0][0][D[0][0]] = True
for i in range(H):
	for j in range(W):
		for n in range(R):
			if not dp[i][j][n]:
				continue
			if j != W-1:
				d = D[i][j+1]
				dp[i][j+1][n+d] = True
				dp[i][j+1][abs(n-d)] = True
			if i != H-1:
				d = D[i+1][j]
				dp[i+1][j][n+d] = True
				dp[i+1][j][abs(n-d)] = True

h,w = H-1, W-1
for i in range(160*80):
	if dp[h][w][i]:
		print(i)
		exit()

### FIXED CODE ###

H,W = map(int,input().split())
A = [[] for i in range(H)]
B = [[] for i in range(H)]

for i in range(H):
	a = list(map(int,input().split()))
	A[i] = a
for i in range(H):
	b = list(map(int,input().split()))
	B[i] = b

D = [[abs(A[i][j] - B[i][j]) for j in range(W)] for i in range(H)]
R = 160*80
"""
dp = [[[False for k in range(R)] for j in range(W)] for i in range(H)]
dp[0][0][D[0][0]] = True
for i in range(H):
	for j in range(W):
		r = 80 * (i+j+2)
		for n in range(r):
			if not dp[i][j][n]:
				continue
			if j != W-1:
				d = D[i][j+1]
				dp[i][j+1][n+d] = True
				dp[i][j+1][abs(n-d)] = True
			if i != H-1:
				d = D[i+1][j]
				dp[i+1][j][n+d] = True
				dp[i+1][j][abs(n-d)] = True

"""
dp = [[0 for j in range(W)] for i in range(H)]
dp[0][0] = 2**(R + D[0][0]) | 2**(R - D[0][0])
for i in range(H):
	for j in range(W):
		if j != W-1:
			d = D[i][j+1]
			dp[i][j+1] |= (dp[i][j] << d | dp[i][j] >> d)
		if i != H-1:
			d = D[i+1][j]
			dp[i+1][j] |= (dp[i][j] << d | dp[i][j] >> d)
h,w = H-1, W-1
for i in range(R):
	mask = 2 ** (R+i) | 2 ** (R-i)
	if dp[h][w] & mask > 0:
		print(i)
		exit()
def acgt_2(t):
    w = ["A","C","G","T"]
    string_list = []
    for i in range(4):
        a = t // (4**(3-i))
        t = t % (4**(3-i))
        s = w[a]
        string_list.append(s)
    
    def acgt_sw(inst,a,b):
        st = copy.deepcopy(inst)
        st[a], st[b] = st[b], st[a]
        return "".join(st)

    
    string_list_2 = ["".join(string_list)] + [acgt_sw(string_list,i,i+1) for i in range(3)] 
    judge = False
    for i in string_list_2:

        if i[:3] == "AGC":
            judge = True

        if i[1:] == "AGC":
            judge = True

    return judge, "".join(string_list)
        

mod = 10**9+7
ng_list = []
for i in range(256):
    if acgt_2(i)[0]:
        ng_list.append(i)



n = int(input())
if n == 3:
    ans = 61
else:
    dp_list = [ 1 for i in range(4**4) ]
    for i in ng_list:
        dp_list[i] = 0

    for i in range(n-4):
        new_dp_list = [ 0 for i in range(4**4) ]
        for j in range(4**4):
            base = dp_list[j]
            new_index = [ 4*(j % 64) + k for k in range(4) ]
            for k in new_index:
                new_dp_list[k] += base
        for j in ng_list:
            new_dp_list[j] = 0
            dp_list = [ i%mod for i in new_dp_list]

print(sum(dp_list)%mod)

### FIXED CODE ###

import copy
def acgt_2(t):
    w = ["A","C","G","T"]
    string_list = []
    for i in range(4):
        a = t // (4**(3-i))
        t = t % (4**(3-i))
        s = w[a]
        string_list.append(s)
    
    def acgt_sw(inst,a,b):
        st = copy.deepcopy(inst)
        st[a], st[b] = st[b], st[a]
        return "".join(st)

    
    string_list_2 = ["".join(string_list)] + [acgt_sw(string_list,i,i+1) for i in range(3)] 
    judge = False
    for i in string_list_2:

        if i[:3] == "AGC":
            judge = True

        if i[1:] == "AGC":
            judge = True

    return judge, "".join(string_list)
        

mod = 10**9+7
ng_list = []
for i in range(256):
    if acgt_2(i)[0]:
        ng_list.append(i)



n = int(input())
if n == 3:
    ans = 61
else:
    dp_list = [ 1 for i in range(4**4) ]
    for i in ng_list:
        dp_list[i] = 0

    for i in range(n-4):
        new_dp_list = [ 0 for i in range(4**4) ]
        for j in range(4**4):
            base = dp_list[j]
            new_index = [ 4*(j % 64) + k for k in range(4) ]
            for k in new_index:
                new_dp_list[k] += base
        for j in ng_list:
            new_dp_list[j] = 0
            dp_list = [ i%mod for i in new_dp_list]
    ans = sum(dp_list)%mod

print(ans)