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 = [int(input()) for _ in range(m)]
fibo = [1,1]
ans = 1

for i in range(n):
            fibo.append((fibo[-1]+fibo[-2])%1000000007)

if m:
    r = [a[0]-1]

    for i in range(m-1):
        r.append((a[i+1]-a[i])-2)
        if a[i+1]-a[i] == 1:
            print(0)
            exit()

    else:
        r.append(n-a[-1]-1)

        for i in range(len(r)):
            ans = (fibo[r[i]] * ans)%1000000007

        print(ans)
else:
    print(fibo[n])

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    N, M = map(int, input().split())
    a = [0] * (1 + 10 ** 5)
    for _ in range(M):
        a[int(input())] = 1
    dp = [0] * (N + 1)
    dp[0] = 1
    if a[1]:
        pass
    else:
        dp[1] = 1

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

    print(dp[N])

main()

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    N, M = map(int, input().split())
    a = [0] * (1 + 10 ** 5)
    for _ in range(M):
        a[int(input())] = 1
    dp = [0] * (N + 1)
    dp[0] = 1
    if not a[1]:
        dp[1] = 1

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

    print(dp[N])

main()

Solution (Python):
def main():
    N, M = map(int, input().split())
    a = [0] * (1 + 10 ** 5)
    for _ in range(M):
        a[int(input())] = 1
    dp = [0] * (N + 1)
    dp[0] = 1
    if not a[1]:
        dp[1] = 1

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

    print(dp[N])

main()

Solution (Python):
def main():
    N, M = map(int, input().split())
    a = set(int(input()) for _ in range(M))
    dp = [0] * (N + 1)
    dp[0] = 1
    if 1 not in a:
        dp[1] = 1

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

    print(dp[N])

main()

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

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

print(dp[N])

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

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

print(dp[N])

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

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

print(dp[N])

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

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

print(dp[N])

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

for i in range(2, N + 1):
    for k in [-2, -1]:
        if i + k not in a:
            dp[i] += dp[i+k]

print(dp[N] % 1000000007)

Solution (Python):
N, M = map(int, input().split())
ans = ["0"]*(N+2)
ans[0] = 0
ans[1] = 1
mod = 10**9 + 7

for _ in range(M):
  a = int(input())
  ans[a+1] = 0

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

print(ans[-1])

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

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

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

Solution (Python):
def resolve():
    import sys
    input = sys.stdin.readline
    
    
    
    n, m = map(int, input().split())
    
    A = [int(input()) for i in range(m)]
    
    
    
    

    Route = [0] * (n+1)
    Route[0] = 1
    MOD = 10**9 + 7

    is_safe = [True] * (n+1)
    for a in A:
        is_safe[a] = False

    if is_safe[1] == True:
       Route[1] = 1

    for i in range(2, n+1):
        if is_safe[i] == True:
            Route[i] = (Route[i-1] + Route[i-2]) % MOD


    print(Route[n])

resolve()

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+2)
    for a in A:
        is_safe[a+1] = False

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

    return dp[N+1]


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

Solution (Python):
n, m = map(int, input().split())
w = [1 for _ in range(n+1)]
for _ in range(m):
    w[int(input())] = 0
for i in range(2, n+1):
    if w[i] != 0:
        w[i] = w[i-2] + w[i-1]

print(w[-1] % 1000000007)

Solution (Python):
n, m = map(int, input().split())
aaa = [0] * (n + 1)
for _ in range(m):
    aaa[int(input())] = 1
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 0 if aaa[1] == 1 else 1
for i in range(2, n + 1):
    if aaa[i] == 1:
        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 = set([int(input()) for _ in range(M)])

mod = 1000000007

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

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

print(dp[0] % mod)

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

dp = [0 for _ in range(N+1)]
dp[0] = 1
if 1 not in broken:
  dp[1] = 1

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

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

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

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

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
large_p = 10**9 + 7
a = []
kazu_memo = {}
kazu_tmp = 0
def f(target_step):
    global kazu_memo, kazu_tmp
    
    if target_step < 0:
        return 0
    else:
        if kazu_memo[target_step] >= 0:
            return kazu_memo[target_step]
        else:
            kazu_tmp = (f(target_step - 1) + f(target_step - 2)) % large_p
            kazu_memo[target_step] = kazu_tmp
            return kazu_tmp

def main():
    global a, kazu_memo
    n, m = map(int, input().split())
    kazu_memo = {e: -1 for e in range(0, n + 1)}
    kazu_memo[0] = 1
    for _ in range(m):
        ta = int(input())
        kazu_memo[ta] = 0

    r = f(n)
    print(r % large_p)


if __name__ == '__main__':
    main()

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

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

mod = 1000000007

A = []
for i in range(M):
    A.append(int(input()))
A=set(A)
    
DP = [0]*(N+2)
DP[1] = 1

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

print(DP[N+1]%mod)

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

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

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

for _ in range(M):
    a = int(input())
    oks[a] = False

dp = [1] + [0] * N
for now in range(N):
    for nxt in range(now+1, min(N, now+2)+1):
        if oks[nxt]:
            dp[nxt] += dp[now]
            dp[nxt] %= 1e9 + 7

print(int(dp[N]))

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

P = [-1] * (N+1)
P[0] = 1
P[1] = 1
flg=False
MOD = 10**9 + 7
for i in range(2, N+1):
    if i in a:
        continue
    if (i-1 not in a) and (i-2 not in a):
        P[i] = (P[i-1] + P[i-2]) % MOD
    elif i-1 not in a:
        P[i] = P[i-1] % MOD
    elif i-2 not in a:
        P[i] = P[i-2] % MOD
    else:
        flg=True
if flg:
    print(0)
else:
    print(P[N] % MOD)

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

P = [-1] * (N+1)
P[0] = 1
P[1] = 1
flg=False
MOD = 10**9 + 7
for i in range(2, N+1):
    if i-1 not in a:
        P[i] = P[i-1]
    if i-2 not in a:
        if P[i] != -1:
            P[i] += P[i-2] % MOD
        else:
            P[i] = P[i-2] % MOD
    if P[i]==-1:
        flg=True
        break
if flg:
    print(0)
else:
    print(P[N] % MOD)

Solution (Python):
import sys
sys.setrecursionlimit(int(1e6))

n,m=map(int,input().split())
memo=[-1]*(n+1)
memo[0]=1
memo[1]=1
for i in range(m):
    memo[int(input())]=-2
def dp(i): 
    if memo[i]==-2:
        return 0
    elif memo[i]==-1:
        s=dp(i-1)
        if i>=2:
            s+=dp(i-2)
        memo[i]=s%(10**9+7)
        return memo[i]
    else:
        return memo[i]
print(dp(n))

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

mod = 10**9 + 7
for i in range(m):
    dp[int(input())] = -1 

dp[0] = 0 

dp[1] = 1 if dp[1] != -1 else -1 
dp[2] = -1 if dp[2] == -1 else (1 if dp[2] != -1 and dp[1] == -1 else 2) 
for i in range(3,n+1):
    if dp[i] != -1 and dp[i-1] != -1:
        dp[i] += dp[i-1]
        dp[i] %= mod
    if i > 1:
        if dp[i] != -1 and dp[i-2] != -1:
            dp[i] += dp[i-2]
            dp[i] %= mod

print(dp[n]%mod)

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

dp = [0] * (n+1)
dp[0] = 1
acounter = 0
if a[0] == 1:
  dp[1] = 0
  acounter = 1
else:
  dp[1] = 1

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

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

dp = [0 for _ in range(N+1)]
dp[0] = 1
if 1 not in broken:
  dp[1] = 1

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

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
from collections import defaultdict
from collections import deque
from functools import lru_cache






MOD = 10**9+7
INF = float('inf')






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)



def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


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


def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i])*n**i for i in range(len(str(X))))


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count





N,M = IL()
A = ILs(M)[::-1]

d = [0 for i in range(N+1)]
d[0] = 1
for i in range(1,N+1):
  if A:
    if i == A[-1]:
      A.pop()
    else:
      if i>1:
        d[i] = d[i-1] + d[i-2]
      else:
        d[i] = d[i-1]
  else:
    if i>1:
      d[i] = d[i-1] + d[i-2]
    else:
      d[i] = d[i-1]
print(d[N]%MOD)

Solution (Python):
N, M = map(int, input().split())
a_n = [int(input()) for i in range(M)]
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
now = 0
before = -9999
answer = 1

for a in a_n:
    if a - before == 1:
        answer = 0
        break

    answer *= Fib( a - 1 - now + 2 )
    answer %= 1000000007
    now = a + 1
    before = a

if answer > 0:
    answer *= Fib( N - now + 2)
    answer %= 1000000007

print(answer)

Solution (Python):

import sys
try:
    from typing import List
except ImportError:
    pass

MOD = 1000000007  


def solve(N: int, M: int, a: "List[int]"):
    sa = set(a)
    dp = [0] * (N + 1)
    dp[0] = 1
    for i in range(1, N + 1):
        if i in sa:
            continue
        c = dp[i - 1]
        if i >= 2:
            c += dp[i - 2]
        dp[i] = c % MOD
    print(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)]  
    solve(N, M, a)


if __name__ == '__main__':
    main()

Solution (Python):
def Fib(n, memo={}):
    if n < 2:
        return 1
    elif n in memo:
        return memo[n]
    else:
        memo[n] = Fib(n - 1, memo) + Fib(n - 2, memo)
        return memo[n]


def resolve():
    N, M = [int(i) for i in input().split()]
    aa = []
    for _ in range(M):
        aa.append(int(input()))
    fib_l = list(Fib(i) for i in range(N + 1))

    ans = 1
    now = 0
    for a in aa:
        if now == a:
            ans = 0
            break
        tmp = a - now - 1
        ans = ans * fib_l[tmp]
        now = a + 1
    else:
        ans = ans * fib_l[N - now]
    print(ans % (10**9 + 7))


resolve()

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

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

broken = [[] for i in range(n+1)]

for i in a:
    broken[i] = 1

dp = [0 for i in range(n+2)]

mod = 1000000007

dp[n] = 1

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

print(dp[0])

Solution (Python):
N,M=map(int,input().split())
dp=[1]*N
listA=[]
for i in range(M):
  a=int(input())
  listA+=[a]
  dp[a-1]=0
setA=set(listA)    
if (1 not in setA) and (2 not in setA) and N!=1:
  dp[1]=2
for i in range(2,N):
  if i+1 not in setA:
    dp[i]=dp[i-1]+dp[i-2]
ans=dp[-1]%(10**9+7)
print(ans)

Solution (Python):
import sys
N,M=map(int,input().split())
dp=[1]*N
listA=[]
for i in range(M):
  a=int(input())
  listA+=[a]
  dp[a-1]=0
for i in range(1,M):
  if listA[i]==listA[i-1]:
    print(0)
    sys.exit()
setA=set(listA)    
if (1 not in setA) and (2 not in setA) and N!=1:
  dp[1]=2
for i in range(2,N):
  if i+1 not in setA:
    dp[i]=dp[i-1]+dp[i-2]
ans=dp[-1]%(10**9+7)
print(ans)

Solution (Python):
n, m = map(int, input().split())
a = set([0] + [int(input()) for _ in range(m)])
MOD = 10 ** 9 + 7

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

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

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

print(dp[-1])

Solution (Python):

N, M = map(int, input().split())
a = []
a_append = a.append

for n in range(M):
    a_append(int(input()))

mod = 1000000007


check = [True] * (N + 1)
for i in a:
    check[i] = False

dp = {0: 1}
if check[1] is True:
    dp[1] = 1
else:
    dp[1] = 0

for n in range(2, N + 1):
    dp[n] = 0
    if check[n - 1] is True:
        dp[n] += dp[n - 1]
    if check[n - 2] is True:
        dp[n] += dp[n - 2]
    dp[n] %= mod

print(dp[N])

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

ok = [True] * (n + 1)
for v in a:
    ok[v] = False

dp = [0] * (n + 1)
dp[0] = 1
if 1 in a:
    dp[1] = 0
else:
    dp[1] = 1
MOD = 10 ** 9 + 7

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

print(dp[-1])

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

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

b=[-1]*(n+2)

def delta_n(ii):
  if b[ii]>=0:
    return b[ii]

  if ii>n or ii in a:
    r=0
  elif ii==n:
    r=1
  else:
    r=delta_n(ii+1)+delta_n(ii+2)
  
  b[ii]=r
  return r

print(delta_n(0)%(7+10**9))

Solution (Python):
n, m = map(int, input().split())
mod = 10 ** 9 + 7
dp = [-1 for i in range(n + 1)]
dp[0], dp[1] = 1, 1
for _ in range(m):
    dp[int(input())] = 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 itertools,sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,M = LI()
a = set([I() for _ in range(M)])
dp = [0]*(N+1) 
dp[0] = 1
dp[1] = 0 if 1 in a else 1
for i,j in itertools.product(range(2,N+1),[1,2]):
    if i in a:
        dp[i] = 0
        continue
    dp[i] += dp[i-j]
    dp[i] %= 10**9+7
print(dp[-1])

Solution (Python):

import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
N, M = LI()
A = [I() for _ in range(M)]
md = 10**9+7


dp = [0] * (N+1)
dp[0] = 1
chk = [True] * (N+1)
for a in A:
  chk[a] = False

for now in range(N):
  for next in range(now+1, now+3):
    if next == N:
      dp[next] += dp[now]
      dp[next] %= md
      break
    if not chk[next]:
      continue
    else:
      dp[next] += dp[now]
      dp[next] %= md

print(dp[N])

Solution (Python):
import math

MOD = int(math.pow(10, 9)) + 7
N, M = map(int, input().split(' '))
broken_steps = {int(input()) for _ in range(M)}

dp = [0] * (N + 1)

dp[0] = 1
if 1 not in broken_steps:
    dp[1] = 1

for step in range(2, N + 1):
    if step not in broken_steps:
        dp[step] = (dp[step - 1] + dp[step - 2]) % MOD

print(dp[N])

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

dp = [0] * (n + 2)
dp[0] = 1
if stair[1]:
    dp[1] = 1

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

print(dp[n])

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


def resolve():
    N, M = map(int, input().split())

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

    for _ in range(M):
        broken[int(input())] = True

    for i in range(1, N + 1):
        if broken[i]:
            continue

        if i == 1:
            dp[i] = dp[i - 1]
        else:
            dp[i] = dp[i - 1] + dp[i - 2]
            dp[i] %= MOD

    print(dp[N])


resolve()

Solution (Python):
def main():
    MOD = 1000000007
    N, M = map(int, input().split())
    a = [int(input()) for _ in range(M)]
    table = [1]*(N+1)
    for broken in a:
        table[broken] = 0
    table[1] = table[0] * table[1]
    if N > 1:
        for n in range(2, N+1):
            table[n] = ((table[n-2] + table[n-1]) * table[n]) % MOD
    print(table[-1])
main()

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

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

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

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

dp=[0]*(n+1)

dp[0]=1
if 1 not in mList:
  dp[1]=1

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











print(dp[n])

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

dp=[0]*(n+1)
dp[0]=1
if 1 not in mList:
  dp[1]=1

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

print(dp[n])

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

for i in range(n):
    if dp[i + 1] >= 0 and dp[i] >= 0:
        dp[i + 1] += dp[i]
    if i >= 1 and dp[i + 1] >= 0 and dp[i - 1] >= 0:
        dp[i + 1] += dp[i - 1]

print(dp[-1] % 1000000007)

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

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

Solution (Python):
n,m = map(int,input().split())
a = [int(input()) for i in range(m)]
step_patern = [0,1]
for i in range(n):
         step_patern.append(step_patern[i] + step_patern[i+1])
kankaku = []
tmp = 0
for i in range(len(a)):
         kankaku.append(a[i] - tmp)
         tmp = a[i] +1
kankaku.append(n + 1 - tmp)
ans = 1
for i in kankaku:
         ans *= step_patern[i]
         ans %= (10 ** 9) +7
print(ans)

Solution (Python):
from collections import Counter 
from collections import defaultdict
from collections import deque
import math
import itertools
import heapq
import sys
sys.setrecursionlimit(10**6)




input_list = lambda : list(map(int,input().split()))

n,m=input_list()
c=[True for _ in range(n+1)]
mod=10**9+7

for _ in range(m):
    num=int(input())
    c[num]=False

fib=[1,1]
if not c[1]:
    fib[1]=0

for i in range(2,n+1):
    if c[i]:
        fib.append((fib[i-1]+fib[i-2])%mod)
    else:
        fib.append(0)


print(fib[-1]%mod)

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

Solution (Python):
import itertools
import math
import fractions
import functools
import copy

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

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

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

A = [int(input().strip()) for _ in range(m)]

a0 = 1
if len(A) == 0:
  a1 = 1
else:
  a1 = 1 if A[0] !=1 else 0
mod = 1000000007

ANS=[0]*(n+1)
ANS[0]=a0
ANS[1]=a1
Next = A if a1 !=0 else A[1:]
next = 0
for i in range(2, n+1):
    if next <= len(Next)-1:
        if i == Next[next]:
            ANS[i] = 0
            next += 1
            continue
    ANS[i] = ANS[i-2] + ANS[i-1]

print(ANS[n]%mod)

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

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

Solution (Python):
n, m = map(int, input().split())
a = [int(input()) for i in range(m)]
broken = [True] * n
for i in a:
    broken[i] = False
dp = [0] * (n + 1)
dp[0] = 1
for i in range(n):
    for j in range(i + 1, min(n + 1, i + 3)):
        if broken[i]:
            dp[j] += dp[i]
            dp[j] %= (10 ** 9 + 7)
print(dp[n])

Solution (Python):
"""
N段の階段 M個の階段が壊れている
"""

N, M = map(int, input().split())
arr = [int(input()) for _ in range(M)]
no_step =[0]*N

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

for i in range(M):
    no_step[arr[i]-1]=1

count = [0]*N
if no_step[0]==0:
    count[0]=1

if no_step[1]==1:
    count[1]=0
elif no_step[0]==0 and no_step[1]==0:
    count[1]=2
elif no_step[0]==1 and no_step[1]==0:
    count[1]=1

for i in range(3,N+1,1):
    count[i-1] = count[i-2]+count[i-3]
    if no_step[i-1] == 1:
        count[i-1] = 0

ans =count[N-1]%1000000007
print(ans)

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

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

for _ in range(M):
  broken.add(int(input()))


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

for i in range(N):
  if i in broken:
    continue
    
  for step in (1, 2):
    if i + step <= N:
      table[i + step] += table[i]
      table[i + step] %= P

print(table[N])

Solution (Python):
import sys

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


a = [-1]

for i in range(M):
    a.append(int(input()))
    
    if a[i+1] - a[i] == 1:
        print(0)
        sys.exit()
        

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


combi = 1

for i in range(len(a) - 1):
    
    dis = a[i+1] - a[i]
    combi *= fib(dis)

dis = N+1 - a[-1]
combi *= fib(dis)

print(combi % 1000000007)

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

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

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,min(N,i+2)+1):
    if ok[j]:
      dp[j] += dp[i]
      dp[j] %= p
      
print(dp[N]%p)

Solution (Python):
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+1 not in a:
        dp[i+1] += dp[i]
    if i<n-1 and i+2 not in a:
        dp[i+2] += dp[i]
print(dp[-1]%(10**9+7))

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

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9 + 7
input = sys.stdin.readline

def inp():
    return int(input())
def inpl():
    return list(map(int,input().split()))
def inpm():
    return map(int,input().split())

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


dp[0] = 1

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

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

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

dp = [0] * (n + 1)
dp[0] = 1
dp[1] = int(1 not in a)

mod = 10**9 + 7

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

print(dp[-1] % mod)

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

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