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

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

### FIXED CODE ###

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

import sys
import copy

def main():
	input = sys.stdin.readline

	N, M = list(map(int,input().split()))
	st = [list(map(int,input().split())) for i in range(M)]

	neighbor = [[] for i in range(N)]
	ineighbor_init = [[] for i in range(N)]
	for s,t in st:
		neighbor[s-1].append(t-1)
		ineighbor_init[t-1].append(s-1)

	INF = 100100100
	ev = [INF]*N
	ev[N-1] = 0
	for i in range(N-2,-1,-1):
		dsum = 0
		dcount = 0
		for j in neighbor[i]:
			dsum += ev[j]
			dcount += 1
		ev[i] = dsum/dcount + 1

	ans = ev[0]
	for i in range(N-1):
		evmax = -1
		if len(neighbor[i])==1: continue
		for j in neighbor[i]:
			if ev[j]>evmax:
				tn = j
				evmax = ev[j]

		ntmp = copy.deepcopy(neighbor)
		ntmp[i].remove(tn)
		evtmp = [INF]*N
		evtmp[N-1] = 0
		for ii in range(N-2,-1,-1):
			dsum = 0
			dcount = 0
			for jj in ntmp[ii]:
				dsum += evtmp[jj]
				dcount += 1
			evtmp[ii] = dsum/dcount + 1

		if evtmp[0]<ans:
			ans = evtmp[0]

	print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
import copy

def main():
	input = sys.stdin.readline

	N, M = list(map(int,input().split()))
	st = [list(map(int,input().split())) for i in range(M)]

	neighbor = [[] for i in range(N)]
	for s,t in st:
		neighbor[s-1].append(t-1)

	INF = 100100100
	ev = [INF]*N
	ev[N-1] = 0
	for i in range(N-2,-1,-1):
		dsum = 0
		dcount = 0
		for j in neighbor[i]:
			dsum += ev[j]
			dcount += 1
		ev[i] = dsum/dcount + 1

	ans = ev[0]
	for i in range(N-1):
		evmax = -1
		if len(neighbor[i])==1: continue
		for j in neighbor[i]:
			if ev[j]>evmax:
				tn = j
				evmax = ev[j]

		# ntmp = copy.deepcopy(neighbor)
		# ntmp[i].remove(tn)
		evtmp = [INF]*N
		evtmp[i+1::] = ev[i+1::]
		for ii in range(i,-1,-1):
			dsum = 0
			dcount = 0
			for jj in neighbor[ii]:
				if ii==i and jj==tn: continue
				dsum += evtmp[jj]
				dcount += 1
			evtmp[ii] = dsum/dcount + 1

		if evtmp[0]<ans:
			ans = evtmp[0]

	print(ans)

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

INF = float("inf")

N, M, P, *ABC = map(int, open(0).read().split())

F = [[] for _ in range(N)]
B = [[] for _ in range(N)]
E = [(a - 1, b - 1, P - c) for a, b, c in zip(*[iter(ABC)] * 3)]

for a, b, c in E:
    F[a].append(b)
    B[b].append(a)

S = {0}
stack = [0]
while stack:
    s = stack.pop()
    for v in F[s]:
        if v not in S:
            stack.append(v)
            S.add(v)

T = {N - 1}
stack = [N - 1]
while stack:
    s = stack.pop()
    for v in B[s]:
        if v not in T:
            stack.append(v)
            T.add(v)

ok = S & T

D = [INF] * N
D[0] = 0

def bellman_ford(N):
    for _ in range(N):
        update = False
        for a, b, c in E:
            if a in ok and b in ok and D[b] > D[a] + c:
                D[b] = D[a] + c
                update = True
        if not update:
            return False
    return True

bellman_ford(N)

print(-1 if bellman_ford(1) else max(-D[-1], 0))


### FIXED CODE ###

def main():
    INF = float("inf")

    N, M, P, *ABC = map(int, open(0).read().split())

    F = [[] for _ in range(N)]
    B = [[] for _ in range(N)]
    E = [(a - 1, b - 1, P - c) for a, b, c in zip(*[iter(ABC)] * 3)]

    for a, b, c in E:
        F[a].append(b)
        B[b].append(a)

    S = {0}
    stack = [0]
    while stack:
        s = stack.pop()
        for v in F[s]:
            if v not in S:
                stack.append(v)
                S.add(v)

    T = {N - 1}
    stack = [N - 1]
    while stack:
        s = stack.pop()
        for v in B[s]:
            if v not in T:
                stack.append(v)
                T.add(v)

    ok = S & T

    D = [INF] * N
    D[0] = 0

    def bellman_ford(N):
        for _ in range(N):
            update = False
            for a, b, c in E:
                if a in ok and b in ok and D[b] > D[a] + c:
                    D[b] = D[a] + c
                    update = True
            if not update:
                return False
        return True

    bellman_ford(N)

    print(-1 if bellman_ford(1) else max(-D[-1], 0))



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

n,k=map(int,input().split())
if n==0:
  print(0)
elif abs(n-2*k)>=abs(n):
  print(min(abs(n-k),abs(n)))
else:
  for i in range(10**19):
    if n<=i*k:
      print(min(abs(n-i*k),abs(n-(i-1)*k)))
      break

### FIXED CODE ###

n,k=map(int,input().split())
p=n//k
if n==0:
  print(0)
elif abs(n-2*k)>=abs(n):
  print(min(abs(n-k),abs(n)))
else:
  print(min(abs(n-p*k),abs(n-(p+1)*k)))
### BUGGY CODE ###

import sys
import collections
from collections import Counter
# from collections import deque
# from collections import defaultdict
import itertools
# from itertools import accumulate
# from itertools import permutations
# from itertools import combinations
# from itertools import takewhile
from itertools import compress
# import functools
# from functools import reduce
import math
# from math import gcd
# from math import inf
# from math import ceil
# from math import floor
# from math import log10
# from math import log2
# from math import log
from math import factorial

# import re

N, M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]

B = list(itertools.accumulate(A))

ans = 0
for l in range(N):
    for r in range(l, N):
        t = B[r] - (B[l - 1] if l - 1 >=0 else 0)
        if t % M == 0:
            ans += 1

print(ans)


### FIXED CODE ###

import sys
import collections
from collections import Counter
# from collections import deque
# from collections import defaultdict
import itertools
# from itertools import accumulate
# from itertools import permutations
# from itertools import combinations
# from itertools import takewhile
from itertools import compress
import functools
# from functools import reduce
import math
# from math import gcd
# from math import inf
# from math import ceil
# from math import floor
# from math import log10
# from math import log2
# from math import log
from math import factorial

# import re

input = sys.stdin.readline

N, M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]

B = list(itertools.accumulate(A))
C = [0] + [x % M for x in B]

ans = 0

CNT = collections.Counter(C)

for k, v in CNT.items():
    if v >= 2:
        ans += v * (v - 1) // 2

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

N = int(input())
A = list(map(int, input().split()))
ans = [0]*N
tmp = A[0]
for i in range(N):
    if i == 0: 
        A[i] = 0
    else:
        tmp = A[i]
        A[i] = A[i-1]
    ans[i] += abs(A[0])
    for j in range(N-1):
        ans[i] += abs(A[j]-A[j+1])
    ans[i] += abs(A[N-1])
    A[i] = tmp
    print(ans[i])

### FIXED CODE ###

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

all = abs(A[0]) + abs(A[N-1])
for i in range(N-1):
    all += abs(A[i+1] - A[i])

print(all - (abs(A[0]) + abs(A[1]-A[0])) + abs(A[1]))

for i in range(1, N-1):
    print(all- (abs(A[i+1]-A[i]) + abs(A[i-1] - A[i])) + abs(A[i+1]-A[i-1]))
    
print(all - (abs(A[N-1])+abs(A[N-1]-A[N-2])) + abs(A[N-2]))
### BUGGY CODE ###

x=input()
y=input()
x_part=[[]]*len(x)
y_part=[[]]*len(y)
x_part[0]=['',x[0]]
y_part[0]=['',y[0]]
x_part1=['',x[0]]
for i in range(1,len(x)) :
  part=[]
  for item  in x_part1 :
    part.append(item+x[i])
  x_part1.extend(part)
 
 
y_part1=['',y[0]]
for i in range(1,len(y)) :
  part=[]
  for item  in y_part1 :
    part.append(item + y[i])
  y_part1.extend(part)
 
 
 
common=list(set(x_part1)& set(y_part1))

 
current_length=0
current_word=''
for item in common :
  if len(item)>current_length :
    current_length=len(item)
    current_word=item
print(current_word)

### FIXED CODE ###

s=input()
t=input()
a=len(s)
b=len(t)
n_list=  ['' for i in range(a)]
b_list=['' for j in range(b)]
for i in range(b) :
  if s[0] in t[:i+1] :
    b_list[i]=s[0]
for i in range(a) :
  if t[0] in s[:i+1] :
    n_list[i]=t[0]

import copy
for i in range(1,b) :
  n_list1=copy.copy(n_list)
  n_list[0]=b_list[i]
  for j in range(1,a) :

    if len(n_list1[j])>len(n_list[j]) :
      n_list[j]=n_list1[j]
    if len(n_list[j-1])>len(n_list[j]) :
      n_list[j]=n_list[j-1]
    if t[i]==s[j] and len(n_list1[j-1])+1>len(n_list[j])  :
      n_list[j] = n_list1[j - 1]+t[i]

print(n_list[-1])
### BUGGY CODE ###

import math

N, K = map(int, input().split())
A = sorted(list(map(int, input().split())))
Ar = A[::-1]
Ai = [Ar[i] - A[i] for i in range(N)]
ans = 0

if K > N//2:
    n, r = N-1, K-1 
    C = math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

    for i in range(N-K+1):
        ans += Ai[i] * C
        C *= N-i-K
        if N-i-1 != 0:
            C //= N-i-1
else:
    C = 1
    for i in range(N-K, -1, -1):
        ans += Ai[i] * C
        C *= N - i
        if N-K+1 - i != 0:
            C //= N-K+1 - i

print(ans % 1000000007)

### FIXED CODE ###

N, K = map(int, input().split())
MOD = 10**9+7
A = [a % MOD for a in sorted(list(map(int, input().split())))]
MIN, MAX = 0, 0

def div_MOD(a):     # (a^{-1} mod MOD) をフェルマーの小定理より求める
    return pow(a, MOD - 2, MOD)     # a^{-1} = a^{p-2} (mod p)

C = [0]*(K-1) + [1]
for n in range(K, N):
    C.append((C[n-1] * n * div_MOD(n-(K-1))) % MOD)

for i in range(N-K+1):
    MIN = (MIN + (A[i] * C[N-i-1]) % MOD) %MOD
for i in range(N-K+1):
    MAX = (MAX + (A[N-1-i] * C[N-i-1]) % MOD) %MOD

print((MAX - MIN) % MOD)
### BUGGY CODE ###

a,b,x = map(int,input().split())
flag = False
for i in range(a,b+1):
    if i%x == 0:
        first = i
        flag = True
        break
if flag:
    print((b-i)//x+1)
else:
    print(0)

### FIXED CODE ###

a,b,x = map(int,input().split())
if a == 0:
    print(b//x+1)
else:
    print(b//x - (a-1)//x)
### BUGGY CODE ###

N = int(input())
arr = [list(map(int,input().split())) for i in range(N)]
arr = sorted(arr, key=lambda x: x[0])
F = [True]*N
P = [0]*N
for i in range(N):
  P[i] = [arr[i][0]-arr[i][1], arr[i][0]+arr[i][1]]
for i in range(N):
  for j in range(i+1,N):
    if F[i]:
      if P[i][1] > P[j][0]:
        F[j] = False
      elif P[i][1] <= P[j][0]:
        break
print(F.count(True))

### FIXED CODE ###

N = int(input())
arr = [list(map(int,input().split())) for i in range(N)]
arr = sorted(arr, key=lambda x: x[0])
F = [True]*N
P = [0]*N
for i in range(N):
  P[i] = [arr[i][0]-arr[i][1], arr[i][0]+arr[i][1]]
P = sorted(P,key=lambda x:x[1])
ind = 0
for i in range(1,N):
  if P[i][0] < P[ind][1]:
    F[i] = False
  else:
    ind = i
print(F.count(True))
### BUGGY CODE ###

N = int(input())
A_list = [int(input()) for i in range(N)]

for i in range(N):
    compare_list = A_list[0:i] + A_list[i+1:]
    print(max(compare_list))


### FIXED CODE ###

N = int(input())
A_list = [int(input()) for i in range(N)]

sorted_A_list = sorted(A_list)
n1 = sorted_A_list[-1]
n2 = sorted_A_list[-2]

for i in range(N):
    if A_list[i] == n1:
        print(n2)
    else:
        print(n1)
### BUGGY CODE ###

n,m=map(int,input().split())
x=list(map(int,input().split()))
x=sorted(x)
l=[0]*(m-1)
for i in range(m-1):
    l[i]=x[i+1]-x[i]
    l=sorted(l)[::-1]
dist=x[m-1]-x[0]-sum(l[:n-1])
print(dist)

### FIXED CODE ###

n,m=map(int,input().split())
x=list(map(int,input().split()))
if n>=m:
    print(0)
    exit()

x=sorted(x)
l=[0]*(m-1)
for i in range(m-1):
    l[i]=x[i+1]-x[i]
    
l=sorted(l)[::-1]
dist=x[m-1]-x[0]-sum(l[:n-1])
print(dist)
### BUGGY CODE ###

import numpy as np
H, N = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N)]
np_ab = np.array(ab)
max_a = max(np_ab[:, 0])
dp = np.full(H+max_a, np.inf)
dp[:max_a] = 0
for i in range(max_a, H+max_a):
    for a, b in ab:
        dp[i] = min(dp[i], dp[i-a] + b)
print(int(dp[-1]))


### FIXED CODE ###

H, N = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N)]
max_a = max(a for a, b in ab)
dp = [0]*(H+max_a)
for i in range(1, H+max_a):
    dp[i] = min(dp[i-a]+b for a, b in ab)
print(dp[H])
### BUGGY CODE ###

H,W = (int(i) for i in input().split())
S = [0] * H
for i in range(H):
    S[i] = list(input())

x = [] * W
y = [] * H
L = [[1]*W for i in range(H)]
R = [[1]*W for i in range(H)]
U = [[1]*W for i in range(H)]
D = [[1]*W for i in range(H)]
ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == "#":
            L[i][j] = 0
            U[i][j] = 0
        elif i == 0 and j == 0:
            continue
        elif i == 0:
            L[i][j] = L[i][j-1] + 1
        elif j == 0:
            U[i][j] = U[i-1][j] + 1
        else:
            L[i][j] = L[i][j-1] + 1
            U[i][j] = U[i-1][j] + 1

for i in range(H-1,-1,-1):
    for j in range(W-1,-1,-1):
        if S[i][j] == "#":
            R[i][j] = 0
            D[i][j] = 0
        elif i == H-1 and j == W-1:
            continue
        elif i == H-1:
            R[i][j] = R[i][j+1] + 1
        elif j == W-1:
            D[i][j] = D[i+1][j] + 1
        else:
            R[i][j] = R[i][j+1] + 1
            D[i][j] = D[i+1][j] + 1

for i in range(H):
    for j in range(W):
        tmp = L[i][j] + R[i][j] + D[i][j] + U[i][j] - 3
        if tmp > ans:
            ans = tmp

print(ans)


### FIXED CODE ###

H,W = (int(i) for i in input().split())
S = [0] * H
for i in range(H):
    S[i] = input()

L = [[1]*W for i in range(H)]
R = [[1]*W for i in range(H)]
U = [[1]*W for i in range(H)]
D = [[1]*W for i in range(H)]
ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == "#":
            L[i][j] = 0
            U[i][j] = 0
        elif i == 0 and j == 0:
            continue
        elif i == 0:
            L[i][j] = L[i][j-1] + 1
        elif j == 0:
            U[i][j] = U[i-1][j] + 1
        else:
            L[i][j] = L[i][j-1] + 1
            U[i][j] = U[i-1][j] + 1


for i in range(H-1,-1,-1):
    for j in range(W-1,-1,-1):
        if S[i][j] == "#":
            R[i][j] = 0
            D[i][j] = 0
        elif i == H-1 and j == W-1:
            R[i][j] = 1
        elif i == H-1:
            R[i][j] = R[i][j+1] + 1
        elif j == W-1:
            D[i][j] = D[i+1][j] + 1
        else:
            R[i][j] = R[i][j+1] + 1
            D[i][j] = D[i+1][j] + 1
        tmp = L[i][j] + R[i][j] + D[i][j] + U[i][j] - 3
        if tmp > ans:
            ans = tmp

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

INF = 1001001001

N, M = map(int, input().split())
key = []
for i in range(M):
    a, b = map(int, input().split())
    s = 0
    c = list(map(int, input().split()))
    for j in range(b):
        c[j] -= 1
        s |= 1<<c[j]
    key.append([s, a])
dp = [INF] * (1<<N)
dp[0] = 0
for s in range(1<<N):
    for i in range(M):
        t = s | key[i][0]
        cost = dp[s] + key[i][1]
        dp[t] = min(dp[t], cost)
ans = dp[-1]
if ans == INF:
    ans = -1
print(ans)

### FIXED CODE ###

INF = 1001001001

N, M = map(int, input().split())
key = []
for i in range(M):
    a, b = map(int, input().split())
    s = 0
    c = list(map(int, input().split()))
    for j in range(b):
        c[j] -= 1
        s |= 1<<c[j]
    key.append([s, a])
dp = [INF] * (1<<N)
dp[0] = 0
for s in range(1<<N):
    for i in range(M):
        t = s | key[i][0]
        cost = dp[s] + key[i][1]
        dp[t] = min(dp[t], cost)
ans = dp[-1]
if ans == INF:
    ans = -1
print(ans)
### BUGGY CODE ###

def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)

def gcd_array(A):
    n = len(A)
    s = A[0]
    i = 1
    while(i < n):
        s = gcd(s,A[i])
        i += 1
    return s

if __name__ == "__main__":
    N = int(input())
    B = list(map(int,input().split()))
    max = 0
    i = 0
    while(i < N):
        A = [i for i in B]
        A.pop(i)
        d = gcd_array(A)
        if max <= d:
            max = d
        i += 1
    print(max)

### FIXED CODE ###

def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)

def gcd_array(A):
    n = len(A)
    s = A[0]
    i = 1
    Down = [0]
    while(i < n):
        t = gcd(s,A[i])
        if t < s:
            Down.append(i)
        s = t
        i += 1
    return s,Down

if __name__ == "__main__":
    N = int(input())
    B = list(map(int,input().split()))
    max = 0
    d,Down = gcd_array(B)
    C = [i//d for i in B]
    c = C[0]
    K = 1
    for j in Down:
        A = [i for i in C]
        c = A.pop(j)
        l = gcd_array(A)[0]
        if K < l:
            K = l
    print(K * d)
### BUGGY CODE ###

n,m = map(int, input().split())
L=list(map(int, input().split()))
L.sort(reverse=True)

for i in range(m):
	L[0]=L[0]/2
	for j in range(n-1):
		if L[j]<L[j+1]:
			L[j], L[j+1]= L[j+1], L[j]
		else:
			break
#小数点を切り捨てる
for i in range(n):
	L[i]=int(L[i])
print(sum(L))

### FIXED CODE ###

n, m = map(int, input().split())
L=list(map(int, input().split()))
A=[]
for i in range(n):
	A.append(-L[i])

import heapq
heapq.heapify(A)

for i in range(m):
	a= -heapq.heappop(A)
	heapq.heappush(A, -(a//2))

print(-sum(A))
### BUGGY CODE ###

s=input()
S=""
i=0
leng=len(s)
while(i<leng):
    if s[i]=="A":
        S+="A"
        i+=1
    elif i+1<leng and s[i:i+2]=="BC":
        S+="B"
        i+=2
    else:
        S+="C"
        i+=1
T=S[::-1]
l=[0]*len(T)
t=len(T)
for i in range(len(T)-1):
    if T[i]=="B":
        l[i+1]=l[i]+1
    elif T[i]=="A":
        l[i+1]=l[i]
ans=0
for i in range(len(T)):
    if T[i]=="A":
        ans+=l[i]
print(ans)


### FIXED CODE ###

s=input()
S=""
i=0
leng=len(s)
while(i<leng):
    if s[i]=="A":
        S+="A"
        i+=1
    elif i+1<leng and s[i]=="B" and s[i+1]=="C":
        S+="B"
        i+=2
    else:
        S+="C"
        i+=1
T=S[::-1]
l=[0]*len(T)
ans=0
t=len(T)
for i in range(len(T)-1):
    if T[i]=="B":
        l[i+1]=l[i]+1
    elif T[i]=="A":
        l[i+1]=l[i]
        ans+=l[i]
if T[-1]=="A":
    ans+=l[-1]
print(ans)
### BUGGY CODE ###

from collections import deque
n = int(input())
tris = list(map(int,input().split()))
cnt = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        for k in range(j+1,n):
            if tris[i] < tris[j] + tris[k] and tris[j] < tris[k] + tris[i] and tris[k] < tris[i] + tris[j]:
                cnt += 1
print(cnt)


### FIXED CODE ###

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

t=input()
ans=""
for i in t:
  if i=="?":
    ans+="D"
  else:
    ans+=i
print(ans)



### FIXED CODE ###

t=input()
ans=""
for i in range(len(t)):
  if t[i]=="?":
    ans+="D"
  else:
    ans+=t[i]
print(ans)
### BUGGY CODE ###

import numpy as np

N = int(input())
P = np.array(input().split(' '), dtype = int)

counta = 0
for i in range(N):
    counta += np.all((P[:i+1] >= P[i]))
print(counta)

### FIXED CODE ###

N = int(input())
# P = np.array(input().split(' '), dtype = int)
P = list(map(int, input().split(' ')))

p_min = P[0]
ans = 0
for p in P:
    if p <= p_min:
        p_min = p
        ans += 1
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
#import numpy as np
n,m = map(int, input().split())
i=0
lst = []
while i < m: 
    l = list(map(int, input().split()))
    l.append(i)
    lst.append(l)
    i+=1
sort_lst = sorted(lst)
i=1
res=[]
for i in range(1,n+1):
    j=1
    for k in sort_lst:
        if i == k[0]:
            res.append([k[2],str(k[0]).rjust(6,'0') + str(j).rjust(6,'0')])
            j+=1
#ans
for ans in sorted(res):
    print(ans[1])


### FIXED CODE ###

# -*- coding: utf-8 -*-
n,m = map(int, input().split())
i=0
lst = []
while i < m: 
    lst.append(list(map(int, input().split())) + [i])
    i+=1
lst = sorted(lst)
j=0
i=1
for k in lst:
    if i != k[0]:
        i=k[0]
        j=1
        k[1]=i*1000000+j
    else:
        j+=1
        k[1]=i*1000000+j

#ans
for ans in sorted(lst, key=lambda x:x[2]):
    print('{0:012d}'.format(ans[1]))
### BUGGY CODE ###

import numpy
n=int(input())
plist=list(map(int,input().split()))
ans=0

while plist:
  min_index = numpy.argmin(plist)
  if min_index==0:
    ans+=1
    plist=[]
  else:
    ans+=1
    plist=plist[:min_index]

print(ans)

### FIXED CODE ###

n=int(input())
lists=list(map(int,input().split()))
 
mn=n+1
cnt=0
for li in lists:
  if mn>li:
    mn=li
    cnt+=1
print(cnt)
### BUGGY CODE ###

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


if __name__ == "__main__":
    s = input()
    ope_num = 0
    index = 0
    a_stock = []
    b_stock = []
    s = list(s)
    while index < len(s):
        si = s[index]
        # print(index)
        # print(si)
        # print(a_stock)
        # print(b_stock)
        # print(ope_num)
        # print()
        if si == "A":
            if len(b_stock) > 0:
                b_stock = []
                a_stock = [si]
            else:
                a_stock.append(si)
        elif si == "B" and len(a_stock) > 0 and len(b_stock) == 0:
            b_stock.append(si)
        elif si == "C" and len(a_stock) > 0 and len(b_stock) > 0:
            ope_num = ope_num + 1
            s[index - 2] = "B"
            s[index - 1] = "C"
            s[index] = "A"
            a_stock = []
            b_stock = []
            if index - 4 >= -1:
                index = index - 4
            else:
                index = index - 1
        else:
            a_stock = []
            b_stock = []
        index = index + 1
    print(ope_num)

# ABCの数
# ABCの前にあるAの分だけ追加で操作できる
# ABCの後にある(BC)の分だけ追加で操作できる

# Aがあれば覚えておく
# ABCと来たら、それより前側に隣接しているAの回数だけ追加で操作できる
# 見つかったABCをBCAに置き換える
# BCAのAから走査を継続する


### FIXED CODE ###

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


if __name__ == "__main__":
    s = input()
    ope_num = 0
    index = 0
    a_stock = 0
    b_stock = 0
    s = list(s)
    while index < len(s):
        # print(s)
        # print(index)
        # print(ope_num)
        # print()
        si = s[index]
        if si == "A":
            if b_stock > 0:
                a_stock = 1
            else:
                a_stock = a_stock + 1
            b_stock = 0
        elif a_stock > 0:
            if b_stock == 0:
                if si == "B":
                    b_stock = 1
                else:
                    a_stock = 0
                    b_stock = 0
            elif si == "C":
                ope_num = ope_num + a_stock
                # s[index - 2 - a_stock + 1] = "B"
                # s[index - 1 - a_stock + 1] = "C"
                # s[index] = "A"
                # index = index - 1
                a_stock = a_stock
                b_stock = 0
            else:
                a_stock = 0
                b_stock = 0
        else:
            a_stock = 0
            b_stock = 0
        index = index + 1
    print(ope_num)

# ABCの数
# ABCの前にあるAの分だけ追加で操作できる
# ABCの後にある(BC)の分だけ追加で操作できる

# Aがあれば覚えておく
# ABCと来たら、それより前側に隣接しているAの回数だけ追加で操作できる
# 見つかったABCをBCAに置き換える
# BCAのAから走査を継続する
### BUGGY CODE ###

MOD = 1000000007
n, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
dp = [-1 for _ in range(n+1)]
dp[0] = 1
dp[1] = 1
if 1 in A:
    dp[1] = 0

step = 2
while True:
    if step == n+1:
        break
    
    if step in A:
        dp[step] = 0
    else:
        dp[step] = (dp[step-1] + dp[step-2]) % MOD
        
    step += 1
    
print(dp[n])

### FIXED CODE ###

mod = 1000000007
def add(a, b):
    return (a + b) % mod

N, M = map(int, input().split())
Broken_set = set([])
for _ in range(M):
    Broken_set.add(int(input()))

if 1 in Broken_set:    
    dp = [0]*(N+1)
    dp[0] = 1
    dp[1] = 0
    for i in range(2, N+1):
        if i in Broken_set:
            dp[i] = 0
        else:
            dp[i] = add(dp[i-1], dp[i-2])

else:
    dp = [0]*(N+1)
    dp[0] = 1
    dp[1] = 1
    for i in range(2, N+1):
        if i in Broken_set:
            dp[i] = 0
        else:
            dp[i] = add(dp[i-1], dp[i-2])

print(dp[N])