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
mod=10**9+7 ; inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict 
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  
  
from functools import lru_cache
from bisect import bisect_left as bileft, bisect_right as biright





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


@lru_cache(maxsize=10**10)
def qwe(x):
    if x==n:return 1
    if x>n:return 0
    if NG[x+1] and NG[x+2]: print(0);exit()
    if NG[x+1]:return qwe(x+2)%mod
    if NG[x+2]:return qwe(x+1)%mod
    return (qwe(x+2)+qwe(x+1))%mod
print(qwe(0))

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

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

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

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

print(dp[n])

Solution (Python):
N,M = map(int,input().split())
A = [int(input()) for i in range(M)]
n = 0
if M != 0:
    a = b = A[0]
else:
    a = b = -2
c = 0
ans = [0,1]
for i in range(1,N+1):
    if  i == a:
        c = 0
        n += 1
        b = a
        if n <= M-1:
            a = A[n]
    elif i-2 == b:
        c = ans[-1]
    elif i-1 == b :
        c = ans[-2]
    else:
        c  = ans[-1] + ans[-2]
    c %= 10**9 + 7
    ans.append(c)
print(ans[-1])

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

class UnionFind():
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * n

    def root(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.root(self.par[x])
            return self.par[x]

    def union(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                self.par[x] = y
            else:
                self.par[y] = x
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1

    def samegrp(self, x, y):
        return self.root(x) == self.root(y)

N, M = [int(x) for x in input().split()]
X = UnionFind(N + 1)
for i in range(M):
    X.union(0, int(input()))

dp = [0]*(N + 1)
dp[0] = 1
if X.samegrp(0, 1):
    dp[1] = 0
else:
    dp[1] = 1
for i in range(2, N + 1):
    if X.samegrp(0, i):
        dp[i] = 0
    else:
        dp[i] = (dp[i - 1] + dp[i - 2]) % P

ans = dp[N]
print(ans)

Solution (Python):
n,m = map(int,input().split())
a = set([int(input()) for _ in range(m)])
step = [0] * (n+1)
step[0] = 1
if 1 not in a:
    step[1] = 1
else:
    step[1] = 0
for i in range(2,n+1):
    if i in a:
        continue
    step[i] = (step[i-1] + step[i-2]) % 1000000007
print(step[-1])

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

MOD=10**9+7

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

    for i in range(M):
        dp[a[i]]=-1

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

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

else:
    if M==0:
        print(1)
    else:
        print(0)

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

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

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


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

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

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

mod=10**9+7

dp=np.zeros(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]%=mod

print(int(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())
dp = [0]*(n+1)
dp[0],dp[1] = 1,1

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

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

print(dp[n]%(10**9+7) if dp[n]!=-1 else 0)

Solution (Python):

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


dp = [0]*(N+1)


dp[0] = 1

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

Solution (Python):
MOD = 10**9 + 7
N, M = map(int,input().split())
a = [int(input()) for k in range(M)]
dp = [0]*(N+2)
dp[0] = 1
for e in a:
    dp[e] = -1
for k in range(N):
    if dp[k] != -1:
        if dp[k+1] != -1:
            dp[k+1] += dp[k]
            dp[k+1] %= MOD
        if dp[k+2] != -1:
            dp[k+2] += dp[k]
            dp[k+2] %= MOD
print(max(0,dp[N]))

Solution (Python):
n,m = map(int,input().split())
s = [0]*n
dp = [0]*(n+1)
for i in range(m):
    s[int(input())-1] = 1
dp[0] = 1
if s[0] == 1:
    dp[1] = 0
else:
    dp[1] = 1
for i in range(2,n+1):
    if s[i-1] == 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 = 10**9+7
ans = [0]*(n+1)
ans [0] = 1
if 1 not in a: ans[1] = 1

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

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

step = [0]*(N+1)
last = -1
for a in A:
    if a == last + 1 or a == last - 1:
        print(0)
        exit()
    step[a] = 1
    last = a

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

chk = 0
for i in range(1, N+1):
    if step[i] == 0 and chk <= 0:
        ans[i+1] = ans[i] + ans[i-1]
        chk = 0
    elif step[i] == 1:
        ans[i+1] = ans[i]
        chk = 2
    elif step[i] == 0 and chk > 0:
        ans[i+1] = ans[i]
        chk -= 1
        
print(ans[-1]%(10**9 + 7))

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

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

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

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

now = 0
for i in range(m):
  next = int(input()) - 1
  step.append(next - now)
  now = next + 2

step.append(n-now)  
step.sort()

def fibo():
  s = []
  a = 1
  b = 1
  s.append(a)
  s.append(b)
  for i in range(n):
    c = a+b
    a = b
    b = c
    s.append(c)
  return s

ans = 1

if step[0] < 0:
  ans = 0

else:
  f = fibo()
  for i in step:
    ans *= f[i]

print(ans % 1000000007)

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

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

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

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

print(dp[n])

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

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

Solution (Python):

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

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

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

Solution (Python):
N,M=map(int,input().split())
res = 0
flag = True

INF = 100000000000
stepList = [INF]*(N+1)
stepList[0] = 1
stepList[1] = 1
def stepF(K):
  if K == 0:
    return stepList[0]
  else:
    for i in range(1,K+1):
      if i == 1:
        pass
      else:
        if stepList[i]==INF:
          stepList[i]= stepList[i-2] + stepList[i-1]
    return stepList[K]
  
if M == 0:
  res = stepF(N)
  
else:
  List = []
  for i in range (M):
    List.append(int(input()))
  
  
  for i in range(M):
    if i == 0:
      res = stepF(List[i]-1)
    else:
      if List[i] - List[i-1] == 1:
        flag = False
        break
      res = res * stepF(List[i]-List[i-1]-2)
  res = res * stepF(N-List[M-1]-1)
if flag:
  print(res%1000000007)
else:
  print(0)

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

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

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

print(dp[N])

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

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

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

print(dp[N])

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

Solution (Python):
def solve(N, a):
    mod = 10**9 + 7
    dp = [0] * (N+1)
    step = [0] * (N+1)
    for aa in a:
        step[aa] = 1

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

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

    return dp[N]


if __name__ == "__main__":
    N, M = map(int, input().split())
    a = [int(input()) for _ in range(M)]

    print(solve(N, a))

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

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

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

print(dp[N])

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

n, m = map(int, input().split())
a_s = [int(input()) for _ in range(m)] + [n + 1]
dp = [0 for _ in range(n + 1)]
dp[0] = 1
a_pos = 0
for i in range(1, n + 1):
    if a_s[a_pos] == i:
        a_pos += 1
        continue
    dp[i] = dp[i - 1] + dp[i - 2]
    dp[i] %= MOD
print(dp[-1])

Solution (Python):
from collections import Counter
n, m = map(int, input().split())
l = []
a0 = 0
for i in range(m):
    a = int(input())
    if a - a0 == 0:
        print(0)
        exit()
    l.append(a - a0 - 1)
    a0 = a + 1
l.append(n - a0)
d = Counter(l)
key = list(d.keys())

ma = max(key)
fib = [1]*(ma + 1)
for i in range(2, ma + 1):
    fib[i] = fib[i - 2] + fib[i - 1]

ans = 1
for k in key:
    ans *= fib[k]**d[k]
    ans %= 10**9 + 7

print(ans)

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

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

for now in range(N):
    for nex in range(now+1, min(N, now+2) + 1):
        if oks[nex] == 1:
            dp[nex] += dp[now]
            dp[nex] %= 10 ** 9 + 7

print(dp[N])

Solution (Python):

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

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

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

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

isbroken = [1 for _ in range(N+1)]
for i in range(M):
  isbroken[A[i]] = 0


dp = [0 for _ in range(N+1)]
dp[0] = 1
mod = 10**9 + 7

dp[1] = dp[0] * isbroken[0]
  
for j in range(1,N):
  dp[j+1] = (dp[j] * isbroken[j] + dp[j-1] * isbroken[j-1]) % mod
    
print(dp[N])

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

Solution (Python):


n, m = [int(i) for i in input().split()]
broken = set()
MOD = 10**9 + 7
for _ in range(m):
    broken.add(int(input()))

steps = [0] * (n + 1)
steps[0] = 1
if 1 in broken:
    steps[1] = 0
else:
    steps[1] = 1

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

print(steps[n])

Solution (Python):
import sys
import math
import itertools
import collections
from collections import deque
from collections import defaultdict

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
MOD2 = 998244353
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()

def main():
    
    N, M = NMI()
    A = [NI() for _ in range(M)]
    
    broken = [1 for _ in range(N+1)]
    
    for a in A:
        broken[a] = 0
    
    dp = [0 for _ in range(N+1)]
    
    dp[0] = 1
    dp[1] = int(not(1 in A))
    
    for n in range(2,N+1):
        dp[n] = ((dp[n-1]*broken[n-1] + dp[n-2]*broken[n-2])*broken[n])%MOD
        
    print(dp[N])


if __name__ == '__main__':
    main()

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

Solution (Python):
n,m=map(int,input().split())
a=[int(input()) for _ in range(m)]
l=[1]+[0 for _ in range(n+5)]
if m==0:a=[200000]
for x in range(n):
    if x<a[0]:
        l[x+1]+=l[x]
        l[x+2]+=l[x]
    if x==a[0]:
        if len(a)>=2:a.pop(0)
        else:a[0]=200000
print(l[n]%(10**9+7))

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

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

Solution (Python):
import bisect,collections,copy,itertools,math,string
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())
def main():
    lst = [1 for i in range(10**5+5)]
    s = 1
    for i in range(3,10**5+5):
        s += lst[i-2]
        lst[i] = s
    n,m = LI()
    kaidan = [1 for _ in range(n+1)]
    for _ in range(m):
        a = I()
        kaidan[a] = 0
    itr = itertools.groupby(kaidan)
    span = []
    ans = 1

    for key, group in itr:
        lenth = len(list(group))
        if key == 0 and lenth >= 2:
            ans = 0
        elif key == 1:
            span.append(lenth)

    for i in span:
        ans *= lst[i]%1000000007
        ans %= 1000000007
    
    print(ans)

main()

Solution (Python):









import os
import sys




def main():
    n, m = map(int, input().split())
    stairs = [0]*(n+1)
    stairs[0] = 1
    for _ in range(m):
        a = int(input())
        stairs[a] = -1
    for i in range(n-1):
        if stairs[i] == -1:
            continue

        if stairs[i+1] == -1:
            pass
        else:
            stairs[i+1] += stairs[i]

        if stairs[i+2] == -1:
            pass
        else:
            stairs[i+2] += stairs[i]
    if stairs[n-1] != -1:
        print((stairs[n-1]+stairs[n])%1000000007)
    else:
        print(stairs[n]%1000000007)


if __name__ == "__main__":
    main()

Solution (Python):
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

n,m=nii()

mod=10**9+7

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

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

print(dp[-1])

Solution (Python):
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

n,m=nii()

mod=10**9+7

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

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

print(dp[-1])

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

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

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

Solution (Python):
n, m = list(map(int, input().split()))
a = {}

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

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

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

print(c[n] % 1000000007)

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, M = mapint()
mod = 10**9+7

dp = [0]*(N+1)
dp[0] = 1
broken = set([int(input()) for _ in range(M)])
for i in range(1, N+1):
    if i in broken:
        continue
    dp[i] += dp[i-1]
    if i>=2:
        dp[i] += dp[i-2]
    dp[i] %= mod
print(dp[-1])

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

MOD = 10 ** 9 + 7

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

result = {0: 1}

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

    
    if i in A:
        result[i] = 0

    
    else:
        if i - 1 in result:
            min_1 = result[i-1]
        else:
            min_1 = 0
        if i - 2 in result:
            min_2 = result[i-2]
        else:
            min_2 = 0
        result[i] = (min_2 + min_1) % MOD

print(result[N])

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

MOD = 10 ** 9 + 7

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

result = {0: 1}

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

    
    if i in A:
        result[i] = 0

    
    else:
        if i - 1 in result:
            min_1 = result[i-1]
        else:
            min_1 = 0
        if i - 2 in result:
            min_2 = result[i-2]
        else:
            min_2 = 0
        result[i] = (min_2 + min_1) % MOD

print(result[N])

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

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

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

print(dp[n]%mod)

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

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

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

ans = dp[N]
print(ans)

Solution (Python):
N,M = map(int,input().split())
A = set([]); MOD = pow(10,9)+7
for i in range(M):
  a = int(input())
  A.add(a-1)
dp = [[0]*2 for _ in range(N)] 
if 0 not in A:
  dp[0][0] = 1
if N == 1:
  print(sum(dp[0]))
  exit()
if 1 not in A:
  dp[1][0] = dp[0][0]+dp[0][1]
  dp[1][1] = 1
for i in range(2,N):
  if i in A:
    continue
  dp[i][0] = (dp[i-1][0]+dp[i-1][1])%MOD
  dp[i][1] = (dp[i-2][0]+dp[i-2][1])%MOD
ans = sum(dp[N-1])%MOD

print(ans)

Solution (Python):
import sys

mod = 1000000007

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

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


print(dp[N])

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

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

A = [int(input()) for _ in range(M)]

memo = [0]*(100001)

for a in A:
    memo[a] = 1

ruiseki = [0]*(N+1)

ruiseki[0] = 1

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

Solution (Python):
n, m = map(int, input().split())
arr = 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 not i in arr:
        if i == 1:
            dp[i] = dp[i - 1] % MOD
        else:
            dp[i] = (dp[i - 1] + dp[i - 2]) % MOD

print(dp[-1])

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

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

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

dp=[0]*(n+1)

broken=[0]*(n+1)

for aa in a:
    broken[aa]=1

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

mod=10**9+7

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

print(dp[-1])

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

MOD = 10**9+7
dp = [0]*(n+1)
dp[0] = 1
for i in range(n):
    if i+1 <= n and al[i+1]:
        dp[i+1] += dp[i]
        dp[i+1]%=MOD
    if i+2 <= n and al[i+2]:
        dp[i+2] += dp[i]
        dp[i+2]%=MOD

print(dp[n])

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

aset = set(A)
MOD = 10 ** 9 + 7

dp = [0] * (N + 1)

if 1 not in aset:
    dp[1] = 1

if 2 not in aset and N >= 2:
    dp[2] += dp[1] + 1

for i in range(3, N + 1):
    if i in aset:
        continue

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

print(dp[N] % MOD)

Solution (Python):
def solve():
    for i in range(2, n+1):
        prev1 = dp[i-1]
        prev2 = dp[i-2]
        if i in set:
            continue
        else:
            dp[i] = prev1 + prev2
    return dp[n]


n, m = map(int, input().split())
lst = []
for i in range(m):
    lst.append(int(input()))
set = set(lst)
dp = [0] * (n+1)
dp[0] = 1
if 1 not in set:
    dp[1] = 1
res = solve()
print(res%1000000007)

Solution (Python):
import sys

input = sys.stdin.readline
mod = 10 ** 9 + 7
n, m = map(int, input().split())
dp = [0] * (n + 1)
dp[0] = 1
ng = set(int(input()) for _ in range(m))

for i in range(n):
    next1 = i + 1
    if next1 not in ng:
        dp[next1] += dp[i]
        dp[next1] %= mod
    next2 = i + 2
    if next2 not in ng and next2 <= n:
        dp[next2] += dp[i]
        dp[next2] %= mod
print(dp[-1])

Solution (Python):
import sys

input = sys.stdin.readline
mod = 1000000007
n, m = map(int, input().split())
dp = [0] * (n + 1)
dp[0] = 1
ng = set()
for _ in range(m):
    a = int(input())
    ng.add(a)

for i in range(n):
    next1 = i + 1
    if next1 not in ng:
        dp[next1] += dp[i]
        dp[next1] %= mod
    next2 = i + 2
    if next2 not in ng and next2 <= n:
        dp[next2] += dp[i]
        dp[next2] %= mod
print(dp[-1])

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

a = []
for _ in range(m):
    a.append(int(input()))
a.append(n+1)

def solve(a,n,m):
    for i in range(len(a)-1):
        if a[i+1] == a[i] + 1:
            return 0

    a_diff = [a[0]-1]
    for i in range(1, m+1):
        a_diff.append(a[i] - a[i-1] - 2)
    ans = 1
    for y in a_diff:
        if y == 0 or y == 1:
            continue
        ans *= count_way(y)
    return ans

def count_way(n):
    memo = [0]*(n+1)
    memo[0] = 1
    memo[1] = 1
    for j in range(n-1):
        memo[j+2] = memo[j+1] + memo[j]
    return memo[n]

print(solve(a,n,m)%1000000007)

Solution (Python):
import math
n,m=map(int,input().split())
h=[0 for _ in range(n+1)]
dp=[0 for _ in range(n+1)]
for i in range(m):
	s=int(input())
	h[s]=1
dp[0]=1
if h[1]==1:
	dp[1]=0
else:
	dp[1]=1
for i in range(2,n+1):
	if h[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())
    
num_list = [0]*(n+1)
num_list[0] = 1
a_list =set([int(input()) for _ in range(m)])
if 1 not in a_list:
    num_list[1] = 1
for i in range(2,n+1):
    if i not in a_list:
        num_list[i] = num_list[i-1] + num_list[i-2]
print(num_list[n]%(10**9+7))

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

nums = [0]*(n+1)
nums[0] = 1
if 1 not in a: nums[1] = 1

for i in range(2,n+1):
  if i not in a: nums[i] = nums[i-1] + nums[i-2]
print(nums[n]%(10**9+7))

Solution (Python):
N,M=map(int,input().split())
L=[0]*N
c={}
mod=1000000007
for i in range(M):
  k=int(input())
  c[k]=0
for i in range(N):
  if i==0:
    L[i]=1
  elif i==1:
    if L[0]==0:
      L[i]=1
    else:
      L[i]=2
  else:
    L[i]=(L[i-1]+L[i-2])%mod
  if i+1 in c:
    L[i]=0
print(L[N-1])

Solution (Python):
N, M = (int(s) for s in input().split())

broken = {int(input()) for _ in range(M)}

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

for k in range(1, N+1):
  if k in broken:
    dp[k] = 0
  elif k > 1:
    dp[k] = dp[k-1] + dp[k-2]

print(dp[N] % 1000000007)

Solution (Python):

import sys 
input = sys.stdin.readline

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

dp = [-1 for _ in range(n)]
for i in range(m):
    dp[a[i]-1] = 0 

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

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

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

print(dp[n-1])

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

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

Solution (Python):





MOD = 10**9+7

def solve(n,stairs):
  
  dp = [1] + [0] * (n+1)
  dp[1] = stairs[1]
  for i in range(n):
    dp[i+2] = (dp[i] + dp[i+1]) * stairs[i+2]
    dp[i+2] %= MOD

  return dp[n]



def main():
  N,M = map(int,input().split())
  stairs = [1]*(N+10)
  for i in range(M):
    stairs[int(input())] = 0
  print(solve(N,stairs))
  return

if __name__ == '__main__':
  main()

Solution (Python):





MOD = 10**9+7

def solve(n,a):
  
  stairs = [1]*(n+10)
  for x in a:
    stairs[x] = 0

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

  return dp[n]



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

if __name__ == '__main__':
  main()

Solution (Python):
n,m = list(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)