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):
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
print(dp[n] % mod)

Solution (Python):
import sys
input = sys.stdin.readline
from sys import setrecursionlimit
setrecursionlimit(10**9)

def inpl(): return list(map(int, input().split()))
N, M = inpl()
MOD = 10**9 + 7
A = [1]*(N+3)
A[N+2] = 0
A[N+1] = 0
for _ in range(M):
    a = int(input())
    A[a] = 0

DP = [0]*(N+3)
DP[0] = 1
for i in range(N):
    DP[i+1] = ((DP[i+1] + DP[i])*A[i+1])%MOD
    DP[i+2] = ((DP[i+2] + DP[i])*A[i+2])%MOD
print(DP[N]%MOD)

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

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

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

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007


def A():
    p,q,r = LI()
    print(p+q+r-max(p,q,r))
    return


def B():
    n = I()
    w = LI()
    ans = float("inf")
    for i in range(n):
        m = sum(w[:i])
        l = sum(w[i:])
        ans = min(ans,abs(m-l))
    print(ans)
    return


def C():
    n,m = LI()
    f = [1 for i in range(n+10000)]
    for i in range(m):
        a = I()
        f[a] = 0
    dp = [0 for i in range(n+10000)]
    dp[0] = 1
    for i in range(n):
        if f[i+1]:
            dp[i+1] += dp[i]
            dp[i+1] %= mod
        if f[i+2]:
            dp[i+2] += dp[i]
            dp[i+2] %= mod
    print(dp[n])
    return


def D():
    h,w = LI()
    s = SR(h)
    vi = [[0 for j in range(w)] for i in range(h)]
    ho = [[0 for j in range(w)] for i in range(h)]
    q = deque()
    for y in range(h):
        for x in range(w):
            if s[y][x] == "
                l = len(q)
                while q:
                    i,j = q.pop()
                    vi[i][j] = l
            else:
                q.append((y,x))
        l = len(q)
        while q:
            i,j = q.pop()
            vi[i][j] = l
    for x in range(w):
        for y in range(h):
            if s[y][x] == "
                l = len(q)
                while q:
                    i,j = q.pop()
                    ho[i][j] = l
            else:
                q.append((y,x))
        l = len(q)
        while q:
            i,j = q.pop()
            ho[i][j] = l
    ans = 0
    for y in range(h):
        for x in range(w):
            ans = max(ans,vi[y][x]+ho[y][x]-1)
    print(ans)
    return


def E():
    n = I()

    return


def F():
    n = I()

    return


if __name__ == "__main__":
    C()

Solution (Python):
N, M = list(map(int, input().split()))
V = 10 ** 9 + 7
a = [int(input()) for _ in range(M)]
A = set(a)
ANS = [0 for _ in range(N + 5)]

ANS[0] = 1
for i in range(N):
    
    
    if i in A:
        continue
    ANS[i + 1] += ANS[i]
    
    ANS[i + 2] += ANS[i]
    
print(ANS[N] % V)

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

Solution (Python):
n,m = map(int,input().split())
A = [int(input()) for i in range(m)]
B = [0 for i in range(10**5+10)]
for i in range(len(A)):
    B[A[i]] = 1

mod = 10**9 + 7

DP = [1,1]
if B[1] == 1:
    DP[1] = 0
for i in range(2,n+1):
    if B[i] == 0:
        DP.append((DP[i-1]+DP[i-2])%mod)
    else:
        DP.append(0)
    if i >= 3:
        DP[i-3]=0
print(DP[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:
        if a[i-1]==0 and a[i-2]==0: pat[i]=pat[i-1]+pat[i-2]
        elif a[i-1]==0 and a[i-2]==-1: pat[i]=pat[i-1]
        elif a[i-1]==-1 and a[i-2]==0: pat[i]=pat[i-2]
        else:
            print(0)
            sys.exit()

    pat[i]%=MOD
print(pat[N])

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

mod = 10 ** 9 + 7

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


for i in range(1, n + 1):
    if i in broken:
        continue

    if i == 1:
        dp[1] = dp[0]
        continue

    dp[i] = dp[i - 1] + dp[i - 2]
    dp[i] %= mod

print(dp[n])

Solution (Python):
import fractions as fr
import itertools as it
import collections as col
import heapq as hq
import sys
sys.setrecursionlimit(10**9)

"""
N=int(input())
W=list(map(int, input().split()))
ans=10**100
for T in range(1,N):
        S1=sum(W[:T])
        S2=sum(W[T:])
        ans = min(ans, abs(S1-S2))
print(ans)
"""
"""
P,Q,R=map(int, input().split())
print(min([P+Q, P+R, Q+R]))
"""
MOD=1000000007
N,M=map(int, input().split())
A=set()
for i in range(M):
        A.add(int(input()))

dp=dict()
dp[0]=1
dp[1]=1
def f(i):
        if i in A: return 0
        if i in dp: return dp[i]
        m1=0 if (i-1) in A else f(i-1)
        m2=0 if (i-2) in A else f(i-2)
        dp[i]=(m1+m2) % MOD
        return dp[i]

print(f(N))

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
MOD = 1000000007
def POW(x, y): return pow(x, y, MOD)
def INV(x, m=MOD): return pow(x, m - 2, m)
def DIV(x, y, m=MOD): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())

N,M = LI()

st = set()
for i in range(M):
    st.add(int(input()))

pat1 = 1
pat2 = 0

for i in range(1, N):
    tmp = pat2
    pat2 = pat1
    pat1 = ((pat1 + tmp)%MOD) if not i in st else 0
    
print((pat1+pat2)%MOD)

Solution (Python):
def c_typical_stairs(N, M, A, MOD=10**9 + 7):
    a = set(A)
    stairs = [0] * (N + 100)
    stairs[0] = 1
    for i in range(N):
        if i + 1 <= N and (i + 1) not in a:
            stairs[i + 1] += stairs[i]
        if i + 2 <= N and (i + 2) not in a:
            stairs[i + 2] += stairs[i]
    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):
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 < M 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 < M 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):
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from fractions import gcd
from functools import lru_cache, reduce
from math import ceil, floor
from sys import setrecursionlimit

import heapq as hq
import itertools as its
import operator as op



inf = float('inf')
N = 0


def set_inputs():
    global N
    return


def main():
    setrecursionlimit(100000)
    set_inputs()
    
    n, m = get_li()
    A = get_data(m, [int])
    MOD = 1000000007
    dp = [0] * (n + 2)
    dp[0] = 1
    dp[-1] = 0
    stepable = [True] * (n + 2)
    for a in A:
        stepable[a] = False
    for i in range(1, n + 1):
        if stepable[i]:
            dp[i] = (dp[i-1] + dp[i-2]) % MOD
    print(dp[n])
    return


def get_int():
    return int(input())


def get_float():
    return float(input())


def get_str():
    return input().strip()


def get_li():
    return [int(i) for i in input().split()]


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def get_data(n, types, sep=None):
    if len(types) == 1:
        return [types[0](input().strip()) for _ in range(n)]
    return list(zip(*(
        [t(x) for t, x in zip(types, input().strip().split(sep=sep))]
        for _ in range(n)
    )))


if __name__ == '__main__':
    main()

Solution (Python):
import sys
N,M = map(int, input().strip().split(' '))
broken = set(int(line.strip()) for line in sys.stdin)
p = [0]*(N+2)
p[0] = 1
for i in range(N):
  
  if i in broken:
    continue
  p[i+1] += p[i]
  p[i+2] += p[i]
print(p[N]%1000000007)

Solution (Python):



def solve():
    n, m = map(int, input().strip().split())
    am = set([int(input().strip()) for i in range(m)])
    ans = [0] * (n + 1000)
    ans[0] = 1
    md = (10 ** 9) + 7
    for i in range(n):
        if (i + 1) not in am:
            ans[i + 1] = (ans[i] + ans[i + 1]) % md
        if (i + 2) not in am:
            ans[i + 2] = (ans[i] + ans[i + 2]) % md
    print(ans[n])

if __name__ == "__main__":
    solve()

Solution (Python):
N, M = map(int, input().split())
kaidan = [True] * (N+3)
for i in range(M):
    kaidan[int(input())] = False

dp = [0]*(N+3)
dp[0] = 1
for i in range(N):
    if kaidan[i+2]:
        dp[i+2] += dp[i]
        dp[i+2] %= 1000000007
    if kaidan[i+1]:
        dp[i+1] += dp[i]
        dp[i+1] %= 1000000007

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):
import sys

n, m = list(map(int, input().split()))
aaa = set(map(int, sys.stdin))
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):
MOD = 1000000007

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

T = [0 for _ in range(N + 5)]

for a in A:
    T[a] = -1

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

print(T[N])

Solution (Python):
import bisect
n,m = map(int,input().split())
p = [0]*(n+1)
mod = 10**9+7

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

p[0]=1

for i in range(1,n+1):
  k = bisect.bisect_left(a,i)
  k2 = bisect.bisect_right(a,i)
  if k == k2:
    p[i] += p[i-1]
    if i >= 2:
      p[i] += p[i-2]
    p[i] = p[i]%mod

print(p[-1]%mod)

Solution (Python):
import bisect
from operator import itemgetter
import math
import functools
import itertools
import numpy as np
import sys
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N,M = IL()
a = [I() for i in range(M)]

dp = [0]*(N+1)
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):

import sys
from collections.abc import Iterable
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd

MOD = 1000000007  

def solve(N: int, M: int, a: "List[int]"):
    dp = [0] * (N + 2)
    dp[0] = 1
    a =set(a)

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


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) ]  
    result = solve(N, M, a)
    if isinstance(result, Iterable) and not isinstance(result, str):
        result = '\n'.join([str(v) for v in result])
    print(result)

if __name__ == '__main__':
    main()

Solution (Python):
MOD = 10**9 + 7
n, m = [int(item) for item in input().split()]
a = set([-1]) 
dp = [0] * (n+10)
dp[0] = 1
for i in range(m):
    val = int(input())
    a.add(val)
for i in range(n):
    if i+1 in a and i+2 in a:
        print("0")
        exit()
    elif i+1 in a:
        dp[i+2] += dp[i]
    elif i+2 in a:
        dp[i+1] += dp[i]
    else:
        dp[i+1] += dp[i]
        dp[i+2] += dp[i]
    dp[i+1] %= MOD
    dp[i+2] %= MOD
print(dp[n] % MOD)

Solution (Python):
N, M = list(map(int, input().split(" ")))
A = {int(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):
MOD = 1000000007

A = set()




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

for _ in range(m):
    a = int(input())
    A.add(a)

res = [0]*(n+1)

res[0] = 1
if 1 not in A:
    res[1] = 1

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

print(res[n])

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

for i in range(N):
  if a[i]==-1:
    continue
  if a[i+1]!=-1:
    a[i+1]+=a[i]
    a[i+1]%=MOD
  if i+2<=N and a[i+2]!=-1:
    a[i+2]+=a[i]
    a[i+2]%=MOD
print(max(0,a[N]))

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

bk = set()
for i in range(M):
    bk.update([int(input())])

DP = [0]*N
DP[0] = 1
if 1 not in bk:
    DP[1] = 1

for i in range(2, N):
    if i not in bk:
        DP[i] = DP[i-1] + DP[i-2]


print(DP[-1] % 1000000007)

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

dp = [0]*(N + 1)
dp[0] = 1
for step in range(N):
    if step in a:
        continue
    for width in [1, 2]:
        to = step + width
        if to <= N and not to in a:
            dp[to] = (dp[to] + dp[step]) % MOD

print(dp[N])

Solution (Python):
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

def s(generator, splitter, mapper):
    return [ mapper(s) for s in generator().split(splitter) ]


def get_nums_l():
    return [ int(s) for s in input().split(" ")]


def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

MOD = 1000000007

n,m = get_nums_l()
breaks = map(int, sys.stdin.readlines()) if m>0 else []

dp = [0] * (n+1)

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

dp[n] = 1

for i in range(n-1, -1, -1):
    if dp[i] == -1:
        continue
    
    x = 0
    if dp[i+1] != -1:
        x += dp[i+1]
    
    if i <= (n-2) and dp[i+2] != -1:
        x += dp[i+2]
    
    dp[i] = x % MOD

print(dp[0])

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

s = [-1 for i in range(n + 1)]
s[0] = 1
s[1] = 1

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

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

print(s[n])

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

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

mod = 10**9+7

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

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

print(max(dp[n],0))

Solution (Python):
nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

N, M = nl()
A = set()
for i in range(M):
    A.add(n())

dp = [0] * (N+1)
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]
    dp[i] %= 1000000007

print(dp[N])

Solution (Python):
read = input 
rn = lambda :list(map(int, read().split()))
n, m  = rn()
M = []
P = 1000000007
for i in range(m):
    M.append(int(read()))
M = set(M)
dp = [0 for i in range(n + 1000)]
dp[0] = 1
for i in range(n+1):
    for nxt in range(i+1, i+3):
        if(nxt not in M):
            dp[nxt] += dp[i]
            dp[nxt] %= P
print(dp[n])

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

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

def main():
    N, M = LI()
    A = []
    for _ in range(M):
        A.append(II())
    A.append(INF)
    dp = [0] * (N + 1)
    dp[0] = 1
    k = 0
    if A[0] == 1:
        dp[1] = 0
        k = 1
    else:
        dp[1] = dp[0]
    for i in range(2, N + 1):
        if i == A[k]:
            k += 1
            dp[i] = 0
        else:
            dp[i] = (dp[i - 1] + dp[i - 2]) % MOD
    ans = dp[N]
    return ans

print(main())

Solution (Python):
n, m = list(map(int, input().split(' ')))
arr  = set()
for _ in range(m):
    x = int(input())
    arr.add(x)


MOD = int(1e9) + 7

w = [0 for _ in range(n + 1)]
w[0] = 1
for i in range(1, n+1):
    if i in arr:
        continue

    if i - 1 >= 0 and i - 1 not in arr:
        w[i] += w[i-1]

    if i - 2 >= 0 and i - 2 not in arr:
        w[i] += w[i-2]
    
    w[i] %= MOD



print(w[n])

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

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

dp = [0]*(N+4)
dp[0] = 1
for a in A:
    dp[a] = -1

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

print(dp[N])

Solution (Python):
import collections as c
ip = lambda : map(int, input().split())

mod = 1e9+7
N,M = ip()
a = set()
for i in range(M):
    a.add(int(input()))
dp = [0]*(N+1)
dp[0] = 1
if 1 in a:
    pass
else:
    dp[1] = dp[0]
if N>1:
    for i in range(2,N+1):
        if i in a:
            continue
        dp[i] += dp[i-2] + dp[i-1]
        dp[i] = int(dp[i] % mod)
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] * (N + 100)
dp[0] = 1
not_use = [False] * (N + 100)
for a in a_list:
    not_use[a] = True

for i in range(N+1):
    not_u = not_use[i]
    if not_u:
        continue
    else:
        dp[i + 1] += dp[i]
        dp[i + 1] %= mod
        dp[i + 2] += dp[i]
        dp[i + 2] %= mod

print(dp[N] % mod)

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

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, log2
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

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()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

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

dp = [0]*(N+2)
dp[0] = 1
if b[1] == 1:
	dp[1] = 0
else:
	dp[1] = 1


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

print(dp[N])

Solution (Python):


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

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

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



print(acc[-1]%1000000007)

Solution (Python):


MOD =  1000000007

def f(N, A):
    A.append(-1)

    a = A.pop(0)

    c0 = 0
    c1 = 1

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

        if i == a:
            c1 = 0
            a = A.pop(0)

    return c1
            


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

    print(f(N, A))


if __name__ == '__main__':
    main()

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

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):
import sys
from collections import deque
from collections import defaultdict
import math
sys.setrecursionlimit(20000000)
input = sys.stdin.readline
n,m = map(int,input().split())
a = [int(input()) for i in range(m)]
a = set(a)
mod = 10**9+7
dp = [0]*(n+5)
dp[0] = 1
for i in range(1,n+1):
        if i in a:
                continue
        dp[i] = dp[i-1] + dp[i-2]
        dp[i] %= mod
print(dp[n]%mod)

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

Solution (Python):
import numpy as np
import math
import sys
sys.setrecursionlimit(10000000)

def main():
    N, M = map(int, input().split())
    A = [0] * (N + 1)
    for i in range(M):
        bre = int(input())
        A[bre] = -1
    A[0] = 1
    A[1] = 1 if A[1] != -1 else -1
    
    for i in range(N):
        if (A[i] == -1) & (A[i + 1] == -1):
            print(0)
            sys.exit()

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

if __name__ == '__main__':
    main()

Solution (Python):

n,m = map(int, input().split())
a = set([int(input()) for _ in range(m)])
MOD = 1000000007

dp = [0]*(n+2)
dp[0] = 1
for i in range(n):
    if i+1 not in a:
        dp[i+1] += dp[i]
        dp[i+1] %= MOD
    if i+2 not in a:
        dp[i+2] += dp[i]
        dp[i+2] %= MOD

print(dp[n])

Solution (Python):
N, M = list(map(int, input().split()))
V = 10 ** 9 + 7
a = [int(input()) for _ in range(M)]
A = set(a)
ANS = [0 for _ in range(100000 + 5)]

ANS[0] = 1
for i in range(N):
    
    if not i + 1 in A:
        ANS[i + 1] += ANS[i]
        
    if not i + 2 in A:
        ANS[i + 2] += ANS[i]
        
print(ANS[N] % V)

Solution (Python):
import sys
input=sys.stdin.readline
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
    memo[1]=1 if is_breake[1]==0 else 0
    for n in range(2,N+1):
        if is_breake[n]:
            memo[n] =0
            
        else:
            memo[n]=(memo[n-2]+memo[n-1])%DIV
    return memo[-1]

print(main())

Solution (Python):


import sys
sys.dont_write_bytecode = True
stdin = sys.stdin
input = stdin.readline
sys.setrecursionlimit(1000000000)






import math, itertools, operator
from math import *
from math import factorial as fact
from operator import itemgetter, attrgetter
from itertools import permutations, combinations
from functools import reduce, lru_cache


from fractions import gcd
from fractions import Fraction as Frac

inf = float('inf')

def lcm(a, b):
    return a * b // gcd(a,b)

def perm(a, b):
    import scipy.special
    return scipy.special.perm(a, b, exact = True)

def comb(a, b):
    import scipy.special
    return scipy.special.comb(a, b, exact = True)

def dfact(n):
    import scipy.special
    return scipy.special.factorial2(n, exact = True)

def prod(l):
    return reduce(operator.mul, l)

def input_ints(func = input, sep = None, conv = int):
    return list(map(conv, func().split(sep = sep)))



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


BROKEN = [False for i in range(N)]
for a in A:
    BROKEN[a] = True

@lru_cache()
def dp(cur):
    if cur > N:
        return 0
    if cur == N:
        return 1
    if BROKEN[cur]:
        return 0
    return dp(cur + 1) + dp(cur + 2)

print(dp(0) % 1000000007)

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

MOD = 1000000007

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

p[N] = 1
if p[N-1] != -1:
    p[N-1] = 1

for i in range(N-2, -1, -1):
    if p[i] == -1:
        continue
    if p[i+1] == -1 and p[i+2] == -1:
        p[i] = -1
    elif p[i+1] == -1:
        p[i] = p[i+2]
    elif p[i+2] == -1:
        p[i] = p[i+1]
    else:
        p[i] = p[i+1] + p[i+2]

    if p[i] > 0:
        p[i] %= MOD

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

print(ans)

Solution (Python):

def ispossible(a):
    d = [a[i] - a[i-1] for i in range(1, len(a))]
    return not 1 in d


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

    MOD = 10**9+7

    if not ispossible(a):
        print(0)
        return

    s = [1] * (N+1)

    a = set(a)

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

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

        s[i] = 0
        if i-1 not in a:
            s[i] += s[i-1] % MOD
        if i-2 not in a:
            s[i] += s[i-2] % MOD
        

    print(s[N] % MOD)


if __name__ == '__main__':
    main()

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

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

tmp = [0 for _ in range(n + 1)]
tmp[0] = 1

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


print(tmp[-1] % 1000000007)

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

dp = [0] * (N+3)
dp[0] = 1
for i in range(M):
    dp[broken[i]] = -1 * float('inf')

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

print(dp[N] % mod)