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())
A=[]
for i in range(M):
    a=int(input())
    if i!=0 and a==A[-1]:
        continue
    if i!=0 and a==A[-1]+1:
        print(0)
        quit()
    A.append(a)
INF=10**9+7
B=[]
tmp=0
A.append(N+1)
for i in A:
    B.append(i-tmp)
    tmp=i+1
dp=[0]*(N+3)
dp[0]=1
dp[1]=1
dp[2]=1
for i in range(2,N+2):
    dp[i+1]=dp[i]+dp[i-1]
    dp[i+1]%=INF
ans=1
for i in B:
    ans*=dp[i]
    ans%=INF
print(ans)

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

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

idx = 0
for pos in range(1, N + 1):
    if a[idx] == pos:
        memo[pos] = 0
        for i in range(idx, N):
            if a[i] > pos: break
        idx = i
        continue
    else:
        if pos > a[idx]:
            for i in range(idx, N):
                if a[i] > pos: break
            idx = i
        
        if pos == 1:
            memo[1] = (memo[0]) % (10 ** 9 + 7)
        else:
            memo[pos] = (memo[pos - 2] + memo[pos - 1]) % (10 ** 9 + 7)


print(memo[-1])

Solution (Python):
import sys

n, m = list(map(int, input().split()))
if m > 0:
    aaa = set(map(int, sys.stdin))
else:
    aaa = set()
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1 if 1 not in aaa else 0
MOD = 10 ** 9 + 7

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

Solution (Python):
import sys
input = sys.stdin.readline
mod=10**9+7
n,m=map(int,input().split())
A=set()
for i in range(m):
  A.add(int(input()))
S=[0]*(n+1)
S[0]=1
if 1 not in A:
  S[1]=1
for i in range(2,n+1):
  if i in A:
    S[i]=0
  else:
    S[i]=(S[i-1]+S[i-2])%mod
print(S[n]%mod)

Solution (Python):
N,M=list(map(int,input().strip().split(' ')))
B=[]
MOD=10**9+7
for _ in range(M):
    B+=[int(input())]
broken=set(B)
dp=[0]*(N+1)
dp[0]=1
for i in range(1,len(dp)):
    if i in broken:
        dp[i]=0
    else:
        if i==1:
            dp[1]=dp[0]
        else:
            dp[i]=(dp[i-1]+dp[i-2])%(MOD)
print(dp[-1])

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

kaidan = [True for _ in range(n+1)]
dp = [0 for _ in range(n+1)]

for i in a:
    kaidan[i] = False

dp[0] = 1
dp[1] = 1 if kaidan[1] else 0

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

Solution (Python):
N, M = map(int, input().split())
stair = [0]*(N+1)
for i in range(M):
    num = int(input())
    stair[num] = -1

stair[0] = 1
if stair[1] == -1:
    stair[1] = 0
else:
    stair[1] = 1

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

ans = stair[N] % 1000000007
print("{}".format(ans))

Solution (Python):


import sys

class bigint:
    def __init__(self,n,mod=10**9+7):
        self.n = n % mod
        self.mod = mod
        return
    
    def __str__(self):
        return str(self.n)
    
    def __add__(self,other):
        assert self.mod==other.mod, "modulos of the two not match"
        return bigint(self.n+other.n,self.mod)
    
    def __iadd__(self,other):
        assert self.mod==other.mod, "modulos of the two not match"
        self.n = (self.n + other.n) % self.mod
        return self
    
    def __sub__(self,other):
        assert self.mod==other.mod, "modulos of the two not match"
        return bigint(self.n-other.n,self.mod)
    
    def __isub__(self,other):
        assert self.mod==other.mod, "modulos of the two not match"
        self.n = (self.n - other.n) % self.mod
        return self


n,m = [ int(x) for x in sys.stdin.readline().split() ]
step= [bigint(0)] * (n+1)
wall= [False] * (n+1)
for i in range(m):
    am = int( sys.stdin.readline() )
    wall[am] = True

step[0]= bigint(1)
if not wall[1]: step[1]= bigint(1)

zero=bigint(0)
for i in range(2,n+1):
    if wall[i]: continue
    s1= step[i-1]
    s2= step[i-2]
    if s1==s2==zero: break
    step[i] = s1 + s2

print( step[n] )

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

amari = 1000000007

dp = [0]*(n+1)

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

print(dp[n]%amari)

Solution (Python):


import itertools
from collections import Counter
from collections import defaultdict
import bisect
from heapq import heappush, heappop

def main():
    MOD = 1000000007

    N, M = map(int, input().split())
    A = set()
    for _ in range(M):
        a = int(input())
        A.add(a)

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

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


if __name__ == '__main__':
    main()

Solution (Python):
import sys

from collections import deque
from heapq import heappush,heappop
import re

def int_raw():
    return int(input())
 
def ss_raw():
    return input().split()
 
def ints_raw():
    return tuple(map(int, ss_raw()))


DIV = 10**9+7


def main():
    N,M = ints_raw()
    As = [int_raw() for _ in range(M)]
    is_breake = [0]*(N+1)
    for a in As:
        is_breake[a]=1
    memo = [0]*(N+1)
    memo[0]=1
    if N ==0:
        return memo[0]
    memo[1]=1 if is_breake[1]==0 else 0
    if N ==1:
        return memo[1]
    for n in range(2,N+1):
        if is_breake[n]==1:
            memo[n] =0

        else:
            memo[n]=(memo[n-2]+memo[n-1])%DIV
    return memo[N]

print(main())

Solution (Python):


N, M = map(int, input().split())
hsh = {}
for i in range(M):
    hsh[int(input())] = True

acc = [0 for _ in range(N+1)]
acc[0] = 1
if 1 in hsh:
    acc[1] = 0
else:
    acc[1] = 1

for i in range(2,N+1):
    if i-2 in hsh:  
        if i-1 in hsh: 
            d = 0
        else:
            d = acc[i-1]
    else:  
        if i-1 in hsh:  
            d = acc[i-2]
        else: 
            d = acc[i-1] + acc[i-2]
    acc[i] = d



print(acc[-1]%1000000007)

Solution (Python):
N,M = map(int,input().split())
A = [int(input()) for i in range(M)]
INF = 10**9+7
ans = [0]*(N+1)
ans[1] = 1
if M != 0:
    s = A[0]
    if s == 1:
        ans[1] = 0
A = set(A)
ans[0] = 1

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

Solution (Python):

from __future__ import division, print_function

import os
import sys
from __builtin__ import xrange as range
from cStringIO import StringIO
from future_builtins import ascii, filter, hex, map, oct, zip
from io import IOBase

import __pypy__


MOD = 10**9 + 7

def main():
    N, M = read_int_array()
    nums = []
    for _ in range(M):
        nums.append(read_int())
    print(solve(N, nums))


def solve(N, nums):
    dp = [0] * (N + 1)
    dp[0] = 1
    broken = set(nums)
    for i in range(1, N + 1):
        if i in broken:
            dp[i] = 0
            continue
        dp[i] = dp[i - 1]
        if i > 1:
            dp[i] = (dp[i] + dp[i - 2]) % MOD
    return dp[N]


import math
import random


def always_true(*args, **kwargs):
    return True


def generate_nums(n, min, max, check_if_good=always_true):
    while True:
        numSet = set()
        nums = []
        for _ in range(n):
            while True:
                x = random.randint(min, max)
                if x not in numSet:
                    numSet.add(x)
                    nums.append(x)
                    break
        if check_if_good(nums):
            return nums


def main2():
    for _ in range(1000000):
        N = random.randint(1, 10**5)
        M = random.randint(0, min(3, N-1))
        nums = generate_nums(M, 1, N-1, lambda nums: len(nums) == len(set(nums)))
        print(solve(N, nums), flush=True)




BUFSIZE = 8192


class FastI(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = StringIO()
        self.newlines = 0

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count("\n") + (not b)
            ptr = self._buffer.tell()
            self._buffer.seek(0, 2), self._buffer.write(b), self._buffer.seek(ptr)
        self.newlines -= 1
        return self._buffer.readline()


class FastO(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = __pypy__.builders.StringBuilder()
        self.write = lambda s: self._buffer.append(s)

    def flush(self):
        os.write(self._fd, self._buffer.build())
        self._buffer = __pypy__.builders.StringBuilder()


def print(*args, **kwargs):
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


sys.stdin, sys.stdout = FastI(sys.stdin), FastO(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

read = input
read_int = lambda: int(input())
read_array = lambda sep=None, maxsplit=-1: input().split(sep, maxsplit)
read_int_array = lambda: [int(a) for a in read_array()]



if __name__ == "__main__":
    main()

Solution (Python):
N,M  = [int(x)for x in input().split()]

a = [0 for i in range(N+8)]

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

DP = [0 for i in range(N+8)]
DP[0] = 1
DP[1] = 1
if a[1] == 1:
    DP[1] = 0
for i in range(2,N+1):
    if a[i] == 0:
        DP[i] = (DP[i-2]+DP[i-1])
        if DP[i] >1000000007:
            DP[i] %=1000000007
    else:
        pass

print(DP[N])

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

mod=10**9+7
for i in range(2,n+1):
    if l[i]==-1:
        continue
    elif l[i-1]==-1 and l[i-2]==-1:
        l[i]=0
    elif l[i-1]==-1:
        l[i]=l[i-2]
    elif l[i-2]==-1:
        l[i]=l[i-1]
    else:
        l[i]=l[i-1]+l[i-2]
        l[i]%=mod
   
print(l[-1]%mod)

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

mod = int(1e9+7)

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

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


stairs = set(range(2,N+1)) - set(A)


if len(A) > 0 and A[0] == 1:
  solver[1] = 0
else:
  solver[1] = 1

for i in stairs: 
    var = (solver[i-2] + solver[i-1]) % mod
    solver[i] = var
    
print(solver[-1])

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

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

waru=1000000007

def Fib(n):
    a, b = 0, 1
    if n == 1:
        return a
    elif n == 2:
        return b
    else:
        for i in range(n-2):
            a, b = b, a + b
        return b

ans=1
now=0
for i in range(m):
    ans*=Fib(a[i]-now+1)
    now=a[i]+1
ans*=Fib(n-now+2)
print(ans%waru)

Solution (Python):
N, M = map(int, input().split())
a_set = set()
for i in range(M):
    a_set.add(int(input()))
mod = 1000000007

ways = [0] * (N + 1)
if N not in a_set:
    ways[N] = 1
if N - 1 not in a_set:
    ways[N - 1] = 1

for n in reversed(range(N - 1)):
    if n in a_set:
        continue
    ways[n] = (ways[n + 1] + ways[n + 2]) % mod
print(ways[0])

Solution (Python):
from collections import defaultdict

N, M = map(int, input().split())
aList = [int(input()) for _ in range(M)]
mod = 1000000007

dp = defaultdict(int)
dp[0] = 1
for i, a in enumerate(aList):
    dp[a] = None

for i in range(1, N + 1):
    if dp[i] != None:
        if i >= 1 and dp[i - 1] != None:
            dp[i] += dp[i - 1]
        if i >= 2 and dp[i - 2] != None:
            dp[i] += dp[i - 2]

        dp[i] %= mod

if dp[N] == None:
    dp[N] = 0
print(dp[N])

Solution (Python):
N,M=map(int,input().split())
mod=10**9+7
isbroken=[1 for i in range(N+1)]
dp=[0 for i in range(N+1)]
dp[0]=1
for i in range(M):
    ai=int(input())
    isbroken[ai]=0
for i in range(N):
    dp[i+1]=isbroken[i]*dp[i]+isbroken[i-1]*dp[i-1]
    dp[i+1]%=mod
print(dp[N])

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

comb = [0] * (N + 1)
comb[0] = 1
comb[1] = 0 if 1 in a else 1

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

print(comb[N])

Solution (Python):
import collections

BIGINT = int(1e9 + 7)

N, M = map(int, input().split())
invalid = {int(input()) for _ in range(M)}
dp = collections.defaultdict(int)
dp[0] = 1
for i in range(1, N + 1):
    if i in invalid:
        dp[i] = 0
    else:
        dp[i] = (dp[i - 1] + dp[i - 2]) % BIGINT

print(dp[N])

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

mod = 10 ** 9 + 7

dp = [0 for _ in range(N+100)]
dp[0] = 1
a_set = set(a_list)

for i in range(N):
    if i in a_set:
        continue
    else:
        if 0 <= i <= N - 1:
            dp[i + 1] += dp[i]
            dp[i + 1] %= mod
        if 0 <= i <= N - 2:
            dp[i + 2] += dp[i]
            dp[i + 2] %= mod

print(dp[N] % mod)

Solution (Python):
import sys

def main():
    input = sys.stdin.readline
    MOD = 10**9 + 7
    N, M = map(int, input().split())
    A = [int(input()) for _ in range(M)]
    is_safe = [True] * (N+1)
    for a in A:
        is_safe[a] = False

    dp = [0] * (N+2)
    dp[1] = 1
    for i in range(N):
        step = i+2
        if is_safe[i+1]:
            dp[step] = dp[step-1] + dp[step-2]
            dp[step] %= MOD
        else:
            dp[step] = 0

    return dp[N+1]


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

Solution (Python):
mod = 10 ** 9 + 7
N, M = map(int, input().split())
F = [0, 1]
fib_minus1 = 1
fib_minus2 = 0
for i in range(N):
	fib = (fib_minus1 + fib_minus2) % mod
	F.append(fib)
	fib_minus2 = fib_minus1
	fib_minus1 = fib
x = 1
a = -1
for i in range(M):
	b = int(input())
	if b > a + 1:
		x = (x * F[b - a - 1]) % mod
		a = b
	elif b == a + 1:
		x = 0
x = (x * F[N - a]) % mod
print(x)

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

broken = [N+1]*(M+1)
ans = [0]*(N+1)
broken_pointer = 0
for i in range(M):
    a = int(input())
    broken[i] = a

ans[0] = 1
if(broken[0] == 1):
    ans[1] = 0
    broken_pointer += 1
else:
    ans[1] = 1

for i in range(2,N+1):
    if (broken[broken_pointer] == i):
        ans[i] = 0
        broken_pointer += 1
    else:
        ans[i] = ans[i-1] + ans[i-2]
    

print(ans[N]%1000000007)

Solution (Python):
N,M = map(int,input().split())
ans = 1
a = -1
if M > 0:
    a = int(input())
    ans = 1
    b = 0
    for i in range(a-1):
        c = ans
        ans = ans + b
        b = c
for i in range(M-1):
    new_ans = 1
    b = 0
    new_a = int(input())
    if new_a == a + 1:
        ans = 0
        break
    k = new_a - a - 2
    for j in range(k):
        c = new_ans
        new_ans = new_ans + b
        b = c
    ans = ans * new_ans % 1000000007
    a = new_a
new_ans = 1
b = 0
for j in range(N - a - 1):
    c = new_ans
    new_ans = new_ans + b
    b = c
ans = ans * new_ans % 1000000007
print(ans)

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

Solution (Python):
n, m = map(int, input().split())
a_array = [int(input()) for x in range(m)]
res = [1 for x in range(n + 1)]
res[1] = 1
for i in a_array:
    res[i] = -1
if n <= 2:
    print(n if m == 0 else 1)
    exit()
for i in range(2, n + 1):
    if res[i] == -1:
        continue
    if res[i - 1] != -1 and res[i - 2] != -1:
        res[i] = (res[i - 1] + res[i - 2])%1000000007
    elif res[i - 1] != -1 or res[i - 2] != -1:
        res[i] = max(res[i - 1], res[i - 2])%1000000007
    else:
        res[i] = 0
print(res[-1])

Solution (Python):
N,M = map(int,input().split())
MOD = 1000000007
 
a = set()

for m in range(M):
    aa = int(input())
    a.add(aa)





x = [0 for n in range(N+1)]
x[0] = 1
x[1] = 1 if 1 not in a else 0
for n in range(2,N+1):
    if n in a or (n-1 in a and n-2 in a):
        x[n] = 0
    elif n-1 in a:
        x[n] = x[n-2]%MOD
    elif n-2 in a:
        x[n] = x[n-1]%MOD
    else:
        x[n] = (x[n-1] + x[n-2])%MOD


print(x[N])

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

for i in range(m):
    a.add(int(input()))

p = [0 for i in range(n)]

if 1 not in a:
    p[0] = 1

if n >= 2 and 2 not in a:
    p[1] = p[0] + 1

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

print(p[n - 1] % 1000000007)

Solution (Python):


MOD =  1000000007

def f(N, A):
    c0 = 0
    c1 = 1

    for i in range(1, N+1):
        c0, c1 = c1, (c0+c1)%MOD

        if i in A:
            c1 = 0

    return c1
            


def main():
    N,M = map(int, input().split())
    A = set(int(input()) for i in range(M))
    print(f(N, A))


if __name__ == '__main__':
    main()

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

mod = 10 ** 9 + 7

dp = [0 for _ in range(N+100)]
dp[0] = 1
a_set = set(a_list)

for i in range(N):
    if i in a_set:
        continue
    else:
        if 0 <= i <= N - 1:
            dp[i + 1] += dp[i]
            dp[i + 1] %= mod
        if 0 <= i <= N - 2:
            dp[i + 2] += dp[i]
            dp[i + 2] %= mod

print(dp[N] % mod)

Solution (Python):
N, M = map(int, raw_input().split(" "))
A = {int(raw_input()) for _ in range(M)}

memo = [0] * (N + 1)
memo[0] = 1
memo[1] = 0 if 1 in A else 1

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

Solution (Python):


from collections import deque


MOD = 1000000007 


N,M = map(int, input().split())
An = [int(input()) for _ in range(M)]

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


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

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N,M=MAP()
broken=[False]*(N+1)
for i in range(M):
    a=INT()
    broken[a]=True

dp=[0]*(N+1)
dp[0]=1
for i in range(N):
    if not broken[i+1]:
        dp[i+1]+=dp[i]
        dp[i+1]%=MOD
    if i!=N-1:
        if not broken[i+2]:
            dp[i+2]+=dp[i]
            dp[i+2]%=MOD
print(dp[N])

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


reslist = [0]*(N+1)
reslist[0] = 1
if alist[1]:
  reslist[1] = 1

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

print(reslist[N])

Solution (Python):
Q = 1000000007
n, m = map(int, input().split())
a = set(int(input()) for _ in range(m))
dp = {
    0: 1,
    1: 0 if 1 in a else 1,
}

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

print(dp[n])

Solution (Python):


import sys
def input(): return sys.stdin.readline().strip()

MOD = 10**9 + 7


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


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

if M != 0:
    for _ in range(M):
        dp[int(input())] = -1

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

print(dp[N])

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


if __name__ == "__main__":
    [n, m] = li()
    broken = [int(input()) for _ in range(m)]
    mod = 10 ** 9 + 7

    pattern = [0] * (n + 1)
    pattern[0] = 1
    broken_index = 0
    checking = broken[broken_index] if len(broken) > broken_index else -1
    if checking != 1:
        pattern[1] = 1
    else:
        pattern[1] = 0
        broken_index = broken_index + 1
        checking = broken[broken_index] if len(broken) > broken_index else -1

    for i in range(2, n + 1):
        if checking != i:
            pattern[i] = (pattern[i - 2] + pattern[i - 1]) % mod
        else:
            pattern[i] = 0
            broken_index = broken_index + 1
            checking = broken[broken_index] if len(broken) > broken_index else -1
    print(pattern[n])

Solution (Python):
N, M = map(int, input().split())
arr = []
MOD = 1000000007
for i in range(M):
    arr.append(int(input())) 

arr.append(10**10)

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

tmp = 0

if arr[0] == 1:
    dp[1] = 0
    tmp += 1
else:
    dp[1] = 1

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

print(dp[N])

Solution (Python):
n,m = map(int,input().split())
judge = [True for i in range(n+5)]
for i in range(m):
    judge[int(input())] = False
dp = [0]*(n+5)
dp[0] = 1
for i in range(n):
    if i + 1 > n:continue
    if judge[i + 1]:dp[i+1] = (dp[i] +dp[i+1]) %1000000007
    if i + 2 > n:continue
    if judge[i + 2]:dp[i+2] = (dp[i] + dp[i+2]) %1000000007
print(dp[n]%1000000007)

Solution (Python):
def c_typical_stairs(N, M, A, MOD=(10**9 + 7)):
    a = set(A)
    stairs = [0] * (N + 1)
    stairs[0] = 1
    for i in range(1, N + 1):
        if i in a:
            continue
        if i - 1 >= 0:
            stairs[i] += stairs[i - 1]
            stairs[i] %= MOD
        if i - 2 >= 0:
            stairs[i] += stairs[i - 2]
            stairs[i] %= MOD
    return stairs[N] % MOD

N, M = [int(i) for i in input().split()]
A = [int(input()) for _ in range(M)]
print(c_typical_stairs(N, M, A))

Solution (Python):
mod = int(1e9) + 7
def solve():
    n, m = map(int, input().split())
    li = [1, 1] + [-1] * n
    for a in (int(input()) for _ in range(m)):
        li[a] = 0
    for i in range(2, n + 1):
        if li[i]:
            li[i] = (li[i - 2] + li[i - 1]) % mod
    print(li[n])
solve()

Solution (Python):
N,M = map(int, input().split())
dp = [1] * (N + 1)

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

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


print(dp[-1])

Solution (Python):
N,M  = [int(x)for x in input().split()]

a = [0 for i in range(N+8)]

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

DP = [0 for i in range(N+8)]
DP[0] = 1
DP[1] = 1
if a[1] == 1:
    DP[1] = 0
for i in range(2,N+1):
    if a[i] == 0:
        DP[i] = (DP[i-2]+DP[i-1])%1000000007
    else:
        pass

print(DP[N])

Solution (Python):
import sys
import math

input = sys.stdin.readline
p=1000000007
N,M=map(int,input().split())
fib=[1,1]
for i in range(N):
	fib.append(fib[-1]+fib[-2])

cur=0
ans=1
flag=False
for i in range(M):
	x=int(input())
	if x==cur:
		flag=True
		print(0)
		break
	ans*=fib[x-cur-1]
	ans%=p
	cur=x+1
ans*=fib[N-cur]
ans%=p
if not flag:
	print(ans%p)

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

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

print(a[n])

Solution (Python):
import sys

mod = 10**9 + 7
N, M = map(int,input().split())
A = []




pos = 0 

fib = [1, 1]
for i in range(N-1):
    fib.append(fib[i] + fib[i+1])

ans = 1

for i in range(M):
    a = int(input())
    step = a-1 - pos
    if step >= 0:
        ans = (ans * (fib[step] % mod)) % mod
        pos = a+1
    else:
        print("0")
        sys.exit()
step = N - pos
ans = (ans * (fib[step] % mod)) % mod
print(str(ans))

Solution (Python):
import sys
import collections
ns = lambda: sys.stdin.readline().rstrip()
ni = lambda: int(ns())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
nsm = lambda: map(str, sys.stdin.readline().split())
nsl = lambda: list(nsm())

mod = 1000000007

n, m = nm()
dp = [0] * (n + 2)
for i in range(m):
    tmp = ni()
    dp[tmp] = -1
dp[0] = 1
for i in range(n):
    if i + 1 <= n:
        if dp[i + 1] != -1 and dp[i] != -1:
            dp[i + 1] += dp[i] % mod
            dp[i + 1] %= mod
    if i + 2 <= n:
        if dp[i + 2] != -1 and dp[i] != -1:
            dp[i + 2] += dp[i] % mod
            dp[i + 2] %= mod
if dp[n] == -1:
    print(0)
else:
    print(dp[n] % mod)

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

counts = [0] * (N + 1)
for i in range(N + 1):
    if i == 0:
        counts[i] = 1
    elif i == 1:
        if i not in A:
            counts[i] = 1
    else:
        if i not in A:
            for j in [i - 2, i - 1]:
                if j not in A:
                    counts[i] += counts[j]
                    counts[i] %= 1000000007

print(counts[N])

Solution (Python):
mod = 1000000007

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

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

for i in a:
  dp[i] = -1

for i in range(N+1):
  if dp[i] == -1:
    continue
  if i+1 <= N:
     if dp[i+1] != -1:
      dp[i+1] += dp[i]%mod
  if i+2 <= N:
    if dp[i+2] != -1:
      dp[i+2] += dp[i]%mod

print(dp[N]%mod)

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

for i in range(N):
    if dp[i] % 1 == 0:
        dp[i+1] = (dp[i+1] + dp[i]) % mod
        dp[i+2] = (dp[i+2] + dp[i]) % mod

print(dp[N] % mod)

Solution (Python):

import sys
import math
import numpy as np
import itertools

MOD = 1000000007

n,m = (int(i) for i in input().split())  


if m > 0:
    a = [int(input()) for i in range(m)]
else:
    a = []
a.append(9999999) 
dame=0

b=[1]
if a[dame]==1:
    dame += 1
    b.append(0)
else:
    b.append(1)

for i in range(2,n+1):
    if i==a[dame]:
        dame += 1
        b.append(0)
    else:
        c=(b[i-1]+b[i-2]) % MOD
        b.append(c)


print(b[n])

Solution (Python):
import sys
MOD=10**9+7
N,M=map(int,input().split())

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

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

pat=[0 for i in range(N+1)]
pat[0]=1
if a[1]==0: pat[1]=1

for i in range(2,N+1):
    if a[i]==0: pat[i]=pat[i-1]+pat[i-2]
    pat[i]%=MOD
print(pat[N])

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

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

for i in range(N + 1):
    if i + 1 < N + 1 and not i + 1 in A:
        ans[i + 1] += ans[i]
        ans[i + 1] %= MOD
    if i + 2 < N + 1 and not i + 2 in A:
        ans[i + 2] += ans[i]
        ans[i + 2] %= MOD

print(ans[N])

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

A = []
if len(A_pre)>0:
    A.append(A_pre[0])
    for i in range(1,M):
        if A[-1] != A_pre[i]:
            A.append(A_pre[i])

ans = [0] * (N+1)
ans[0] = 1
break_floor_count = 0
if break_floor_count < len(A) and A[break_floor_count] == 1:
    break_floor_count += 1
else:
    ans[1] = 1

for i in range(2,N+1):
    if break_floor_count < len(A) and A[break_floor_count] == i:
        break_floor_count += 1
    else:
        ans[i] = (ans[i-2]+ans[i-1])%mod_num 

print(ans[N])

Solution (Python):


N, M = map(int, input().split())
hsh = {}
for i in range(M):
    hsh[int(input())] = True

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

for i in range(1,N+1):
    if i > 1 and i-2 in hsh:  
        if i-1 in hsh: 
            d = 0
        else:
            d = acc[i-1]
    else:  
        s = acc[i-2] if i > 1 else 0
        if i-1 in hsh:  
            d = s
        else: 
            d = acc[i-1] + s
    acc[i] = d



print(acc[-1]%1000000007)

Solution (Python):
mod = 10**9+7
import sys
sys.setrecursionlimit(10000000)

N,M = [int(x) for x in input().split()]
a = [int(input()) for _ in range(M)]
di = {}
for i in a:
    di[i]=1
dp = [0 for _ in range(N+1)]
dp[0] = 1
for i in range(N+1):
    if(i in di):
        continue
    if(i<N-1):
        if(i+2 not in di):
            dp[i+2]+=dp[i]
            dp[i+2]%=mod
    if(i<N):
        if(i+1 not in di):
            dp[i+1]+=dp[i]
            dp[i+1]%=mod
print(dp[N])

Solution (Python):


def solve():
    N, M = list(map(int, input().split()))
    A = {}
    for i in range(1, N+1):
        A[i] = True  
    for i in range(M):
        a = int(input())
        A[a] = False  
    MOD = 10**9+7

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

    for i in range(1, N+1):
        if A[i] is False: continue

        dp[i] += dp[i-1]
        if i-2 >= 0:
            dp[i] += dp[i-2]
        dp[i] %= MOD
    
    print(dp[N]%MOD)


if __name__ == "__main__":
    solve()