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

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

A=[]
for i in range(m):
    b,c=map(int,input().split())
    A.append([b,c])
B=[]
for i in range(q):
    b,c=map(int,input().split())
    B.append([b,c,i])

C=[[0 for i in range(n+3)] for j in range(n+3)]
#print(C)
for i in range(m):
    C[A[i][0]][A[i][1]]+=1


A.sort(key=lambda x:x[1])
A.sort(key=lambda x:x[0])

B.sort(key=lambda x:x[1])
B.sort(key=lambda x:x[0])

D=[]

co=0
ml=0
mr=0
for i in range(q):
    l=B[i][0]
    r=B[i][1]
    nu=B[i][2]
    if ml<l :
        co=0
        for j in range(l,r+1):
            for k in range(j,r+1):
                co+=C[j][k]
        D.append([co,nu])
    else:
        for j in range(mr+1,r+1):
            for k in range(l,r+1):
                co+=C[k][j]
        D.append([co,nu])
    ml=l
    mr=r

D.sort(key=lambda x:x[1])
for i in range(q):
    print(D[i][0])


### FIXED CODE ###

import numpy

n,m,q=map(int,input().split())
M=[]
Q=[]
for i in range(m):
    M.append(list(map(int,input().split())))
for i in range(q):
    Q.append(list(map(int,input().split())))

#print(M)
#print(Q)

A=[[0 for i in range(n+1)] for j in range(n+1)]

for i in range(m):
    A[M[i][0]][M[i][1]]+=1

B=[[0 for i in range(n+1)] for j in range(n+1)] #Aの累積和のリスト

#B[0][0]=A[0][0]
#for i in range(1,n+1):
#    B[i][0]=A[i][0]+B[i-1][0]
#    B[0][i]=A[0][i]+B[0][i-1]

#for i in range(1,n+1):
#    for j in range(1,n+1):
#        B[i][j]=A[i][j]+B[i-1][j]+B[i][j-1]

#print(A)
#print(B)

B = numpy.cumsum(A,axis=0)
C = numpy.cumsum(B,axis=1)

#print(C)

for i in range(q):
    le=Q[i][0]
    ri=Q[i][1]
    print(C[ri][ri]-C[ri][le-1]-C[le-1][ri]+C[le-1][le-1])
### BUGGY CODE ###

s = input()
q = int(input())

rev = 0

for _ in range(q):
    t = [x for x in input().split()]
    if t[0] == "1":
        rev += 1
    else:
        if (t[1] == "1" and rev % 2 == 0) or (t[1] == "2" and rev % 2 != 0):
            tmp = [t[2],s]
            s = "".join(tmp)
        else:
            tmp = [s,t[2]]
            s = "".join(tmp)

if rev % 2 == 0:
    print(s)
else:
    print(s[::-1])

### FIXED CODE ###

from collections import deque
s = deque(input())
q = int(input())

rev = False

for _ in range(q):
    t = [x for x in input().split()]
    if t[0] == "1":
        rev = not rev
    else:
        if t[1] == "1":
            s.append(t[2]) if rev else s.appendleft(t[2])
        else:
            s.appendleft(t[2]) if rev else s.append(t[2])

if rev:
    s.reverse()
print("".join(s))
### BUGGY CODE ###

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

ans = 0
for i in range(N - 1):
    for j in range(i + 1, N):
        ans += (A[i] * A[j])
        ans = ans % (10 ** 9 + 7)

print(ans)


### FIXED CODE ###

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

X = 0
Ans = 0

for i in range(N - 1):
    X += A[i]
    Ans += X * A[i + 1]
    Ans = Ans % (10 ** 9 + 7)

print(Ans)
### BUGGY CODE ###

K, N = map(int, input().split())
Alist = list(map(int, input().split()))
  
#for each house, traverse clock/anti-clock wise
Alen = len(Alist)
min_distance = 10000000
for s in range(Alen):
  distance = 0
  start_p = s
  current_p = s
  next_p = 0 # random number
  #clock-wise
  while (True):
    # calculate next point
    if (current_p == (Alen-1)):
      next_p = 0
    else:
      next_p = current_p+1
    # finish if reached to start point again
    if (next_p == start_p):
      break
    # add distance from current to next point
    if (next_p == 0):
      distance += (K-Alist[current_p]+Alist[next_p])
    else:
      distance += (Alist[next_p]-Alist[current_p])
    # move to next point
    current_p = next_p
   
  if (distance < min_distance):
    min_distance = distance
  #anti- clock-wise
  #distance = 0
  #while (True):
  #  if (s == 0):
   #   distance += (Alist[s]+(K-Alist[s-1]))
   # else:
   #   distance += (Alist[s]-Alist[s-1])
   # s -= 1
  #  if ( (s-1) == ((-1*Alen)+start_p) ):
   #   break
 # print("anti"+str(distance))
  #if (distance < min_distance):
   # min_distance = distance

print(min_distance)
      

### FIXED CODE ###

K, N = input().split()
K = int(K)
N = int(N)
houses = list(map(int, input().split()))
first = True
distance = 0
for i in range(N):
  firstHouse = houses[i]
  lastHouse = houses[i - 1]
  if lastHouse > firstHouse:
    distance = lastHouse - firstHouse
  else:
    distance = (K - firstHouse) + lastHouse
  if first or distance < minDistance:
    minDistance = distance
    first = False
print(minDistance)
### BUGGY CODE ###

from itertools import chain

h, w = map(int, input().split())
s = [input() for _ in range(h)]
a = [[-1] * w for _ in range(h)]
for i in range(h):
    p = 0
    while p < w:
        j = p
        while j < w and s[i][j] == '.':
            j += 1
        for k in range(p, j):
            a[i][k] += j - p
        p = j + 1

for j in range(w):
    p = 0
    while p < h:
        i = p
        while i < h and s[i][j] == '.':
            i += 1
        for k in range(p, i):
            a[k][j] += i - p
        p = i + 1

print(max(chain.from_iterable(a)))


### FIXED CODE ###

from itertools import chain

h, w = map(int, input().split())
s = [input() for _ in range(h)]
a = [[-1] * w for _ in range(h)]
for i in range(h):
    p = 0
    while p < w:
        j = p
        while j < w and s[i][j] == '.':
            j += 1
        for k in range(p, j):
            a[i][k] += j - p
        p = j + 1

for j in range(w):
    p = 0
    while p < h:
        i = p
        while i < h and s[i][j] == '.':
            i += 1
        for k in range(p, i):
            a[k][j] += i - p
        p = i + 1

print(max(chain.from_iterable(a)))
### BUGGY CODE ###

nv, ne = map(int, input().split(' '))
edges = []
for i in range(ne):
    s, t, w = map(int, input().split(' '))
    edges.append((s, t, w))

for r in range(nv):
    dist = [float('inf')] * nv
    dist[r] = 0

    for i in range(nv - 1):
        for s, t, w in edges:
            if dist[t] > dist[s] + w:
                dist[t] = dist[s] + w

    for s, t, w in edges:
        if dist[t] > dist[s] + w:
            print("NEGATIVE CYCLE")
            exit()

    print(' '.join([str(d) if d < float('inf') else "INF" for d in dist]))

### FIXED CODE ###

nv, ne = map(int, input().split(' '))
edges = []
for i in range(ne):
    s, t, w = map(int, input().split(' '))
    edges.append((s, t, w))

dist = [[float('inf')] * nv for i in range(nv)]
for i in range(nv):
    dist[i][i] = 0
for s, t, w in edges:
    dist[s][t] = w

for k in range(nv):
    for i in range(nv):
        for j in range(nv):
            if dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] = dist[i][k] + dist[k][j]

for i in range(nv):
    if dist[i][i] < 0:
        print("NEGATIVE CYCLE")
        exit()

for row in dist:
    print(' '.join(str(d) if d < float('inf') else 'INF' for d in row))
### BUGGY CODE ###

# coding: utf-8

import sys
import math
from collections import Counter
import itertools
import fractions
#import numpy as np
#from functools import reduce

# 入力を整数に変換して受け取る
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
# 入力全てを整数に変換したものの配列を受け取る
def LI(): return list(map(int, sys.stdin.readline().split()))
# 入力全てを整数に変換して1引いたものの配列を受け取る
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SR(): return sys.stdin.readline().rstrip()

ascii_lowercase = 'abcdefghijklmnopqrstuvwxyz'
ascii_uppercase = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
ascii_uppercase2 = 'ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ'

# リストを改行区切りで出力する
p2D = lambda x: print(*x, sep="\n")
p2E = lambda x: print(''.join(x))
p2S = lambda x: print(*x, sep=" ")

# ###########################################
n=II()
A=LI()

ans = 1
for a in A:
    ans *= a

if ans > 1000000000000000000:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

# coding: utf-8
 
import sys
import math
from collections import Counter
import itertools
import fractions
#import numpy as np
#from functools import reduce
 
# 入力を整数に変換して受け取る
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
# 入力全てを整数に変換したものの配列を受け取る
def LI(): return list(map(int, sys.stdin.readline().split()))
# 入力全てを整数に変換して1引いたものの配列を受け取る
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SR(): return sys.stdin.readline().rstrip()
 
ascii_lowercase = 'abcdefghijklmnopqrstuvwxyz'
ascii_uppercase = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
ascii_uppercase2 = 'ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ'
 
# リストを改行区切りで出力する
p2D = lambda x: print(*x, sep="\n")
p2E = lambda x: print(''.join(x))
p2S = lambda x: print(*x, sep=" ")
 
# ###########################################
n=II()
A=LI()
 
ans = 1

if 0 in A:
    print(0)
    exit()

for a in A:
    ans *= a
    if ans > 1000000000000000000:
        print(-1)
        exit()
 
if ans > 1000000000000000000:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

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

for i in a:
    for j in range(i, max(a) + 1, i):
        l[j] += 1

for i in a:
    if l[i] == 1:
        ans += 1

print(ans)

### FIXED CODE ###

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

for i in a:
    for j in range(i, ln, i):
        l[j] += 1

for i in a:
    if l[i] == 1:
        ans += 1

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

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

for i in range(k):
  shifta = b+c; shiftb = a+c; shiftc = a+b
  a=shifta; b=shiftb; c=shiftc
  
  if abs(a-b)>10**18:print("Unfair");exit

print(a-b)

### FIXED CODE ###

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

if k%2 == 0 and abs(a-b)<=10**18:print(a-b)
elif k%2 != 0 and abs(b-a)<=10**18:print(b-a)
else:print("Unfair")
### BUGGY CODE ###

n,m=map(int,input().split())
l,r=map(int,input().split())
a=set(range(l,r+1))
for i in range(m-1):
    l,r=map(int,input().split())
    a.intersection_update(range(l,r+1))
print(len(a))

### FIXED CODE ###

n,m=map(int,input().split())
ll,rr=0,n
for i in range(m):
    l,r=map(int,input().split())
    ll=max(l,ll)
    rr=min(r,rr)
print(max(rr-ll+1,0))
### BUGGY CODE ###

#!/usr/bin/env python3

def main():
    N = int(input())
    A = list(map(int, input().split()))
    ans = 0
    for i in range(N):
        ans += A[i] * sum(A[i + 1:])
        ans %= 10**9 + 7
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3

mod = 10**9 + 7


def main():
    N = int(input())
    A = list(map(int, input().split()))
    Asum = [0] * N
    Asum[0] = A[N - 1]
    for i in range(1, N):
        Asum[i] = Asum[i - 1] + A[N - 1 - i]
    ans = 0
    for i in range(N - 1):
        ans += (A[i] * Asum[N - 2 - i]) % mod
        ans %= mod
    print(ans)


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

import heapq
h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
road_map = []
for i in range(h):
    road = input()
    road_map.append(road)
queue = []
heapq.heappush(queue,[0,ch-1,cw-1])
used_map = [[-1]*w for _ in range(h)]

layer_set = set()
layer_set.add((ch-1,cw-1))
loop = 0
while used_map[dh-1][dw-1] == -1 and queue != []:
    #move walk
    while queue != []:
        dot = heapq.heappop(queue)
        if dot[1] < 0 or dot[2] < 0 or dot[1] >= h or dot[2] >= w:
            continue
        if used_map[dot[1]][dot[2]] > -1 and used_map[dot[1]][dot[2]] <= dot[0]:
            continue
        if road_map[dot[1]][dot[2]] == "#":
            continue
        used_map[dot[1]][dot[2]] = dot[0]
        layer_set.add((dot[1],dot[2]))

        if not (dot[2] - 1 < 0):
            heapq.heappush(queue,[dot[0],dot[1],dot[2]-1])
        if not (dot[2] + 1 >= w):
            heapq.heappush(queue,[dot[0],dot[1],dot[2]+1])
        if not (dot[1]+1 >= h):
            heapq.heappush(queue,[dot[0],dot[1]+1,dot[2]])
        if not (dot[1]-1 < 0):
            heapq.heappush(queue,[dot[0],dot[1]-1,dot[2]])

    temp = []
    for s in layer_set:
        for x in range(-2,3,1):
            for y in range(-2,3,1):
                if not(s[0]+ x < 0 or s[1]+y < 0 or s[0]+x >= h or s[1]+y >= w):
                    if used_map[s[0]+x][s[1]+y] == -1 and road_map[s[0]+x][s[1]+y] == ".":
                        temp = [s[0]+x,s[1]+y]
                        heapq.heappush(queue,[loop+1,temp[0],temp[1]])
        
    loop+=1
    
print(used_map[dh-1][dw-1])

### FIXED CODE ###

#shotoyooさんのコードをお借りしてテスト

import numpy as np
from numba import njit, b1, i4, i8, f8
from heapq import heappop as hpp, heappush as hp

@njit((b1[:, :],i8,i8,i8,i8), cache=True)
def main(ss,ch,cw,dh,dw):
    inf = 1<<30
    h,w = ss.shape
    start = ch*w+cw
    goal = dh*w+dw
    n = h*w
    seen = np.full(n, inf, np.int64)
    seen[start] = 0
    q = [(0, start)] # ワープ回数, 現在位置, 最後の道の位置
    while q:
        pnum,pu = hpp(q)
        ux,uy = divmod(pu,w)
        if pu==goal:
            break
        for xx in range(-2, 3):
            for yy in range(-2, 3):
                if xx==yy==0:
                    continue
                if abs(xx)+abs(yy)<=1:
                    vv = 0
                else:
                    vv = 1
                x,y = ux+xx, uy+yy
                u = x*w + y
                num = pnum+vv
                if x<0 or y<0 or x>=h or y>=w or ss[x][y]:
                    continue
        #         print(x,y)
                if seen[u]>num:
                    seen[u] = num
                    hp(q,(num, u))
                
    val = seen[goal]
    if val==inf:
        return -1
    else:
        return val
      

h,w = map(int, input().split())
ch,cw = map(int, input().split())
dh,dw = map(int, input().split())
ch -= 1
cw -= 1
dh -= 1
dw -= 1
ss = np.array([[c=="#" for c in input()] for _ in range(h)])

print(main(ss,ch,cw,dh,dw))
### BUGGY CODE ###

import sys
def input():
	return sys.stdin.readline()[:-1]
n, s = map(int, input().split())
a = list(map(int, input().split()))
MOD = 998244353
dp = [0 for _ in range(3001)]
dp[0] = 1
ans = 0
for i in range(n):
	for j in range(s, a[i]-1, -1):
		dp[j] += dp[j-a[i]]
		dp[j] %= MOD
	dp[a[i]] += i
	dp[a[i]] %= MOD
	ans += dp[s]
	ans %= MOD
print(ans)

### FIXED CODE ###

import sys
def input():
	return sys.stdin.readline()[:-1]
n, s = map(int, input().split())
a = list(map(int, input().split()))
MOD = 998244353
dp = [0 for _ in range(3001)]
dp[0] = 1
ans = 0
for i in range(n):
	for j in range(s, a[i]-1, -1):
		dp[j] += dp[j-a[i]]
		dp[j] %= MOD
	dp[a[i]] += i
	dp[a[i]] %= MOD
	ans += dp[s]
	ans %= MOD
print(ans)
### BUGGY CODE ###

import math
N,K= list(map(int,input().split()))
Num = 10*18
while Num > 0:
    if N % K ==0:
        Num = 0
        break
    if Num > abs(N-K):
        Num = abs(N-K)
        N  = Num
        if N < abs(N-K):
            break
print(Num)

### FIXED CODE ###

import math
N,K= list(map(int,input().split()))
a = int(N/K)
a1 = a*K
a2 = (a+1)*K
if N % K ==0:
    Num = 0
else:
    if abs(N%K) < abs((N%K)-K) :
        Num = abs(N%K)
    else:
        Num =  abs((N%K)-K)
    
print(Num)
### BUGGY CODE ###

def main():
  H,N = map(int,input().split())
  AB = [list(map(int,input().split())) for _ in range(N)]
  mi_a,mi_b = min(AB,key = lambda x:x[1])
  INF = float('inf')
  dp = [0]+[mi_b]*mi_a+[INF]*H
  for i in range(mi_a+1,H+1):
    mi = float('inf')
    for a,b in AB:
      mi = min(mi,dp[max(0,i-a)]+b)
    if dp[i]>mi:
      dp[i] = mi

  print(dp[H])
  
main()

### FIXED CODE ###

H,N = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N)]
INF = float('inf')
dp = [INF]*(H+1)
dp[0] = 0
for i in range(1,H+1):
  for k in AB:
    a = k[0]
    b = k[1]
    tmp = max(0,i-a)
    dp[i] = min(dp[i],dp[tmp]+b)
    
print(dp[H])
### BUGGY CODE ###

n = int(input())
p = list(map(int, input().split(' ')))
res = 0
for i in range(n):
    x = p[:i+1]
    if min(x) >= p[i]:
        res += 1
print(res)

### FIXED CODE ###

n = int(input())
p = list(map(int, input().split(' ')))
res = 0
y = p[0]
for i in range(n):
    z = p[i]
    if y >= z:
        y = z
        res += 1
print(res)
### BUGGY CODE ###

T1, T2 = map(int, input().split())
A1, A2 = map(int, input().split())
B1, B2 = map(int, input().split())

D1 = T1 * (A1 - B1)
D2 = T2 * (A2 - B2)
li = [D1, D2]
li.sort()

pos = 0
cnt = 0
for _ in range(10000000):
  pos += li[0]
  pos1 = pos
  pos += li[1]
  pos2 = pos
  if pos1 < 0 and pos2 >= 0:
    cnt += 2
if cnt >= 1000000:
  print("infinity")
else:
  print(cnt-1)

### FIXED CODE ###

t1, t2 = map(int, input().split())
a1, a2 = map(int, input().split())
b1, b2 = map(int, input().split())

if ((a1 - b1) * (a2 - b2) > 0) or (abs(a1 - b1) * t1 > abs(a2 - b2) * t2):
  print(0)
elif abs(a1 - b1) * t1 == abs(a2 - b2) * t2:
  print("infinity")
else:
  d, m = divmod(abs(a1 - b1) * t1, abs(a2 - b2) * t2 - abs(a1 - b1) * t1)
  ans = d * 2
  if m > 0:
    ans += 1
  print(ans)
### BUGGY CODE ###

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

answer = 1
for i in range(N):
    answer = answer * v[i]

if answer <= 10 ** 18:
    print(answer)
else:
    print(-1)

### FIXED CODE ###

N = int(input())
v = list(map(int, input().split()))
limit = 10 ** 18

answer = 1
if 0 in v:
  answer = 0
else:
  for i in v:
    answer = answer * i
    if answer <= limit:
      continue
    else:
      answer = -1
      break
print(answer)
### BUGGY CODE ###

n = int(input())
l_list = list(map(int,input().split()))
temp_sum = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        
        # print(temp_sum)
        for k in range(j+1,n):
            if l_list[i] < l_list[j] + l_list[k] and l_list[j] < l_list[k] + l_list[i] and l_list[k] < l_list[j] + l_list[i]:
                temp_sum += 1


print(temp_sum)


### FIXED CODE ###

import bisect
n = int(input())
l_list = list(map(int,input().split()))
l_list.sort()
ans = 0
right = 0
# print(l_list)
for i in range(n-2):
    for j in range(i+1,n-1):
        right = bisect.bisect_left(l_list[j+1:],l_list[i]+l_list[j])
        # print(right)
        ans += right
        
print(ans)
### BUGGY CODE ###

k, s = map(int, input().split())
count = 0
for x in range(k+1):
    if(x > s):
        break
    for y in range(k+1):
        if(x + y > s):
            break
        for z in range(k+1):
            if (x + y + z == s):
                count = count + 1
print(count)

### FIXED CODE ###

k, s = map(int, input().split())
count = 0
for x in range(k+1):
    if(x > s):
        break
    for y in range(k+1):
        if(x + y > s):
            break
        if(s - (x + y) <= k):
            count = count + 1
print(count)
### BUGGY CODE ###

import numpy as np

N, M = map(int, input().split())
A = []
B = []

for i in range(0, N):
    a, b = np.array(list(map(int, input().split())))
    A.append(a)
    B.append(b)

arrayA = np.array(A)
arrayB = np.array(B)

for k in range(0, len(arrayA) - 1):
    for l in range(0, len(arrayA)- 1 - k) :
        idx = l
        if arrayA[idx] > arrayA[idx + 1]:
            tmpA = arrayA[idx]
            arrayA[idx] = arrayA[idx + 1]
            arrayA[idx + 1] = tmpA
            tmpB = arrayB[idx]
            arrayB[idx] = arrayB[idx + 1]
            arrayB[idx + 1] = tmpB

cnt = 0
sum = 0
flag = 0
for j in range(0, N):
    pay = arrayA[j]
    num = arrayB[j]
    if cnt + num < M :
        cnt += num
        sum += pay*num
    else :
        diff = M - cnt
        for t in range(0, diff):
            sum += pay
            cnt += 1
            if cnt == M :
                flag = 1
                print(sum)
                break
    if flag == 1:
        break


### FIXED CODE ###

import numpy as np

N, M = map(int, input().split())
A = []

for i in range(0, N):
    a, b = np.array(list(map(float, input().split())))
    A.append((a, b))

dtype = [('key', int), ('value', int)]
arrayA = np.array(A, dtype=dtype)
arrayA = np.sort(arrayA, order=['key'])
cnt = 0
sum = 0
flag = 0
for j in range(0, N):
    pay = arrayA[j][0]
    num = arrayA[j][1]
    if cnt + num < M :
        cnt += num
        sum += pay*num
    else :
        diff = int(M - cnt)
        for t in range(0, diff):
            sum += pay
            cnt += 1
            if cnt == M :
                flag = 1
                print(int(sum))
                break
    if flag == 1:
        break
### BUGGY CODE ###

n, m = map(int,input().split())
a = []
for i in range(m):
    a.append(int(input()))
p = [0 for i in range(n+1)]
for i in range(1,n+1):
    if i in a:
        p[i] = 0
    elif i == 1:
        p[i] = 1
    elif i == 2:
        p[i] = p[1] + 1
    else:
        p[i] = p[i-1] + p[i-2]
print(p[n] % (10**9 + 7))

### FIXED CODE ###

n, m = map(int,input().split())
p = [0 for i in range(n+1)]
a = [0 for i in range(n+1)]
for i in range(m):
    a[int(input())] = 1
for i in range(1,n+1):
    if a[i] == 1:
        p[i] = 0
    elif i == 1:
        p[i] = 1
    elif i == 2:
        p[i] = p[1] + 1
    else:
        p[i] = p[i-1] + p[i-2]
print(p[n] % (10**9 + 7))
### BUGGY CODE ###

A, B, C, D = map(int, input().split())

count = 0
for i in range(A, B+1):
    if i % C != 0 and i % D != 0:
        count+=1

print(count)

### FIXED CODE ###

import fractions
a, b, c, d = map(int, input().split())

ans = b - (b // c + b//d - b//(c*d // fractions.gcd(c, d))) - ( a - 1  - ((a-1) // c + (a-1)//d - (a-1)//(c * d //fractions.gcd(c, d))))  

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

import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
from bisect import bisect_left


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

bc = [tuple(map(int,input().split())) for i in range(m)]
bc = sorted(bc, reverse=True, key=lambda x: x[1])

for b, c in bc:
    index = bisect_left(a, c)
    for i in range(min(index,b)):
        a[i] = c
    a.sort()

print(sum(a))


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
from bisect import bisect_left


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

bc = [tuple(map(int,input().split())) for i in range(m)]
bc = sorted(bc, reverse=True, key=lambda x: x[1])

i = 0
for b, c in bc:
    for _ in range(b):
        if c <= a[i]: break
        a[i] = c
        i += 1
        if i >= n :break
    else:
        continue
    break

print(sum(a))
### BUGGY CODE ###

import itertools
import numpy as np
N = int(input())

def prime_factorize(n):
    ans = [1]
    i = 2
    while i * i <= n:
        if n % i == 0:
            n //= i
            ans.append(i)
        else:
            i += 1
    if n != 1:
        ans.append(n)
    
    return ans

primes = prime_factorize(N)
index = [i for i in range(len(primes))]
ans = False

for i in range(1, len(primes) // 2 + 1):
    for cmb in itertools.combinations(index, i):
        if i != len(primes):
            i_moved = np.prod(np.array([primes[k] for k in range(len(primes)) if k in cmb])) - 1
            j_moved = np.prod(np.array([primes[k] for k in range(len(primes)) if k not in cmb])) - 1 
        else:
            i_moved = np.prod(np.array(primes)) - 1
            j_moved = 0
        if ans is not False:
            ans = min(ans, i_moved + j_moved)
        else:
            ans = i_moved + j_moved
            
print(ans)

### FIXED CODE ###

N = int(input())
div = []
ans = N - 1
i = 2
while i ** 2 <= N:
    if N % i == 0:
        div.append(i)
    i += 1

for d in div:
    ans = min(ans, d + N // d - 2)

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

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

data = []
for m in range(M):
    data.append(list(map(int, input().split(' '))))

cnt = 0
for n in range(1, N+1):
    flg = True
    for m in range(M):
        li, ri = data[m]
        if not(li <= n <= ri):
            flg = False
    if flg:
        cnt += 1
print(cnt)

### FIXED CODE ###

N, M = map(int, input().split(' '))
 
data = []
l = 1
r = 10**5
for m in range(M):
    li, ri = map(int, input().split(' '))
    if li > l:
      l = li
    if ri < r:
      r = ri
 
if l<= N <= r:
  cnt = (N - l) + 1
elif l > r:
  cnt = 0
elif r < N:
  cnt = (r - l) + 1
else:
  cnt = 0
 
print(cnt)