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

from collections import deque
import numpy as np

num_r,num_c = map(int,input().split())
field = [list(input()) for i in range(num_r)]
q_r = deque([])
q_c = deque([])
seen = np.zeros((num_r,num_c))
step_r = [1,0,-1,0]
step_c = [0,1,0,-1]

for i in range(num_r):
  for j in range(num_c):
    if field[i][j] == "#":
      q_r.append(i)
      q_c.append(j)
      g_r = 0
      g_c = 0

while q_r:
  r = q_r.popleft()
  c = q_c.popleft()

  for i in range(4):
    next_r = r + step_r[i]
    next_c = c + step_c[i]
    
    if (next_r<0) or (num_r<=next_r) or (next_c<0) or (num_c<=next_c) or (field[next_r][next_c] == "#"):
      continue
    
    field[next_r][next_c] = "#"
    q_r.append(next_r)
    q_c.append(next_c)
    seen[next_r][next_c] = seen[r][c] + 1
#    print(seen[next_r][next_c],next_r,next_c)
    g_r = next_r
    g_c = next_c

print(int(seen[g_r][g_c]))

### FIXED CODE ###

def main():
    h,w = map(int,input().split())
    a = []
    for i in range(h):
        a.append(input())

    used = [True]*(h*w)

    p = []
    for i in range(h):
        for j in range(w):
            if a[i][j] == '#':
                p.append(i*w+j)
                used[i*w+j] = False


    
    res = 0
    while p:
        tank = []
        for e in p:
            if e>w-1 and used[e-w]:
                tank.append(e-w)
                used[e-w] = False
            if e%w > 0 and used[e-1]:
                tank.append(e-1)
                used[e-1] = False
            if e<(h-1)*w and used[e+w]:
                tank.append(e+w)
                used[e+w] = False
            if e%w<w-1 and used[e+1]:
                tank.append(e+1)
                used[e+1] =  False
        p = tank
        res += 1
    print(res-1)

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

N, M = map(int, input().split())
H_i = list(map(int, input().split()))
U = [list(map(int, input().split())) for i in range(M)]

path = [[0 for i in range(N)] for j in range(N)]

ans = 0

for i in U:
    path[i[0] - 1][i[1] - 1] = 1
    path[i[1] - 1][i[0] - 1] = 1

for i in range(N):
    for j in range(N):
        if path[i][j] == 1:
            if H_i[i] <= H_i[j]:
                break
        if j == N - 1:
            ans += 1

print(ans)


### FIXED CODE ###

N, M = map(int, input().split())
H = list(map(int, input().split()))

good = [True] * N

for _ in range(M):
  A, B = map(int, input().split())
  A -= 1
  B -= 1
  if H[A] >= H[B]:
    good[B] = False
  if H[A] <= H[B]:
    good[A] = False
print(sum(good))
### BUGGY CODE ###

n = int(input())
s = list(input())
q = int(input())
que = [list(input().split()) for _i in range(q)]
for x, y, z in que:
    if x == '1':
        s[int(y)-1] = z
    else:
        print(len(set(s[int(y)-1:int(z)])))

### FIXED CODE ###

n = int(input())
s = list(input())

dic = {}
for i in range(26):
    dic[chr(i+97)] = []

for i in range(n):
    dic[s[i]].append(i)

for i in range(26):
    dic[chr(i+97)].append(float('inf'))

from bisect import bisect_left
q = int(input())
for i in range(q):
    x, y, z = input().split()
    if x == '1':
        y = int(y) - 1
        p = bisect_left(dic[s[y]], y)
        dic[s[y]].pop(p)
        dic[z].insert(bisect_left(dic[z], y), y)
        s[y] = z
    else:
        res = 0
        y, z = int(y) - 1, int(z) - 1
        for i in range(26):
            p = dic[chr(i+97)][bisect_left(dic[chr(i+97)], y)]
            if p <= z:
                res += 1
        print(res)
### BUGGY CODE ###

import math
import sys
import bisect
import itertools

N, M = [int(x) for x in input().split()]
MOD = 10 ** 9 + 7

divisor = []
dict = {}

m = M
d = 2
while m != 1:
    while m % d == 0:
        # divisor.append(d)
        m //= d
        dict[d] = dict.get(d, 0) + 1
    d += 1
C = dict.values()
ret = 1


def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


for c in C:
    ret *= combinations_count(c + N - 1, c)
    ret %= MOD

print(ret)


### FIXED CODE ###

import math

N, M = [int(x) for x in input().split()]
MOD = 10 ** 9 + 7

divisor = []
dict = {}

m = M
d = 2
while m != 1:
    while m % d == 0:
        # divisor.append(d)
        m //= d
        dict[d] = dict.get(d, 0) + 1
    d += 1
C = dict.values()
ret = 1


# def combinations_count(n, r):
#     return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def combinations_count(n, r):
    a = max(r, n-r)
    b = min(r, n-r)
    r = 1
    for i in range(a+1, n+1):
        r *= i
    return r // math.factorial(b)


for c in C:
    ret *= combinations_count(c + N - 1, c)
    ret %= MOD

print(ret)
### BUGGY CODE ###

import numpy as np
A, B, Q = list(map(int, input().split()))
s = [int(input()) for i in range(A)]
t = [int(input()) for i in range(B)]
s.append(-100000000000);s.append(100000000000)
t.append(-100000000000);t.append(100000000000)
s = sorted(s, reverse=False)
t = sorted(t, reverse=False)
sn = np.array(s)
tn = np.array(t)

for i in range(Q):
    xi = int(input())
    sr = sn[sn.searchsorted(xi)]
    sl = sn[sn.searchsorted(xi) - 1]
    tr = tn.searchsorted(sn[sn.searchsorted(xi)])
    tl = tn.searchsorted(sn[sn.searchsorted(xi) - 1])

    stot = min(abs(xi - sr) + abs(sr - tn[tr]), abs(xi - sr) + abs(sr - tn[tr - 1]),
               abs(xi - sl) + abs(sl - tn[tl]), abs(xi - sl) + abs(sl - tn[tl - 1]))

    tr = tn[tn.searchsorted(xi)]
    tl = tn[tn.searchsorted(xi) - 1]
    sr = sn.searchsorted(tn[tn.searchsorted(xi)])
    sl = sn.searchsorted(tn[tn.searchsorted(xi) - 1])

    ttos = min(abs(xi - tr) + abs(tr - sn[sr]), abs(xi - tr) + abs(tr - sn[sr - 1]),
               abs(xi - tl) + abs(tl - sn[sl]), abs(xi - tl) + abs(tl - sn[sl - 1]))
    print(min(stot, ttos))

### FIXED CODE ###

import bisect
import sys
input = sys.stdin.readline
A, B, Q = list(map(int, input().split()))
s = [int(input()) for i in range(A)]
t = [int(input()) for i in range(B)]
s.append(-100000000000);s.append(100000000000)
t.append(-100000000000);t.append(100000000000)
s = sorted(s, reverse=False)
t = sorted(t, reverse=False)

for i in range(Q):
    xi = int(input())
    sr = s[bisect.bisect_left(s, xi)]
    sl = s[bisect.bisect_left(s, xi) - 1]
    tr = t[bisect.bisect_left(t, xi)]
    tl = t[bisect.bisect_left(t, xi) - 1]

    ans = min(max(sr, tr) - xi, xi - min(sl, tl),
              tr - sl + min(tr - xi, xi - sl), sr - tl + min(sr - xi, xi - tl))
    print(ans)
### BUGGY CODE ###

n,p=map(int,input().split())
a=list(map(int,input().split()))
cnt=0
for i in range(1<<n):
    total=0
    for j in range(n):
        if i&(1<<j):
            total+=a[j]
    if p==0:
        if total%2==0:
            cnt+=1
    elif p==1:
        if total%2==1:
            cnt+=1
print(cnt)

### FIXED CODE ###

n,p=map(int,input().split())
a=list(map(int,input().split()))
if all(elem %2==0 for elem in a):
    if p==0:
        print(2**n)
    else:
        print(0)
else:
    print(2**(n-1))
### BUGGY CODE ###

N = int(input())
data = []
for _ in range(N):
	A = int(input())
	items = []
	for __ in range(A):
		x, y = map(int, input().split())
		items.append((x - 1, y))
	data.append(items)
 
best = 0
 
def check(i):
    for j in range(N):
        if ((i >> j) & 1) == 1:           
            for x, y in data[j]:
                if y !=((i >> x) & 1):return False						
    return True
 
for i in range(1 << 2**N):
    count=0
    for j in range(N):count += ((i >> j) & 1)
    if count>best:
        if check(i):best = count
	
print(best)

### FIXED CODE ###

N = int(input())
data = []
for _ in range(N):
	A = int(input())
	items = []
	for __ in range(A):
		x, y = map(int, input().split())
		items.append((x - 1, y))
	data.append(items)
 
best = 0
 
def check(i):
    for j in range(N):
        if ((i >> j) & 1) == 1:           
            for x, y in data[j]:
                if y !=((i >> x) & 1):return False						
    return True
 
for i in range(2**N):
    count=0
    for j in range(N):count += ((i >> j) & 1)
    if count>best:
        if check(i):best = count
	
print(best)
### BUGGY CODE ###

N = int(input())
S = input()
cnt = 0
for k in range(N):
    for j in range(k):
        for i in range(j):
            if S[k] != S[j] and S[j] != S[i] and S[k] != S[i] and j - i != k - j:
                cnt = cnt + 1
            else:
                cnt = cnt + 0

print(cnt)

### FIXED CODE ###

n = int(input())
s = input()

r_cnt = s.count('R')
g_cnt = s.count('G') 
b_cnt = s.count('B')

ans = r_cnt * g_cnt * b_cnt
cnt = 0

for i in range(n):
    for d in range(n):
        j = i + d
        k = j + d
        if k >= n:
            break
        if s[i] != s[j] and s[j] != s[k] and s[k] != s[i]:
            cnt += 1

ans = ans - cnt
print(ans)
### BUGGY CODE ###

s = input()
q = int(input())
x = 0
for i in range(q):
    query = input().split()
    if query[0] == '1':
        x += 1
    else :
        y = x + int(query[1])
        if y % 2 == 0:
            s = s + query[2]
        else :
            s = query[2] + s
if x % 2 == 0:
    print(s)
else :
    print(s[::-1])

### FIXED CODE ###

from collections import deque
s = deque(input())
q = int(input())
flag = True
for i in range(q):
    x = input()
    if x == '1':
        flag = not flag
    else :
        if x[2] == '1' and flag :
            s.appendleft(x[4])
        elif x[2] == '2' and not flag :
            s.appendleft(x[4])
        else :
            s.append(x[4])
if flag:
    for i in s :
        print(i, end='')
else :
    for i in range(1, len(s)+1):
        print(s[-i], end='')
print('')
### BUGGY CODE ###

S = input()
Q = int(input())
rev = 1

for i in range(Q):
  line = input()
  if line == '1':
    rev *= -1
  else:
    line = line.split()
    F = int(line[1])
    C = line[2]
    if rev * F in [1, -2]:
      S = C + S
    else:
      S = S + C

if rev == -1:
  S = S[::-1]
  
print(S)

### FIXED CODE ###

S = input()
Q = int(input())
rev = 1

head = []
tail = []

for i in range(Q):
  line = input()
  if line == '1':
    rev *= -1
  else:
    line = line.split()
    F = int(line[1])
    C = line[2]
    if rev * F in [1, -2]:
      head.append(C)
    else:
      tail.append(C)

head = head[::-1]
S = ''.join(head + [S] + tail)

if rev == -1:
  S = S[::-1]
  
print(S)
### BUGGY CODE ###

def strChange(res,i,j):
  cnt=res[i:j]
  cnt=list(cnt)
  ret=[]
  for a in reversed(cnt):
    ret.append(a)
  str_ret="".join(ret)
  return str(res[:i]+str_ret+res[j:])

def solve(res):
  ans=set()
  ans.add(res)
  for i in range(len(res)):
    for j in range(i+1,len(res)+1):
      ans.add(strChange(res,i,j))
  a=len(ans)
  return a

A=input()
print(solve(A))


### FIXED CODE ###

A=input()

dict={}

for i in range(len(A)):
  if A[i] in dict:
    dict[A[i]]+=1
  else:
    dict[A[i]]=1

ans=len(A)*(len(A)-1)/2+1

for k,v in dict.items():
  ans-=(v*(v-1)/2)

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

N = int(input())
xyh = [list(map(int, input().split())) for i in range(N)]
from operator import itemgetter
xyh = sorted(xyh, key = itemgetter(2))
for i in range(201):
    H = xyh[0][2] + i
    #print(H)
    for CX in range(101):
        for CY in range(101):
            ans = True
            for x, y, h in xyh:
                if h != max(H - abs(x - CX) - abs(y - CY), 0):
                    ans = False
                    break
            if ans:
                print(CX, CY, H)
                break
        if ans:
            break
    if ans:
        break


### FIXED CODE ###

N = int(input())
xyh = [list(map(int, input().split())) for i in range(N)]
key = False
for CX in range(101):
    for CY in range(101):
        ans = True
        H = -1
        for x, y, h in xyh:
            if h > 0:
                tmp = h + abs(x - CX) + abs(y - CY)
                if H == -1:
                    H = tmp
                else:
                    if H != tmp:
                        H = -2
                        break

        if H == -2:
            continue

        for x, y, h in xyh:
            if h == 0:
                dist = abs(x - CX) + abs(y - CY)
                if H > dist:
                    H = -2
                    break
                
        if H == -2:
            continue
        
        print(CX, CY, H)
        key = True
        break
        
    if key:
        break
### BUGGY CODE ###

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

a=[]

for i in range(1,N+1):
    a.append(A.index(i)+1)
print(" ".join(map(str,a)))

### FIXED CODE ###

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

a=[0]*N

for i in range(N):
    a[A[i]-1]=i+1

print(" ".join(map(str,a)))
### BUGGY CODE ###

H,W,K = map(int,input().split())
r1,c1,r2,c2 = map(lambda x:int(x)-1,input().split())
C = [input() for i in range(H)]

import heapq
dxy = [(0,1),(1,0),(0,-1),(-1,0)]
INF = float('inf')

dists = [[[INF]*4 for _ in range(W)] for _ in range(H)]
dists[r1][c1][0] = 0
hq = [(r1*W+c1)*4]
heapq.heapify(hq)
while hq:
    v = heapq.heappop(hq)
    cp,d = divmod(v,4)
    cy,x = divmod(cp,W)
    c,y = divmod(cy,H)
    if y==r2 and x==c2:
        print(0--c//K)
        exit()
    for di,(dx,dy) in enumerate(dxy):
        nx,ny = x+dx,y+dy
        if not 0 <= nx < W: continue
        if not 0 <= ny < H: continue
        if C[ny][nx] == '@': continue
        if di != d:
            nc = c + (K-c)%K
            if dists[y][x][di] <= nc: continue
            dists[y][x][di] = nc
            heapq.heappush(hq, ((nc*H+y)*W+x)*4+di)
        else:
            if dists[ny][nx][di] <= c+1: continue
            heapq.heappush(hq, (((c+1)*H+ny)*W+nx)*4+di)
print(-1)

### FIXED CODE ###

import sys
input = sys.stdin.readline
H,W,K = map(int,input().split())
r1,c1,r2,c2 = map(lambda x:int(x)-1,input().split())
C = [input() for i in range(H)]

def solve():
    from collections import deque
    dxy = [(0,1),(1,0),(0,-1),(-1,0)]
    INF = float('inf')
    dists = [[INF]*W for _ in range(H)]
    dists[r1][c1] = 0
    q = deque([(r1,c1)])
    while q:
        y,x = q.popleft()
        if y==r2 and x==c2:
            print(dists[y][x])
            exit()
        for dx,dy in dxy:
            for i in range(1,K+1):
                nx,ny = x+dx*i,y+dy*i
                if not 0 <= nx < W: break
                if not 0 <= ny < H: break
                if C[ny][nx] == '@': break
                if dists[ny][nx] <= dists[y][x]: break
                if dists[ny][nx] <= dists[y][x] + 1: continue
                dists[ny][nx] = dists[y][x] + 1
                q.append((ny,nx))
    print(-1)
solve()
### BUGGY CODE ###

class Node:
    def __init__(self, x, y):
        self.id = x
        self.k = y
        self.children = []
        self.type = ''
        self.depth = 20
        self.parent = '-1'

def findRoot(tree):
    for x in tree:
        for y in x.children:
            for a in tree:
                if y == a.id:
                    a.type = 'internal node'
                    a.parent = x.id
    for i,x in enumerate( tree):
        if x.type == 'root':
            return i

def findLeaf(tree):
    for x in tree:
        if x.k == 0 and x.type != 'root':
            x.type = 'leaf'

def setd(tree,node,d):
    node.depth = d
    if len(node.children) == 0:
        return
    else:
        for tmp in node.children:
            for x in tree:
                if x.id == tmp:
                    setd(tree,x,d+1)


if __name__ == '__main__':
    n = (int)(input())
    tree = [None]*n
    for i in range(0,n):
        tmp = input().split()
        a = Node(tmp[0],(int)(tmp[1]))
        a.children=tmp[2:]
        a.type = 'root'
        tree[int(a.id)] = a
    ri = findRoot(tree)
    findLeaf(tree)
    setd(tree,tree[ri],0)
    
    for tmp in tree:
        print("node {}: parent = {}, depth = {}, {}, {}".format(tmp.id, tmp.parent,tmp.depth,tmp.type,list(map(int,tmp.children))))

    

### FIXED CODE ###

class Node:
    def __init__(self, x, y):
        self.id = x
        self.k = y
        self.children = []
        self.type = ''
        self.depth = 20
        self.parent = '-1'

def findRoot(tree):
    for x in tree:
        for y in x.children:
            tree[int(y)].parent = x.id
            if tree[int(y)].k == 0:
                tree[int(y)].type = 'leaf'
            else:
                tree[int(y)].type = 'internal node'
            '''for a in tree:
                if y == a.id:
                    if a.k == 0:
                        a.type = 'leaf'
                    else:
                        a.type = 'internal node'
                    a.parent = x.id
            '''
    for i,x in enumerate( tree):
        if x.type == 'root':
            return i


def setd(tree,node,d):
    node.depth = d
    if node.k == 0:
        return
    else:
        for tmp in node.children:
            setd(tree,tree[int(tmp)],d+1)
            '''for x in tree:
                if x.id == tmp:
                    setd(tree,x,d+1)
            '''


if __name__ == '__main__':
    n = (int)(input())
    tree = [None]*n
    for i in range(0,n):
        tmp = input().split()
        a = Node(tmp[0],(int)(tmp[1]))
        a.children=tmp[2:]
        a.type = 'root'
        tree[int(a.id)] = a
    ri = findRoot(tree)
    setd(tree,tree[ri],0)
    
    for tmp in tree:
        print("node {}: parent = {}, depth = {}, {}, {}".format(tmp.id, tmp.parent,tmp.depth,tmp.type,list(map(int,tmp.children))))
### BUGGY CODE ###

n, m = map(int, input().split())
a1 = []
bn = []

for i in range(m):
  a, b = map(int, input().split())
  if a == 1:
    a1.append(b)
  elif b == n:
    bn.append(a)


for x in a1:
  if x in bn:
    print('POSSIBLE')
    exit()
print('IMPOSSIBLE')

### FIXED CODE ###

n, m = map(int, input().split())
a1 = []
bn = []

for i in range(m):
  a, b = map(int, input().split())
  if a == 1:
    a1.append(b)
  elif b == n:
    bn.append(a)
la = len(a1)
lb = len(bn)
sa = set(a1)
sb = set(bn)
if len(sa | sb) < la + lb:
  print('POSSIBLE')
  exit()
print('IMPOSSIBLE')
### BUGGY CODE ###

import collections
N = int(input())
a = list(map(int, input().split()))
a_c = collections.Counter(a)
Q = int(input())
BC = [list(map(int, input().split())) for _ in range(Q)]

for bc in BC:
  b = bc[0]
  c = bc[1]
  s = 0
  if b in a_c:
    a_c[c]+=a_c.pop(b)
  for k, v in a_c.items():
    s += k*v
  print(s)

### FIXED CODE ###

import collections
N = int(input())
a = list(map(int, input().split()))
a_c = collections.Counter(a)
Q = int(input())
BC = [list(map(int, input().split())) for _ in range(Q)]
s_old = 0
for k, v in a_c.items():
    s_old += k*v
for bc in BC:
  b = bc[0]
  c = bc[1]
  s = s_old
  if b in a_c:
    n = a_c.pop(b)
    a_c[c]+=n
    s-=n*b
    s+=n*c
  print(s)
  s_old = s
### BUGGY CODE ###

ar = list(input())
count = 0
tc = 0
while True:
    i = 0
    while True:
        if ar[i] == "B" and ar[i+1] == "W":
            ar[i],ar[i+1] = ar[i+1],ar[i]
            i += 2
            count += 1
            tc += 1
        else:
            i += 1
        if i >= len(ar)-1:
            break
    if count == 0:
        break
    else:
        count = 0
print(tc)

### FIXED CODE ###

ar = list(input())
wc = ar.count("W")
count = 0
for i in range(len(ar)):
    if ar[i] == "B":
        count += wc
    else:
        wc -= 1
print(count)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = [0] * (n+1)

i = n
while i > 0:
    cnt = ans[i:n+1].count(1)
    if cnt % 2 != a[i-1]:
        ans[i] = 1
    i -= 1
    #print(cnt)
print(ans.count(1))
for i in range(1,n+1):
    if ans[i] == 1:
        print(i)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = [0] * (n+1)

i = n
while i > 0:
    cnt = 0
    for j in range(1, n+1):
        if i * j  > n:
            break
        cnt += ans[i*j]
    if cnt % 2 != a[i-1]:
        ans[i] = 1
    i -= 1
    #print(cnt)
print(ans.count(1))
for i in range(1,n+1):
    if ans[i] == 1:
        print(i)
### BUGGY CODE ###

s = input()
s = s.replace("BC","D")

ans = 0
while "AD" in s:
    ans += s.count("AD")
    s = s.replace("AD","DA")

print(ans)


### FIXED CODE ###

s = input()
s = s.replace("BC","D").replace("B","E").replace("C","E")
s = s.split("E")

def solve(s):
    ans = 0 ; tmp = 0
    for char in s:
        if char == "A": tmp += 1
        else: ans += tmp
    return ans

ans = 0
for ele in s: ans += solve(ele)
print(ans)
### BUGGY CODE ###

S = list(input())

N = len(S)
child = [1] * N 
memo = [child]
loopmemo = []

for count in range(1,10**100):
    tmpChild = child[:]
    for i in range(N):
        if S[i] == "R" and child[i] >= 1:
            tmpChild[i+1] += child[i]
            tmpChild[i] -= child[i]

        elif S[i] == "L" and child[i] >= 1:
            tmpChild[i-1] += child[i]
            tmpChild[i] -= child[i]
    if child == tmpChild:
        ans = [str(n) for n in child]
        ans = " ".join(ans)
        print(ans)
        break
    child = tmpChild
    memo.append(child)
    if len(memo) >= 3:
        if memo[count-2] == memo[count]:
            ansNum = count - 2
            loopmemo.append(memo[count])
            loopmemo.append(memo[count-1])
            ans = [str(n) for n in loopmemo[(10 * 100 - ansNum) % 2]]
            ans = " ".join(ans)
            print(ans)
            break


### FIXED CODE ###

S = list(input())
N = len(S)
child = [1] * N
memo = []

# RLのインデックスを取得する
for i in range(N-1):
    if S[i] == "R" and S[i+1] == "L":
        memo.append(i)
        memo.append(i+1)
memo.append("dummy")
count = 0
for i in range(N):
    if i != memo[count]:
        if S[i] == "R":
            if (memo[count] - i) % 2 == 0:
                child[memo[count]] += 1
                child[i] -= 1
            else:
                child[memo[count+1]] += 1
                child[i] -= 1
        elif S[i] == "L":
            if (i - memo[count-1]) % 2 == 0:
                child[memo[count-1]] += 1
                child[i] -= 1
            else:
                child[memo[count-2]] += 1
                child[i] -= 1
    else:
        count += 1

ans = [str(n) for n in child]
ans = " ".join(ans)
print(ans)
### BUGGY CODE ###

while True:
    n = input()
    if n==0:
        break
    data=[]
    for i in range(n):
        data.append(raw_input())
    solve=0
    for i in range(n):
        if i+solve<n:
            for j in range(n):
                if j+solve<n:
                    while True:
                        flag=0
                        for a in range(solve+1):
                            for b in range(solve+1):
                                if data[i+a][j+b]=="*":
                                    flag=1
                                    break
                            if flag==1:
                                break
                        if flag==0:
                            solve+=1
                            if i+solve>=n or j+solve>=n: 
                                break
                        else:
                            break
                else:
                    break
        else:
            break
    print solve

### FIXED CODE ###

while True:
    n=input()
    if n==0:
        break
    dp=[[0 for i in range(n+1)]for j in range(n+1)]
    for i in range(1,n+1):
        j=0
        line=" "+raw_input()
        for c in line:
            if c == ".":
                dp[i][j]=min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1
            j+=1
    allmax=0
    for i in range(n+1):
        if allmax<max(dp[i]):
            allmax=max(dp[i])
    print allmax
### BUGGY CODE ###

n, k = map(int, input().split())
mod = 10 ** 9 + 7

s = [0 for i in range(k+1)]

ret = 0
for i in range(k,0,-1):
	a = int(k/i)
	c = a ** n
	for j in range(2,k+1):
#		print("aaa",i,j,k)
		if i*j <= k:
			c -= s[i*j]
		else :
			break
	s[i] = c
#	print(i,a,c%mod,(c*i)%mod)
	ret = (ret+(c%mod)*i)%mod
print(ret)

### FIXED CODE ###

n, k = map(int, input().split())
mod = 10 ** 9 + 7

s = [0 for i in range(k+1)]

ret = 0
for i in range(k,0,-1):
	a = int(k/i)
	c = pow(a,n,mod)
	for j in range(2,k+1):
#		print("aaa",i,j,k)
		if i*j <= k:
			c -= s[i*j]
		else :
			break
	s[i] = c%mod
#	print(i,a,c%mod,(c*i)%mod)
	ret = (ret+(c%mod)*i)%mod
print(ret)
### BUGGY CODE ###

N = int(input())
res = 1
for i in range(N):
  res *= i+1
print(res%1000000007)

### FIXED CODE ###

N = int(input())
res = 1
for i in range(N):
  res *= i+1
  res %= 1000000007
print(res)