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

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

def get_gcd(a, b, c):
    min_ab = min(a, b)
    max_ab = max(a, b)
    amari = max_ab % min_ab
    if amari == 0:
        gcd1 = min_ab
    else:
        x = min_ab
        y = amari
        while y != 0:
            amari = x % y
            if amari == 0:
                gcd1 = y
                break
            x = y
            y = amari
    min_2 = min(c, gcd1)
    max_2 = max(c, gcd1)
    amari = max_2 % min_2
    if amari == 0:
        gcd2 = min_2
    else:
        x = min_2
        y = amari
        while y != 0:
            amari = x % y
            if amari == 0:
                gcd2 = y
                break
            x = y
            y = amari

    return gcd2




    return gcd


k = int(input())
ans = 0

for i in range(1, k+1):
    for j in range(1, k+1):
        for l in range(1, k+1):
            ans += get_gcd(i, j, l)

print(ans)

### FIXED CODE ###

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

def get_gcd(a, b, c):
    min_ab = min(a, b)
    max_ab = max(a, b)
    amari = max_ab % min_ab
    if amari == 0:
        gcd1 = min_ab
    else:
        x = min_ab
        y = amari
        while y != 0:
            amari = x % y
            if amari == 0:
                gcd1 = y
                break
            x = y
            y = amari
    min_2 = min(c, gcd1)
    max_2 = max(c, gcd1)
    amari = max_2 % min_2
    if amari == 0:
        gcd2 = min_2
    else:
        x = min_2
        y = amari
        while y != 0:
            amari = x % y
            if amari == 0:
                gcd2 = y
                break
            x = y
            y = amari

    return gcd2


k = int(input())
ans = 0

for a in range(1, k+1):
    for b in range(a+1, k+1):
        if b == a:
            continue
        for c in range(b+1, k+1):
            if c == a or c == b:
                continue
            ans += get_gcd(a, b, c) * 6

for a in range(1, k+1):
    b = a
    for c in range(1, k+1):
        if c == a:
            continue
        ans += get_gcd(a, b, c) * 3

for a in range(1, k+1):
    b = a
    c = a
    ans += get_gcd(a, b, c)

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

from collections import Counter as coun
from itertools import combinations as comb

import sys
input = sys.stdin.readline

N = int(input())
S = input()

C = coun(S)
r, g = C["R"], C["G"]
b = N - r - g
ans = r * g * b

for i, j in comb(range(N), 2):
  k = 2 * j - i
  if 0 <= k < N:
    a, b, c = S[i], S[j], S[k]
    if a == b or b == c or c == a: continue
    ans -= 1
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
S = input()

ans = S.count("R") * S.count("G") * S.count("B")
for i in range(N-2):
  for j in range(i+1, N-1):
    k = 2 * j - i
    if k < N:
      A, B, C = S[i], S[j], S[k]
      if A != B and B != C and C != A: ans -= 1

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

def main():
    N, K = map(int, input().split())
    h = list(map(int, input().split()))

    dp = [0] * N
    for i in range(1, N):
        dp[i] = dp[i-1] + abs(h[i] - h[i-1])
        for j in range(2, K+1):
            if i-j < 0:
                break
            else:
                dp[i] = min(dp[i], dp[i-j] + abs(h[i] - h[i-j]))

    print(dp[-1])
    return


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    h = list(map(int, input().split()))

    dp = [0] * n
    for i in range(1, n):
        j = max(0, i-k)
        dp[i] = min(x + abs(h[i] - y) for x, y in zip(dp[j:i], h[j:i]))

    print(dp[-1])
    return


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

class BIT:
  def __init__(self, n):
    self.n = n
    self.data = [0]*(n+1)
  def sum(self, i):
    s = 0
    while i > 0:
      s += self.data[i]
      i -= i & -i
    return s
  def add(self, i, x):
    while i <= self.n:
      self.data[i] += x
      i += i & -i

N, Q = map(int, input().split())
Cs = [0] + list(map(int, input().split()))

Qs = [None]*Q
for i in range(Q):
  l,r = map(int, input().split())
  Qs[i] = [i,l,r]
  
Qs.sort(key=lambda x:x[2])

ans = [-1]*Q
dic = {}
b = 1
bt = BIT(N)

for i,l,r in Qs:
  st = set()
  for j in range(b,r+1):
    if not Cs[j] in st and Cs[j] in dic:
      bt.add(dic[Cs[j]],-1)
    st.add(Cs[j])
    dic[Cs[j]] = j
  for s in st:
    bt.add(dic[s], 1)
  b = r + 1
  ans[i] = bt.sum(r) - bt.sum(l-1)
    
for a in ans:
  print(a)

### FIXED CODE ###

from sys import stdin
input = stdin.readline
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
 
n, q = map(int, input().split())
tmp = list(map(int, input().split()))
color = [-1]
for v in tmp:
    color.append(v)
qry = [None]*q
ans = [0]*q
p = 0
for _ in ans:
    l, r = map(int, input().split())
    qry[p] = [l-1, r, p]
    p += 1
qry.sort(key=lambda x: x[1])
dic = {}
last_update_idx = 1
bit = Bit(n)
for l, r, i in qry:
    if last_update_idx < r+1:
        st = set()
        for j in range(last_update_idx, r+1):
            if not color[j] in st and color[j] in dic:
                bit.add(dic[color[j]], -1)
            dic[color[j]] = j
            st.add(color[j])
        for v in st:
            bit.add(dic[v], 1)
        last_update_idx = r+1
    ans[i] = bit.sum(r) - bit.sum(l)
for v in ans:
    print(v)
### BUGGY CODE ###

N,M = map(int,input().split())
B = []
C = []
A = list(map(int,input().split()))
for j in range(1,M+1):
  B_val,C_val = map(int,input().split())
  B.append(B_val)
  C.append(C_val)
A.sort()
for k in range(0,M):
  for l in range(0,B[k]):
    if A[0] <= C[k]:
      A[0] = C[k]
      A.sort()
    else:
      continue
print(sum(A))

### FIXED CODE ###

n,m = map(int,input().split())
a = sorted(list(map(int,input().split())))
bc = sorted([list(map(int,input().split())) for _ in range(m)],key = lambda x:-x[1])
flag = 0
flag_2 = 0
#print(a,bc)
for i in range(n):
  if a[i] < bc[flag_2][1]:
    a[i] = bc[flag_2][1]
  else:
    break
  flag += 1
  if flag == bc[flag_2][0]:
    flag_2 += 1
    flag = 0
  if flag_2 == m:
    break
print(sum(a))
### BUGGY CODE ###

import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()
 
n,m = na()
a = na()
for i in range(m):
    b,c = na()
    for j in range(b):
        a.append(c)

aa = sorted(a)
ans=0
for i in range(len(aa)-n,len(aa)):
    ans += aa[i]

#print(sum(aa[len(aa)-n:]))
print(ans)

### FIXED CODE ###

import sys
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n,m = na()
a = na()

bc = [na() for i in range(m)]
bc.sort(key=lambda x:x[1])

for b,c in bc[::-1]:
  a.extend([c]*b)
  if len(a)>2*n:
    break

a.sort(reverse=True)
print(sum(a[:n]))
### BUGGY CODE ###

n, m = map(int, input().split())
des = []
first = []
second = []
a = 1
for i in range(0, m):
	b = (list(map(int, input().split())))
	if b[0] == 1:
		first.append(b[1])
	if b[1] == n:
		second.append(b[0])

for i in first:
	if i in second:
		print('POSSIBLE')
		a = 0
		break

if a:
	print('IMPOSSIBLE')





### FIXED CODE ###

n, m = map(int, input().split())
des= [0]*(n+1)
a = 1
for i in range(0, m):
	b = (list(map(int, input().split())))
	if b[0] == 1:
		des[b[1]] += 1
		if des[b[1]] == 2:
			print('POSSIBLE')
			a = 0
			break
	if b[1] == n:
		des[b[0]] += 1
		if des[b[0]] == 2:
			print('POSSIBLE')
			a = 0
			break
		
if a:
	print('IMPOSSIBLE')
### BUGGY CODE ###

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

for i in range(N):
    print(max(A[:i] + A[i+1:]))

### FIXED CODE ###

N = int(input())
A = []
for _ in range(N):
    A.append(int(input()))
list = A
list = sorted(list)
max = list[-1]
second_max = list[-2]
cnt = A.count(max)
for i in range(N):
    if A[i] == max and  cnt == 1:
        print(second_max)
    else:
        print(max)
### BUGGY CODE ###

def gcd(m, n):
    a, b = m, n
    r = a % b
    while r != 0:
        a, b = b, r
        r = a % b
    return b

def divisors(x):
    D = []
    for i in range(1, int(x**0.5) + 1):
        if x % i == 0:
            D.append(i)
            if i != x**0.5:
                D.append(x // i)
    D.sort()
    return D


a, b = map(int, input().split())

CD = divisors(gcd(a, b))

ans = 1
for cd in CD:
    if len(divisors(cd)) == 2:
        ans += 1

print(ans)


### FIXED CODE ###

def gcd(x, y):
    a, b = x, y
    r = a % b
    while r != 0:
        a, b = b, r
        r = a % b
    return b

def divisors(x):
    D = []
    for i in range(1, int(x**0.5) + 1):
        if x % i == 0:
            D.append(i)
            if i != x**0.5:
                D.append(x // i)
    D.sort()
    return D

def isprime(x):
    t = 1
    for i in range(2, int(x**0.5) + 1):
        if x % i == 0:
            t = 0
            break
    if t == 1 and x != 1:
        return True
    else:
        return False


a, b = map(int, input().split())

CD = divisors(gcd(a, b))

ans = 1
for cd in CD:
    if isprime(cd):
        ans += 1

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

#!python3

# input
s = input()
t = input()


def main():
    sn, tn = len(s), len(t)
    dp = [[(0, "")] * (tn + 1) for _ in range(sn + 1)]
    for i in range(1, sn + 1):
        for j in range(1, tn + 1):
            if s[i - 1] == t[j - 1]:
                dp[i][j] = (dp[i - 1][j - 1][0] + 1, s[i - 1])
            else:
                dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
    ans = []
    i, j = sn, tn
    while i != 0 and j != 0:
        if s[i - 1] == t[j - 1]:
            ans.append(dp[i][j][1])
            i, j = i - 1, j - 1
        else:
            if dp[i][j - 1][0] < dp[i - 1][j][0]:
                i -= 1
            else:
                j -= 1
    print("".join(ans[::-1]))


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!python3

# input
s = input()
t = input()


def main():
    sn, tn = len(s), len(t)
    dp = [[0] * (tn + 1) for _ in range(sn + 1)]
    w = [[None] * (tn + 1) for _ in range(sn + 1)]
    for i in range(1, sn + 1):
        for j in range(1, tn + 1):
            if s[i - 1] == t[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
                w[i][j] = s[i - 1]
            else:
                dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
    ans = []
    i, j = sn, tn
    while i != 0 and j != 0:
        if s[i - 1] == t[j - 1]:
            ans.append(w[i][j])
            i, j = i - 1, j - 1
        else:
            if dp[i][j - 1] < dp[i - 1][j]:
                i -= 1
            else:
                j -= 1
    print("".join(ans[::-1]))


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

import sys
input = lambda: sys.stdin.readline().strip()
s=str(input())
q=int(input())
for i in range(q):
    j=input()
    if j[0]=="1":
        s=s[::-1]
    else:
        if j[2]=="1":
            s=j[4]+s
        else:
            s+=j[4]
print(s)
        

### FIXED CODE ###

import sys
input = lambda: sys.stdin.readline().strip()
from collections import deque
s=deque(str(input()))
q=int(input())
flag=0
for i in range(q):
    j=input()
    if j[0]=="1":
        flag+=1
    else:
        if flag%2==1:
            if j[2]=="1":
                s.append(j[4])
            else:
                s.appendleft(j[4])
        else:
            if j[2]=="1":
                s.appendleft(j[4])
            else:
                s.append(j[4])
s=''.join(s)
if flag%2==1:
    s=s[::-1]
print(s)
### BUGGY CODE ###

from collections import deque
h,w,k=map(int,input().split())
sy,sx,gy,gx=map(int,input().split())
maze=[list(input()) for _ in range(h)]

sy-=1
sx-=1
gy-=1
gx-=1

maze[sy][sx]="S"

dis=[[-1]*w for _ in range(h)]

dis[sy][sx]=0

d = deque([(sx,sy)])
while len(d)>0:
    (x,y)=d.popleft()
    if x==gx and y==gy:
        print(dis[gy][gx])
        exit()

    for (mx,my) in ((0,1),(1,0),(-1,0),(0,-1)):
        #print(mx,my,d)
        for j in range(1,k+1):
            nx=x+mx*j
            ny=y+my*j
            #print(y,x,">>",ny,nx)
            if 0<=nx<w and 0<=ny<h:
                if maze[ny][nx]=="." and (dis[ny][nx]==-1 or dis[ny][nx]==dis[y][x]+1):
                    dis[ny][nx]=dis[y][x]+1
                    d.append((nx,ny))
                    #pri(dis)
                else:
                    break
            else:
                break

print(-1)
    


                










### FIXED CODE ###

def main():
    import sys
    from collections import deque
    input=sys.stdin.readline

    h,w,k=map(int,input().split())
    sy,sx,gy,gx=map(int,input().split())

    #maze=[]
    #for _ in range(h):
    #    maze.append(tuple(input()))

    maze=[tuple(input()) for _ in range(h)]

    sy-=1
    sx-=1
    gy-=1
    gx-=1

    #maze[sy][sx]="S"

    dis=[[-1]*w for _ in range(h)]



    dis[sy][sx]=0



    d = deque([(sx,sy)])
    while len(d)>0:
        (x,y)=d.popleft()
        if x==gx and y==gy:
            print(dis[gy][gx])
            #maze[gy][gx]="G"

            #pri(dis)
            #pri(maze)

            exit()

        for (mx,my) in ((0,1),(1,0),(-1,0),(0,-1)):
            #print(mx,my,d)
            for j in range(1,k+1):
                nx=x+mx*j
                ny=y+my*j
                #print(y,x,">>",ny,nx)
                if 0<=nx<w and 0<=ny<h:
                    if maze[ny][nx]=="." and (dis[ny][nx]==-1 or dis[ny][nx]==dis[y][x]+1):
                        if dis[ny][nx]==-1:
                            d.append((nx,ny))
                        dis[ny][nx]=dis[y][x]+1
                        
                        #pri(dis)
                    else:
                        break
                else:
                    break

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

def main():
    A, B, C, K = map(int, input().split())

    ans = 0
    cnt = 0

    if A >= 1:
        if K >= A:
            cnt = A
        else:
            cnt = K

        for i in range(cnt):
            ans += 1

    tmp = K - A - B
    if tmp >= 1:
        cnt = tmp
        for i in range(cnt):
            ans -= 1

    print(f'{ans}')

if __name__ == '__main__':
    main()



### FIXED CODE ###

def main():
    A, B, C, K = map(int, input().split())

    ans = 0

    # A
    if A >= 1:
        if K >= A:
            ans = A
        else:
            ans = K

    # C
    tmp = K - A - B
    if tmp >= 1:
        ans -= tmp

    print(f'{ans}')

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

import heapq
from collections import defaultdict

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

connect = defaultdict(list)
for i in range(m):
    u, v, a, b = map(int, input().split())
    connect[u].append((v, a, b))
    connect[v].append((u, a, b))

c, d = [-1], [-1]
for i in range(n):
    c_, d_ = map(int, input().split())
    c.append(c_)
    d.append(d_)

ans = [-1] * (n+1)

h = [(0, s, 1)]
heapq.heapify(h)

while heapq:
    t, coin, city = heapq.heappop(h)

    if ans[city] == -1:
        ans[city] = t
        if all([v >= 0 for v in ans[2:]]):
            break

    for neighbor, a, b in connect[city]:
        if coin - a >= 0:
            heapq.heappush(h, (t+b, coin-a, neighbor))

    heapq.heappush(h, (t+d[city], coin+c[city], city))

print('\n'.join(map(str, ans[2:])))

### FIXED CODE ###

import heapq
from collections import defaultdict
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines

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

connect = defaultdict(list)
for i in range(m):
    u, v, a, b = map(int, input().split())
    connect[u].append((v, a, b))
    connect[v].append((u, a, b))

c, d = [-1], [-1]
for i in range(n):
    c_, d_ = map(int, input().split())
    c.append(c_)
    d.append(d_)

ans = [-1] * (n+1)
dp = [{} for _ in range(n+1)]
coin_max = [-1] * (n+1)

h = [(0, s, 1)]
heapq.heapify(h)

while heapq:
    t, coin, city = heapq.heappop(h)

    if ans[city] == -1:
        ans[city] = t
        if all([v >= 0 for v in ans[2:]]):
            break

    if coin not in dp[city]:
        dp[city][coin] = t
    else:
        continue

    if coin_max[city] >= coin:
        continue
    else:
        coin_max[city] = coin

    for neighbor, a, b in connect[city]:
        if coin - a >= 0 and neighbor != city:
            if coin-a not in dp[neighbor]:
                heapq.heappush(h, (t+b, coin-a, neighbor))

    if coin+c[city] not in dp[city]:
        heapq.heappush(h, (t+d[city], coin+c[city], city))

print('\n'.join(map(str, ans[2:])))
### BUGGY CODE ###

N = int(input())
L = list(map(int,input().split()))
count = 0
L.sort()
#print(L)
for i in range(N-2):
    a = L[i]
    for j in range(i+1,N-1):
        limit = N
        b = L[j]
        c = L[j+1]

        for k in range(N-1,j,-1):
            if L[k]<a+b:
                limit = k+1
                break

        if abs(b-c)<a<b+c:
            count += (limit-1) - j
        #print(a,b,c,i,j,k,"limit=",limit,"count=",count)

print(count)

### FIXED CODE ###

import bisect

N = int(input())
L = list(map(int,input().split()))
L.sort()

ans = 0
for i in range(1,N-1):
  for j in range(i+1,N):
    m = bisect.bisect_right(L,L[j]-L[i])
    if i>m:
      ans += i-m
print(ans)
### BUGGY CODE ###

import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
from heapq import heappop,heappush

h,w = map(int,readline().split())
ch,cw = map(int,readline().split())
dh,dw = map(int,readline().split())
s = read().split()

ch -= 1
cw -= 1
dh -= 1
dw -= 1

wall = [[0] * w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if(s[i][j] == '#'):
            wall[i][j] = 1

cost = [[-1] * w for _ in range(h)]
hq = [(0,ch,cw)]


while(hq):
    ci,xi,yi = heappop(hq)
    if(cost[xi][yi] > -1):
        continue
    cost[xi][yi] = ci

    for dx in range(-2,3):
        xj = xi+dx
        if(xj<0)|(xj>=h):
            continue
        for dy in range(-2,3):
            yj = yi+dy
            # print(xi,yi,xj,yj)
            if(yj<0)|(yj>=w):
                continue
            if(cost[xj][yj]!=-1):
                continue
            if(xi==xj)&(yi==yj):
                continue
            if(wall[xj][yj]==1):
                continue
            if(abs(xi-xj)+abs(yi-yj)==1):
                heappush(hq,(ci,xj,yj))
            else:
                heappush(hq,(ci+1,xj,yj))

print(cost[dh][dw])

### FIXED CODE ###

import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
from collections import deque

h,w = map(int,readline().split())
ch,cw = map(int,readline().split())
dh,dw = map(int,readline().split())
s = read().split()

ch -= 1
cw -= 1
dh -= 1
dw -= 1

wall = [[0] * w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if(s[i][j] == '#'):
            wall[i][j] = 1

inf = 10**10
cost = [[inf] * w for _ in range(h)]
cost[ch][cw]=0
d = deque()
d.append((0,ch,cw))

while(d):
    ci,xi,yi = d.popleft()
    if(cost[xi][yi] > ci):
        continue

    for dx in range(-2,3):
        xj = xi+dx
        if(xj<0)|(xj>=h):
            continue
        for dy in range(-2,3):
            yj = yi+dy
            # print(xi,yi,xj,yj)
            if(yj<0)|(yj>=w):
                continue
            if(xi==xj)&(yi==yj):
                continue
            if(wall[xj][yj]==1):
                continue
            if(abs(xi-xj)+abs(yi-yj)==1):
                if(cost[xj][yj] > ci):
                    cost[xj][yj] = ci
                    d.appendleft((ci,xj,yj))
            else:
                if(cost[xj][yj] > ci+1):
                    cost[xj][yj] = ci+1
                    d.append((ci+1,xj,yj))

if(cost[dh][dw] == inf):
    print(-1)
else:
    print(cost[dh][dw])
### BUGGY CODE ###

n,c=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]

rev=[None]*(n+1)
norm=[None]*(n+1)
rev[0]=(0,0)
norm[0]=(0,0)
ans=0

# normal rotation
for i in range(1,n+1):
    x,v=l[i-1]
    norm[i]=(x,v+norm[i-1][1])

# reverse rotation
for i in range(1,n+1)[::-1]:
    x,v=l[i-1]
    if i==n:
        rev[i]=(c-x,v)
    else:
        rev[i]=(c-x,v+rev[i+1][1])

for i in range(n+1):
    for j in range(n-i+1):
        cost=min(norm[i][0]+2*rev[-j][0],2*norm[i][0]+rev[-j][0])
        ans=max(ans,rev[-j][1]+norm[i][1]-cost)

print(ans)

### FIXED CODE ###

n,c=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]

rev=[None]*(n+1)
norm=[None]*(n+1)
revmax=[None]*(n+1)

rev[0]=(0,0)
revmax[0]=(0,0)
norm[0]=(0,0)
ans=0

# normal rotation
for i in range(1,n+1):
    x,v=l[i-1]
    norm[i]=(x,v+norm[i-1][1])

# reverse rotation
for i in range(1,n+1)[::-1]:
    x,v=l[i-1]
    if i==n:
        rev[i]=(c-x,v)
    else:
        rev[i]=(c-x,v+rev[i+1][1])

for i in range(1,n+1):
    revmax[-i]=(max(revmax[-i+1][0],rev[-i][1]-2*rev[-i][0]),max(revmax[-i+1][1],rev[-i][1]-rev[-i][0]))

for i in range(n+1):
    v1=norm[i][1]-norm[i][0]+revmax[i-n][0]
    v2=norm[i][1]-2*norm[i][0]+revmax[i-n][1]
    ans=max(ans,v1,v2)

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

mod = 10**9 + 7

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

dp = [0] * (n+1)
dp[0] = 1
dp[1] = 1
if 1 in a:
    dp[1] = 0
    
for i in range(2,n+1):
    if i in a:
        continue
    dp[i] = (dp[i-1] + dp[i-2]) % mod

print(dp[n])

### FIXED CODE ###

import math
mod = 10**9 + 7

# http://cav-inet.hateblo.jp/entry/2017/02/18/165141
def binary_search(list,target): 

	result = -1
	left = 0
	right = len(list) - 1

	while left <= right:
		center = (left + right)//2
		if list[center] == target:
			result = center
			break
		elif list[center] < target:
			left = center + 1
		elif list[center] > target:
			right = center - 1

	if result == -1:
		return False
	else:
		return True

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

dp = [0] * (n+1)
dp[0] = 1
dp[1] = 1
if binary_search(a,1):
    dp[1] = 0
    
for i in range(2,n+1):
    if binary_search(a,i):
        continue
    dp[i] = (dp[i-1] + dp[i-2]) % mod

print(dp[n])