Harryxun/stf_run huggingface dataset:
x=int(input())
c=1
for b in range(1,x):
    for p in rangenge(2,x):
        if b**p<=x:c=max(c,b**p)
        else:break
print(c)

### FIXED CODE ###

x=int(input())
c=1
for b in range(1,x):
    for p in range(2,x):
        if b**p<=x:c=max(c,b**p)
        else:break
print(c)
n = int(input())
m = int(input())
print((n-1)*(m-1))

### FIXED CODE ###

n, m = map(int, input().split())
print((n-1)*(m-1))
input_num=(input().split())
input_str=input().split()
anslen=[]
for i in range(input_num[1]):
  divpoint=(input().split())
  k=''.join(input_str[divpoint[0]:divpoint[1]])
  anslen.append(k.count("AC"))
for i in range(input_num[1]):
  print(anslen[i])


### FIXED CODE ###

N,Q=map(int,input().split())
S=input()
t=[0]*(N+1)
for i in range(N):
  t[i+1]=t[i]+(1 if S[i:i+2]=="AC" else 0)
for i in range(Q):
  start,end=map(int,input().split())
  print(t[end-1]-t[start-1])
n = int(input())
li =list(input().split())
a=0
for i in range(n-1):
  if li[i] == li[i+1]:
    a += 1
print(n-a)


### FIXED CODE ###

a,b=map(int,input().split())
if a >= 2*b:
  print(a-2*b)
else:
  print(0)
n,ma,mb=map(int,input().split())
dp=[[10**9 for j in range(400)]for i in range(400)]
dp[0][0]=0 
for i in range(n):
    a,b,c=map(int,input().split())
    for x in range(400):
        for y in range(400):
            if x<a or y<b:
                continue 
            dp[x][y]=min(dp[x][y],dp[x-a][y-b]+c)
mini=10**9 
for i in range(1,41):
    mini=min(mini,dp[ma*i][mb*i])
if mini>=10**9:
    print(-1)
else:
    print(mini)

### FIXED CODE ###

def main():
    n,ma,mb = map(int,input().split())
    dp = [[[float("inf") for _ in range(401)] for _ in range(401)] for _ in range(n+1)]
    dp[0][0][0]=0

    for i in range(1,n+1):
        a,b,c = map(int,input().split())
        for j in range(401):
            for k in range(401):
                if a<=j and b<=k:
                    dp[i][j][k] = min(dp[i-1][j][k],dp[i-1][j-a][k-b]+c)
                else:
                    dp[i][j][k] = dp[i-1][j][k]
    ans = float("inf")
    for i in range(1,401):
        for j in range(1,401):
            if i*mb == j*ma:
                ans = min(ans,dp[n][i][j])
    if ans==float("inf"):
        print(-1)
    else:
        print(ans)
if __name__ == "__main__":
    main()
N, K = input().split()
N = list(N)
N[int(K)] = N[int(K)].lower()
print(str(N))


### FIXED CODE ###

N, K = map(int,input().split())
S = input()
S = list(S)
S[K-1] = S[K-1].lower()
print(''.join(S))
x,k,d = ,ap(int,input().split())
x = abs(x)
if x-k*d>0:
    print(x-k*d)
elif (k-x//d)%2 ==1:
    print(abs(x%d-d))
else:
    print(x%d)

### FIXED CODE ###

x,k,d = map(int,input().split())
x = abs(x)
if x-k*d>0:
    print(x-k*d)
elif (k-x//d)%2 ==1:
    print(abs(x%d-d))
else:
    print(x%d)
H, A = [int(x) for x in input().split()]
print(math.ceil(H/A))

### FIXED CODE ###

import math
H, A = [int(x) for x in input().split()]
print(math.ceil(H/A))
N,K = map(int, input().split())
A = list(map(int, input().split()))

A.sort(reverse=True)

P = []
M = []
Ans = []
p = 0
m = 0

for i in range(N):
    if 0 <= A[i]:
        P.append(A[i])
    else:
        M.append(A[i])

if K % 2 == 1 and len(P) != 0:
    Ans.append(P[p])
    p += 1

while len(Ans) < K:

    #Mのストックがもうない時
    if m+1 >= len(M):
        Ans.append(P[p])
        if p+1 >= len(P):
            break
        Ans.append(P[p + 1])
        p += 2
    elif p+1 >= len(P):
        Ans.append(M[m])
        if m+1 >= len(M):
            break
        Ans.append(M[m + 1])
        m += 2
    else:
        if P[p]*P[p+1] < M[m]*M[m+1]:
            Ans.append(M[m])
            Ans.append(M[m+1])
            m += 2
        else:
            Ans.append(P[p])
            Ans.append(P[p + 1])
            p += 2

answer = 1
for i in range(K):
    answer = (answer * Ans[i]) % 1000000007

print(answer)

### FIXED CODE ###

import sys

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

A.sort(reverse=True)

P = []
M = []
Ans = []
p = 0
m = 0

for i in range(N):
    if 0 <= A[i]:
        P.append(A[i])
    else:
        M.append(A[i])

M.sort()

if K % 2 == 1 and len(P) != 0:
    Ans.append(P[p])
    p += 1
elif K % 2 == 1 and len(P) == 0:
    M.sort(reverse=True)
elif len(M) == 0:
    answer = 1
    for i in range(K):
        answer = (answer * P[i]) % 1000000007

    print(answer)
    sys.exit()

while len(Ans) < K:

    #Mのストックがもうない時
    if m+1 >= len(M) and p < len(P):
        Ans.append(P[p])
        if len(Ans) == K:
            break
        if p + 1 < len(P):
            Ans.append(P[p + 1])
            p += 2
        else:
            p += 1
        
    elif p+1 >= len(P) and m < len(M):
        Ans.append(M[m])
        if len(Ans) == K:
            break
        Ans.append(M[m + 1])
        m += 2
    elif m >= len(M) and p < len(P):
        Ans.append(P[p])
        p += 1
    elif p >= len(P) and m < len(M):
        Ans.append(M[m])
        m += 1
    else:
        if P[p]*P[p+1] < M[m]*M[m+1]:
            Ans.append(M[m])
            Ans.append(M[m+1])
            m += 2
        else:
            Ans.append(P[p])
            Ans.append(P[p + 1])
            p += 2

answer = 1
for i in range(K):
    answer = (answer * Ans[i]) % 1000000007

print(answer)
a,b,x=map(int,input().split())
print("YES" a<=x and x<=a+b else "NO" )

### FIXED CODE ###

a,b,x=map(int,input().split())
print("YES" if a<=x and x<=a+b else "NO" )
m, n, q = map(int, input().split())
aa = [0]*q
bb = [0]*q
cc = [0]*q
dd = [0]*q
for i in range(q):
    aa[i],bb[i],cc[i], dd[i] = list(map(int, input().split()))
    
import itertools
ss = set(itertools.permutations([0]*(n-1)+[1]*(m-1)))
score = 0
for tu in ss:
    tmp = 0
    xx = [1]*n
    j = 0
    for t in tu:
        if t == 0:
            j += 1
        if t == 1:
            xx[j] += 1
    for i in range(q):
        if xx[bb[i]-1] - xx[aa[i]-1] ==cc[i]: 
            tmp += dd[i]
    score = max(score, tmp)
print(score)    

### FIXED CODE ###

import numpy as np
from itertools import combinations_with_replacement
 
n, m, q = map(int, input().split())
 
pt = np.array(list(combinations_with_replacement(range(1,m+1), n)))
score = np.zeros(len(pt))
 
for i in range(q):
    a, b, c, d =map(int, input().split())
    flg = pt[:,b-1] - pt[:,a-1] == c
    score += flg * d
#    print(score)
 
print(int(score.max()))
n = int(input()1
for i in range(26):
    for j in range(15):
        if i * 4 + j * 7 == n:
            cnt +=1
if cnt >0:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

#105 A
import math
N,K= map(int,input().split())
print(abs(math.ceil(N/K)- N//K))
# coding: utf-8
# Your code here!

num = int(input())

qm = 1000000000000001

alf = [chr(i) for i in range(97, 97+26)]
#print(alf)

ans = []
f = False

for i in reversed(range(12)):
    if (num-num//26)//26**i >= 1:
        f = True

    if f:
        ans.append(alf[(num-i)//26**i-1])
        num = num % 26**i
print("".join(ans))


### FIXED CODE ###

# coding: utf-8
# Your code here!

import numpy as np

x,n = map(int,input().split())

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

m = np.array(list(range(-200,400)))
m = (m-x)**2
for i in (np.argsort(m)-200):
    if p.count(i) == 0:
        print(i)
        break
#python3
cnt = 0
s = 1
def main():
    n = int(input())
    a = [int(i) for i in input().split()]

    def solve(ar):
        global cnt
        global s
        idx = 0
        f = False
        for i in range(len(ar)):
            if s == ar[i]:
                idx = i
                cnt += 1
                f = True
                break
        if (not f) or (idx>n):
            return 
        s += 1
        solve(ar[idx+1:])
        return cnt

    p = solve(a)
    print(n-p) if p else print(-1)
main()

### FIXED CODE ###

#python3
def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    k = 1
    for i in range(n):
        if a[i] == k:
            k += 1
    k -= 1
    print(n - k) if k else print(-1)  

main()
a = int(input())
s = int(input())

if a>=3200:
    print(s)
else:
    print('red')

### FIXED CODE ###

a = int(input())
s = input()

if a>=3200:
    print(s)
else:
    print('red')
n,k = (int(i) for i in input().split())
t = [int(input()) for i in range(n)] 
t = [10,15,11,14,12]
t = sorted(t)
min = float('inf')
for i in range(n-k):
    s = t[i+k-1]-t[i]
    if s < min:

print(min)
#print(t)
    

### FIXED CODE ###

#115-C
n,k = (int(i) for i in input().split())
t = [int(input()) for i in range(n)] 
#t = [10,15,11,14,12]
t = sorted(t)
min = t[k-1]-t[0]
for i in range(n-k+1):
    s = t[i+k-1]-t[i]
    if s < min:
        min = s

print(min)
#print(t)
W,H,x,y ==map(int ,raw_input().split())
i = 0
if x*2 = W and y +2 =H:
    i = 1
print float(W*H)/2,i

### FIXED CODE ###

W,H,x,y =map(int ,raw_input().split())
i = 0
if x*2 == W and y*2 ==H:
    i = 1
print float(W*H)/2,i
def dps(u,p,c):
  x[c]= u
  u = k-(1 if p<0 else 2)
  for i in range(len(l[c])):
    if l[c][i]!=p:
      if u>0:
        dps(u,c,l[c][i])
        u-=1
      else:
        break
  return

n,k=map(int,input().split())

l=[[] for i in range(n)]
x=[0]*n

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

dps(k,-1,0)

t=1
for i in range(n):
  t=(t*x[i])%(10**9+7)

print(t)


### FIXED CODE ###

import sys

sys.setrecursionlimit(100000)

def dps(u,p,c):
  x[c]= u
  u = k-(1 if p<0 else 2)
  for i in range(len(l[c])):
    if l[c][i]!=p:
      if u>0:
        dps(u,c,l[c][i])
        u-=1
      else:
        break
  return

n,k=map(int,input().split())

l=[[] for i in range(n)]
x=[0]*n

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

dps(k,-1,0)

t=1
for i in range(n):
  t=(t*x[i])%(10**9+7)

print(t)
n=int(input())
ans=0
for i in range(n):
  l[i],r[i]=map(int,input().split())
  ans+=r[i]-l[i]+1
print(ans)


### FIXED CODE ###

n=int(input())
ans=0
for i in range(n):
  l,r=map(int,input().split())
  ans+=r-l+1
print(ans)
n, m = map(int, input().split())
G = [[] for _ in range(n+1)]
for i in range(m):
    x, y = map(int, input().split())
    G[x].append(y)

memo = [0]*(n+1)
seen = [False]*(n+1)
def dp(v):
    if seen[v]:
        return memo[v]
    ans = 0
    for nv in G[v]:
        ans = max(ans, dp(nv) + 1)

    seen[v] = True
    memo[v] = ans
    return ans

ans = 0
for v in range(1, n+1):
    ans = max(ans, dp(v))
print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

n, m = map(int, input().split())
G = [[] for _ in range(n)]
for i in range(m):
    x, y = map(int, input().split())
    x, y = x-1, y-1
    G[x].append(y)

memo = [-1]*n
def dp(v):
    if memo[v] != -1:
        return memo[v]
    res = 0
    for nv in G[v]:
        res = max(res, dp(nv) + 1)
    
    memo[v] = res
    return res

ans = 0
for v in range(n):
    ans = max(ans, dp(v))
print(ans)
s_vec1 = input()
s_vec2 = input()
def abc_057_2(o,e):
    s_vec3 = []
    for i in range(0,len(o)):
    s_vec3.append(o[i])
    s_vec3.append(e[i])
    if len(o) == len(e):
        pass
    else:
        s_vec3.append(o[i+1])
    return(''.join(s_vec3))    

### FIXED CODE ###

s_vec1 = input()
s_vec2 = input()
def abc_057_2(o,e):
    s_vec3 = []
    for i in range(0,len(e)):
        s_vec3.append(o[i])
        s_vec3.append(e[i])
    if len(o) == len(e):
        pass
    else:
        s_vec3.append(o[i+1])
    return(''.join(s_vec3))
print(abc_057_2(s_vec1,s_vec2))
a, b, c = map(int, input().split().split())
if  b−a == c−b:
  print ("YES")
else:
 print("NO")

### FIXED CODE ###

a,b,c = map(int,input().split())
if b-a == c-b:
    print("YES")
else:
    print("NO")
N,M = map(int,input().split())
dic = {}
for _ in range(N):
    a,b = map(int,input().split())
    if a > M:
        pass
    else:
        if a in dic.keys():
            dic[a].append(b)
        else:
            dic[a] = [b]
#print(dic)
lis = [[]] * M
for p in dic.keys():
    lis[p-1] = dic[p]
#print('lis:',lis)
g = 0
for i in range(M):
    if lis[i] == []:
        pass
    else:
        #print('sublis:',lis[i])
        mx = max(lis[i])
        g += mx
        lis[i].remove(mx)
        if i+1 < M:
            if len(lis[i])>0:
                lis[i+1].extend()
    #print(lis)
print(g)

### FIXED CODE ###

import heapq
n,m= map(int,input().split())
feeindays = [[] for _ in range(m)]
for i in range(n):
    a,b= map(int,input().split())
    if a<=m:feeindays[a-1]+=[b]
q=[]
heapq.heapify(q)
pay=0
for l in feeindays:
    for c in l:heapq.heappush(q,-c)
    if len(q)!=0:pay+=-1 * heapq.heappop(q)
print(pay)
import heapq
from sys import exit
N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = sorted([tuple(map(int, input().split())) for _ in range(M)], key=lambda x: x[1], reverse=True)
heapq.heapify(A)

ans = sum(A)
for b, c in BC:
    for _ in range(b):
        a = heapq.heappop(A)
        if a < c:
            ans += c - a
        else:
            print(ans)
            exit()
print(ans)


### FIXED CODE ###

import heapq
from sys import exit
N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = sorted([tuple(map(int, input().split())) for _ in range(M)], key=lambda x: x[1], reverse=True)
heapq.heapify(A)

ans = sum(A)
for b, c in BC:
    for _ in range(b):
        if len(A) == 0:
            print(ans)
            exit()
        a = heapq.heappop(A)
        if a < c:
            ans += c - a
        else:
            print(ans)
            exit()
print(ans)
N,M=map(int,input().split(' '))

x=[]
y=[]
z=[]
for _ in range(N):
  _x,_y,_z=map(int,input().split(' '))
  x.append(_x)
  y.append(_y)
  z.append(_z)

def argmin(l):
  m=min(l)
  for i in range(len(l)):
    if l[i]==m:
      return i
  return i

def f(sign_x, sign_y, sign_z):
  l=[]
  for i in range(N):
    s=x[i]*sign_x + y[i]*sign_y + z[i]*sign_z
    if len(l)<M:
      l.append(s)
    elif min(l)<s:
      del l[argmin(l)]
      l.append(s)
  return sum(l)


res=0
for x_s in [1,-1]:
  for y_s in [1,-1]:
    for z_s in [1,-1]:
      score = f(x_s, y_s, z_s)
      if score>res:
        res=score

print(res)




### FIXED CODE ###

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

x=[]
y=[]
z=[]
for _ in range(N):
  _x,_y,_z=map(int,input().split(' '))
  x.append(_x)
  y.append(_y)
  z.append(_z)

def argmin(l):
  m=min(l)
  for i in range(len(l)):
    if l[i]==m:
      return i

def f(sign_x, sign_y, sign_z):
  l=[]
  for i in range(N):
    s=x[i]*sign_x + y[i]*sign_y + z[i]*sign_z
    l.append(s)
    if len(l)>M:
      del l[argmin(l)]
  return sum(l)


res=0
for x_s in [1,-1]:
  for y_s in [1,-1]:
    for z_s in [1,-1]:
      score = f(x_s, y_s, z_s)
      if score>res:
        res=score

print(res)
n,k=map(int,input().split())
l=list(map(int,input().split()))
l.sort()
mod=10*9+7
total=0
from math import factorial
for i in range(n-k):
   f=(factorial(n-i-1)/factorial(k)/factorial(n-k-i-1))%mod
   total+=int((l[n-i-1]-l[i])*f)
   total%=mod
print(total)


### FIXED CODE ###

n,k=map(int,input().split())
l=list(map(int,input().split()))
l.sort()
mod=10**9+7
n_max=2*10**5
F,FI=[0]*(n_max+1),[0]*(n_max+1)
F[0],FI[0]=1,1
for i in range(n_max):
  F[i+1]=(F[i]*(i+1))%mod
  FI[i+1]=pow(F[i+1],mod-2,mod)
def comb(x,y):
  return (F[x]*FI[x-y]*FI[y])%mod
total=0
for i in range(n-k+1):
   f=comb(n-i-1,k-1)%mod
   total+=int((l[n-i-1]-l[i])*f)
   total%=mod
print(total)
import math
x,y = map(int,input().split())
sum_xy = x+y

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 8*(10**6)
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

if sum_xy%3!=0:
    print(0)
else:
    ab_sum = sum_xy//3
    a = x-ab_sum
    b = y-ab_sum
    if a<0 or b<0:
        print(0)
    else:
        print(cmb(ab_sum,a,inf))

### FIXED CODE ###

x, y = map(int, input().split())
if (x+y)%3 != 0:
    print(0)
    exit()

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
 
mod = 10**9+7
N = 10**6
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]
 
for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
 
 
a = (2*x-y)//3
b = (2*y-x)//3
n = a+b
r = a
res = cmb(n,r,mod)
print(res)
x = double( input() )
print( x*x*x)


### FIXED CODE ###

x = int( input() )
print( x*x*x)
N = (int)(input())
edges = []
for _ in range(N-1):
    edges.append((list)(map(int, input().split())))

Q, K = (list)(map(int, input().split()))
querys = []
for _ in range(Q):
    querys.append((list)(map(int, input().split())))

'''
 N:num of nodes
 Q: num of query
 K: node must passed in query

'''
dist = [-1]*(N+1)
for e in edges:
    if dist[e[0]] == -1:
        dist[e[0]] = [[e[1], e[2]]]
    else:
        dist[e[0]].append([e[1], e[2]])

    if dist[e[1]] == -1:
        dist[e[1]] = [[e[0], e[2]]]
    else:
        dist[e[1]].append([e[0], e[2]])

dist_from_k = [-1]*(N+1)


def dfs(v, p, cost):
    if dist_from_k[v] != -1:
        return

    dist_from_k[v] = cost
    for e in dist[v]:
        if e[0] == p:
            continue
        dfs(e[0], v, cost+e[1])


dfs(K, -1, 0)

for q in querys:
    print(dist_from_k[q[0]] + dist_from_k[q[1]])


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
N = (int)(input())
edges = []
for _ in range(N-1):
    edges.append((list)(map(int, input().split())))

Q, K = (list)(map(int, input().split()))
querys = []
for _ in range(Q):
    querys.append((list)(map(int, input().split())))

'''
 N:num of nodes
 Q: num of query
 K: node must passed in query

'''
dist = [-1]*(N+1)
for e in edges:
    if dist[e[0]] == -1:
        dist[e[0]] = [[e[1], e[2]]]
    else:
        dist[e[0]].append([e[1], e[2]])

    if dist[e[1]] == -1:
        dist[e[1]] = [[e[0], e[2]]]
    else:
        dist[e[1]].append([e[0], e[2]])

dist_from_k = [-1]*(N+1)


def dfs(v, cost):
    if dist_from_k[v] != -1:
        return

    dist_from_k[v] = cost
    for e in dist[v]:
        dfs(e[0], cost+e[1])


dfs(K, 0)

for q in querys:
    print(dist_from_k[q[0]] + dist_from_k[q[1]])
from math import *
s=int(input())
a=math.ceil(math.sqrt(s))
print(0,0,a,1,a**2-s,a)

### FIXED CODE ###

import math
from collections import Counter

s = int(input())

def primes(n) :
    ps = [2]
    for i in range(3, n+1) :
        for p in ps :
            if i%p == 0 :
                break
        else :
            ps.append(i)
    return ps

def factorint(n) :
    ps = primes(n)
    l = []
    while n != 1 :
        for p in ps :
            if n%p == 0 :
                n //= p
                l.append(p)
                break
    return Counter(l)

a = math.ceil(math.sqrt(s))
print(0, 0, a, 1, a**2-s, a)
N = input()
a = list(map(input(),range(1,N+1)))
i = 0
for x in a:
	if x%2!=0 and a[x]%2!=0:
    	i+==1
     
    print(i)

### FIXED CODE ###

N = int(input())
a = list(map(int,input().split()))
i=0
for x,y in enumerate (a):
    b=x+1
    if b%2!=0 and y%2!=0:
        i+=1
print(i)
N = int(input())
K = 0
for i in range(N)
    s = i % 3
    t = i % 5
    if s !=0 and t != 0:
        K += i
print(K)


### FIXED CODE ###

N = int(input())
K = 0
for i in range(N):
    s = (i+1) % 3
    t = (i +1) % 5
    if s !=0 and t != 0:
        K +=( i+1)
print(K)
y,m,d = input().split("/")
print("2018/"+m"/"+d if y == "2017" else y+"/"+m"/"+d)

### FIXED CODE ###

y,m,d = input().split("/")
print("2018/"+m+"/"+d if y == "2017" else y+"/"+m+"/"+d)
N, M = map(int, input().split())
#リスト内包表記でaに入れる
a = [int(input()) for _ in range(M)]

#MODに1000000007を入れる
MOD = 10**9 + 7
#Zに集合を作成する
Z = set(a)
 
#i段目までにたどりつく方法を順に求める
dp = [0 for _ in range(N + 1)]
#0段目の場合1とする
dp[0] = 1
#1段目の場合は集合の中に1が含まれていないかどうか、含まれていない:1、含まれている:0
dp[1] = int(1 not in Z)
#2段目以降の場合
for i in range(2, N + 1):
  #集合の中にiが含まれていない場合
    if i not in Z:
      #i段目に1段か2段で上ってきた経路数を足して、MODで割る、dp[i]に蓄積する
        dp[i] = (dp[i - 1] + dp[i - 2]) % MOD
#ansに答えを入れる
ans = dp[i]
print(dp[i])

### FIXED CODE ###

n, m = map(int, input().split())
#リスト内包表記でaに入れる
a = [int(input()) for _ in range(m)]

#MODに'1000000007'を入れる
MOD = 10**9 + 7
#zに集合を作成する
z = set(a)
 
#i段目までにたどりつく方法を順に求める
x = [0 for _ in range(n + 1)]
#0段目の場合1とする
x[0] = 1
#1段目の場合は集合の中に1が含まれていないかどうか、含まれていない:1、含まれている:0
x[1] = int(1 not in z)
#2段目以降の場合
for i in range(2, n + 1):
#集合の中にiが含まれていない場合
    if i not in z:
#i段目に1段か2段で上ってきた経路数を足して、MODで割る、dp[i]に蓄積する
        x[i] = (x[i - 1] + x[i - 2]) % MOD
print(x[n])
from numpy import *

N = int(input())
a = zeros(N)
a = list(map(int, input().split()))

count = 0

for i in range(N):
    if count + 1 == a[i]:
        count += 1

ans = N - count

if count == 0:
    ans = -1

print(ans)

### FIXED CODE ###

from numpy import *

N = int(input())
a = zeros(N)
a = list(map(int, input().split()))

count = 0

for i in range(N):
    if count + 1 == a[i]:
        count += 1

ans = N - count

if count == 0:
    ans = -1

print(ans)
H,W=map(int, input().split())
d = [ [ 100000 for _ in range(W+2)] for _ in range(H+2)]
S = []
S.append('#' * (W+2))
for i in range(H):
    S.append('#'+ input() + '#')
S.append('#' * (W+2))
dmax = 0

def SUB(x,y,n):
    d[y][x] = n
    dmax = max(n,dmax)
    if (S[y-1][x] == '.') and (d[y-1][x] > n+1): SUB(x,y-1,n+1)
    if (S[y][x-1] == '.') and (d[y][x-1] > n+1): SUB(x-1,y,n+1)
    if (S[y+1][x] == '.') and (d[y+1][x] > n+1): SUB(x,y+1,n+1)
    if (S[y][x+1] == '.') and (d[y][x+1] > n+1): SUB(x+1,y,n+1)

for y in range(1,H+1):
    for x in range(1,W+1):
        if S[y][x] == '.':
            SUB(x,y,0)
            for iy in range(1,H+1):
                for ix in range(1,W+1):
                    d[iy][ix] = 100000
print(dmax)



### FIXED CODE ###

from collections import deque

def mk_idx(y,x):
    return y*22+x

H,W=map(int, input().split())
DINF = 100000
S = []
S.append('#' * (W+2))
for i in range(H):
    S.append('#'+ input() + '#')
S.append('#' * (W+2))
dmax = 0
G = [ [] for _ in range( mk_idx(22,22) ) ]
for y in range(1,H+1):
    for x in range(1,W+1):
        if (S[y][x] == '.'):
            if (S[y-1][x] == '.'):  G[ mk_idx(y,x) ].append( mk_idx(y-1,x) )
            if (S[y][x-1] == '.'):  G[ mk_idx(y,x) ].append( mk_idx(y,x-1) )
            if (S[y+1][x] == '.'):  G[ mk_idx(y,x) ].append( mk_idx(y+1,x) )
            if (S[y][x+1] == '.'):  G[ mk_idx(y,x) ].append( mk_idx(y,x+1) )

for y in range(1,H+1):
    for x in range(1,W+1):
        if S[y][x] == '.':
            d = [ DINF for _ in range( mk_idx(22,22) ) ]
            d[ mk_idx(y,x) ] = 0
            q = deque( [mk_idx(y,x)] )
            while len(q) != 0:
                v = q.popleft()
                n = d[v];
                dmax = max(dmax, n)
                for nv in G[v]:
                    if d[ nv ] <= n+1 :
                        continue
                    d[ nv ] = n+1
                    q.append(nv)
print(dmax)