Problem:
 Score : 300 points    Problem Statement There is a staircase with N steps. Takahashi is now standing at the foot of the stairs, that is, on the 0 -th step.
He can climb up one or two steps at a time.  However, the treads of the a_1 -th, a_2 -th, a_3 -th, \ldots , a_M -th steps are broken, so it is dangerous to set foot on those steps.  How many are there to climb up to the top step, that is, the N -th step, without setting foot on the broken steps?
Find the count modulo 1\ 000\ 000\ 007 .      Constraints  1 \leq N \leq 10^5  0 \leq M \leq N-1  1 \leq a_1 < a_2 <  ...  < a_M \leq N-1         Input Input is given from Standard Input in the following format:  N  M  a_1  a_2  .  .  .  a_M       Output Print the number of ways to climb up the stairs under the condition, modulo 1\ 000\ 000\ 007 .        Sample Input 1 6 1
3      Sample Output 1 4  There are four ways to climb up the stairs, as follows:   0 \to 1 \to 2 \to 4 \to 5 \to 6  0 \to 1 \to 2 \to 4 \to 6  0 \to 2 \to 4 \to 5 \to 6  0 \to 2 \to 4 \to 6        Sample Input 2 10 2
4
5      Sample Output 2 0  There may be no way to climb up the stairs without setting foot on the broken steps.       Sample Input 3 100 5
1
23
45
67
89      Sample Output 3 608200469  Be sure to print the count modulo 1\ 000\ 000\ 007 .

Solution (Python):
from sys import stdin
import bisect

n,m = [int(x) for x in stdin.readline().rstrip().split()]
if m == 0:
    li = [0]
else:
    li = [int(stdin.readline().rstrip()) for _ in range(m)]

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

dp[0] = 1

if li[0] == 1:
    dp[1] = 0
else:
    dp[1] = 1

for i in range(2,n+1):
    if li[bisect.bisect_right(li,i)-1] == i:
        dp[i] = 0
    else:
        dp[i] = dp[i-1] + dp[i-2]

print(dp[n]%(10**9+7))

Solution (Python):
from sys import stdin

n,m = [int(x) for x in stdin.readline().rstrip().split()]

lin = [0]*(n+1)

if m != 0:
    for i in range(m):
        lin[int(stdin.readline().rstrip())] = -1

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

dp[0] = 1

if lin[1] == -1:
    dp[1] = 0
else:
    dp[1] = 1

for i in range(2,n+1):
    if lin[i] == -1:
        dp[i] = 0
    else:
        dp[i] = dp[i-1] + dp[i-2]

print(dp[n]%(10**9+7))

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

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

Solution (Python):
import numpy as np


def main(n, m, a):
    dp = np.zeros(n + 1, dtype=int)
    dp[0] = 1
    dp[1] = 1 if 1 not in a else 0

    for i in range(2, len(dp)):
        dp[i] = dp[i - 1] + dp[i - 2] if i not in a else 0
        dp[i] %= 1000000007

    return dp[-1]


if __name__ == '__main__':
    N, M = map(int, input().split())
    A = set()
    for _ in range(M):
        A.add(int(input()))

    print(main(N, M, A))

Solution (Python):
N,M = map(int, input().split())
a = [int(input()) for _ in range(M)]

step_normal = [True for _ in range(N+1)]

for i in range(M):
    step_normal[a[i]] = False

dp = [0 for _ in range(N+1)]
dp[0] = 1
for i in range(0,N):
    if step_normal[i+1] == True:
        dp[i+1] += dp[i]
    if N >= i+2 and step_normal[i+2] == True:
        dp[i+2] += dp[i]
print(dp[N] % 1000000007)

Solution (Python):
def fibonacci(N):
    a = 1
    b = 2
    c = 0

    if N <= 1:
        return 1
    elif N == 2:
        return 2
    else:
        for i in range(N-2):
            c = a+b
            a = b
            b = c
    return c


def main():
    N,M = map(int,input().split())
    A = [int(input()) for _ in range(M)]

    temp = 1
    for i in range(M+1):
        if M == 0:
            temp = fibonacci(N)
            break
        else:
            if i == 0:
                num = fibonacci(A[i]-1)
            else:
                if i <= M-1:
                    if A[i-1] == A[i]-1:
                        print(0)
                        return
                    num = fibonacci(A[i]-A[i-1]-2)
                else:
                    num = fibonacci(N-A[i-1]-1)
        temp *= num
    print(temp%1000000007)


if __name__ == '__main__':
    main()

Solution (Python):
def fibcmb(start,end):
    start += 1
    end -= 1
    up = end - start
    a1 = 1
    a2 = 2
    if up < 0:
        return 0
    elif up == 0:
        return 1
    elif up == 1:
        return a1
    elif up == 2:
        return a2
    else:
        for _ in range(up-2):
            an = a1 + a2
            a1 = a2
            a2 = an
        return an

n,m = map(int,input().split())
a = [int(input()) for _ in range(m)]
ans = 1
cmb = [0]*(m+1)
if m == 0:
    ans = fibcmb(-1,n+1)
else:
    cmb[0] = fibcmb(-1,a[0])
    for i in range(1,m):
        cmb[i] = fibcmb(a[i-1],a[i])
    cmb[-1] = fibcmb(a[-1],n+1)
    for i in range(m+1):
        ans *= cmb[i]
print(ans%1000000007)

Solution (Python):
n,m=map(int,input().split())
a=[int(input()) for i in range(m)]
mod=10**9+7
d=[mod]*(n+1)
d[0]=1;d[1]=1
for i in a:
  d[i]=0
for i in range(2,n+1):
  d[i]=min(d[i],(d[i-1]+d[i-2])%mod)
print(d[n])

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

Solution (Python):
n,m = map(int,input().split())
A = set([int(input()) for _ in range(m)])
mod = 1000000007
dp = [0]*(n+1)
dp[0] = 1
for i in range(1,n+1):
    dp[i] = (dp[i-1] + dp[i-2])%mod
    if i in A:dp[i] = 0
print(dp[n])

Solution (Python):
def solve():
    N,M = map(int, input().split())
    if N == 1 and M == 0:
        return 1
    elif N == 1 and M == 1:
        return 0
    elif N == 2 and M == 0:
        return 2
    elif N == 2 and M == 1:
        return 1
    elif N == 2 and M == 2:
        return 0
    
    l = [-1]*(N+1)
    for m in range(M):
        a = int(input())
        l[a] = 0
    if l[1] == 0 and l[2] == 0:
        return 0
    elif l[1] == 0 and l[2] != 0:
        l[2] = 1
    elif l[1] != 0 and l[2] == 0:
        l[1] = 1
    else:
        l[1] = 1
        l[2] = 2
    
    l.pop(0)
    for i in range(2,N):
        if l[i] == 0:
            continue
        else:
            l[i] = l[i-1] + l[i-2]
    
    return l[-1]%1000000007


if __name__ == '__main__':
    print(solve())

Solution (Python):
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
aset = set(a)
memo = [0 for _ in range(N + 10)]
memo[0] = 1
DIV = 10**9 + 7
for idx in range(N):
	if(memo[idx]):
		if(idx + 1 not in aset):
			memo[idx + 1] += memo[idx]
			memo[idx + 1] %= DIV
		if(idx + 2 not in aset):
			memo[idx + 2] += memo[idx]
			memo[idx + 2] %= DIV
print(memo[N])

Solution (Python):
import numpy as np

N, M = map(int, input().split())
stairs_exist = np.ones(N+1)
div_num = 10 ** 9 + 7

for c in range(M):
    stairs_exist[int(input())] = 0
    
steps = np.zeros(N+1)
steps[0] = 1
for i in range(N):
    for j in range(i+1, min(N+1, i+3)):
        if stairs_exist[j]:
            steps[j] += steps[i]
            steps[j] %= div_num
            
print(int(steps[-1]))

Solution (Python):
n,m = map(int,input().split())
a = set([int(input()) for i in range(m)])

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

print(result[n])

Solution (Python):
n,m = map(int,input().split())


dp = [0]*(n+1)
dp[0] = 1

for i in range(m):
	dp[int(input())] = -1

if dp[1] != -1:
	dp[1] = 1

for i in range(n-1):
	if dp[i+2] != -1:
		if dp[i+1] != -1:
			dp[i+2] += dp[i+1]
		if dp[i] != -1:
			dp[i+2] += dp[i]

print(dp[n]%1000000007)

Solution (Python):
N,M = map(int, input().split())
A = [int(input()) for _ in range(M)]

mod = 10**9+7
dp = [0]*(N+1)
dp[0] = 1
dp[1] = 1
a = -1
if len(A):
    a = A.pop(0)
    if a == 1:
        dp[1] = 0

        
for i in range(1, N):
    if a == -1 and len(A):
        a = A.pop(0)
    if i == a:
        dp[i] = 0
        dp[i+1] = dp[i-1]
        a = -1
    else:
        dp[i+1] = dp[i] + dp[i-1]
        
print(dp[N]%mod)

Solution (Python):
n,m = map(int,input().split())
A = set([int(input()) for _ in range(m)])
mod = 1000000007
dp = [0]*(n+1)
dp[0] = 1
for i in range(1,n+1):
    dp[i] = (dp[i-1] + dp[i-2])%mod
    if i in A:dp[i] = 0
print(dp[n])

Solution (Python):
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])

Solution (Python):

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

a = [(int(input())) for i in range(M)]

import sys
sys.setrecursionlimit(100000)

memo  =[-1]*(N+2)
memo[0] = 1
memo[1] = 1
def stair_count(n):
    for j in range(2,n+1):
        memo[j] = memo[j-1] + memo[j-2]

start = 0
answer = 1
dif = []
for i in a:
    if i == start:
        print(0)
        exit()
    else:
        n = i-1-start
        dif.append(n)
        start = i+1
dif.append(N-start)
stair_count(max(dif))
for i in dif:
        answer = (answer * memo[i])

print(answer%1000000007)

Solution (Python):
n = list(map(int, input().split()))
s = [int(input()) for i in range(n[1])]
s.append(n[0]+1)
memo = [0] * 100001
memo[0] = 1
memo[1] = 1
def stairs(x):
    for i in range(2, x+1):
        memo[i] = memo[i-2] + memo[i-1]

salst = [s[0]-1]
for i in range(n[1]):
    sa = (s[i+1]-1) - (s[i]+1)
    salst.append(sa)
    if sa < 0:
        break
if salst[-1] < 0:
    print(0)
else:
    ans = 1
    maxnum = max(salst)
    stairs(maxnum)
    for l in salst:
        ans *= memo[l]
    print(ans%1000000007)

Solution (Python):

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

a = [(int(input())) for i in range(M)]

import sys

sys.setrecursionlimit(100000)
memo  =[-1]*(N+2)
def stair_count(n):
    if memo[n]!= -1:
        return memo[n]
    if n==0 or n==1:
        memo[n] =1
        return memo[n]
    memo[n] = stair_count(n-1) + stair_count(n-2)
    return memo[n]

start = 0
answer = 1
for i in a:
        if i == start:
            print(0)
            exit()
        else:
            n = i-1-start
            answer = (answer * stair_count(n))
            start = i+1
n = N -start
answer = (answer * stair_count(n))
print(answer%1000000007)

Solution (Python):
n = list(map(int, input().split()))
s = [int(input()) for i in range(n[1])]
s.append(n[0]+1)
memo = [0] * (n[0]+1)
def stairs(x):
    memo[0] = 1
    memo[1] = 1
    for i in range(2, x+1):
        memo[i] = memo[i-2] + memo[i-1]

salst = [s[0]-1]
for i in range(n[1]):
    sa = (s[i+1]-1) - (s[i]+1)
    salst.append(sa)
    if sa < 0:
        break
if salst[-1] < 0:
    print(0)
else:
    ans = 1
    maxnum = max(salst)
    stairs(maxnum)
    for l in salst:
        ans *= memo[l]
    print(ans%1000000007)

Solution (Python):
n = list(map(int, input().split()))
s = [int(input()) for i in range(n[1])]
s.append(n[0]+1)
memo = [0] * 100001
def stairs(x):
    memo[0] = 1
    memo[1] = 1
    for i in range(2, x+1):
        memo[i] = memo[i-2] + memo[i-1]

salst = [s[0]-1]
for i in range(n[1]):
    sa = (s[i+1]-1) - (s[i]+1)
    salst.append(sa)
    if sa < 0:
        break
if salst[-1] < 0:
    print(0)
else:
    ans = 1
    maxnum = max(salst)
    stairs(maxnum)
    for l in salst:
        ans *= memo[l]
    print(ans%1000000007)

Solution (Python):
N,M=map(int,input().split())
A=[int(input()) for n in range(M)]
S=[1]*(N+1)
for a in A:
  S[a]=0
for i in range(2,N+1):
  S[i]=(S[i-1]+S[i-2])%1000000007*S[i]

print(S[-1])

Solution (Python):
N, M = map(int, input().split())
A=[int(input()) for _ in range(M)]





S = [1] * (N+1)
for a in A:
    S[a] = 0



for i in range(2,N+1):
    S[i] = (S[i-1] + S[i-2]) * S[i]

print(S[-1]%1000000007)

Solution (Python):
import sys
input = sys.stdin.readline


def fib(n):
    '''f(n)=f(n-1)+f(n-2)'''
    a, b = 0, 1
    for _ in range(n-1):
        a, b = b, a+b
    return b


n, m = map(int, input().split())
mod = 10**9+7
a = [int(input()) for _ in range(m)]
if not a:
    ans = fib(n+1) % mod
else:
    ans = fib(a[0])*fib(n-a[m-1]) % mod
    for i in range(m-1):
        if a[i+1]-a[i] == 1:
            ans = 0
            break
        ans = ans * fib(a[i+1]-a[i]-1) % mod

print(ans)

Solution (Python):
n,m=map(int,input().split())
a=[int(input()) for _ in range(m)]
dp=[1]*(n+1)
for i in a:
  dp[i]=0
for i in range(2,n+1):
  dp[i]=(dp[i-1]+dp[i-2])%1000000007*dp[i]
print(dp[-1])

Solution (Python):
n,m=map(int, input().split())
a=[0 for i in range(n)]
b = [True for i in range(n)]
for i in range(m):
    b[int(input()) - 1] = False
for i in range(n):
    if b[i]==False:
        continue
    if i == 0:
        a[i] = 1
    elif i == 1:
        a[i] = 1 + a[i - 1]
    else:
        a[i] = a[i - 1] + a[i - 2]

print(a[-1]%int(1e9+7))

Solution (Python):
N, M = map(int,input().split())
a = [] 

for i in range(M):
    a.append(int(input()))
a.sort()
diff = [a[i+1]-a[i] for i in range(M-1)] if M!=1 else []
if diff and min(diff)==1 :
    print(0)
else:
    if M==0:
        stairs = [N]
    elif not(diff):
        stairs = [a[0]-1,N-a[0]-1]
    else :
        stairs = [a[0]-1]+[diff[i]-2 for i in range(M-1)]+[N-a[-1]-1]
    
    t = [1,1]
    for i in range(max(stairs)-1):
        t.append(t[-1]+t[-2])
    ans = 1
    for i in stairs:
        ans *= t[i]
    print(ans%1000000007)

Solution (Python):
n, m = map(int, input().split())
a = {int(input()) for _ in range(m)}
law = 10 ** 9 + 7

prepre = 0
pre = 1
for floor in range(1, n+1):
    if floor in a:
        prepre = pre
        pre = 0
    else:
        pre = (prepre + pre) % law
        prepre = (pre - prepre) % law
print(pre)

Solution (Python):
"""
問題文
    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)]


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
    
    
    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])

Solution (Python):
MOD = 1000000007

fact = [0 for i in range(100001)] 
inv_fact = [0 for i in range(100001)] 
 

def mod_pow(a, n, P):
	if n == 0: 
		return 1
	if n%2 == 0: 
		x = mod_pow(a, n/2, P)
		return (x*x)%P
	
	return (a*mod_pow(a, n-1, P))%P
 

def comb(n, k):
	if n < k:
		return 0
	ans = fact[n]
	ans = (ans * inv_fact[k])%MOD
	ans = (ans * inv_fact[n-k])%MOD
	return ans

def move(n):
	twonum = n // 2
	com = 0
	for i in range(twonum + 1):
		up = n - i
		com += comb(up, i)
	return com


fact[0] = inv_fact[0] = 1
for i in range(100000):
	
	fact[i+1] = (fact[i]*(i+1))%MOD
	
	inv_fact[i+1] = (inv_fact[i]*mod_pow(i+1, MOD-2, MOD))%MOD

N, M = map(int, input().split())
a = []
a.append(0)
for i in range(M):
	a.append(int(input()))
a.append(N+1)

s = 1
for i in range(M+1):
	step = a[i+1] - a[i] - 1
	if step > MOD:
		step = step % MOD
	m = move(step)
	s = (s * m) % MOD
	a[i+1] += 1

print(s)

Solution (Python):

import sys

sys.setrecursionlimit(10 ** 7)


MOD = 1000000007  


def solve(N: int, M: int, a: "List[int]"):
    ways_to_stairs = {}
    stairs = []
    for i in range(N + 1):
        stairs.append(True)
    for i in a:
        stairs[i] = False

    routes_to_stairs = {0: 1}
    if 1 not in a:
        routes_to_stairs[1] = 1

    for i in range(N + 1):
        if i <= 1:
            continue
        ways = 0
        if stairs[i]:
            if stairs[i - 1]:
                ways += routes_to_stairs[i - 1]
            if stairs[i - 2]:
                ways += routes_to_stairs[i - 2]
        routes_to_stairs[i] = ways

    print(routes_to_stairs[N] % MOD)
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    a = [int(next(tokens)) for _ in range(M)]  
    solve(N, M, a)

if __name__ == '__main__':
    main()

Solution (Python):
n,m,*a=map(int,open(0).read().split())
b=[1]*(n+1)
for i in a:
    b[i]=0
for i in range(2,n+1):
    b[i]=(b[i-1]+b[i-2])%1000000007*b[i]
print(b[-1])

Solution (Python):
n,m,*a=map(int,open(0).read().split())
if n==1:
    print(1)
    exit()
b=[-1]*(n+1)
a+=[0,0]
for i in a:
    b[i]=0
if a[0]==1 and a[1]==2:
    b[1],b[2]=0,0
elif a[0]==1:
    b[2]=1
elif a[0]==2:
    b[1]=1
else:    
    b[1],b[2]=1,2
for i in range(3,n+1):
    if b[i]==-1:
        b[i]=(b[i-1]+b[i-2])%1000000007
print(b[-1])

Solution (Python):
n,m = map(int,input().split())
li = [int(input()) for i in range(m)]

st = [1]*(n+1)
for i in range(m):
    st[li[i]-1] = 0

if st[0] == 0 and st[1] == 0:
    print(0)
    exit()
elif st[0] == 0 and st[1] != 0:
    st[1] = 1
elif st[0] == 1 and st[1] != 0:
    st[1] = 2

for i in range(2,n+1):
    if st[i] == 0:
        continue
    else:
        st[i] = (st[i-1] + st[i-2])%1000000007
print(st[n-1])

Solution (Python):
N, M = map(int, input().split())
a = []
for i in range(M):
	a.append(int(input()))
a.append(-1)

m = []
for i in range(N):
	if i == a[0] - 1:
		del a[0]
		m.append(0)
	elif i == 0:
		m.append(1)
	elif i == 1:
		m.append(m[0]+1)
	else:
		m.append(m[i-1]+m[i-2])

print(m[N-1] % 1000000007)

Solution (Python):
n,m = list(map(int,input().split()))
dp = [0]*(n+1)
for i in range(m):
    x = int(input())
    dp[x] = -1
dp[0] = 1
for i in range(1,n+1):
    if dp[i] == -1:continue
    elif dp[i-1] == -1:dp[i] = dp[i-2]
    elif dp[i-2] == -1:dp[i] = dp[i-1]
    elif i > 1:
        dp[i] = dp[i-2]+dp[i-1]
    else:dp[i] = dp[i-1]
print(dp[n]%(10**9+7) if dp[n] != -1 else 0)

Solution (Python):
n,m=map(int,input().split())
A=list(int(input()) for i in range(m))+[-1]
dp=[0]*(n+1)
dp[0]=1
j=0
for i in range(1,n+1):
    if i==A[j]:
        dp[i]=0
        j +=1
    else:
        dp[i]=dp[i-1]+dp[i-2]
print(dp[n]%1000000007)

Solution (Python):
n,m=map(int,input().split())
A=list(int(input()) for i in range(m))+[-1]
dp=[0]*(n+1)
dp[0]=1
j=0
for i in range(1,n+1):
    if i==A[j]:
        dp[i]=0
        j +=1
    else:
        dp[i]=(dp[i-1]+dp[i-2])

print(dp[n]%1000000007)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,M,*A = map(int,read().split())

MOD = 10**9 + 7

dp = [0] * (N+10)
dp[0] = 1
is_broken = [False] * (N+1)

for x in A:
    is_broken[x] = True

for n in range(1,N+1):
    if is_broken[n]:
        continue
    x = dp[n-1] + dp[n-2]
    if x >= MOD:
        x -= MOD
    dp[n] = x

answer = dp[N]
print(answer)

Solution (Python):
def solve():
    N, M = map(int, input().split())
    a = []
    for _ in range(M):
        a.append(int(input()))
    
    dp = [0] * (N + 1)
    dp[0] = 1
    a_ind = 0
    for i in range(1, N+1):
        if a_ind < M and i == a[a_ind]:
            a_ind += 1
            dp[i] = 0
            continue

        dp[i] += dp[i - 1]
        if i > 1:
            dp[i] += dp[i - 2]

    print(dp[N] % 1000000007)

if __name__ == '__main__':
    solve()

Solution (Python):
n,m=map(int,input().split())
a=set(int(input()) for i in range(m))
mod=10**9+7
dp=[0]*(n+1)
dp[0]=1
if 1 not in a:
    dp[1]=1

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

Solution (Python):
n,m=map(int,input().split())
a=set(int(input()) for i in range(m))
mod=10**9+7
dp=[0]*(n+1)
dp[0]=1
if 1 not in a:
    dp[1]=1

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

Solution (Python):
N,M = map(int, input().split())
A = [int(input()) for a in range(M)]
A = set(A)
	
DP = [0] * (N + 1)	
DP[0] = 1

mod = (10 ** 9) + 7

for i in range(1,N+1):
	if i in A:
		DP[i] = 0
	else:
		DP[i] = DP[i-1] + DP[i-2]

print(DP[N] % (mod))

Solution (Python):
N,M = map(int, input().split())
A = [int(input()) for a in range(M)]
A = set(A)
	
DP = [0] * (N + 1)	
DP[0] = 1

mod = (10 ** 9) + 7

for i in range(1,N+1):
	if i in A:
		DP[i] = 0
	else:
		DP[i] = DP[i-1] + DP[i-2]

print(DP[N] % (mod))

Solution (Python):
n, m = map(int,input().split())
a = [int(input()) for i in range(m)]
dp = [float("inf")] * (n+1)
dp[0] = 1
dp[1] = 1
for i in a:
    dp[i] = 0
for i in range(2, n+1):
    dp[i] = min(dp[i], (dp[i-1] + dp[i-2])%(10**9+7))
print(dp[n])

Solution (Python):
n, m = map(int,input().split())
a = [int(input()) for i in range(m)]
dp = [float("inf")] * (n+1)
dp[0] = 1
dp[1] = 1
for i in a:
    dp[i] = 0
for i in range(2, n+1):
    dp[i] = min(dp[i], (dp[i-1] + dp[i-2]))
print(dp[n] % 1000000007)

Solution (Python):
n, m = map(int,input().split())
a = [int(input()) for i in range(m)]
dp = [float('inf')] * (n+1)
dp[0] = 1
dp[1] = 1
for i in a:
    dp[i] = 0
for i in range(2, n+1):
    dp[i] = min(dp[i], (dp[i-1] + dp[i-2]) % 1000000007)
print(dp[n])

Solution (Python):
import sys
n, m = map(int,input().split())
a = [int(input()) for i in range(m)]
b = [0] * (m+1)
ans = 1
step = [0] * (n+1)
step[0] = 1
step[1] = 1
for i in range(2, n+1):
    step[i] = (step[i-1] + step[i-2]) % 1000000007
if m == 0:
    print(step[n])
    sys.exit()
for i in range(m-1):
    if a[i] + 1 == a[i+1]:
        print("0")
        quit()
if m > 0:
    b[0] = a[0] - 1
    b[m] = n - a[-1] - 1   
if m >= 2:
    for i in range(m-1, 0, -1):
        b[i] = a[i] - a[i-1] - 2
for i in b:
    ans = ans * step[i] % 1000000007
print(ans)

Solution (Python):
N, M = map(int, input().split())
A = set(int(input()) for i in range(M))
x = [0] * (N+1)
x[0] = 1
 
for i in range(1, N+1): 
  if i in A: x[i] = 0
  else:
    x[i] = (x[i-1] + x[i-2])%(10**9+7)
    
print(x[N])

Solution (Python):
def main():
  N,M = map(int,input().split())
  a = [int(input()) for i in range(M)]
  m = 10**9+7
  
  stair = [0]*(N+1)
  for i in a:
    stair[i] = -1
  
  dp = [0]*(N+1)
  dp[0] = 1
  if 1 not in a:
    dp[1] = 1
  for i in range(2,N+1):
    if stair[i] == 0:
      dp[i] = dp[i-1] + dp[i-2]
      dp[i] %= m
  print(dp[N])

if __name__ == '__main__':
  main()

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

Solution (Python):
n, m = map(int,input().split())
a = [int(input()) for i in range(m)]
a = set(a)
dp = [0] * (n+1)
dp[0] = 1

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

print(dp[n] % 1000000007)

Solution (Python):
N,M=map(int,input().split())
N=list(range(1,N+1))
for i in range(M):
    N[int(input())-1]=0
m=10**9+7
ans=[0,1]
for i in N:
    if i==0 and i+1==0:
        print(0)
        exit()
    if i==0:
        ans.append(0)
    else:
        ans.append(ans[-1]+ans[-2])

print(ans[-1] % m)

Solution (Python):
n,m=map(int,input().split())
a=[int(input()) for _ in range(m)]
dp=[0]*(n+1)
for i in range(m):
    dp[n-a[i]]=-1
if dp[1]==0:
    dp[1]=1
else:
    dp[1]=0
if n>1:
    if dp[2]==0:
        dp[2]=dp[1]+1
    else:
        dp[2]=0
if n>=3:
    for i in range(3,n+1):
        if dp[i]==0:
            dp[i]=dp[i-1]+dp[i-2]
        else:
            dp[i]=0
print(dp[n]%1000000007)

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

Solution (Python):
MOD=int(1e9+7)
n,m=map(int,input().split())
stairs=[True]*(n+10) 
a=[]
for i in range(m):
  s=int(input())
  a.append(s)
for j in a:
  stairs[j]=False
dp=[-1]*(n+10)
dp[0]=1
dp[1]=dp[0]*stairs[1]
for k in range(0,n):
  dp[k+2]=(dp[k+1]+dp[k])*stairs[k+2]%MOD

print(dp[n])

Solution (Python):
MOD=int(1e9+7)
n,m=map(int,input().split())
stairs=[True]*(n+10) 
a=[]
for i in range(m):
  s=int(input())
  a.append(s)
for j in a:
  stairs[j]=False
dp=[-1]*(n+10)
dp[0]=1
dp[1]=dp[0]*stairs[1]
for k in range(0,n):
  dp[k+2]=(dp[k+1]+dp[k])*stairs[k+2]%MOD

print(dp[n])

Solution (Python):
def typical_stairs():
    n, m, *dangerous = map(int, open(0).read().split())
    dangerous = set(dangerous)
    mod = 1000000007
    dp = [0] * (n + 1)
    dp[0] = 1
    if 1 not in dangerous:
        dp[1] = 1
    for i in range(2, n + 1):
        if i not in dangerous:
            dp[i] = (dp[i - 2] + dp[i - 1]) % mod
    print(dp[-1])


if __name__ == '__main__':
    typical_stairs()

Solution (Python):
import sys
input = sys.stdin.readline


def typical_stairs():
    n, m = map(int, input().split())
    dangerous = set(int(input()) for _ in range(m))
    mod = 1000000007
    dp = [0] * (n + 1)
    dp[0] = 1
    if 1 not in dangerous:
        dp[1] = 1
    for i in range(2, n + 1):
        if i not in dangerous:
            dp[i] = (dp[i - 2] + dp[i - 1]) % mod
    print(dp[-1])


if __name__ == '__main__':
    typical_stairs()

Solution (Python):
n,m = map(int,input().split())	
s=[1 for _ in range(n+2)]
for _ in range(m):
    s[int(input())+1]=0
mod=1000000007
num=[0 for _ in range(n+2)]
num[0]=num[1]=1
for i in range(n):
    if num[2]==2:
        num[2]=1
    num[i+2]=(num[i+1]*s[i+1]+num[i]*s[i])%mod

if num[2]==2:
    num[2]=1
print(num[n+1])

Solution (Python):
import sys


def typical_stairs():
    n, m = map(int, input().split())
    dangerous = set(int(sys.stdin.readline()) for _ in range(m))
    mod = 1000000007
    dp = [0] * (n + 1)
    dp[0] = 1
    if 1 not in dangerous:
        dp[1] = 1
    for i in range(2, n + 1):
        if i not in dangerous:
            dp[i] = dp[i - 2] + dp[i - 1]
    print(dp[-1] % mod)


if __name__ == '__main__':
    typical_stairs()

Solution (Python):
import sys
input = sys.stdin.readline


def typical_stairs():
    n, m = map(int, input().split())
    dangerous = set(int(input()) for _ in range(m))
    mod = 1000000007
    dp = [0] * (n + 1)
    dp[0] = 1
    if 1 not in dangerous:
        dp[1] = 1
    for i in range(2, n + 1):
        if i not in dangerous:
            dp[i] = dp[i - 2] + dp[i - 1]
    print(dp[-1] % mod)


if __name__ == '__main__':
    typical_stairs()

Solution (Python):
def typical_stairs():
    n, m = map(int, input().split())
    dangerous = set(int(input()) for _ in range(m))
    mod = 1000000007
    dp = [0] * (n + 1)
    dp[0] = 1
    if 1 not in dangerous:
        dp[1] = 1
    for i in range(2, n + 1):
        if i not in dangerous:
            dp[i] = dp[i - 2] + dp[i - 1]
    print(dp[-1] % mod)


if __name__ == '__main__':
    typical_stairs()

Solution (Python):
def typical_stairs():
    n, m = map(int, input().split())
    dangerous = set(int(input()) for _ in range(m))
    mod = 1000000007
    dp = [0] * (n + 1)
    dp[0] = 1
    if 1 not in dangerous:
        dp[1] = 1
    for i in range(2, n + 1):
        if i not in dangerous:
            dp[i] = dp[i - 2] + dp[i - 1]
    print(dp[-1] % mod)


if __name__ == '__main__':
    typical_stairs()

Solution (Python):
INIT = 1
n, m = map(int, input().split())
dp = [INIT for i in range(n + 1)]

for i in range(m):
    a = int(input())
    dp[a] = 0

for i in range(2, n + 1):
    dp[i] = (dp[i - 1] + dp[i - 2]) * dp[i]

print(dp[n] % 1000000007)

Solution (Python):
N, M = map(int, input().split())
stairs = [1] * (N+1)
for m in range(M):
    a = int(input())
    stairs[a] = 0
for n in range(2, N+1):
    stairs[n] = (stairs[n-1] + stairs[n-2])*stairs[n]
print(stairs[N]%1000000007)

Solution (Python):
n,m=map(int,input().split())
l=[1 for i in range(n+1)]
for i in range(m):
    s=int(input())
    l[s]=0
if n!=1:
    for i in range(2,n+1):
        if l[i]!=0:
            a=max(1,l[i-2]) if l[i-2]!=0 else 0
            b=max(1,l[i-1]) if l[i-1]!=0 else 0
            l[i]=a+b
print(l[n]%(10**9+7))

Solution (Python):
def fib(n):
    a, b = 0, 1
    for i in range(n):
        a, b = b, a + b
    return b


n, m = map(int, input().split())
if m == 0:
    print(fib(n) % 1000000007)
    exit()
a = [int(input()) for _ in range(m)]

total = 1
i = 0
for x in a:
    if x == i:
        print(0)
        exit()
    total *= fib(x - i - 1)
    i = x + 1
if a[-1] != n:
    total *= fib(n - (a[-1] + 1))

print(total % 1000000007)

Solution (Python):
import math
def fib(number):
    a, b = 0, 1
    for _ in range(number):
        a, b = b, a + b
    return b
N, M = map(int, input().split())
a = []
ans = 1
tmp = 0
for _ in range(M):
    a.append(int(input()))
for i in a:
    number = i-tmp
    if i == 1:
        tmp = 2
        continue
    else:
        if number<1:
            print(0)
            exit()
        else:
            ans *= fib(number-1)
            tmp = i+1
print((ans*fib(N-tmp))%1000000007)

Solution (Python):
from sys import stdin
INF = int(1e9+7)


def modadd(a, b):
    
    return (a + b) % INF


def main():
    lines = stdin.readlines()
    N = int(lines[0].split()[0])
    a = [True] * (N + 1)
    for i in map(int, lines[1:]):
        a[i] = False
    dp = [0] * (N + 1)
    dp[:2] = 1, 1 if a[1] else 0
    for i in range(2, N + 1):
        if a[i]:
            dp[i] = modadd(dp[i - 1], dp[i - 2])
    print(dp[N])
    return


main()

Solution (Python):
from sys import stdin
INF = int(1e9+7)


def modadd(a, b):
    
    return (a + b) % INF


def main():
    lines = stdin.readlines()
    N = int(lines[0].split()[0])
    M = [True] * (N + 1)
    for i in map(int, lines[1:]):
        M[i] = False
    dp = [0] * (N + 1)
    dp[:2] = 1, 1 if M[1] else 0
    for i in range(2, N + 1):
        if M[i]:
            dp[i] = modadd(dp[i - 1], dp[i - 2])
    print(dp[N])
    return


main()

Solution (Python):
from sys import stdin
INF = int(1e9+7)


def modadd(a, b):
    
    return (a + b) % INF


def main():
    lines = stdin.readlines()
    N = int(lines[0].split()[0])
    M = [True] * (N + 1)
    for i in map(int, lines[1:]):
        M[i] = False
    dp = [0] * (N + 1)
    dp[0] = 1
    for cur in range(N + 1):
        for i in range(cur + 1, min(cur + 2, N) + 1):
            if M[i]:
                dp[i] = modadd(dp[cur], dp[i])
    print(dp[N])
    return


main()

Solution (Python):
def run():
  N, M = map(int, input().split())
  stairs = [1] * (N+1)
  for m in range(M):
    a = int(input())
    stairs[a] = 0
  
  for n in range(2, N+1):
    stairs[n] = (stairs[n-1] + stairs[n-2])*stairs[n]
  print(stairs[N]%1000000007)
  
if __name__ == '__main__':
  run()

Solution (Python):
N,M = map(int,input().split())
a = [int(input()) for _ in range(M)]


for i in range(1,M):
    if a[i]-a[i-1] == 1:
        print(0)
        exit()
        


stair = [-1]*(N+1)
stair[0] = 1
stair[1] = 1

for i in range(M):
    stair[a[i]] = 0
    
for i in range(2,N+1):
    if stair[i] != 0:
        stair[i] = stair[i-1] + stair[i-2]

print(stair[-1]%1000000007)

Solution (Python):
N, M = map(int,input().split())

dp = [1]*(N+1)
for i in range(M):
    dp[int(input())]=0

for i in range(1,N+1):
    if dp[i]==1:
        if not i==1:
            dp[i]=dp[i-1]+dp[i-2]
        else:
            dp[i]=dp[i-1]
print(dp[N]%1000000007)

Solution (Python):
n,m=map(int,input().split())
l=[0]*m
for i in range(m):
    l[i]=int(input())

dp=[-1]*(n+1)
dp[0]=1
for j in l:
    dp[j]=0

if dp[1]==-1:dp[1]=1
for i in range(2,n+1):
    if dp[i]==-1:
        dp[i]=(dp[i-1]+dp[i-2])%1000000007
print(dp[-1]%1000000007)