Harryxun/stf_run huggingface dataset:
import sys
inf=1000002
sys.setrecursionlimit(inf)
from collections import deque
h,w,k=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
c=[input() for i in range(h)]
dp=[[inf if c[i][j]=="." else -1 for j in range(w)] for i in range(h)]
now=deque([x1-1,y1-1])
dp[x1-1][y1-1]=0
def bfs(d):
    global dp,now
    l=len(now)
    if l==0:
        return
    dp_sub=deque()
    cand=set()
    for i in range(l):
        x,y=now.popleft()
        for j in range(1,min(k+1,w-y)):
            if dp[x][y+j]==inf:
                dp_sub.append([x,y+j,d])
                cand.add((x,y+j))
            else:
                break
        for j in range(1,min(k+1,y+1)):
            if dp[x][y-j]==inf:
                dp_sub.append([x,y-j,d])
                cand.add((x,y-j))
            else:
                break
        for j in range(1,min(k+1,h-x)):
            if dp[x+j][y]==inf:
                dp_sub.append([x+j,y,d])
                cand.add((x+j,y))
            else:
                break
        for j in range(1,min(k+1,x+1)):
            if dp[x-j][y]==inf:
                dp_sub.append([x-j,y,d])
                cand.add((x-j,y))
            else:
                break
    while dp_sub!=deque([]):
        e=dp_sub.popleft()
        dp[e[0]][e[1]]=e[2]
    for i in cand:
        now.append(i)
    bfs(d+1)
bfs(1)
print(dp[x2-1][y2-1] if dp[x2-1][y2-1]!=inf else -1)

### FIXED CODE ###

import sys
inf=1000002
sys.setrecursionlimit(inf)
from collections import deque
h,w,k=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
c=[input() for i in range(h)]
dp=[[inf if c[i][j]=="." else -1 for j in range(w)] for i in range(h)]
now=deque()
now.append([x1-1,y1-1])
dp[x1-1][y1-1]=0
#kの更新が遅い
def bfs(d):
    global h,w,k,dp,now,x2,y2
    l=len(now)
    if l==0:
        return
    dp_sub=deque()
    cand=set()
    for i in range(l):
        x,y=now.popleft()
        for j in range(1,min(k+1,w-y)):
            if dp[x][y+j]==inf:
                dp_sub.append([x,y+j,d])
                #dp[x][y+j]=d
                cand.add((x,y+j))
                #now.append([x,y+j])
            else:
                break
        for j in range(1,min(k+1,y+1)):
            if dp[x][y-j]==inf:
                dp_sub.append([x,y-j,d])
                #dp[x][y-j]=d
                cand.add((x,y-j))
                #now.append([x,y-j])
            else:
                break
        for j in range(1,min(k+1,h-x)):
            if dp[x+j][y]==inf:
                dp_sub.append([x+j,y,d])
                #dp[x+j][y]=d
                cand.add((x+j,y))
                #now.append([x+j,y])
            else:
                break
        for j in range(1,min(k+1,x+1)):
            if dp[x-j][y]==inf:
                dp_sub.append([x-j,y,d])
                #dp[x-j][y]=d
                cand.add((x-j,y))
                #now.append([x-j,y])
            else:
                break
    while dp_sub!=deque([]):
        e=dp_sub.popleft()
        dp[e[0]][e[1]]=e[2]
    for i in cand:
        now.append(i)
    bfs(d+1)
bfs(1)
print(dp[x2-1][y2-1] if dp[x2-1][y2-1]!=inf else -1)
import heapq

n = int(input())
d = list(map(int, input().split()))
heapq.heapify(d)
if d[0] != 0:
    print(0)
else:
    pre = -1
    num = 0
    ans = 1
    for i in range(len(d)):
        if d[0] == 0:
            if i > 0:
                print(0)
                break
            else:
                pre = 0
                heapq.heappop(d)
                continue
        if d[0] == pre:
            num += 1
            if i == n-1:
                ans *= d[i]**num
            heapq.heappop(d)
        elif d[0] - pre > 1:
            print(0)
            break
        else:
            if i == 1:
                num = 1
                pre = d[0]
                heapq.heappop(d)
                continue
            ans *= pre**num
            pre = d[0]
            if i == n-1:
                ans *= pre
            num = 1
            heapq.heappop(d)
    else:
        print(ans)


### FIXED CODE ###

n = int(input())
d = list(map(int, input().split()))
lis = [0 for i in range(10**5+100)]
ans = 1
mx = -1
for i in d:
    lis[i] += 1
    if i > mx:
        mx = i
if lis[0] != 1 or d[0] != 0:
    print(0)
else:
    for i in range(1, mx+1):
        ans *= lis[i-1]**lis[i]
    print(ans%998244353)
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]


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

ablst=[[0]*w for i in range(h)]
ma=0
for i in range(h):
    for j in range(w):
        ablst[i][j]=abs(a[i][j]-b[i][j])
        ma=max(ma,ablst[i][j])
lst1=[0]*ma*(h+w+10)

lst=[[lst1[:] for i in range(w)] for i in range(h)]
lst[0][0][abs(a[0][0]-b[0][0])]=1


# print(lst)
for i in range(h):
    for j in range(w):
        if i+1<h:
            for k in range(len(lst[i][j])):
                if lst[i][j][k]==1:
                    lst[i+1][j][k+ablst[i+1][j]]=1
                    lst[i+1][j][abs(k-ablst[i+1][j])]=1
        if j+1<w:
             for k in range(len(lst[i][j])):
                if lst[i][j][k]==1:
                    lst[i][j+1][k+ablst[i][j+1]]=1
                    lst[i][j+1][abs(k-ablst[i][j+1])]=1
    # print(d)
        # print(lst[i][j])
# anslst=list(lst[-1][-1].keys())
# anslst.sort(key=lambda x: abs(x))
# print(lst)
for i in range(len(lst[-1][-1])):
    if lst[-1][-1][i]==1:
        print(i)
        break

### FIXED CODE ###

import sys

input = sys.stdin.buffer.readline

h, w = map(int, input().split())
AA = [list(map(int, input().split())) for _ in range(h)]
BB = [list(map(int, input().split())) for _ in range(h)]

kouho = [[0] * (w) for _ in range(h)]
delta = abs(AA[0][0] - BB[0][0])
kouho[0][0] |= 1 << delta
for y in range(h):
    for x in range(w):
        nx = x + 1
        ny = y
        if nx < w:
            delta = abs(AA[ny][nx] - BB[ny][nx])
            temp = 0
            for i in range(1, delta + 1):
                if (kouho[y][x] >> i) % 2:
                    temp |= 1 << (delta - i)
            # print(x,y,kouho[y][x],temp,delta)
            kouho[ny][nx] |= kouho[y][x] << delta
            kouho[ny][nx] |= kouho[y][x] >> delta
            kouho[ny][nx] |= temp

        nx = x
        ny = y + 1
        if ny < h:
            delta = abs(AA[ny][nx] - BB[ny][nx])
            temp = 0
            for i in range(1, delta + 1):
                if (kouho[y][x] >> i) % 2:
                    temp |= 1 << (delta - i)
            # print(x,y,kouho[y][x],temp,delta)
            kouho[ny][nx] |= kouho[y][x] << delta
            kouho[ny][nx] |= kouho[y][x] >> delta
            kouho[ny][nx] |= temp
# print(kouho)
for i in range(81):
    if (kouho[h - 1][w - 1] >> i) % 2:
        print(i)
        exit()
#-*-coding:utf-8-*-
import sys
input=sys.stdin.readline

def main():
    numbers=[]
    #n = int(input())
    n,m = map(int,input().split())
    #numbers=list(map(int,input().split()))
    numbers=[list(map(int,input().split())) for _ in range(m)]
    dp={}
    for number in numbers:
        for n in number:
            if n not in dp:
                dp[n]=1
            else:
                dp[n]+=1
    for i in range(1,n+1):
        print(dp[i])

if __name__=="__main__":
    main()

### FIXED CODE ###

#-*-coding:utf-8-*-
import sys
input=sys.stdin.readline

def main2():
    numbers=[]
    n,m = map(int,input().split())
    numbers=[list(map(int,input().split())) for _ in range(m)]
    dp=[0]*n
    for number in numbers:
        for n in number:
            dp[n-1]+=1
    for ans in dp:
        print(ans)

def main():
    numbers=[]
    n,m = map(int,input().split())
    numbers=[list(map(int,input().split())) for _ in range(m)]
    dp={}
    for number in numbers:
        for n in number:
            if n not in dp:
                dp[n]=1
            else:
                dp[n]+=1
    print(dp)
    for i in range(1,len(dp)+1):
        print(dp[i])

if __name__=="__main__":
    main2()
def main():
    N = int(input())

    ans = [0] * 4001
    for i in range(1, 201):
        for j in range(1, 201):
            if i**2 + j**2 < 4001:
                for k in range(1, 201):
                    tmp = i**2 + j**2 + k**2 + i*j + j*k + i*k
                    if tmp < 4001:
                        ans[tmp] += 1

    for i in range(1, N+1):
        print(ans[i])


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N = int(input())

    ans = [0] * 10001
    for i in range(1, 101):
        for j in range(1, 101):
            if i**2 + j**2 < 10001:
                for k in range(1, 101):
                    tmp = i**2 + j**2 + k**2 + i*j + j*k + i*k
                    if tmp < 10001:
                        ans[tmp] += 1

    for i in range(1, N+1):
        print(ans[i])


if __name__ == '__main__':
    main()
import sys
from collections import deque
import copy
def main():
    A,B = map(int, input())
    print(A * B)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from collections import deque
import copy
def main():
    A, B = map(int, input().split())
    print(A * B)

if __name__ == '__main__':
    main()
n = int(input())
v = [int(x) for x in input().split()]
even = [0] * (10 ** 5)
odd = [0] * (10 ** 5)
for i in range(10 ** 5):
    even[i] = [0] * 2
    odd[i] = [0]*2
    even[i][1] = i
    odd[i][1] = i

for j in range(n):
    if j % 2 == 0:
        even[v[j]][0] += 1
    else:
        odd[v[j]][0] += 1
even = sorted(even, reverse=True)
odd = sorted(odd, reverse=True)
if even[0][1] == odd[0][1]:
    if even[0][0] > odd[0][0]:
        ans = n - even[0][0] - odd[1][0]
    else:
        ans = n - odd[0][0] - even[1][0]
else:
    ans = n-even[0][0]-odd[0][0]
print(ans)


### FIXED CODE ###

n = int(input())
v = [int(x) for x in input().split()]
big = 10**5+1
even = [0] * big
odd = [0] * big
for i in range(big):
    even[i] = [0] * 2
    odd[i] = [0]*2
    even[i][1] = i
    odd[i][1] = i

for j in range(n):
    if j % 2 == 0:
        even[v[j]][0] += 1
    else:
        odd[v[j]][0] += 1

even = sorted(even, reverse=True)
odd = sorted(odd, reverse=True)

ans = 0
if even[0][1] == odd[0][1]:
    ans = min(n - odd[0][0] - even[1][0], n - even[0][0] - odd[1][0])
else:
    ans = n - even[0][0] - odd[0][0]
print(ans)
def answer(n: int, k: int, d: []) -> int:
    numbers = list({0, 1, 2, 3, 4, 5, 6, 7, 8, 9} ^ set(d))
    payment = ''
    for i in str(n):
        for num in numbers:
            if int(i) <= num:
                payment += str(num)
                break
    return int(payment)


def main():
    n, k = map(int, input().split())
    d = map(int, input().split())
    print(answer(n, k, d))


if __name__ == '__main__':
    main()


### FIXED CODE ###

def is_bad_nums(j: int, d: []) -> bool:
    while j:
        if j % 10 in d:
            return True
        j //= 10
    return False


def answer(n: int, k: int, d: []) -> int:
    for i in range(n, 100000):
        if is_bad_nums(i, d):
            continue
        return i


def main():
    n, k = map(int, input().split())
    d = list(map(int, input().split()))
    print(answer(n, k, d))


if __name__ == '__main__':
    main()
import sys
import math
from io import StringIO


lines = [[0,1,2], [3,4,5], [6,7,8],[0,3,6],[1,4,7],[2,4,8],[0,4,8],[2,4,6]]

table = [int(s) for s in input().split()]
table += [int(s) for s in input().split()]
table += [int(s) for s in input().split()]

lis = [int(input()) for _ in range(int(input()))]

ans = [ n in lis for n in table ]

for line in lines:
  valid = True
  for num in line:
    if not ans[num] :
      valid = False
      break

      if valid:
        print('Yes')
        return

      print('No')


### FIXED CODE ###

import sys
import math
from io import StringIO
import unittest

lines = [[0,1,2], [3,4,5], [6,7,8],[0,3,6],[1,4,7],[2,5,8],[0,4,8],[2,4,6]]

def resolve():
    table = [int(s) for s in input().split()]
    table += [int(s) for s in input().split()]
    table += [int(s) for s in input().split()]

    lis = [int(input()) for _ in range(int(input()))]

    ans = [ n in lis for n in table ]

    for line in lines:
        valid = True
        for num in line:
            if not ans[num] :
                valid = False
                break

        if valid:
            print('Yes')
            return

    print('No')
resolve()
import math
N,X=map(int,input().split())
x=list(map(int,input().split()))
L=sorted(x+[X])
def GCD(LIST):
	if len(LIST)==2:
		return math.gcd(LIST[0],LIST[1])
	else:
		return GCD([math.gcd(LIST[0],LIST[1])]+LIST[2::])
if N==1:
	print(abs(X-x[0]))
else:
	LL=[L[i+1]-L[i] for i in range(N-1)]
	print(GCD(LL))

### FIXED CODE ###

from functools import reduce
N,X=map(int,input().split())
x=list(map(int,input().split()))
L=x+[X]
if N==1:
	print(abs(X-x[0]))
else:
	LL=[abs(L[i+1]-L[i]) for i in range(N)]
	def gcd(a,b):
		while b>0:
			a,b=b,a%b
		return a
	print(reduce(gcd,LL))
import sys
from itertools import accumulate
from itertools import groupby
from scipy.special import comb

#booltable=[0]+booltable
"""
6
1 3 -4 2 2 -2

3
"""

def resolve():
    input = sys.stdin.readline
    N=int(input().rstrip())
    A=list(map(int,input().rstrip().split()))
    A=[0]+A

    cumsum = sorted(list(accumulate(A)))
    ans=0
    for key, group in groupby(cumsum):
        groupsize=len(list(group))
        if groupsize%2==0:
            ans += comb(groupsize,2) # 組み合わせ列挙 5C3
    print(int(ans))        
    

from io import StringIO
import unittest

import sys
from io import StringIO
import unittest

class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """6
1 3 -4 2 2 -2"""
        output = """3"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """7
1 -1 1 -1 1 -1 1"""
        output = """12"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """5
1 -2 3 -4 5"""
        output = """0"""
        self.assertIO(input, output)

if __name__ == "__main__":
    #unittest.main()
    resolve()

### FIXED CODE ###

import sys
from itertools import accumulate
from itertools import groupby
#from scipy.special import comb
#from scipy.misc import comb

#booltable=[0]+booltable
"""
6
1 3 -4 2 2 -2

3
"""

def resolve():
    #input = sys.stdin.readline
    N=int(input().rstrip())
    #A=list(map(int,input().rstrip().split()))
    A=[int(x)for x in input().split()]


    cumsum = sorted(list(accumulate(A)))
    ans=0
    for key, group in groupby(cumsum):
        groupsize=len(list(group))
        if groupsize>=2:
            #ans += comb(groupsize,2,1) # 組み合わせ列挙 5C3
            ans+=groupsize*(groupsize-1)//2
        if key==0:
            ans+=groupsize
    print(int(ans))        
    


import sys
from io import StringIO
import unittest

class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """6
1 3 -4 2 2 -2"""
        output = """3"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """7
1 -1 1 -1 1 -1 1"""
        output = """12"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """5
1 -2 3 -4 5"""
        output = """0"""
        self.assertIO(input, output)

if __name__ == "__main__":
    #unittest.main()
    resolve()
# -*- coding: utf-8 -*-
import numpy as np

n,m = map(int, input().split())
graph = [[] for j in range(n)]
graph = np.array(graph)

for i in range(m):
    a,b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

used = [False]*n
used[0] = True

def DFS(v,used):
    if all(used):
        return 1
    ans = 0
    for i in graph(v):
        if used[i]:
            continue
        used[i] = True
        ans += DFS(i,used)
        used[i] = False
    return ans
  
print(DFS(0,used))

### FIXED CODE ###

# -*- coding: utf-8 -*-
import numpy as np

n,m = map(int, input().split())
graph = [[0 for i in range(n)] for j in range(n)]
graph = np.array(graph)

for i in range(m):
    a,b = map(int, input().split())
    graph[a-1,b-1] = 1
    graph[b-1,a-1] = 1

used = [False]*n
used[0] = True

def DFS(v,used):
    global ans
    if all(used):
        ans += 1
        return 
    for i in range(n):
        if used[i]:
            continue
        if graph[i,v] == 0:
            continue
        used[i] = True
        DFS(i,used)
        used[i] = False
    return

ans = 0
DFS(0,used)

print(ans)
from bisect import bisect_left
 
n = int(input())
l = list(map(int, input().split())).sort
 
c = 0
for i in range(n-2):
  for j in range(i+1, n-1):
    c += bisect_left(l, l[i]+l[j], j+1)
 
print(c)


### FIXED CODE ###

from bisect import bisect_left
 
n = int(input())
l = list(map(int, input().split()))
l.sort()
 
c = 0
for i in range(n-2):
  for j in range(i+1, n-1):
    c += bisect_left(l, l[i]+l[j]) - j - 1
 
print(c)
n,k=map(int,input().split())
l=[0]*(k+1)
for i in range(k):
    num=(k-i)
    if k//num==1:
        l[num]=1
    else:
        ret=(k//num,n,10**9+7)
        for j in range(2,k//num+1):
            ret-=l[num*j]
            ret%=(10**9+7)
        l[num]=(ret)%(10**9+7)
ans=0
for i in range(k+1):
    ans+=(l[i]*i)%(10**9+7)
print(ans%(10**9+7))


### FIXED CODE ###

n,k=map(int,input().split())
l=[0]*(k+1)
for i in range(k):
    num=(k-i)
    if k//num==1:
        l[num]=1
    else:
        ret=pow(k//num,n,10**9+7)
        for j in range(2,k//num+1):
            ret-=l[num*j]
            ret%=(10**9+7)
        l[num]=(ret)%(10**9+7)
ans=0
for i in range(k+1):
    ans+=(l[i]*i)%(10**9+7)
print(ans%(10**9+7))
import itertools as itl

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

for mi in M:
    flg = False
    for i in range(n):
        for j in itl.combinations(A, i+1):
            if sum(j) == mi:
                flg = True
                break
        if flg: break
    if flg: print("yes")
    else: print("no")


### FIXED CODE ###

import itertools as itl

n = int(input())
A = list(map(int, input().split()))
q = int(input())
M = list(map(int, input().split()))
S = []

for i in range(n):
    cmb = list(itl.combinations(A, i+1))
    for j in cmb:
        S.append(sum(j))

for m in M:
    flg = False
    for s in S:
        if s == m:
            flg = True
            break
    if flg:
        print("yes")
    else:
        print("no")
import math
try:
    a,b,c,d=map(int,input().split())
except EOFError:
    pass

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

def ans_cnt(i,y,z):
    return i - (i//y + i//z - i//lcm(y,z))

print(ans_cnt(b,c,d)-ans_cnt(a-1,c,d))

### FIXED CODE ###

from fractions import gcd
a,b,c,d=map(int,input().split())

def lcm(x,y):
    return (x*y)//gcd(x,y)

def ans_cnt(i,y,z):
    return i - (i//y + i//z - i//lcm(y,z))

print(ans_cnt(b,c,d)-ans_cnt(a-1,c,d))
n = int(input())
h = list(map(int, input().split()))

dp = [0] * (n + 10)
dp[1] = abs(h[1] - h[0])
for i in range(2, n):
    dp[i] = min(dp[i - 1] + abs(h[i] - h[i - 1]), dp[i - 2] + abs(h[i] - h[i - 2]))              dp[i - 2] + abs(h[i] - h[i - 2]))
print(dp[n - 1])


### FIXED CODE ###

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

dp = [0] * (n + 10)
dp[1] = abs(h[1] - h[0])
for i in range(2, n):
    dp[i] = min(dp[i - 1] + abs(h[i] - h[i - 1]), dp[i - 2] + abs(h[i] - h[i - 2]))
print(dp[n - 1])
from math import gcd
n = int(input())
T = [int(input()) for i in range(n)]
ans = 1
for t in T:
    ans = int(ans*t/gcd(ans,t))
print(ans)

### FIXED CODE ###

from fractions import gcd
n = int(input())
T = [int(input()) for i in range(n)]
ans = 1
for t in T:
    ans = ans*t//gcd(ans,t)
print(ans)
a,b,k = map(int, input().split())


A = []

B = []


for i in range (1,a+1):

	if(a % i == 0):

		A.append(i)


for j in range (1,b+1):

	if(a % i == 0):

		B.append(j)


G = set(A) & set(B)


G.reverse()



print(G[k])







### FIXED CODE ###

a,b,k = map(int, input().split())
count = 0
for i in range (min(a,b),0,-1):
	if a % i == 0 and b % i == 0:
		count += 1
		d = i;
	if count == k:
		print(d)
		break
import numpy as np
H, W = map(int, input().split())
S = []
ij = np.zeros((H,W), dtype=int)    # .の連続数を格納用

for i in range(H):
    S.append(input())
    cnt = 0
    start = 0
    end = 0
    for j in range(W):
        if S[i][j] == '#':
            ij[i, start:end+1] += cnt
            cnt = 0
        elif j > 0 and S[i][j-1] == '#':    # .のstart
            start = j
            end = j
            cnt = 1
        else:
            end = j
            cnt += 1
        if j == W-1:    # 最後に書き込み
            ij[i, start:end+1] += cnt
            cnt = 0

for j in range(W):
    cnt = 0
    start = 0
    end = 0
    for i in range(H):
        if S[i][j] == '#':
            ij[start:end+1, j] += cnt
            cnt = 0
        elif i > 0 and S[i-1][j] == '#':    # .のstart
            start = i
            end = i
            cnt = 1
        else:
            end = i
            cnt += 1
        if i == H-1:    # 最後に書き込み
            ij[start:end+1, j] += cnt
            cnt = 0

ij = ij - 1  # 自分が2回足されるので、1引く
ans = ij.max()
print(ans)


### FIXED CODE ###

import numpy as np
H, W = map(int, input().split())
S = np.array([list(input()) for _ in range(H)]) == '.'
us = np.zeros((H,W), dtype=int)    # .の連続数を格納用
ds = np.zeros((H,W), dtype=int)    # .の連続数を格納用
ls = np.zeros((H,W), dtype=int)    # .の連続数を格納用
rs = np.zeros((H,W), dtype=int)    # .の連続数を格納用

for h in range(1,H):
    us[h, :] = (us[h-1, :] + 1) * S[h-1, :]
for h in range(H-2, -1, -1):
    ds[h, :] = (ds[h+1, :] + 1) * S[h+1, :]
for w in range(1,W):
    ls[:, w] = (ls[:, w-1] + 1) * S[:, w-1]
for w in range(W-2, -1, -1):
    rs[:, w] = (rs[:, w+1] + 1) * S[:, w+1]

ans = ((us + ds + ls + rs)*S).max() + 1
print(ans)
import sys
input = sys.stdin.readline

_x, _y = map(int, input().split())


def combination(n, r, mod=10 ** 9 + 7):
    n1, r = n + 1, min(r, n - r)
    numer = denom = 1
    for i in range(1, r + 1):
        numer = numer * (n1 - i) % mod
        denom = denom * i % mod
    return numer * pow(denom, mod - 2, mod) % mod


X, Y = map(int, input().split())
if (X + Y) % 3 != 0 or not (X <= 2 * Y and Y <= 2 * X):
    print(0)
    exit()

n = (X + Y) // 3
r = Y - n
print(combination(n, r))


def nCk(n, k, m=10 ** 9 + 7):
    a = b = 1
    k = min(k, n - k)
    for i in range(k):
        a = (a * (n - i)) % m
        b = (b * (i + 1)) % m

    return (a * pow(b, m - 2, m)) % m


def chker(x, y):
    if (x + y) % 3 != 0 or x > 2 * y or y > 2 * x:
        print(0)
        return

    if x == y:
        b = x // 3
        print(nCk(2 * b, b))
        return

    x, y = (x, y) if x < y else (y, x)

    b = 2 * x - y
    if b % 3 != 0:
        print(0)
        return

    d1, d2 = b // 3, x - 2 * (b // 3)
    u = d1 + d2

    print(nCk(u, d1))


chker(_x, _y)


### FIXED CODE ###

import sys
input = sys.stdin.readline

_x, _y = map(int, input().split())


def nCk(n, k, m=10 ** 9 + 7):
    a = b = 1
    k = min(k, n - k)
    for i in range(k):
        a = (a * (n - i)) % m
        b = (b * (i + 1)) % m

    return (a * pow(b, m - 2, m)) % m


def chker(x, y):
    if (x + y) % 3 != 0 or x > 2 * y or y > 2 * x:
        print(0)
        return

    if x == y:
        b = x // 3
        print(nCk(2 * b, b))
        return

    x, y = (x, y) if x < y else (y, x)

    b = 2 * x - y
    if b % 3 != 0:
        print(0)
        return

    d1, d2 = b // 3, x - 2 * (b // 3)
    u = d1 + d2

    print(nCk(u, d1))


chker(_x, _y)