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):
MOD = 10 ** 9 + 7
N, M = map(int, input().split())
table = [0] * (N + 1)
table[0] = 1
banned = [0] * (N + 1)
for _ in range(M):
    banned[int(input())] = 1
for i in range(N + 1):
    now = table[i]
    if i + 1 < N + 1 and not banned[i + 1]:
        table[i + 1] = (table[i + 1] + now) % MOD
    if i + 2 < N + 1 and not banned[i + 2]:
        table[i + 2] = (table[i + 2] + now) % MOD
print(table[N])

Solution (Python):
MOD = 10 ** 9 + 7
N, M = map(int, input().split())
table = [0] * (N + 1)
table[0] = 1
banned = [0] * (N + 1)
for _ in range(M):
    banned[int(input())] = 1
for i in range(N + 1):
    now = table[i]
    if i + 1 < N + 1 and not banned[i + 1]:
        table[i + 1] = (table[i + 1] + now) % MOD
    if i + 2 < N + 1 and not banned[i + 2]:
        table[i + 2] = (table[i + 2] + now) % MOD
print(table[N])

Solution (Python):
mod = 1000000007

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

memo = [0]*(n+1)

memo[0] = 1

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

Solution (Python):
A,B=map(int,input().split())
DP=[float("INF")]*(A+1)
DP[0]=1
for i in range(B):
   DP[int(input())]=0
for i in range(A):
   if i==0:
      DP[i+1]=min(DP[i+1],DP[0])
   else:
      DP[i+1]=min(DP[i+1],DP[i]+DP[i-1])
print(DP[-1]%(10**9+7))

Solution (Python):
MOD = 1000000007

n, m = [int(i) for i in input().split()]
oks = [True] * (n + 1)
for i in range(m):
    a = int(input())
    oks[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 not oks[j]:
            continue
        dp[j] += dp[i]
        dp[j] %= MOD

print(dp[n])

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

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

print(dp[N])

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

st = [1] * (N+1)

for i in range(M):
    x = int(input())
    st[x] = 0


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


print(st[-1] % 1000000007)

Solution (Python):

import sys

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, M = map(int, readline().split())
A = list(map(int, readlines()))
assert len(A) == M

MOD = 10 ** 9 + 7


def solve():
    broken = [False] * (N + 1)
    for a in A:
        broken[a] = True
    p1, p2 = 1, 0
    for i in range(1, N + 1):
        if broken[i]:
            p1, p2 = 0, p1
        elif i == 1:
            p1, p2 = p1, p1
        else:
            p1, p2 = (p1 + p2) % MOD, p1
    return p1


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

Solution (Python):

import sys

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, M = map(int, readline().split())
A = list(map(int, readlines()))
assert len(A) == M

MOD = 10 ** 9 + 7


def solve():
    broken = [False] * (N + 1)
    for a in A:
        broken[a] = True

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


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

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

k = 1000000007


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

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



print(dp[-1])

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

k = 1000000007


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

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

n = dp[-1] % k

print(n)

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

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

s = [1]*(n+1)

if 1 in a:
    s[1] = 0

for i in range(n-1):
    if i+2 in a:
        s[i+2] = 0
        continue
    s[i+2] = (s[i+1] + s[i]) % (10**9+7)
    
print(s[-1])

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

s = [1]*(n+1)

if 1 in a:
    s[1] = 0

for i in range(n-1):
    if i+2 in a:
        s[i+2] = 0
        continue
    s[i+2] = (s[i+1] + s[i]) % (10**9+7)
    
print(s[-1])

Solution (Python):
import sys
input = sys.stdin.readline
N,M = map(int,input().split())
lst=[int(input()) for i in range(M)]
t=0
ans=[0]*(N+1)
ans[0]=1
for j in range(N):
 if M!=0:
  if lst[t]==j+1:
   ans[j+1]=0
   t+=1
   t=min(M-1,t)
  else:
   ans[j+1]+=ans[j]
   if j!=0:
    ans[j+1]+=ans[j-1]
   ans[j+1]%=(10**9+7)
 else:
  ans[j+1]+=ans[j]
  if j!=0:
   ans[j+1]+=ans[j-1]
  ans[j+1]%=(10**9+7)
print(ans[N])

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

Solution (Python):
n, m = map(int, input().split())
MOD = 10**9+7

a = [True]*(n+1)

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

dp = [0]*(n+1)

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

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

print(dp[n])

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

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

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

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

print(dp[-1] % mod)

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

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

if dp[n] == -1:
    print(0)
else:
    print(dp[n])

Solution (Python):
import numpy as np


def main():
    MOD = 10**9 + 7
    N, M = list(map(int, input().split(' ')))
    broken = np.zeros(N + 1)
    for _ in range(M):
        a = int(input())
        broken[a] = 1
    dp = np.zeros(N + 1)
    dp[0] = 1
    for i in range(1, N + 1):
        dp[i:(i + 2)] += dp[i - 1] * (1 - broken[i:(i + 2)])
        dp[i:(i + 2)] %= MOD
    print(int(dp[N]))


if __name__ == '__main__':
    main()

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

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

dp_table = [0] * (n+1)

dp_table[0] = 1



j = 0
for i in range(1,n+1):
    if j < m and i == a[j]:
        dp_table[i] = 0 
        j += 1
    elif i == 1:
        dp_table[i] = dp_table[i-1]
    else:
        dp_table[i] = dp_table[i-1] + dp_table[i-2]

print(dp_table[-1] % 1000000007)

Solution (Python):
e=10**9+7
n,m=map(int,input().split())
l=[]
d={}
for i in range(m):
    d[int(input())]=0
k=[0]*(n+1)
k[0]=1
for i in range(1,n+1):
    if i==1:
        try:
            c=d[i]
        except:
            k[i]=1
    else:
        try:
            c=d[i]
        except:
            k[i]=(k[i-1]+k[i-2])%e
print(k[-1])

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

MOD = 10 ** 9 + 7

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

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

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

print(dp[n])

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

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


dp = [0 for i in range(N+1)]
for item in a:
    dp[item]=-1
dp[0]=1
if 1 in a:
    dp[1] = 0
else:
    dp[1] = 1

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

print(dp[-1])

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

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

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

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

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

print(dp[n])

Solution (Python):

n, m = map(int, input().split())
a = [1] * (n + 1)
b = [1] * (n + 1)

for i in range(m):a[int(input())] = 0
mod = 1e9+7

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

Solution (Python):
N,M=map(int,input().split())
a=set()
mod=1000000007
for _ in range(M):
    aa=int(input())
    a.add(aa)
dp=[0]*(N+2)
dp[0]=1
for i in range(0,N):
    if i in a:
        continue
    else:
        dp[i+1]+=dp[i]
        dp[i+2]+=dp[i]
print(dp[N]%mod)

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

mod = 1000000007

dp=[0]*(n+1)

dp[0]=1
dp[1]=1
d={}
for j in range(n+1):
    d[j]=0

for _ in range(m):
    s = int(input())
    d[s]=1
    dp[s]=0

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

print(dp[-1]%mod)

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

mod = 1000000007

dp=[0]*(n+1)

dp[0]=1
dp[1]=1
d={}
for j in range(n+1):
    d[j]=0

for _ in range(m):
    s = int(input())
    d[s]=1
    dp[s]=0

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

print(dp[-1]%mod)

Solution (Python):




n, m = map(int,input().split())
sav_a = -1
ans = 0
a = [0] * (n+1)
imp_flg = False
for i in range(m):
    ia = int(input())
    a[ia] = 1
    if sav_a + 1 == ia:
        imp_flg = True
    sav_a = ia

dp = [0] * (n+1)

if imp_flg != True and n > 1:
    dp[1] = 1
    dp[2] = 2
    if a[1] == 1:
        dp[1] = 0
        dp[2] = 1
    if a[2] == 1:
        dp[2] = 0

    for i in range(3, n+1):
        if a[i] == 0:
            dp[i] = (dp[i-1] + dp[i-2]) % (10**9+7)
elif n == 1:
    dp[1] = 1


print(dp[n])

Solution (Python):
def typical_stairs(n, m, ali):

    mod = 10**9+7
    flag = [True]*(n+1)
    for i in ali:
        flag[i] = False

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

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

    return dp[i]

def main():
    n, m = map(int, input().split())
    ali = [int(input())for i in range(m)]
    print(typical_stairs(n, m, ali))

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 + 1)
dp[0] = 1
for i in range(1, N + 1):
    if not i in A:
         dp[i] = (dp[i - 1] + dp[i - 2]) % mod
print(dp[-1] % mod)

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 in range(2,N+1):
    if i in a:
        dp[i] = 0
        continue
    dp[i] = (dp[i-1]+dp[i-2])%(10**9+7)
print(dp[-1])

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

broken = [0] * (n + 1)
for i in a:
    broken[i] = 1

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

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] = 1
for i in range(N+1):
    if i in a:
        dp[i] = 0
        continue
    if i-2>=0:
        dp[i] = (dp[i-1]+dp[i-2])%(10**9+7)
print(dp[-1])

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 in range(2,N+1):
    if i in a:
        dp[i] = 0
        continue
    dp[i] = (dp[i-1]+dp[i-2])%(10**9+7)
print(dp[-1])

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 in range(N+1):
    if i in a:
        dp[i] = 0
        continue
    if i-2>=0:
        dp[i] = (dp[i-1]+dp[i-2])%(10**9+7)
print(dp[-1])

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 in range(1,N+1):
    if i in a:
        dp[i] = 0
        continue
    if i-2>=0:
        dp[i] = (dp[i-1]+dp[i-2])%(10**9+7)
print(dp[-1])

Solution (Python):

import sys  
sys.setrecursionlimit(500*500)

D = 1000000007
n, m = map(int, input().split())
a = [0] * (10**5 + 1)
for i in range(m):
    a[int(input())] += 1


s0 = 1
if (a[1] == 1):
    s1 = 0
else:
    s1 = 1


def calc(l, acc1, acc2):
    
    if (l == 1):
        return acc2
    else:
        oldacc2 = acc2
        acc2 = (acc1 + acc2) % D if a[n - l + 2] == 0 else 0
        acc1 = oldacc2
        return calc(l - 1, acc1, acc2)


print(calc(n, s0, s1))

Solution (Python):

D = 1000000007
n, m = map(int, input().split())
a = [0] * (10**5 + 1)
for i in range(m):
    a[int(input())] += 1


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




def calc(n):
    if(a[n] == 1):
        return 0
    else:
        return (s[n - 1] + s[n - 2]) % D


def solver(n):
    for i in range(2, n + 1):
        s[i] = calc(i)


solver(n)
print(s[n])

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from itertools import permutations, accumulate, combinations, combinations_with_replacement
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce
from fractions import gcd
import sys
def I(): return int(input())
def Is(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()
def LS(): return list(input())
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(10**6)
MOD = 10**9+7
INF = float('inf')


n, m = Is()
A = IR(m)
dp = [0]*(n+3)
dp[0] = 1

A.sort(reverse=True)
if len(A) > 0:
    tmp = A.pop()
else:
    tmp = -1
if tmp == 1:
    dp[1] = 0
    if len(A) > 0:
        tmp = A.pop()
else:
    dp[1] = 1

for i in range(n+1):
    if tmp == i+2:
        dp[i+2] = 0
        if len(A) > 0:
            tmp = A.pop()
    else:
        dp[i+2] += dp[i+1] + dp[i]

print(dp[n] % MOD)

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

is_broken = [False] * (N+1)

for i in range(M):
    A[i] = int(input())
    is_broken[A[i]] = True

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

for i in range(1, N+1):
    if is_broken[i]:
        continue
    dp[i]  = (dp[i-1] + dp[i-2]) % (10**9 + 7)

print(dp[-1])

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

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

Solution (Python):
N,M = map(int,input().split())
a = [True]*(N+1)
for _ in range(M):
  b = int(input())
  a[b] = False

mod = 10**9+7
dp = [0]*(N+1)
dp[0] = 1
for i in range(N):
  for j in range(i+1,min(i+2,N)+1):
    if a[j]:
      dp[j] += dp[i]
      dp[j] %= mod


print(dp[-1])

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

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

for i in range(1, N+1):
    if i in Broken:
        continue
    DP[i] = DP[i-1] + DP[i-2]
    DP[i] %= 10**9 + 7
print(DP[N])

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
n,m = map(int,input().split())
a = [int(input()) for _ in range(m)]
mod = 10**9+7
memo = [-1]*(n+1)
def rec(x):
    if memo[x] != -1: pass
    elif x == 0: memo[x] = 1
    elif a and x == a[-1]:
        memo[x] = 0
        a.pop()
    elif x == 1: memo[x] = 1
    else: memo[x] = (rec(x-1)+rec(x-2))%mod
    return memo[x]
print(rec(n))

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
n,m = map(int,input().split())
a = [int(input()) for _ in range(m)]
mod = 10**9+7
memo = [-1]*(n+1)
def rec(x):
    if memo[x] != -1: pass
    elif x == 0: memo[x] = 1
    elif a and x == a[-1]:
        memo[x] = 0
        a.pop()
    elif x == 1: memo[x] = 1
    else: memo[x] = rec(x-1)+rec(x-2)
    return memo[x]%mod
print(rec(n))

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

dp[0] = 1
if a[idx] == 1: idx += 1
else: dp[1] = 1

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

print(dp[n])

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

dp[0] = 1
if a[idx] == 1: idx += 1
else: dp[1] = 1

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

Solution (Python):
N,M = (int(x) for x in input().split())
a = set(int(input()) for _ in range(M))
dp = [0] * N
broke = False
if N == 1:
    print('1')
    broke = True
elif 1 in a and 2 not in a:
    dp[1] = 1
elif 1 not in a and 2 in a:
    dp[0] = 1
else:
    dp[0] = 1
    dp[1] = 2
if 1 in a and 2 in a:
    print('0')
    broke = True
else:
    for i in range(3,N+1):
        if i-1 in a and i-2 in a:
            print('0')
            broke = True
            break
        elif i-1 in a:
            dp[i-1] = dp[i-3]
        elif i-2 in a:
            dp[i-1] = dp[i-2]
        else:
            dp[i-1] = (dp[i-2] + dp[i-3]) % 1000000007
if broke == False:
    print(dp[N-1])

Solution (Python):
n,m=map(int,input().split())
MOD=10**9+7
dp=[0]*(n+1)
breakstair=[False]*(n+1)
a=[]
for i in range(m):
    tmp=int(input())
    breakstair[tmp]=True
dp[0]=1
dp[1]=1
for i in range(2,n+1):
    if breakstair[i-1]:
        if breakstair[i-2]:
            print(0)
            exit()
        dp[i]=dp[i-2]
    elif breakstair[i-2]:
        dp[i]=dp[i-1]
    else:
        dp[i]=(dp[i-1]+dp[i-2])%MOD
print(dp[-1])

Solution (Python):
import sys



import math






stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)
MIN = -10 ** 9
MOD = 10 ** 9 + 7
INF = float("inf")
IINF = 10 ** 18



n,m = map(int, stdin.readline().rstrip().split())


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

broke = [0 for _ in range(n+1)]
for i in range(m):
    broke[int(stdin.readline().rstrip())] = 1

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

print(dp[n]%MOD)

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

ct[0] = 1
mod = 1000000007
for i in range(1, n+1):
    if A[i-2] == True:
        ct[i] += ct[i-1]
    if i > 1 and A[i-3] == True:
        ct[i] += ct[i-2]
    ct[i] %= mod
print(ct[-1])

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

ct[0] = 1
mod = 1000000007
for i in range(1, n+1):
    if A[i-2] == True:
        ct[i] += ct[i-1]
    if i > 1 and A[i-3] == True:
        ct[i] += ct[i-2]
    ct[i] %= mod
print(ct[-1])

Solution (Python):


MOD = (10 ** 9) + 7
N, M = map(int, input().split())
A = [False] * (N + 1)
for _ in range(M):
    A[int(input())] = True
dp = [0] * (N + 1)
dp[0] = 1
if A[1] == False:
    dp[1] = 1

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

print(dp[N])

Solution (Python):


def fib(m):
    if m < 0:
        return 0
    elif m == 0 or m == 1:
        return 1
    elif m == 2:
        return 2
    else:
        a, b = 1, 1
        for i in range(m - 1):
            a, b = b, a + b
        return b

n, m = map(int, input().split())
ans = 1
begin = 0
for i in range(m):
    a = int(input())
    end = a - 1 - begin
    
    begin = a+1
    ans = ans * (fib(end) % 1000000007) % 1000000007

end = n - begin
ans = ans * (fib(end) % 1000000007) % 1000000007
print(ans)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
def main():
    N, M, *a = map(int, read().split())
    A = {i for i in a}
    P = (10**9)+7

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

    if not (1 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])%P
    print(dp[N])
if __name__ == '__main__':
    main()

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
def main():
    N, M, *a = map(int, read().split())
    A = {i for i in a}
    P = (10**9)+7

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

    if not (1 in A):
        dp[1] = 1
        

    for i in range(2, N+1):
        if i in A:
            continue
        else:
            dp[i] = (dp[i-1] + dp[i-2])%P
    print(dp[N])
if __name__ == '__main__':
    main()

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
def main():
    N, M, *a = map(int, read().split())
    A = set()
    P = (10**9)+7
    for i in a:
        A.add(i)

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

    if not (1 in A):
        dp[1] = 1
        

    for i in range(2, N+1):
        if i in A:
            continue
        else:
            dp[i] = (dp[i-1] + dp[i-2])%P
    print(dp[N])
if __name__ == '__main__':
    main()

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

if n==1:
  print(1)
  exit()
if n==2:
  if m==0:
    print(2)
  else:
    print(1)
  exit()

fib=[0 for i in range(n+2)]
fib[1]=1
for i in range(2,n+2):
  fib[i] = (fib[i-1]+fib[i-2]) % 1000000007

com=1
anow=-1
for i in range(m):
  a=int(input())
  if a-anow==1:
    print(0)
    exit()
  com = (com * fib[a-anow-1]) % 1000000007
  anow=a

com = (com * fib[n-anow]) % 1000000007
print(com)

Solution (Python):
import 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)])
if N==1:
    print(1)
    exit()
dp = [0]*(N+1) 
dp[1] = 0 if 1 in a else 1
dp[2] = 0 if 2 in a else (1+dp[1])
for i in range(3,N+1):
    if i in a:
        dp[i] = 0
        continue
    dp[i] = (dp[i-2]+dp[i-1])%1000000007
print(dp[-1])

Solution (Python):
N, M = map(int, input().split())
a = list(int(input()) for i in range(M))
DP = [0]*(N+1)
pointer = 0
for i in range(N+1):
    if pointer < M:
        if i == a[pointer]:
          DP[i] = 0
          pointer += 1
          continue
    if i == 0 or i == 1:
        DP[i] = 1
    else:
        DP[i] = (DP[i-1]+DP[i-2])
print(DP[-1]%1000000007)

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

mod = 10**9+7
dp = [0]*(n+1)
dp[0]=1
if 1 not in a:
    dp[1]=1
for i in range(2,n+1):
    if i in a :
        continue
    else:
        dp[i]= dp[i-1] + dp[i-2]
        dp[i]%= mod


print(dp[n])

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque
def main():
    N, M = map(int, input().split())
    A = deque([int(input()) for i in range(M)])
    if N == 1:
        print(1)
    else:
        dp = [0]*N
        
        if len(A) != 0:
            out = A.popleft() 
        else:
            out = 0

        if out != 1:
            dp[0] = 1
        else:
            dp[0] = 0
            if len(A) != 0:
                out = A.popleft()
        if out != 2:
            dp[1] = 1+dp[0]
        else:
            dp[1] = 0
            if len(A) != 0:
                out = A.popleft()

        for i in range(2,N):
            if i+1 == out:
                dp[i] = 0
                if len(A) != 0:
                    out = A.popleft()
            else:
                if dp[i-2] != 0 or dp[i-1] != 0:
                    dp[i] = dp[i-2] + dp[i-1]

        if dp[N-1] != 0:
            print(dp[N-1]%(10**9 + 7))
        else:
            print(0)
    
if __name__ == '__main__':
    main()

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

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

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

Solution (Python):
n,m=map(int,input().split())
lis=[1]
a=[]
for i in range(m):
  a.append(int(input()))
  
count=0
for i in range(1,n+1):
  try:
    kiken=a[count]
  except IndexError:
    kiken=-1
  if i-2!=-1:
    maemae=lis[i-2]
  else:
    maemae=0
  try:
    mae=lis[i-1]
  except IndexError:
    mae=0
  if i==kiken:
    lis.append(0)
    count+=1
  else:
    lis.append((mae+maemae)%(10**9+7))
    
print(lis[-1])

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

stair = [True] * N
for i in a:
    stair[i-1] = False


dp = [0] * N
if stair[0]:
    dp[0] = 1
if N >= 2:
    if stair[1]:
        dp[1] = dp[0] + 1
    else:
        dp[1] = 0

for i in range(2, N):
    if not stair[i]:
        dp[i] = 0
        continue
    if stair[i-1] and stair[i-2]:
        dp[i] = (dp[i-1] + dp[i-2])%MOD
    elif stair[i-1]:
        dp[i] = dp[i-1]
    elif stair[i-2]:
        dp[i] = dp[i-2]

print(dp[N-1])

Solution (Python):
n,m=map(int,input().split())
flag=list(1 for _ in range(n+1))
count=list(0 for _ in range(n+1))
ans=0
for i in range(m):
    x=int(input())
    flag[x]=0

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

Solution (Python):
n,m=map(int,input().split())
flag=list(1 for _ in range(n+1))
count=list(0 for _ in range(n+1))
ans=0
for i in range(m):
    x=int(input())
    flag[x]=0

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

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]
    dp[i] %= 1000000007

print(dp[n])