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):
n, m = map(int, input().split())

dp = [0] * (n + 1)
 
for _ in range(m):
  a = int(input())
  dp[a] = -1
  

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

mod = 10 ** 9 + 7

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

print(dp[n])

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

mod = 1000000007

from collections import deque

d = deque()

for _ in range(m):
    d.append(int(input()))

old = 0
new = 1

for i in range(1, n+1):
    if len(d):
        if i != d[0]:
            old, new = new, (old+new) % mod
        else:
            old, new = new, 0
            d.popleft()
    else:
        old, new = new, (old+new) % mod



print(new)

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

Solution (Python):
N,M = map(int,input().split())
MOD = 10**9+7
dp = [0] * (N+1)
dp[1] = 1
for _ in range(M):
  dp[int(input())] = -1
if N<2:
  print(dp[N])
  exit()

if dp[2] != -1:
  dp[2] = 1
for i in range(N+1):
  if dp[i] == -1: continue
  if i-1>=0 and dp[i-1] != -1:
    dp[i] += dp[i-1]
  if i-2>=0 and dp[i-2] != -1:
    dp[i] += dp[i-2]
  dp[i] %= MOD

print(dp[N])

Solution (Python):
import sys

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

if N==1:
	print(1)
	sys.exit()

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

for j in range(2,N+1):
	if dp[j]!=-1:
		dp[j]=0
		if dp[j-1]!=-1:
			dp[j]+=dp[j-1]
		if dp[j-2]!=-1:
			dp[j]+=dp[j-2]

print(dp[N]%1000000007)

Solution (Python):
def main():
    
    
    
    
    n, m = map(int, input().split())
    a = set(int(input()) for i in range(m))
    mod = 1000000007

    
    d = [0] * (n+1)
    
    cnt = 0 
    
    d[0] = 1
    if 1 not in a:
        d[1] = 1
    
    
    
    for i in range(2, n+1):
        if i in a:
            d[i] = 0
            cnt += 1
            if cnt == 2:
                print('0')
                exit()
        else:
            d[i] = (d[i-1] + d[i-2]) % mod
            cnt = 0
    
    ans = d[n]        
    print(ans)

if __name__ == '__main__':
    main()

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

def main():
    
    
    n, m = map(int, readline().split())
    a = set(map(int, read().split()))
    mod = 1000000007

    
    d = [0] * (n+1)
    
    cnt = 0 
    
    d[0] = 1
    if 1 not in a:
        d[1] = 1
    
    
    
    for i in range(2, n+1):
        if i in a:
            d[i] = 0
            cnt += 1
            if cnt == 2:
                print('0')
                exit()
        else:
            d[i] = (d[i-1] + d[i-2]) % mod
            cnt = 0
    
    ans = d[n]        
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):


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

ban = [False] * (n+1)

for i in range(m):
    a = int(input())
    ban[a] = True


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


for i in range(n):
    
    if (ban[i]):
        dp[i] = 0
    
    if (i + 1) <= n:
        dp[i+1] += dp[i]
    if (i + 2) <= n:
        dp[i+2] += dp[i]

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

Solution (Python):
n, m = map(int, input().split())
keep = [0] * (n + 1)
kep = [-1] * (n + 1)

for i in range(m):
    a = int(input())
    kep[a] = 0
keep[0] = 1
keep[1] = 0 if kep[1] == 0 else 1
for j in range(0, n - 1):
    keep[j + 2] = [0, keep[j] + keep[j + 1]][kep[j + 2]] % 1000000007
print(keep[n])

Solution (Python):
S=[0]*100010
S[1]=1
S[2]=1
for i in range(3,100010):
    S[i]=(S[i-2]+S[i-1])%1000000007

N,M=map(int,input().split())
if M==0:
    ans=1
    print(S[N+1])
    exit()
T=[]
for i in range(M):
    T.append(int(input()))
    if i>=1:
        if T[i]-1==T[i-1]:
            print(0)
            exit()

U=[]
U.append(T[0])
for i in range(1,M):
    U.append(T[i]-T[i-1]-1)

U.append(N-T[M-1])

ans=1
for i in range(len(U)):
    ans=(ans*S[U[i]])%1000000007
print(ans)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
MOD = 10**9+7

n, m = map(int, readline().split())
a = set(map(int, read().split()))

dp = [0] * (n + 1)
dp[0] = 1
if 1 not in a:
    dp[1] = 1
cnt = 0
for i in range(2, n + 1):
    if i not in a:
        dp[i] = (dp[i - 1] + dp[i - 2]) % MOD
        cnt = 0
    else:
        cnt += 1
        if cnt == 2:
            print('0')
            exit()
print(dp[n])

Solution (Python):
import sys

input = lambda: sys.stdin.readline().rstrip()
mod = 10**9 + 7


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

    dp = [0 for _ in range(N + 1)]
    dp[0] = 1

    for i in range(0, N):
        if i + 1 <= N and A[i + 1] != 1:
            dp[i + 1] += dp[i]
            dp[i + 1] %= mod
        if i + 2 <= N and A[i + 2] != 1:
            dp[i + 2] += dp[i]
            dp[i + 2] %= mod

    print(dp[N])


if __name__ == '__main__':
    solve()

Solution (Python):
N,M = [int(x) for x in input().split()]
mod = 10**9 + 7
DP = [0]*(N+1)
for i in range(M):
    aa = int(input())
    DP[aa] = -1
DP[0] = 1
if DP[1] != -1:
    DP[1] = 1
for i in range(2,N+1):
    if DP[i] != -1:
        DP[i] = max(0,DP[i-1]) + max(0,DP[i-2])
ans = DP[N] % mod
print(ans)

Solution (Python):



def main():
    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
    for i in range(N):
        if (i+1)<=N and (not i+1 in a):
            dp[i+1] += dp[i]
            dp[i+1] %= mod
        if (i+2)<=N and (not i+2 in a):
            dp[i+2] += dp[i]
            dp[i+2] %= mod

    print(dp[N])

if __name__ == '__main__':
    main()

Solution (Python):
import collections
n,m = map(int, raw_input().split(' '))
forbidden = set([int(raw_input()) for _ in range(m)])
q = collections.deque([1])
mod = (10 ** 9) + 7
w = 1
while(w <= n):
	if w == 0:
		q.append(1)
	else:
		q.append((1 if w not in forbidden else 0) * (sum(q) % mod))
	w += 1
	if len(q) == 3: q.popleft() 
print q[-1]

Solution (Python):
import collections
q = collections.deque([1])
n,m = map(int, raw_input().split(' '))
forbidden = set([int(raw_input()) for _ in range(m)])

mod = (10 ** 9) + 7
for w in range(1,n+1):
	if w not in forbidden:
		q.append(sum(q) % mod)
	else:
		q.append(0)
	if len(q) == 3:
		q.popleft() 
print q[-1]

Solution (Python):
N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
mod = 10**9+7
DP = [0] * (N + 2)
DP[0] = 1
STEP = set(range(N + 1)) - set(A)

for s in STEP:
  if s + 1 in STEP:
    DP[s + 1] += DP[s]
  if s + 2 in STEP:
    DP[s + 2] += DP[s]

print(DP[N]%mod)

Solution (Python):
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
b=[]
for i in range(m):
    b.append(int(input()))
a=set(b)
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:
        dp[i]=0
    else:
        dp[i]=dp[i-1]+dp[i-2]
print(dp[n]%1000000007)

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


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

dp = [0]*(N+2)

dp[N] = 1
dp[N+1] = 0

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

Solution (Python):
r = 10 ** 9 + 7
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
dp = [0] * (N+1)
a = sorted(set(a))

if 1 in a:
    dp[1] = 0
    del a[0]
else:
    dp[1] = 1

if N == 1:
    print(dp[1])
    exit()

if 2 in a:
    dp[2] = 0
    del a[0]
else:
    dp[2] = dp[1] + 1

if N == 2:
    print(dp[2])
    exit()

for i in range(1,N-1):
    if a == [] :
        dp[i+2] = (dp[i] + dp[i+1]) % r
    elif i+2 == a[0]:
        dp[i+2] = 0
        del a[0]
    else:
        dp[i+2] = (dp[i] + dp[i+1]) % r

print(dp[N])

Solution (Python):
import sys

N, M = map(int, sys.stdin.readline().strip().split())
A = set()
for _ in range(M):
    A.add(int(sys.stdin.readline()))


dp = [0 for _ in range(N+1)]
dp[0] = 1
dp[1] = 0 if 1 in A else 1

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

print(dp[N])

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

a = []
for _ in range(m):
    tmp = int(input())
    a.append(tmp)
a = set(a)

dp = [0] * (10**5 + 7)
dp[0] = 1

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

print(dp[n]%mod)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 6)

from itertools import product

def mat2_mul(X, Y):
    Z = [ [0, 0], 
          [0, 0] ]
    for (i,j,k) in product(range(2),range(2),range(2)):
        Z[i][j] += X[i][k] * Y[k][j]
    return Z

def mat2_pow(X, n):
    if n == 0:
        return [ [1, 0],
                 [0, 1] ]
    elif n % 2:
        return mat2_mul(X, mat2_pow(X, n-1))  
    else:
        half_pow = mat2_pow(X, n/2)
        return mat2_mul(half_pow, half_pow)

def Fib(n):
    if n == 0:
        return 0
    else:
        F = [ [0, 1],
              [1, 1] ]
        return mat2_pow(F, n-1)[1][1]
    
    
N, M = map(int, input().split())
A = [int(input()) for i in range(M)]

x=0
L=[]
for i in range(M):
    L += [A[i] - 1 - x]
    x = A[i] + 1
L += [N - x]
L = [Fib(i+1)%1000000007 for  i in L]

X=1
for i in range(len(L)):
    X *= L[i]
    X %= 1000000007 
print(X)

Solution (Python):
from sys import stdin, setrecursionlimit


def main():
    mod = 10 ** 9 + 7
    input = stdin.buffer.readline
    n, m = map(int, input().split())
    a = [1] * (n + 1)
    for _ in range(m):
        idx = int(input())
        a[idx] = 0

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

    print(dp[-1] % mod)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Solution (Python):
import itertools
import collections
N,M = map(int, input().split())
A = [list(list(input().split())) for i in range(M)]
AList = list(itertools.chain.from_iterable(A))
cnt = collections.Counter(AList)
INF = 10**9+7
dp = [INF]*(N+1)
MOD = 10**9+7

def solve(val1, val2):
    if val1 == 0 and val2 == 0:
        print(0)
        exit()
    else:
        return val1 + val2

for i in range(N+1):
    if i == 0:
        dp[0] = 1
    elif i == 1:
        if cnt['1'] == 0:
            dp[1] = 1
        else:
            dp[1] = 0
    else:
        if cnt[str(i)] == 1:
            dp[i] = 0
        else:
            dp[i] = solve(dp[i-2], dp[i-1])
print(dp[N] % MOD)

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

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

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

safe_out = [True] * (n + 1)
for i in range(m):
    a = int(input())
    safe_out[a] = False
    
way_cnt = [0] * (n + 1)
way_cnt[0] = 1
way_cnt[1] = 1

for i in range(2, n + 1):
    if safe_out[i - 1]:
        way_cnt[i] += way_cnt[i - 1]
    
    if safe_out[i - 2]:
        way_cnt[i] += way_cnt[i - 2]
        
    way_cnt[i] %= (10**9 + 7)

print(way_cnt[n])

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

Solution (Python):
N,M = map(int, input().split())
h = [0]*(N+1)
mod = 1000000007

for _ in range(M):
  h[int(input())] = 1

for i in range(1,N):
  if h[i]+h[i+1] == 2:
    print(0)
    exit()

memo = [0]*(N+1)
memo[0] = 1
if h[1] == 0:
  memo[1] = 1
else:
  memo[1] = 0

for i in range(2,N+1):
  if h[i] == 1:
    memo[i] = 0
  else:
    memo[i] = (memo[i-1] + memo[i-2]) % mod
    
print(memo[N])

Solution (Python):
N, M = map(int, input().split())
Q = 1000000007
A = set()
for _ in range(M):
    A.add(int(input()))

p = []
for i in range(1, N+1):
    if i in A:
        p.append(0)
    elif i == 1:
        p.append(1)
    elif i == 2:
        p.append(p[0] + 1)
    else:
        p.append(p[i-2] + p[i-3])

print(p[N-1] % Q)

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

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

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

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

print(dp[n] % 1000000007)

Solution (Python):
from sys import stdin
def main():
    
    readline=stdin.readline
    mod=10**9+7
    n,m=map(int,readline().split())
    a=[int(readline()) for _ in range(m)]
    flags=[True]*(n+1)
    for i in a:
        flags[i]=False

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

    print(dp[-1])
        
if __name__=="__main__":
    main()

Solution (Python):
N, M = map(int, input().split())
q = 10**9 + 7
stairs = [0]* (N+1)
for _ in range(M):
    a = int(input())
    stairs[a] = "*"

stairs[0] = 1
if stairs[1] != "*":
    stairs[1] = 1

for i in range(2, N+1):
    if stairs[i] != "*":
        if stairs[i-1] != "*" and stairs[i-2] != "*":
            stairs[i] = (stairs[i-1] + stairs[i-2]) % q
        elif stairs[i-1] == "*" and stairs[i-2] != "*":
            stairs[i] = stairs[i-2] % q
        elif stairs[i-1] != "*" and stairs[i-2] == "*":
            stairs[i] = stairs[i-1] % q
        else:
            stairs[i] = 0
print(stairs[N] % q)

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

mod = 10**9 + 7

no = [False] * (n+1)

for _ in range(m):
    a = int(input())
    no[a] = True
    
dp = [0] * (n+1)
dp[0] = 1

for i in range(n):
    if (no[i]):
        dp[i] = 0
    
    if i + 1 <= n:
        dp[i+1] += dp[i]
    if i + 2 <= n:
        dp[i+2] += dp[i]
        
print(dp[n] % mod)

Solution (Python):
N, M = map(int, input().split())
a = [int(input()) for i in range(M)]
step = [True]*(N+1)
dp = [0]*(N+1)
dp[0] = 1
dp[1] = 1 if step[1] else 0


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

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

print(dp[-1])

Solution (Python):
N, M = map(int, input().split())
A = [int(input()) for i in range(M)]
mod = 10**9 +7

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

dp[0] = 1
if dp[1] == -1:
    dp[1] = dp[0]
for i in range(2, N+1):
    if dp[i] == 0:
        continue
    dp[i] = dp[i-1] + dp[i-2]

ans = dp[N] % mod
print(ans)

Solution (Python):
from collections import deque

CONST = 1000000007

n,m = map(int,input().split())
lis = deque([int(input()) for _ in range(m)])
lis.append(n+1)
nhole = lis.popleft()

memo = deque([0, 1])
for i in range(1,n+1):
    if i == nhole:
        memo.append(0)
        nhole = lis.popleft()
    else:
        memo.append((memo[-1] + memo[-2])%CONST)
print(memo[-1])

Solution (Python):
import math
from collections import deque

memo = deque([1, 2])
floor = 1
def search(x):
    global memo, floor
    while x > floor:
        memo.append(memo[-1] + memo[-2])
        floor += 1
    return memo[x-1]

CONST = 1000000007
n,m = map(int,input().split())
lis = []
prev = -1
for _ in range(m):
    a = int(input())
    if prev + 1 == a:
        print(0)
        exit()
    lis.append(a-prev-2)
    prev = a
lis.append(n-prev-1)


ans = 1
for v in lis:
    if v == 0: continue
    ans = (ans * search(v)) % CONST
print(ans)

Solution (Python):
N, M = [int(x) for x in input().split()]
a = set(int(input()) for _ in range(M))
 
MOD = 10 ** 9 + 7
dp = [0] * (N + 1)
dp[0] = 1
 
for i in range(1, N + 1):
  if i in a:
    continue
  x = dp[i - 1]
  if i > 1:
    x += dp[i - 2]
  dp[i] = x % MOD

ans = dp[N]
print(ans)

Solution (Python):
n,m = map(int,input().split())
a = set(int(input()) for i in range(m))
mod = 1000000007
lis = []
 
if n ==  1 and m == 0:
  print(1)
  exit()
  
if 1 not in a:
  lis.append(1)
  if 2 in a:
    lis.append(0)
  else:
    lis.append(2)
    
elif 1 in a:
  lis.append(0)
  if 2 in a:
    lis.append(0)
  else:
    lis.append(1)
 
 
for i in range(3,n+1):
  if i in a:
    lis.append(0)
  else:
    lis.append((lis[i-2] + lis[i-3])%mod)
    
print(lis[-1])

Solution (Python):
MOD = 10**9+7

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

method = [0]*(N+1)
method[0]=1
method[1]=1-is_broken[1]
for i in range(2,N+1,1):
    if is_broken[i]== 0:
        method[i]= (method[i-1]+method[i-2])%MOD
    else:
        method[i]=0
print(method[N])

Solution (Python):
from collections import defaultdict
def prepare(n, MOD):
    
    f = 1
    factorials = [1]  
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    
    inv = pow(f, MOD - 2, MOD)
    
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    return factorials, invs
    
def main():
    MOD = 1000000007

    n,m=map(int, input().split())
    dd={i:0 for i in range(0,n+1)}
    a = [2]*(n)
    a[-1]=1
    for i in range(m):
        s  = int(input())
        dd[s]+=1
    dp=[0]*(n+1)
    dp[0]=1
    if dd[1]==0:
        dp[1]=1
    else:
        dp[2] = 1
        if dd[2]>0:
            print(0)
            exit()
    for i in range(2,n+1):
        dp[i] = dp[i-1] + dp[i-2]
        if dd[i]>0:
            dp[i]=0
    print(dp[n]%MOD)




if __name__ == '__main__':
    main()

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

now = 0
point = 1
mod = 10**9+7

def fib(n,mod):
    a, b = 1, 1
    for _ in range(n):
        a, b = b %mod, (a + b)%mod
    return a%mod

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

for i in a:
    point *= fib((i-1-now),mod)
    point %= mod
    now = i+1
    if now == n:
        break

point *= fib(n-now,mod)
point %= mod

print(point)

Solution (Python):
N, M = [int(x) for x in input().split()]
a = set(int(input()) for _ in range(M))
 
MOD = 10 ** 9 + 7
dp = [0] * (N + 1)
dp[0] = 1
 
for i in range(1, N + 1):
  if i in a:
    continue
  x = dp[i - 1]
  if i > 1:
    x += dp[i - 2]
  dp[i] = x % MOD
 
ans = dp[N]
print(ans)

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

for i in range(n, -1, -1):
    if flag[i]:
        if i == n or i == n - 1:
            cnt[i] = 1
        else:
            cnt[i] = (cnt[i + 1] + cnt[i + 2]) % (10 ** 9 + 7)
    else:
        cnt[i] = 0
print (cnt[0])

Solution (Python):
import sys


sys.setrecursionlimit(10 ** 6)


def f(n):
    if memo[n] > 0:
        return memo[n]
    memo[n] = f(n - 1) + f(n - 2)
    return memo[n]


N, M, *A = map(int, open(0).read().split())
memo = [1, 1] + [-1] * N
A = list(A) + [N + 1]
MOD = 10 ** 9 + 7
ans = 1
prev = 0
for a in A:
    if a == prev:
        ans = 0
        break
    ans *= f(a - 1 - prev)
    ans %= MOD
    prev = a + 1
print(ans)

Solution (Python):

N, M = [int(x) for x in input().split()]
a = set(int(input()) for _ in range(M))

MOD = 10 ** 9 + 7
dp = [0] * (N + 1)
dp[0] = 1

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

ans = dp[N]
print(ans)

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
mod = 10**9 + 7

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

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 not in a:
	dp[1] = 1
else:
	dp[1] = 0
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):
N, M = map(int, input().split())
A = {}
for _ in range(M):
    a = int(input())
    A[a] = True

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

for i in range(2, N+1):
    
    

    if not i-1 in A:
        dp[i] += dp[i-1]
    if not i-2 in A:
        dp[i] += dp[i-2]

print(dp[N] % 1000000007)

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

A = set(A)

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

for i in range(n):
    if i in A:
        continue
    if i+1 <= n and i+1 not in A:
        dp[i+1] += dp[i]
        dp[i+1] %= mod
    if i+2 <= n and i+2 not in A:
        dp[i+2] += dp[i]
        dp[i+2] %= mod

print(dp[-1]%mod)

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

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

step = [0]*N

for i in range(M):
    a = int(input())
    step[a-1] = 1

mod = int(1e9+7)

dp = [0]*N

if N == 1:
    if step[0]:
        print(0)
    else:
        print(1)
    exit()

if not step[0] and not step[1]:
    dp[0] = 1
    dp[1] = 2
elif step[0] and not step[1]:
    dp[0] = 0
    dp[1] = 1
elif not step[0] and step[1]:
    dp[0] = 1
    dp[1] = 0
else:
    print(0)
    exit()

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

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
a = [INT() for _ in range(M)]
is_broken = [0]*(N+1)
for x in a:
	is_broken[x] = 1

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

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

print(dp[N])

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

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

N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
s = set(a)
dp = [0]*(N+1)
MOD = 10**9+7
dp[0] = 1

for i in range(1, N+1):
    if i not in s:
        dp[i] += dp[i-1]
        
        if i-2>=0:
            dp[i] += dp[i-2]
        
        dp[i] %= MOD

print(dp[N])

Solution (Python):
import sys
class Fib:
  def __init__(self):
    self.memo = {}
  def calc(self, n):
    if n == 1 or n == 2:
      self.memo[n] = 1
      return 1
    if n <= 0:
      self.memo[n] = 0
      return 0
    if n in self.memo.keys():
      return self.memo[n]
    self.memo[n] = self.calc(n - 1) + self.calc(n - 2)
    return self.memo[n]
sys.setrecursionlimit(200000)
N, M = map(int, input().split())
ans = 1
mod = 10 ** 9 + 7
pre = -1
for i in range(M):
  a = int(input())
  if a == 1:
    pre = a
    continue
  if a == pre + 1 and pre != 0:
    print(0)
    sys.exit()
  ans *= Fib().calc(a - pre - 1) % mod
  pre = a
ans *= Fib().calc(N - pre) % mod
print(ans % mod)

Solution (Python):
import numpy as np

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

brk_stair = np.ones(N+1, dtype = int)
dp = np.zeros(N+1, dtype= int)

for _ in range(M):
    brk_stair[int(input())] = 0



dp[0] = 1
dp[1] = 1 * brk_stair[1]

for i in range(2, N + 1):
    dp[i] = (dp[i - 1] + dp[i-2]) * brk_stair[i]
    if(dp[i] > 1000000007):
        dp[i] = dp[i] % 1000000007


print(dp[-1] % 1000000007)

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

brk_stair = [1] * (N + 1)
dp = [0] * (N + 1)

for _ in range(M):
    brk_stair[int(input())] = 0



dp[0] = 1
dp[1] = 1 * brk_stair[1]

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

print(dp[-1] % 1000000007)

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

Solution (Python):
N, M = [int(i) for i in input().split()]
a = [int(input()) for _ in range(M)]
divisor = 10**9 + 7

fl = [True] * N

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

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

for i in range(1, N+1):
    if i > 0 and fl[i-1]:
        dp[i] += dp[i-1] % divisor
    if i > 1 and fl[i-2]:
        dp[i] += dp[i-2] % divisor
    
print(dp[N]%divisor)

Solution (Python):
n, m = map(int, input().split())
mod = 1e9 + 7
ok = [True] * (n+1)
for i in range(m):
    a = int(input())
    ok[a] = False
dp = [0] * (n+1)
dp[0] = 1
for i in range(n):
    for j in range(i+1, 1 + min(n, i + 2)):
        if ok[j]:
            dp[j] += dp[i]
            dp[j] %= mod
print(int(dp[-1]))

Solution (Python):
n, m = map(int, input().split())
mod = 1e9 + 7
ok = [True] * (n+1)
for i in range(m):
    a = int(input())
    ok[a] = False
dp = [0] * (n+1)
dp[0] = 1
for i in range(n):
    for j in range(i+1, 1 + min(n, i + 2)):
        if ok[j]:
            dp[j] += dp[i]
            dp[j] %= mod
print(int(dp[-1]))

Solution (Python):
N, M = map(int, input().split())
a = set([int(input()) for i in range(M)])
count = [0 for i in range(N)]
mod = 10**9 + 7

for i in range(N):
    if i+1 not in a:
        if i+1 == 1:
            count[i] += 1
        elif i+1 == 2:
            count[i] += count[0] + 1
        else:
            count[i] += count[i-1] + count[i-2]

print(count[-1] % mod)

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

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
for i in range(n):
    if i+1<n+1 and not i+1 in a:
        dp[i+1] += dp[i]
        dp[i+1] %= mod
    if i+2<n+1 and not i+2 in a:
        dp[i+2] += dp[i]
        dp[i+2] %= mod

print(dp[n])

Solution (Python):
n, m = map(int, input().split())
dp = [0 for i in range(n + 1)]
mod = 10 ** 9 + 7
broke = set()
for i in range(m):
    broke.add(int(input()))
dp[0] = 1
for i in range(n):
    if i + 1 <= n and i + 1 not in broke:
        dp[i + 1] += dp[i]
        dp[i + 1] %= mod
    if i + 2 <= n and i + 2 not in broke:
        dp[i + 2] += dp[i]
        dp[i + 2] %= mod
print(dp[-1] % mod)

Solution (Python):

n,m = map(int,input().split())
As = [int(input()) for _ in range(m)]
step = [ 0 for i in range(n+1)]
INF = 1000000007

dp = [0]*(n)

for i in As:
    step[i] = -1

for i in range(n-1):
    if step[i+1] == -1 and step[i+2] == -1:
        print(0)
        exit()
    if step[i+1] != -1:
        step[i+1] +=  1
    if step[i+2] != -1:
        step[i+2] +=  1

step[0] = 1
if step[1] != -1:
    step[1] = 1

for i in range(2,n+1):
    if step[i] == -1 or step[i] == 0:
        continue
    else:
        a = 0
        b = 0
        if step[i-2] != -1:
            a = step[i-2]
        if step[i-1] != -1:
            b = step[i-1]
        step[i] = a + b

print(step[n]%INF)

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import copy
from itertools import permutations
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

from itertools import permutations
from math import factorial, hypot





N, M = getNM()
A = set(getArray(M))

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

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