Harryxun/stf_run huggingface dataset:
from scipy.sparse import coo_matrix
from scipy.sparse.csgraph import bellman_ford, NegativeCycleError
import sys
input = sys.stdin.readline


def main():
    n, m, p = map(int, input().split())

    edges = []
    routes = [[] for _ in range(n)]
    rev_routes = [[] for _ in range(n)]


    def get_reachable_nodes(start, routes):
        seen = {start}
        todo = []
        for to in routes[start]:
            todo.append(to)
            seen.add(to)

        while todo:
            node = todo.pop()
            for to in routes[node]:
                if to in seen:
                    continue
                todo.append(to)
                seen.add(to)
        return seen


    for _ in range(m):
        node1, node2, value = map(int, input().split())
        node1, node2, value = node1 - 1, node2 - 1, value - p
        edges.append([node1, node2, value])
        routes[node1].append(node2)
        rev_routes[node2].append(node1)

    from_start = get_reachable_nodes(0, routes)
    if n-1 not in from_start:
        print(-1)
        return

    to_goal = get_reachable_nodes(n-1, rev_routes)

    from_start_to_goal = from_start & to_goal

    matrix = [[10**6] * n for _ in range(n)]

    for row, col, value in edges:
        if {row, col} <= from_start_to_goal:
            if -value < matrix[row][col]:
                matrix[row][col] = -value

    graph = coo_matrix(matrix)
    try:
        bf = bellman_ford(graph, indices=[0])
        print(max(0, -int(bf[0][n - 1])))
    except NegativeCycleError:
        print(-1)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

n, m, p = map(int, input().split())

edges = []
routes  = [[] for i in range(n)]
rev_routes = [[] for i in range(n)]
from_start = set()
to_goal = set()

def dfs(node, routes, seen):
    if node in seen:
        return
    seen.add(node)
    candidates = routes[node]
    for to in candidates:
        dfs(to, routes, seen)


for _ in range(m):
    node1, node2, value = map(int, input().split())
    node1, node2, value = node1-1, node2-1, value - p
    edges.append([node1, node2, value])
    routes[node1].append(node2)
    rev_routes[node2].append(node1)

dfs(0, routes, from_start)
dfs(n-1, rev_routes, to_goal)

from_start_to_goal = from_start & to_goal

graph = [-float('INF')] * n
graph[0] = 0

for i in range(n):
    is_updated = False
    for node, to, value in edges:
        if node not in from_start_to_goal or to not in from_start_to_goal:
            continue
        current_point = graph[node]
        next_point = graph[node] + value
        if graph[to] < next_point:
            graph[to] = next_point
            is_updated = True
        else:
            continue
    if not is_updated:
        score = max(0, graph[n-1])
        break
else:
    score = -1
      
print(score)
a = input()

print(2* min(a.count('1'),a.count('0') )

### FIXED CODE ###

a = input()

print(2* min(a.count('1'),a.count('0') ))
import sys
sys.setrecursionlimit(100000)
n = int(input())
li = list(map(int,input().split()))
a = li[0]
del li[0]

def f(num1,num2,l):
  if l == []:
    return True
  else:
    if num1^num2 in l:
      l.remove(num1^num2)
      return f(num2,num1^num2,l)
    else:
      return False

for i in li:
  if f(a,i,li[1:]):
    print("Yes")
    exit()
  else:continue
print("No")

### FIXED CODE ###

n=int(input())
*a,=map(int,input().split())
s=list(set(a))
s.sort()
ans="No"
if len(s)==1:
  if 0 in s:
    ans="Yes"
elif len(s)==2:
  if a.count(0)*2==a.count(s[1]):
    ans="Yes"
elif len(s)==3 and a.count(s[0])==a.count(s[1])==a.count(s[2]) and s[0]^s[1]^s[2]==0:
  ans="Yes"
print(ans)
a, b = map(int, input().split())
h, w = map(int, input().split())

print((H-h)*(W-w))

### FIXED CODE ###

import sys
 
 
H,W = sys.stdin.readline().strip().split()
H = int(H)
W = int(W)
 
h,w = sys.stdin.readline().strip().split()
h = int(h)
w = int(w)

ans = (H-h)*(W-w)
ans = int(ans)
print(ans)
from sys import stdin
N = [int(_) for _ in stdin.readline().rstrip().split()]
print(N**3)

### FIXED CODE ###

from sys import stdin
N = int(stdin.readline().rstrip())
print(N**3)
n, len(a)= map(int, input().split())
a= list(map(int, input().split()))
c= n-sum(a)
print(c)

### FIXED CODE ###

n,m= map(int, input().split())
a = list(map(int, input().split()))
c = n-sum(a)
if m == len(a) and c>= 0:
    print(c)
else:
    print(-1)
N, M = map(int, input().split())
ans = {i:0 for i in range(N)}
pn = {i:0 for i in range(N)}
ans_num = 0
pn_num = 0

for i in range(M):
    p_tmp, S_tmp = input().split()
    p_tmp = int(p_tmp)
    
    if ans[p_tmp] == 0 and S_tmp == "AC":
        ans[p_tmp] = 1
        ans_num += 1
        pn_num += pn[p_tmp]
        
    elif ans[p_tmp] != 1 and S_tmp == "WA":
        pn[p_tmp] = pn[p_tmp] + 1
        
print(ans_num, pn_num)

### FIXED CODE ###

N, M = map(int, input().split())
ans = {i:0 for i in range(N+1)}
pn = {i:0 for i in range(N+1)}
ans_num = 0
pn_num = 0

for i in range(M):
    p_tmp, S_tmp = input().split()
    p_tmp = int(p_tmp)
    
    if ans[p_tmp] == 0 and S_tmp == "AC":
        ans[p_tmp] = 1
        ans_num += 1
        pn_num += pn[p_tmp]
        
    elif ans[p_tmp] != 1 and S_tmp == "WA":
        pn[p_tmp] = pn[p_tmp] + 1
        
print(ans_num, pn_num)
import bisect
from collections import deque
N,K=map(int,input().split())
A=sorted(list(map(int,input().split())),reverse=True)
MOD=10**9+7
if N==K:
    ans=1
    for i in A:
        ans=ans*i%MOD
    print(ans)
    exit()
if K%2==1 and A[0]<0:
    ans=1
    for i in range(K):
        ans=ans*A[i]%MOD
    print(ans)
    exit()
if N-A.count(0)<K:
    print(0)
    exit()
A=A[::-1]
x=deque(A[bisect.bisect_right(A,0):][::-1]+[0])
y=deque(A[:bisect.bisect_left(A,0)]+[0])
c=0
t=[]
while c<K:
    if c==K-1:
        t.append(x.popleft())
        c+=1
    elif x[0]*x[1]>=y[0]*y[1]:
        t.append(x.popleft())
        c+=1
    else:
        t.append(y.popleft())
        t.append(y.popleft())
        c+=2
ans=1
for i in t:
    ans*=i
    ans%=MOD
print(ans)



### FIXED CODE ###

N,K=map(int,input().split())
A=sorted(list(map(int,input().split())),reverse=True)
MOD=10**9+7
if N==K:
    ans=1
    for i in A:
        ans=ans*i%MOD
    print(ans)
    exit()
if K==1:
    print(A[0]%MOD)
    exit()
if K%2==1 and A[0]==0:
    print(0)
    exit()
if K%2==1 and A[0]<0:
    ans=1
    for i in range(K):
        ans=ans*A[i]%MOD
    print(ans)
    exit()
if N-A.count(0) <K:
    print(0)
    exit()
if A[-1]>=0:
    ans=1
    for i in range(K):
        ans=ans*A[i]%MOD
    print(ans)
    exit()
l=0
r=N-1
t=[]
c=0
if K%2==1:
    tk=K-1
    flg=True
else:
    tk=K
    flg=False
while c<tk:
    if A[l]*A[l+1]<=A[r]*A[r-1]:
        t.append(A[r])
        t.append(A[r-1])
        r-=2
        c+=2
    else:
        t.append(A[l])
        t.append(A[l+1])
        l+=2
        c+=2
if flg:
    t.append(A[l])
ans=1
for i in t:
    ans=ans*i%MOD
print(ans)
from fraction import gcd
from functools import reduce

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

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

N = int(input())
T = []
for _ in range(N):
    T.append(int(input()))

ans = lcm_list(T)
print(ans)

### FIXED CODE ###

from fractions import gcd
from functools import reduce

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

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

N = int(input())
T = []
for _ in range(N):
    T.append(int(input()))

ans = lcm(*T)
print(ans)
import numpy as np
import itertools
n,m,x=map(int,input().split())
a=[]
b=[0]*m
skill=np.array([b])
ans=[]
money=0
for _ in range(n):
    a.append(list(map(int,input().split())))
for i in range(1,n+1):
    for j in itertools.combinations_with_replacement(range(1,n+1),i):
        for k in range(len(j)):
            money+=a[j[k]-1][0]
            skill+=np.array([a[j[k]-1][1:m+1]])
        if all([i>=x for i in skill[0]]):
            ans.append(money)
        money=0
        skill=np.array([b])
print(min(ans))

### FIXED CODE ###

import numpy as np
import itertools
n,m,x=map(int,input().split())
a=[]
b=[0]*m
skill=np.array([b])
ans=[]
money=0
for _ in range(n):
    a.append(list(map(int,input().split())))
for i in range(1,n+1):
    for j in itertools.combinations(range(1,n+1),i):
        for k in range(len(j)):
            money+=a[j[k]-1][0]
            skill+=np.array([a[j[k]-1][1:m+1]])
        if all([i>=x for i in skill[0]]):
            ans.append(money)
        money=0
        skill=np.array([b])
if len(ans)==0:
    print(-1)
else:
    print(min(ans))
from itertools import permutations
from collections import Counter


n = int(input())
balls = []
cost = n
for _ in range(n):
    x, y = map(int, input().split())
    balls.append((x, y))

counter = Counter()
for b1, b2 in permutations(balls, 2):
    p, q = b1[0] - b2[0], b1[1] - b2[1]
    counter[(p, q)] += 1

(p, q), val = counter.most_common(1)[0]
print(n - val)

### FIXED CODE ###

from itertools import permutations
from collections import Counter


n = int(input())
balls = []

for _ in range(n):
    x, y = map(int, input().split())
    balls.append((x, y))

if n == 1:
    print(1)
else:
    counter = Counter()
    for b1, b2 in permutations(balls, 2):
        p, q = b1[0] - b2[0], b1[1] - b2[1]
        counter[(p, q)] += 1

    (p, q), val = counter.most_common(1)[0]
    print(n - val)
h,w=map(int,input().split())
a=['#'(w+2)]+['#'+input()+'#' for _ in range(h)]+['#'*(w+2)]
for x in a:
  print(x)


### FIXED CODE ###

h,w=map(int,input().split())
a=['#'*(w+2)]+['#'+input()+'#' for _ in range(h)]+['#'*(w+2)]
for x in a:
  print(x)
N = input()
A = input()

if (N-A) % 500 ==0{
  print("Yes")
}
else{
  print("No")
}

### FIXED CODE ###

N = int(input())
A = int(input())
 
if  A >= (N%500):
  print("Yes")
else:
  print("No")
from itertools import accumulate

def main():
    n, k = map(int, input().strip().split())
    A = list(map(int, input().strip().split()))
    
    # for _ in range(min(k,int(math.log(n,2)))):
    
    
    def solve():
        nonlocal A
        for _ in range(k):
            b=[0]*(n+1)
            
            for i in range(n):
                b[max(0,i-A[i])]+=1
                b[min(n,i+A[i]+1)]-=1
            
            # update ans
            # cnt=0
            # for i in range(1,n):
            #     b[i]+=b[i-1]
            a=[*accumulate(b)]
            A=b
            if min(A)==n:
                break
        print(*A[:-1])
    solve()

if '__main__' == __name__:
    main()

### FIXED CODE ###

import sys
from itertools import accumulate
input=sys.stdin.buffer.readline

def main():
    n, k = map(int, input().split())
    A = [*map(int, input().split())]
    
    # for _ in range(min(k,int(math.log(n,2)))):
    
    for _ in "_"*k:
        b=[0]*(n)
        
        for i,v in enumerate(A):
            if i>v:
            # b[max(0,i-v)]+=1
                b[i-v]+=1
            else:
                b[0]+=1
            j=i-~v
            # if i+v+1<n:
            #     b[i+v+1]-=1
            if j<n:
                b[j]-=1
        
        # update ans
        # cnt=0
        # for i in range(1,n):
        #     b[i]+=b[i-1]
        A=[*accumulate(b)]
        
        if min(A)==n:
            break
    print(" ".join(map(str,A)))

if '__main__' == __name__:
    main()
a,b,K=map(int,input().split())
C=998244353
fac=[0]*a #階乗 fac[i]=i!
finv=[0]*a# i!の逆元
inv=[0]*a
N=a-1
def com_init():
	fac[0],fac[1],finv[0],finv[1]=1,1,1,1
	inv[1]=1
	for i in range(2,N+1):
		fac[i]=fac[i-1]*i%C
		inv[i]=C-inv[C%i]*(C//i)%C#ある数の逆元
		finv[i]=finv[i-1]*inv[i]%C
def com(m,k):
	if m<k: return 0
	elif m<0 or k<0:return 0
	else:
		return fac[m]*(finv[k]*finv[m-k]%C)%C
com_init()
bfac=[0]*a
bfac[0]=1
for i in range(1,a):
  bfac[i]=bfac[i-1]*(b-1) %C
ans=0

for i in range(K+1):
  ans+= com(a-1,i)*bfac[a-1-i]%C
print(ans*b%C)

### FIXED CODE ###

a,b,K=map(int,input().split())
C=998244353
fac=[0]*a #階乗 fac[i]=i!
finv=[0]*a# i!の逆元
inv=[0]*a
N=a-1
def com_init():
	fac[0],finv[0]=1,1
	if a<2:return
	fac[1],finv[1]=1,1
	inv[1]=1
	for i in range(2,N+1):
		fac[i]=fac[i-1]*i%C
		inv[i]=C-inv[C%i]*(C//i)%C#ある数の逆元
		finv[i]=finv[i-1]*inv[i]%C
def com(m,k):
	if m<k: return 0
	elif m<0 or k<0:return 0
	else:
		return fac[m]*(finv[k]*finv[m-k]%C)%C
com_init()
bfac=[0]*a
bfac[0]=1
for i in range(1,a):
  bfac[i]=bfac[i-1]*(b-1) %C
ans=0

for i in range(K+1):
  ans+= com(a-1,i)*bfac[a-1-i]%C
print(ans*b%C)
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))

count = 0

for i in range(n):

    if i == 0:
        count += b[a[i]-1]

    else:
        count += b[a[i]-1]

        if a[i] - a[i-1] == 1:
            count += c[a[i-1]-1]

print(count)

### FIXED CODE ###

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

count = 0

for i in range(n):

    if i == 0:
        count += b[a[i]-1]

    else:
        count += b[a[i]-1]

        if a[i] - a[i-1] == 1:
            count += c[a[i-1]-1]

print(count)
t_hp_str,t_atack_str,a_hp_str,a_atack_str= input().split()
t_hp = int(t_hp_str)
t_atack = int(t_atack_str)
a_hp=int(a_hp_str)
a_atack = int(a_atack_str)

while True:
  if num%2 == 0:
    a_hp = a_hp - t_atack
    if a_hp <= 0:
      print("Yes")
      break
  else:
    t_hp = t_hp - a_atack
    if t_hp <= 0:
      print("No")
      break



### FIXED CODE ###

t_hp_str,t_atack_str,a_hp_str,a_atack_str= input().split()
t_hp = int(t_hp_str)
t_atack = int(t_atack_str)
a_hp=int(a_hp_str)
a_atack = int(a_atack_str)

for num in range(300):
  if num%2 == 0:
    a_hp = a_hp - t_atack
    if a_hp <= 0:
      print("Yes")
      break
  else:
    t_hp = t_hp - a_atack
    if t_hp <= 0:
      print("No")
      break
import sys
#import cython

def main():
    read = lambda: sys.stdin.readline().rstrip()
    
    #N: cython.longlong = 0
    n = int(read.input())
    a = list(map(int,read().split()))
    ans = 1
    flag = True
    for num in a:
      ans *= num
      if ans > 10**18:
        flag = False
        break
    print(ans if flag else -1)
 
if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
#import cython
 
def main():
    read = lambda: sys.stdin.readline().rstrip()
    
    #N: cython.longlong = 0
    n = int(read())
    a = list(map(int,read().split()))
    ans = 1
    flag = True
    iszero = any(num == 0 for num in a)
    if iszero: print(0)
    else:
        for num in a:
          ans *= num
          if ans > 10**18:
            flag = False
            break
        print(ans if flag else -1)
 
if __name__ == "__main__":
    main()
S = int(input() S >= 10000)
s = int(input())
a = int(h = (S / 3600), m = ((S % 3600) / 60), for s in range(0, 60):.split )
print(a['h:m:s'])

### FIXED CODE ###

S = int(input())

s = S % 60
m = S // 60 % 60
h = S // 60 // 60

print("{0}:{1}:{2}".format(h,m,s))
n = int(input())
a = list(map(int, input().split()))

a.sort(reverse=True)
print(sun(a[::2])-sun(a[1::2]))

### FIXED CODE ###

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

a.sort(reverse=True)
print(sum(a[::2])-sum(a[1::2]))
a,b = int(input())
if 1 <= a <=100 and 1 <= b <= 100
     print(a*b)


### FIXED CODE ###

a,b =map(int,input().split())
if 1 <= a <=100 and 1 <= b <= 100:
     print(a*b)
K = input()
A, B = [int(a) for a in input().split()]
p = A // K + K
if A < p and B < p:
    print("OK")
else:
    print("NG")

### FIXED CODE ###

K = int(input())
A, B = [int(a) for a in input().split()]
p = (A // K) * K
if (A <= p and p <= B) or (A <= p + K and p + K <= B):
    print("OK")
else:
    print("NG")
def main():
    N = input()

    ab = input( )

    ab = ab.split()
    
    if 0 in ab:
        print(0)


    SUM = 1
    for i in range(int(N)):
        SUM = SUM * int(ab[i])
         if (int(SUM) < 10 ** 18):
        	print(SUM)
        else:
        print(-1)
        
main()

### FIXED CODE ###

def main ():
    N = int(input())
    A = list(map(int,input().split()))
    if 0 in A:
        print (0)
        return
    prod = 1 
    for a in A:
        prod *= a
        if prod > 1000000000000000000:
            print(-1) 
            return
    print(prod)

    
main ()
import numpy as np

n, q = [int(item) for item in input().split()]
s = input()
lr = [[int(item) for item in input().split()] for _ in range(q)]

is_ac = np.zeros(n)
for i in range(n-2):
  if s[i:i+2] == "AC":
    is_ac[i] = True

for item in lr:
  ans = sum(is_ac[item[0]-1: item[1]])
  if s[item[1]-1] == "A":
    if item[1] != n:
      if s[item[1]] == "C":
        ans -= 1
  print(int(ans))

### FIXED CODE ###

n, q = [int(item) for item in input().split()]
s = input()
lr = [[int(item) for item in input().split()] for _ in range(q)]

is_ac = [0] * n
count = 0
for i in range(n-1):
  if s[i] == "A":
    if s[i+1] == "C":
      count += 1
  is_ac[i+1] = count
is_ac[-1] = count
for item in lr:
  ans = is_ac[item[1]-1] - is_ac[item[0]-1]
  print(ans)
number = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
 
print(number[k-1])

### FIXED CODE ###

number = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
 
print(number[int(input())-1])
n = int(input())
a = list(map(int, input().split()))
x = 1
if 0 in a:
    x = 0
for j in a:
    x = j*x
    if x > 10**18:
        x = -1
        break
print(x)

### FIXED CODE ###

A, B = map(int, input().split())
print(A*B)
import math
 
stri = input()
ary = stri.split()
n = int(ary[0])
k = int(ary[1])
 
ans1 = 1 * (n-k +1 )
ansi = 0
ansi = ans1
print(ansi)
for i in range(2,k+1):
    ansi = ansi * (k- i + 1) / ( i - 1 ) *  (n-k - i + 2) / i 
    print(int(ansi % 1000000007))

### FIXED CODE ###

import math
 
stri = input()
ary = stri.split()
n = int(ary[0])
k = int(ary[1])
 
ans1 = 1 * (n-k +1 )
ansi = 0
ansi = int(ans1)
print(ansi)
for i in range(2,k+1):
    ansi = ansi * (k- i + 1) // int( i - 1 ) *  (n-k - i + 2) // int(i) 
    type(ansi)
    print(int(ansi % int(1000000007)))
n,m = map(int, input().split())
xy = [map(int,input().split()) for _ in range(m)]
x,y = [list(i) for i in zip(*xy)]
l = x + y


d = {}#辞書同士の追加はupdate

for i in n:
    d[i] =0
for i in l:
    if i not in d:
        d[i] = 0
    d[i] += 1

for j in range(1,n+1):
    print(d[j])

### FIXED CODE ###


n,m = map(int, input().split())
xy = [map(int,input().split()) for _ in range(m)]
x,y = [list(i) for i in zip(*xy)]
l = x + y


d = {}#辞書同士の追加はupdate

for i in range(1,n+1):
    d[i] =0
for i in l:
    if i not in d:
        d[i] = 0
    d[i] += 1

for j in range(1,n+1):
    print(d[j])
newArray = []
 
x = input()
 
while x != "0":    
    newArray.append(x)
    x = input()
 
for i in range(len(newArray)):
    #print("Case " + str(i + 1) + ": " + newArray[i])
    print("Case %d: %s"%((str(i + 1)),(newArray[i])))

### FIXED CODE ###

x=int(input())
i=1
while x!=0:
    print("Case %d: %s" %(i,x))
    x=int(input())
    i+=1
n = int(input())
x_bin = input()
x = int(x_bin, 2)

pc = x_bin.count('1')
pc_p = pc + 1
pc_m = pc - 1

p = {0: 1}
m = {0: 1}
for i in range(1, n):
    p[i] = p[i-1]*2 % pc_p
    m[i] = m[i-1]*2 % pc_m

rest = {0: 0}
for i in range(1, pc + 1):
    rest[i] = rest[i % bin(i).count('1')] + 1

x_p = x % pc_p
x_m = x % pc_m

for i in range(n, 0, -1):
    if x_bin[n-i] == '1':
        if pc_m != 0:
            a = (x - m[i-1]) % pc_m
            print(rest[a] + 1)
        else:
            print(0)
    else:
        a = (x + p[i-1]) % pc_p
        print(rest[a] + 1)


### FIXED CODE ###

n = int(input())
x_bin = input()
x = int(x_bin, 2)

pc = x_bin.count('1')
pc_p = pc + 1
pc_m = pc - 1

if pc == 1:
    for i, v in enumerate(x_bin):
        if v == '1':
            print(0)
        else:
            if i != n-1:
                if x_bin[-1] == '0':
                    print(1)
                else:
                    print(2)
            else:
                print(2)
    exit()

p = {0: 1}
m = {0: 1}
for i in range(1, n):
    p[i] = p[i-1]*2 % pc_p
    m[i] = m[i-1]*2 % pc_m

rest = {0: 0}
for i in range(1, pc + 1):
    rest[i] = rest[i % bin(i).count('1')] + 1

x_p = x % pc_p
x_m = x % pc_m

for i in range(n, 0, -1):
    if x_bin[n-i] == '1':
        a = (x_m - m[i-1]) % pc_m
        print(rest[a] + 1)
    else:
        a = (x_p + p[i-1]) % pc_p
        print(rest[a] + 1)
from collections import deque
n,k = map(int,input().split())
alist = list(map(int,input().split()))


flag = ['.']*(n+1)
flag[1] = 'v'

been = [1]

for i in range(k):
    goto = alist[been[-1]-1]
    if flag[goto] == '.':
        been.append(goto)
        flag[goto] = 'v'
    else:
        loopstart = goto
        break
loop = been[been.index(loopstart):]
print(loop[(k-loopstart)%len(loop)])



### FIXED CODE ###

n,k = map(int,input().split())
alist = list(map(int,input().split()))
memo = []
p = 1
vis = ['.']*n
while vis[p-1] == '.':
    memo.append(p)
    vis[p-1] = 'v'
    p = alist[p-1]

loop = memo.index(p)
if k < len(memo):
    print(memo[k])
else:
    print(memo[loop+(k-loop)%(len(memo)-loop)])
import fractions as fr
import itertools as it
import collections as col
import heapq as hq
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
"""
python3 main.py < input.txt
"""

"""
N=int(input())
W=list(map(int, input().split()))
ans=10**100
for T in range(1,N):
        S1=sum(W[:T])
        S2=sum(W[T:])
        ans = min(ans, abs(S1-S2))
print(ans)
"""
"""
P,Q,R=map(int, input().split())
print(min([P+Q, P+R, Q+R]))
"""
"""
MOD=1000000007
N,M=map(int, input().split())
A=set()
for i in range(M):
        A.add(int(input()))

dp=dict()
dp[0]=1
dp[1]=0 if 1 in A else 1
for i in range(2, N+1):
        if i in A: dp[i] = 0
        else:
                m1=0 if (i-1) in A else dp[i-1]
                m2=0 if (i-2) in A else dp[i-2]
                dp[i]=(m1+m2) % MOD
print(dp[N])
"""
def genArr2(h,w): return [0]*(h*w)
def setArr2(A,ij,x): A[ij[0]*W + ij[1]] = x
def getArr2(A,ij): return A[ij[0]*W + ij[1]]
H,W=map(int, input().split())
S=genArr2(H,W)
for i in range(H):
        s=input()
        l=list(s)
        for j in range(W):
                setArr2(S,(i,j),l[j])

SWR=genArr2(H,W)
for i in range(H):
        setArr2(SWR, (i, 0), 0 if getArr2(S, (i, 0)) == "#" else 1)
        for j in range(1,W):
                if getArr2(S,( i, j)) == "#": setArr2(SWR, (i, j), 0)
                else: setArr2(SWR, (i, j), getArr2(SWR, (i, j-1)) + 1)
SWL=genArr2(H,W)
for i in range(H):
        setArr2(SWL, (i, W-1), 0 if getArr2(S, (i, W-1)) == "#" else 1)
        for j in range(W-2,-1,-1):
                if getArr2(S,( i, j)) == "#": setArr2(SWL, (i, j), 0)
                else: setArr2(SWL, (i, j), getArr2(SWL, (i, j+1)) + 1)
SHB=genArr2(H,W)
for j in range(W):
        setArr2(SHB, (0, j), 0 if getArr2(S, (0, j)) == "#" else 1)
        for i in range(1,H):
                if getArr2(S,( i, j)) == "#": setArr2(SHB, (i, j), 0)
                else: setArr2(SHB, (i, j), getArr2(SHB, (i-1, j)) + 1)
SHT=genArr2(H,W)
for j in range(W):
        setArr2(SHT, (H-1, j), 0 if getArr2(S, (H-1, j)) == "#" else 1)
        for i in range(H-2, -1, -1):
                if getArr2(S,( i, j)) == "#": setArr2(SHT, (i, j), 0)
                else: setArr2(SHT, (i, j), getArr2(SHT, (i+1, j)) + 1)

ans=0
for n in range(H*W):
        ij=(n//W,n%W)
        x=getArr2(SWR, ij) + getArr2(SWL, ij) + getArr2(SHB, ij) + getArr2(SHT,ij) - 3
        ans=max(ans,x)
print(ans)

### FIXED CODE ###

import fractions as fr
import itertools as it
import collections as col
import heapq as hq
import sys
sys.setrecursionlimit(10**9)

"""
N=int(input())
W=list(map(int, input().split()))
ans=10**100
for T in range(1,N):
        S1=sum(W[:T])
        S2=sum(W[T:])
        ans = min(ans, abs(S1-S2))
print(ans)
"""
"""
P,Q,R=map(int, input().split())
print(min([P+Q, P+R, Q+R]))
"""
MOD=1000000007
N,M=map(int, input().split())
A=set()
for i in range(M):
        A.add(int(input()))

dp=dict()
dp[0]=1
dp[1]=1
def f(i):
        if i in A: return 0
        if i in dp: return dp[i]
        m1=0 if (i-1) in A else f(i-1)
        m2=0 if (i-2) in A else f(i-2)
        dp[i]=(m1+m2) % MOD
        return dp[i]

print(f(N))