Harryxun/stf_run huggingface dataset:
from itertools import combinations
 
N, M, X = list(map(int,input().split()))
A = []
for i in range(N):
  A.append(list(map(int,input().split())))
sum = []
subsets=[]
for i in range(len(A) + 1):
    for c in combinations(A, i):
        subsets.append(list(c))
 
for i in subsets:
  tmp = [0]*(M+1)
  if len(i) == 1:
    sum.append(i[0])
  elif len(i) == 0:
    sum.append([0]*(M+1))
  else:
    for j in i:
      tmp = list(map(lambda a,b: a + b, tmp,j))
    sum.append(tmp)
    
min_price = 999999999999999
 
for i in sum:
  t = 0
  for j in range(len(i)):
    if j==0:
      pass
    elif X > i[j]:
      t = 1
      break
  if t == 0
    min_price = min(min_price, i[0])
 
if min_price == 999999999999999:
  print(-1)
else:
  print(min_price)

### FIXED CODE ###

from itertools import combinations
 
N, M, X = list(map(int,input().split()))
A = []
for i in range(N):
  A.append(list(map(int,input().split())))
sum = []
subsets=[]
for i in range(len(A) + 1):
    for c in combinations(A, i):
        subsets.append(list(c))
 
for i in subsets:
  tmp = [0]*(M+1)
  if len(i) == 1:
    sum.append(i[0])
  elif len(i) == 0:
    sum.append([0]*(M+1))
  else:
    for j in i:
      tmp = list(map(lambda a,b: a + b, tmp,j))
    sum.append(tmp)
    
min_price = 10000000000
 
for i in sum:
  t = 0
  for j in range(len(i)):
    if j==0:
      pass
    elif X > i[j]:
      t = 1
      break
  if t == 0:
    min_price = min(min_price, i[0])
 
if min_price == 10000000000:
  print(-1)
else:
  print(min_price)
S = input()
print('ABC' if S = 'ARC' else 'ARC')

### FIXED CODE ###

S = input()
print('ABC' if S == 'ARC' else 'ARC')
S = str(input())
K = int(input())

#gosencho = 5 * (10**15)
#gosencho = 5000000000000000

'''
for i in S:
        print(i)
        #K -= int(i) ** gosencho
        K -= pow(int(i), gosencho)
        if K <= 0:
                print(i)
                exit(0)
'''
'''
ans = ''
for i in S:
        for j in range(int(i)**gosencho):
                ans += i

print(ans[K])
'''
if len(S) == 1:
        print(S[0])
        exit(0)

i = 0
while S[i] == '1':
        i += 1
print(S[i])


### FIXED CODE ###

S = str(input())
K = int(input())

if len(S) == 1:
        print(S[0])
        exit(0)

i = 0
while S[i] == '1' and i <= len(S)-2:
        if K <= i + 1:
                print(S[i])
                exit(0)
        i += 1
print(S[i])
import copy
def dfs(cur_node, pre_node, Node_num, map, l):
    #全てのノードを見たとき

    if Node_num == N or cur_node <= 0 or cur_node >= N:
        return
    elif l[pre_node][cur_node]==0: #飛んだ先が、Trueの時
        return
    elif map[cur_node]==True:
        return

    map[cur_node]=True

    for i in range(N):
        if i != cur_node:
            dfs(i, cur_node, Node_num+1, map, l)


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

N = S[0]
M = S[1]


map = [False]*N
map[0] = True

lst = []

for i in range(N):
    lst.append([0]*N)

for i in range(N):
    S = input()
    S = list(S.split())
    idx1 = int(S[0])
    idx2 = int(S[1])
    lst[idx1-1][idx2-1] = 1

graph_count = 0
#全探索
for i in range(1, N, 1):
    map_copy = copy.copy(map)
    lst_copy = copy.copy(lst)

    dfs(i, 0, 0, map_copy, lst_copy)
    count = 0
    for i in map_copy:
        if i == True:
            count = count + 1
    if count == N-1:
        graph_count = graph_count + 1

print(graph_count)



### FIXED CODE ###

import itertools
N,M=map(int,input().split())
edges={tuple(sorted(map(int,input().split()))) for i in range(M)}
ans=0
for i in itertools.permutations(range(2,N+1),N-1):
    l=[1]+list(i)
    ans+=sum(1 for edge in zip(l,l[1:]) if tuple(sorted(edge)) in edges)==N-1
print(ans)
from collections import defaultdict
N = int(input())
dct = defaultdict(int)

for i in range(N):
  s = input()
  sorted_s = "".join(sorted(s))
  dct[sorted_s] += 1

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

print(ans)

### FIXED CODE ###

from collections import defaultdict
import heapq
N, M = map(int, input().split())
dct = defaultdict(list)

for i in range(N):
  A, B = map(int, input().split())
  dct[A].append(-B)

h = []
ans = 0
for i in range(1,M+1):
  if dct[i]:
    for item in dct[i]:
      heapq.heappush(h,item)
  if h:
    ans += heapq.heappop(h)

print(-ans)
N = int(input())
A = list(map(int,input().split()))
MOD = 10**9 + 7
def calc(a):
	if 0 in a:
		if a.count(0) != 1:
			return 0
		for i in [x*2 for x in range(1,int(N/2) + 1)]:
			if a.count(i) != 2:
				return 0
	else:
		for i in [x*2 - 1 for x in range(1,int(N/2) + 1)]:
			if a.count(i) != 2:
				return 0
	return 2 ** int(N/2)
if N % 2 is 0:
	if len(filter(lambda n:n%2==0, A)) > 0:
		print(0)
	else:
		print(calc(A) % MOD)
else:
	if len(filter(lambda n:n%2==1, A)) > 0:
		print(0)
	else:
		print(calc(A) % MOD)

### FIXED CODE ###

N = int(raw_input())
A = list(map(int,raw_input().split()))
A.sort()
MOD = 10**9 + 7
def calc(a):
	if N % 2 == 0:
		B = [int(i/2)*2 + 1 for i in range(0,N)]
		if A != B:
			return 0
	else:
		B = [int(i/2)*2 for i in range(1,N+1)]
		if A != B:
			return 0
	return 2 ** int(N/2)

print(calc(A) % MOD)
import math

N = int(input())
An = [int(x) for x in input().split()]
 
L = [0,0]
for i in range(N):
    if i > 1:
        L.append(int(math.factorial(i) / (math.factorial(i-2) * 2)))

Cn = [An.count(i) for i in range(1,N+1)]
s = sum([L[Cn[i]] for i in range(N)])

for k in range(N):
    print(sum(Dn) - (Cn[An[k]-1]-1))

### FIXED CODE ###

import collections as c

# 入力
N = int(input())
An = [int(x) for x in input().split()]
 
# 各数字の個数を求める
Cn = c.Counter(An)
 
# 全部の組み合わせ
s = 0
for v in Cn.values():
    s += int(v*(v-1) / 2)

for i in range(0,N):
    print(s - (Cn[An[i]] - 1))
n = input()
ans = ''
for x in n:
  if x == '1':
    ans += '9'
   else:
    ans += '1'
print(ans)

### FIXED CODE ###

n = input()
ans = ''
for x in n:
  if x == '1':
    ans += '9'
  else:
    ans += '1'
print(ans)
N,K,Q=input().split()
N=int(N)
K=int(K)
Q=int(Q)

a=[]
for q in range(Q):
    a.append(int(input()))

cnt=[0]*N
for q in range(Q):
    cnt[int(a[q])-1]+=1

'print(cnt)

for n in range(N):
    if K - (Q - cnt[n]) > 0:    
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

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

a=[]
for q in range(Q):
    a.append(int(input()))

cnt=[0]*N
for q in range(Q):
    cnt[int(a[q])-1]+=1

for n in range(N):
    if K - (Q - cnt[n]) > 0:    
        print('Yes')
    else:
        print('No')
n, k = map(int, input().split())
a = list(map(int, input().split()))
stand_bit = [set() for i in range(42)]
acc = [0 for i in range(n+1)]
acc[0] = 0
for i in range(1, n+1):
    acc[i] += a[i-1] + acc[i-1]
set_ans = set()
for i in range(n):
    for j in range(i, n):
        set_ans.add(acc[j+1] - acc[i])
        s = "{:b}".format(acc[j+1] - acc[i])
        s = s.zfill(42)
        for num, bit in enumerate(s):
            if bit == "1":
                stand_bit[num].add(acc[j+1] - acc[i])
for i in range(64):
    if len(set_ans & stand_bit[i]) >= k:
        set_ans &= stand_bit[i]
ans_list = list(set_ans)
ans = ans_list[0]
for i in ans_list:
    ans &= i
print(ans)



### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
stand_bit = [set() for i in range(42)]
acc = [0 for i in range(n+1)]
for i in range(1, n+1):
    acc[i] += a[i-1] + acc[i-1]
set_ans = set()
for i in range(n):
    for j in range(i, n):
        tmp = acc[j+1] - acc[i]
        set_ans.add(tmp)
        s = tmp
        index = 41
        while s:
            if s & 1:
                stand_bit[index].add(tmp)
            s = s >> 1
            index -= 1
for i in range(42):
    if len(set_ans & stand_bit[i]) >= k:
        set_ans &= stand_bit[i]
ans_list = list(set_ans)
ans = ans_list[0]
for i in ans_list:
    ans &= i
print(ans)
def prod(array):
    res = 1
    for a, _ in array:
        res *= a
        res %= MOD
    return res

MOD = 10**9 + 7
N, K = map(int, input().split())
if N==K:
    res = 1
    for a in map(int, input().split()):
        res *= a
        res %= MOD
    print(res)
    exit()
A = []
allsgn = 0
for a in map(int, input().split()):
    A.append((abs(a), a < 0))
    allsgn += a<0
A.sort(reverse=True)
sgn = 0
s0 = -1
lastA = -1
for i, p in enumerate(A[:K]):
    a, s = p
    sgn += s
    if s != s0:
        lastA = i-1
    s0 = s
lasts = s0
if allsgn==N:
    if K%2==1:
        print((-prod(A[-K:]))%MOD)
        exit()
    else:
        print(prod(A[:K])%MOD)
        exit()
raise Exception('Error!')
if sgn%2==0:
    print(prod(A[:K])%MOD)
    exit()
if lasts != A[K][1]:
    res = prod(A[:K-1])*A[K][0]
else:
    firstA = None
    for i, p in enumerate(A[K:],start=K):
        a, s = p
        if s != lasts:
            firstA = i
            break
    res1 = prod(A[:K-1])*A[firstA][0] if firstA is not None else -float("inf")
    res2 = prod(A[:lastA])*prod(A[lastA+1:K+1]) if lastA != -1 else -float("inf")
    res = max(res1, res2)
print(res%MOD)
"""
6 4
5 -3 -3 -3 -3 -2

5 3
-1 -2 -3 -4 -5
"""

### FIXED CODE ###

def prod(array):
    res = 1
    for a, _ in array:
        res *= a
        res %= MOD
    return res

MOD = 10**9 + 7
N, K = map(int, input().split())
if N==K:
    res = 1
    for a in map(int, input().split()):
        res *= a
        res %= MOD
    print(res)
    exit()
A = []
allsgn = 0
for a in map(int, input().split()):
    A.append((abs(a), a < 0))
    allsgn += a<0
A.sort(reverse=True)
sgn = 0
s0 = -1
lastA = -1
for i, p in enumerate(A[:K]):
    a, s = p
    sgn += s
    if s != s0:
        lastA = i-1
    s0 = s
lasts = s0
if allsgn==N:
    if K%2==1:
        print((-prod(A[-K:]))%MOD)
        exit()
    else:
        print(prod(A[:K])%MOD)
        exit()
if sgn%2==0:
    print(prod(A[:K])%MOD)
    exit()
if lasts != A[K][1]:
    res = prod(A[:K-1])*A[K][0]
else:
    firstA = None
    for i, p in enumerate(A[K:],start=K):
        a, s = p
        if s != lasts:
            firstA = i
            break
    if lastA == -1 or (firstA is not None and A[K][0]/A[lastA][0] < A[firstA][0]/A[K-1][0]):
        res = prod(A[:K - 1]) * A[firstA][0]
    else:
        res = prod(A[:lastA]) * prod(A[lastA + 1:K + 1])
print(res%MOD)
"""
6 3
5 -3 -3 -3 -3 -2

10 7
-10 -10 -10 -10 10 10 10 10 10 10
"""
n = int(input())

A = []

for i in range(n):
    a = int(input())
    A.append(a)

maxa = max(A)

copy = A[:]

while True:
    if maxa in copy:
        copy.remove(maxa)
    else:
        break

maxa2 = max(copy)

for i in A:
    if i == max:
        print(maxa2)
    else:
        print(maxa)

### FIXED CODE ###

n = int(input())

A = []

for i in range(n):
    a = int(input())
    A.append(a)

maxa = max(A)

copy = A[:]

copy.remove(maxa)

maxa2 = max(copy)

for i in A:
    if i == maxa:
        print(maxa2)
    else:
        print(maxa)
a,b,c,d=[int(input())for i in[0]*4];print(max(a*b,c*d))

### FIXED CODE ###

a,b,c,d=map(int,input().split());print(max(a*b,c*d))
x, op, y = map(string, input().split())
while not (x == 0 and y == 0 and op == "?") :
 if op == "+" :
  print(x + y)
 elif op == "-":
  print(x - y)
 elif op == "*":
  print(x * y)
 elif op == "/":
  print(x / y)

### FIXED CODE ###

x, op, y = input().split()
x = int(x)
y = int(y)
while op != "?" :
 if op == "+" :
  print(x + y)
 elif op == "-":
  print(x - y)
 elif op == "*":
  print(x * y)
 elif op == "/":
  print(x // y)
 x, op, y = input().split()
 x = int(x)
 y = int(y)
# -*- coding: utf-8 -*-
from itertools import accumulate, combinations
from collections import defaultdict

n, m = map(int, input().split())
ary = [int(_) for _ in input().split()]

sum_ary = accumulate(ary, lambda x, y: x + y)
mod_table = defaultdict(int)
for mod in [s % m for s in (ary[0], *sum_ary)]:
    mod_table[mod] += 1

print(sum([len(list(combinations(range(v), 2))) for v in mod_table.values()]))


### FIXED CODE ###

# -*- coding: utf-8 -*-
from itertools import accumulate
from collections import defaultdict

n, m = map(int, input().split())
ary = [int(_) for _ in input().split()]

sum_ary = list(accumulate(ary, lambda x, y: x + y))
mod_ary = [s % m for s in sum_ary]
mod_table = defaultdict(int)
for mod in mod_ary:
    mod_table[mod] += 1
mod_table[0] += 1

print(sum([mod * (mod - 1) // 2 for mod in mod_table.values()]))
n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
sum = 0
for i in range(n):
    if a[i] - b[i] > 0:
        sum += a[i]- b[i]
    else:
        sum += (b[i] - a[i]) / 2
sum_a = 0
sum_b = 0
for i in range(n):
    sum_a += a.pop(0)
    sum_b += b.pop(0)
if sum <= sum_b - sum_a:
    print ('YES')
else:
    print ('NO')

### FIXED CODE ###

x,y=map(int,input().split())
if x%y == 0:
    print(-1)
else:
    print(x)
# coding:utf-8

import sys

input = sys.stdin.readline
INF = float('inf')
MOD = 10 ** 9 + 7


def inpl(): return list(map(int, input().split()))


H, W, D = inpl()

num_coordinate = {}
for i in range(H):
    w = inpl()
    for j in range(W):
        num_coordinate[w[j]] = (i, j)

c_sum = {}
for d in range(1, D + 1):
    c_sum[d] = [0]

for d in range(1, D + 1):
    for n in range(d + D, H * W, D):
        c_sum[d].append(c_sum[d][-1] + abs(num_coordinate[n][0] - num_coordinate[n - D][0])
                        + abs(num_coordinate[n][1] - num_coordinate[n - D][1]))

Q = int(input())
for _ in range(Q):
    l, r = inpl()
    index = (l - 1) % D + 1
    index_l, index_r = (l - 1) // D, (r - 1) // D

    print(c_sum[index][index_r] - c_sum[index][index_l])


### FIXED CODE ###

# coding:utf-8

import sys

input = sys.stdin.readline
INF = float('inf')
MOD = 10 ** 9 + 7


def inpl(): return list(map(int, input().split()))


H, W, D = inpl()

num_coordinate = {}
for i in range(H):
    w = inpl()
    for j in range(W):
        num_coordinate[w[j]] = (i, j)

c_sum = {}
for d in range(1, D + 1):
    c_sum[d] = [0]

for d in range(1, D + 1):
    for n in range(d + D, H * W + 1, D):
        c_sum[d].append(c_sum[d][-1] + abs(num_coordinate[n][0] - num_coordinate[n - D][0])
                        + abs(num_coordinate[n][1] - num_coordinate[n - D][1]))

Q = int(input())
for _ in range(Q):
    l, r = inpl()
    index = (l - 1) % D + 1
    index_l, index_r = (l - 1) // D, (r - 1) // D

    print(c_sum[index][index_r] - c_sum[index][index_l])
import math
def modpow(a,b,MOD):
    if b == 0:
        return 1
    if b%2:
        return a*modpow(a**2%MOD,b//2,MOD)%MOD
    else:
        return modpow(a**2%MOD,b//2,MOD)
def modinv(a,MOD):
    return modpow(a,MOD-2,MOD)
def modcomb(n,r,MOD):
    return math.factorial(n)%MOD*modinv(math.factorial(r),MOD)%MOD*modinv(math.factorial(n-r),MOD)%MOD

MOD=10**9+7
n,k=map(int,input().split())
for i in range(1,k+1):
    print((modcomb(n-k+1,i,MOD)*modcomb(k-1,k-i,MOD))%MOD)

### FIXED CODE ###

import math
def modpow(a,b,MOD):
    if b == 0:
        return 1
    if b%2:
        return a*modpow(a**2%MOD,b//2,MOD)%MOD
    else:
        return modpow(a**2%MOD,b//2,MOD)
def modinv(a,MOD):
    return modpow(a,MOD-2,MOD)
def modcomb(n,r,MOD):
    return math.factorial(n)%MOD*modinv(math.factorial(r),MOD)%MOD*modinv(math.factorial(n-r),MOD)%MOD

MOD=10**9+7
n,k=map(int,input().split())
for i in range(1,k+1):
    if n-k+1<i:print(0)
    else:print((modcomb(n-k+1,i,MOD)*modcomb(k-1,k-i,MOD))%MOD)
n,k= list(map(int, input().split()))
j = list(map(int, input().split()))
s=0
sumlist=[0]*n
anslist=[0]*(n-k+1)
for i in range(n):
    s+=j[i]
    sumlist[i]=s
for i in range(len(anslist)):
    z=sumlist[i+k]-sumlist[i]
    anslist[i]=z
ans=max(anslist)
ans+=k
ans=ans/2
print(ans)
    

### FIXED CODE ###

n,k= list(map(int, input().split()))
j = list(map(int, input().split()))
s=0
sumlist=[0]*(n+1)
anslist=[0]*(n-k+1)
for i in range(n):
    s+=j[i]
    sumlist[i+1]=s
for i in range(len(anslist)):
     z=sumlist[i+k]-sumlist[i]
     anslist[i]=z
ans=max(anslist)
ans+=k
ans=ans/2
print(ans)
k = int(input())
s = input()

if s <= k :
print(s)

else s >= k :
print(s[:k]+'...')

### FIXED CODE ###

k = int(input())
s = input()
n = len(s)
     
if n <= k:
	print(s)
else:
	print(s[:k] + '...')
# atcoder abc112 A




age = int(input())
A = int(input())
B = int(input())


if age == 2:
	print(A+B)
else:
	print("Hello World")

### FIXED CODE ###

# atcoder abc112 A

try:
	age = int(input())
	A = int(input())
	B = int(input())

except:
	pass

if age == 2:
	print(A+B)
else:
	print("Hello World")
h,w = map(int,input().split())
s = []
for i in range(h):
    s.append(list(input()))

dx = [-1,0,1,-1,1,-1,0,1]
dy = [1,1,1,0,0,-1,-1,-1]

for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            continue
        cnt = 0
        for t in range(8):
            ni=i+dx[t]
            nj=j+dy[t]
            if ni<0 or h<=ni: continue
            if nj<0 or h<=nj: continue
            if s[ni][nj] == '#':
                cnt += 1
        
        s[i][j] = str(cnt)

for i in s:
    print(''.join(i))

### FIXED CODE ###

h,w = map(int,input().split())
s = []
for i in range(h):
    s.append(list(input()))

dx = [-1,0,1,-1,1,-1,0,1]
dy = [1,1,1,0,0,-1,-1,-1]

for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            continue
        cnt = 0
        for t in range(8):
            ni=i+dx[t]
            nj=j+dy[t]
            if ni<0 or h<=ni: continue
            if nj<0 or w<=nj: continue
            if s[ni][nj] == '#':
                cnt += 1
        
        s[i][j] = str(cnt)

for i in s:
    print(''.join(i))
import math
N=int(input())
print(2*N//gcd(2,N))

### FIXED CODE ###

import math
N=int(input())
print(2*N//math.gcd(2,N))
import numpy as np
from scipy.sparse.csgraph import connected_components

n,m = map(int, input().split())
matrix = np.zeros((n,n))
for i in range(m):
  a,b = map(int, input().split())
  matrix[a-1][b-1] += 1

x, labels = connected_components(matrix)
group_count = [0 for i in range(x)]
for i in labels:
  group_count[i] += 1
print(max(group_count))

### FIXED CODE ###

def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]

def unite(x,y):
    x = find(x)
    y = find(y)
        
    if x == y:
        return False
    else:
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True

n,m = map(int,input().split())
par = [-1]*n
line = [0 for i in range(n)]
ans = 0
for i in range(m):
  a,b = map(int, input().split())
  unite(a-1,b-1)
for i in range(n):
  line[find(i)] += 1
  if line[find(i)] > ans:
    ans = line[find(i)]
print(ans)
N=int(input())
A=int(input())
if((N%500<=A):
  print("Yes")
else:
  print("No")
  

### FIXED CODE ###

N=int(input())
A=int(input())
if(N%500<=A):
  print("Yes")
else:
  print("No")
# -*- coding: utf-8 -*-

# AtCoder Beginner Contest
# Problem B

if __name__ == '__main__':
    n, length = list(map(int, input().split()))
    s = sorted([input() for _ in range(length)])

    print(''.join(s))


### FIXED CODE ###

# -*- coding: utf-8 -*-

# AtCoder Beginner Contest
# Problem B

if __name__ == '__main__':
    n, length = list(map(int, input().split()))
    s = sorted([input() for _ in range(n)])

    print(''.join(s))
a,b,c=map(int,input().split())
ans
ans=a-(b+c)
if ans<0:
  ans=0
print(ans)

### FIXED CODE ###

a,b,c=map(int,input().split())
ans=b+c-a
if ans<0:
  ans=0
print(ans)
a, b, k = map(int, input().split())
a, b = max(a,b), min(a,b)
c = []
for i in range(1, b+1):
    if (a % i == 0) & (b % i == 0):
        c.append(i)
print(c[k])

### FIXED CODE ###

a, b, k = map(int, input().split())
a, b = max(a,b), min(a,b)
c = []
for i in range(1, b+1):
    if (a % i == 0) & (b % i == 0):
        c.append(i)
print(c[-k])
from collections import Counter
n = int(input())
res = list(map(int,input().split()))
res2 = res.copy()
a = Counter(res)
b = set()
for i in range(len(res)):
    if res[i] not in b:
        b.add(res[i])
        a[res[i]] -= 1
        sums = 0
        for j in a.values():
            sums += j * (j - 1) // 2
        a[res[i]] += 1
        res2 = [sums if x == res[i] else x for x in res2]
for k in res2:
    print(k)

### FIXED CODE ###

from collections import Counter
n = int(input())
res = list(map(int,input().split()))
a = Counter(res)

sums = 0

for i in a.values():
    sums +=  i * (i - 1) // 2

for j in res:
    print(sums - a[j] * (a[j] -1) //2 + (a[j]-1) * (a[j] -2 ) // 2)
n = input()
ints = list(map(int, input().split()))
ints = sorted(ints)
a = (ints[1] + ints[0])/2
for i in range(2, len(ints)):
    a = (a + int[i]) / 2
    
print(a)



### FIXED CODE ###

n = input()
ints = list(map(int, input().split()))
ints = sorted(ints)
a = (ints[1] + ints[0])/2
for i in range(2, len(ints)):
    a = (a + ints[i]) / 2
    
print(a)
l_si = input().split(" ")
l_si_i = [int(s) for s in l_si]

sm = sum(l_si_i)
av = round(sm /dv)
ret = 0

for it in l_si_i:
  ret = ret + (it -av) **2


print(ret)

### FIXED CODE ###


dv = int(input())
l_si = input().split(" ")
l_si_i = [int(s) for s in l_si]

sm = sum(l_si_i)
av = round(sm /dv)
ret = 0

for it in l_si_i:
  ret = ret + (it -av) **2


print(ret)
n=int(input())
X=[]
Y=[]
A=[]
for i in range(n):
  A=int(input())
  a=A[i]
  x=[]
  y=[]
  for j in range(a):
    x,y=[int(s) for s in input().split()]
  X.append(x)
  Y.append(y)
  
c=0
#for i in range(n):
 # l=[1]*n
  #for j in range(i, n-i):
   # if l[j]==0:continue
    #for k in range(A[j]):
   # 　　l[X[j][k]] *= Y[j][k]
#if c<l.count(1):
 # c=l.count(1) 
  
        
  
print(c)  
   

### FIXED CODE ###

n=int(input())
X=[]
Y=[]
A=[0]*n
for i in range(n):
  A[i]=int(input())
  a=A[i]
  x=[0]*a
  y=[0]*a
  for j in range(a):
    x[j],y[j]=[int(s) for s in input().split()]
  X.append(x)
  Y.append(y)
  
s=0
for i in range(2**n):
  c=0
  d=0
  B=[0]*n
  for j in range(n):
    if((i >> j) & 1):
      c=c+1
      B[j]=1
  for k in range(n):
    if B[k]==1:
      for j in range(A[k]):
        if Y[k][j]!=B[X[k][j]-1]:
          d=-1
          break
    if d<0:
      break
  if s<c and d==0:
    s=c
      
      
print(s)
"""
問題文
    N段の階段があります。高橋君は現在、上り口(0段目)にいます。 高橋君は一歩で1段か2段上ることができます。
    ただし、a1,a2,a3,....aM段目の床は壊れており、その段に足を踏み入れることは危険です。
    壊れている床を踏まないようにしながら、最上段(N段目)にたどりつくまでの移動方法は何通りあるでしょうか？ 
    総数を1,000,000,007で割った余りを求めてください。

制約
    1≦N≦10^5
    0≦M≦N−1
    1≦a1<a2< ... <aM≦N−1
"""
#入力の受け取り
N, M = map(int, input().split())
hoal = [int(input()) for i in range(M)]

#listの初期化
dp = list()
dp = [0]*N
dp[0] = 1
dp[1] = 2
if 1 in hoal:
    dp[0] = 0
    dp[1] = 1
dp_check = list()
dp_check = [0]*N

for i in range(M):
    dp_check[hoal[i]-1]=1

for i in range(N):
    if dp_check[i]==1 and dp_check[i+1]==1:
        print("0")
        exit()

#実際に求める
#dp[i]<-i段までの移動方法の和
for i in range(N):
    if i>1 and dp_check[i]==0:
        dp[i]=dp[i-1]+dp[i-2]

    dp[i]=dp[i]%1000000007

print(dp[N-1])
    

### FIXED CODE ###

"""
問題文
    N段の階段があります。高橋君は現在、上り口(0段目)にいます。 高橋君は一歩で1段か2段上ることができます。
    ただし、a1,a2,a3,....aM段目の床は壊れており、その段に足を踏み入れることは危険です。
    壊れている床を踏まないようにしながら、最上段(N段目)にたどりつくまでの移動方法は何通りあるでしょうか？ 
    総数を1,000,000,007で割った余りを求めてください。

制約
    1≦N≦10^5
    0≦M≦N−1
    1≦a1<a2< ... <aM≦N−1
"""
#入力の受け取り
N, M = map(int, input().split())
hoal = [int(input()) for i in range(M)]

#listの初期化
dp = list()
dp = [0]*N

    
dp_check = list()
dp_check = [0]*N

for i in range(M):
    dp_check[hoal[i]-1]=1
    if dp_check[hoal[i]-1]==1 and dp_check[hoal[i]-2]==1:
        print("0")
        exit()

if N==1:
    if M==1:
        dp[0]=0
    else:
        dp[0]=1
    print(dp[N-1])
else:
    if dp_check[0]==1:
        dp[0]=0
        dp[1]=1
    elif dp_check[1]==1:
        dp[0]=1
        dp[1]=0
    else:
        dp[0] = 1
        dp[1] = 2
    #実際に求める
    #dp[i]<-i段までの移動方法の和
    for i in range(N):
        if i>1 and dp_check[i]==0:
            dp[i]=dp[i-1]+dp[i-2]

        dp[i]=dp[i]%1000000007

    print(dp[N-1])