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
n, m = map(int, input().split())
danger = [int(input()) for i in range(m)]

MOD = 1000000007
MAX = 200000           
fac, finv, inv = [[0]*MAX for i in range(3)]
def combinit():     
  fac[0] = fac[1] = 1
  finv[0] = finv[1] = 1
  inv[1] = 1
  for i in range(2, MAX):
    fac[i] = fac[i - 1] * i % MOD
    inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i - 1] * inv[i] % MOD

def modcomb(n, k):      
  if (n < k):
    return 0
  if (n < 0 or k < 0):
    return 0
  return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD
combinit()          

def poss(n):
  n -= 1
  k = n//2
  ans = 0
  for i in range(k+1):
    ans += modcomb(n-i, i) % MOD
  return ans % MOD
if m == 0:
  print(poss(n+1))
  sys.exit()
ans = poss(danger[0])
for i in range(1, m):
  if danger[i] - danger[i-1] == 1:
    print(0)
    sys.exit()
  ans *= poss(danger[i] - danger[i-1] - 1)
  ans = ans % MOD
ans *= poss(n - danger[m-1])

print(ans % MOD)

Solution (Python):


from sys import stdin

n, m = map(int, stdin.readline().rstrip().split())
a = [int(stdin.readline().rstrip()) for i in range(m)]
oks = []
mod = 1e+9 + 7
for i in range(n + 1):
    oks.append(True)
for ai in a:
    oks[ai] = False
dp = [0] * (n + 1)
dp[0] = 1
for now in range(n):
    for next in range(now + 1, min(n, now + 2) + 1):
        if oks[next]:
            dp[next] += dp[now]
            dp[next] %= mod

print(int(dp[n]))

Solution (Python):
from functools import lru_cache

def main():
    n,m = map(int,input().split())
    import numpy as np
    ans = np.ones(n+1,dtype=int)*-1
    ans[0] = 1
    mod = 10**9+7
    for _ in range(m):
        a = int(input())
        ans[a]=0
    if ans[1]!=0:
        ans[1]=1
    for i in range(2,n+1):
        if ans[i]!=0:
            ans[i] = (ans[i-1]+ans[i-2])%mod
    print(ans[-1])
        

if __name__ == "__main__":
    main()

Solution (Python):
line = input()
X, Y = [int(n) for n in line.split()]

broken_steps = set()
for _ in range(Y):
    line = input()
    broken_steps.add(int(line))

if 1 not in broken_steps:
    if 2 not in broken_steps:
        stairs = [1, 2]
    else:
        stairs = [1, 0]
elif 2 not in broken_steps:
    stairs = [0, 1]
else:
    stairs = [0, 0]

for i in range(2, X):
    number_of_steps = 0
    if i+1 not in broken_steps:
        number_of_steps = stairs[i - 1] + stairs[i-2]
    stairs.append(number_of_steps)
predicted_value = stairs[X-1]
print(predicted_value % 1000000007)

Solution (Python):
def fib(n, broken):
    a = 1
    b = 1
    for i in range(n-2):
        

        a, b = b, a + b
    print(b)



t = 1

for _ in range(t):
    n, m = [int(x) for x in input().split()]
    broken = set()
    for _ in range(m):
        broken.add(int(input()))

    x = 0
    y = 1
    i = 1
    impossible = False
    c = 0
    while i <= n:
        
        
        if i in broken:
            
            x = y
            if i + 1 in broken:
                impossible = True
                break
            while not ((i + 1) not in broken and (i + 2) not in broken and (i + 3) not in broken):

                if i + 1 in broken and i + 2 in broken:
                    impossible = True
                if i + 2 in broken and i + 3 in broken:
                    impossible = True

                i += 1
            i += 2
            
            

            
            

            
            
            
            
            

            
            
            
            
            
            

            
            
            

            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
        else:
            y, x = (x + y) % 1000000007, y % 1000000007
            
            c = 0
        i += 1
        
    print(0) if impossible else print(y % 1000000007)

Solution (Python):
def fib(n, broken):
    a = 1
    b = 1
    for i in range(n-2):
        

        a, b = b, a + b
    print(b)



t = 1

for _ in range(t):
    n, m = [int(x) for x in input().split()]
    broken = set()
    for _ in range(m):
        broken.add(int(input()))

    x = 0
    y = 1
    i = 1
    impossible = False
    c = 0
    while i <= n:
        
        
        if i in broken:
            
            x = y
            if i + 1 in broken:
                impossible = True
                break
            while not ((i + 1) not in broken and (i + 2) not in broken and (i + 3) not in broken):

                if i + 1 in broken and i + 2 in broken:
                    impossible = True
                if i + 2 in broken and i + 3 in broken:
                    impossible = True

                i += 1
            i += 2
            
            

            
            

            
            
            
            
            

            
            
            
            
            
            

            
            
            

            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
        else:
            y, x = (x + y) % 1000000007, y % 1000000007
            
            c = 0
        i += 1
        
    print(0) if impossible else print(y % 1000000007)

Solution (Python):
div = 1000000007

n, m, *b = map(int, open(0).read().split())
a = set(b)
 
f = [0] * (n + 1)
f[0] = 1

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

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

Solution (Python):
def main():
    N, M, *a = map(int, open(0).read().split())
    div = 1000000007
    broken = set(a)
 
    comb_list = [0] * (N + 1)
    comb_list[0] = 1
    if 1 not in broken:
        comb_list[1] = 1
 
    for i in range(2, N + 1):
        if i in broken:
            continue
        comb_list[i] = (comb_list[i - 1] + comb_list[i - 2]) % div
 
    print(comb_list[-1])
 
 
if __name__ == "__main__":
    main()

Solution (Python):
def main():
    N, M, *a = map(int, open(0).read().split())
    div = 1000000007
    broken = set(a)

    comb_list = [0] * (N + 1)
    comb_list[0] = 1
    if 1 not in broken:
        comb_list[1] = 1

    for i in range(2, N + 1):
        if i in broken:
            continue
        comb_list[i] = (comb_list[i - 1] + comb_list[i - 2]) % div

    print(comb_list[-1])


if __name__ == "__main__":
    main()

Solution (Python):
import functools
import operator

n,m= map(int,input().split())
def fib(n):
  x,y=1,2
  if n==1 or n==0:
    return x
  elif n==2:
    return y
  else:
    for i in range(n-2):
      x, y = y,x+y
    return y
if m==0:
  print(fib(n)%1000000007)
else:
  li=[int(input()) for i in range(m)]
  l=len(li)
  a=0
  b=0
  c=[]
  for i in range(l):
    b=li[i]-1
    c.append(b-a)
    a=li[i]+1
  c.append(n-(li[-1]+1))
  c2=[i for i in c if i<0]
  if sum(c2)<0:
    print(0)
  else:
    ans=list(map(fib,c))
    result = functools.reduce(operator.mul, ans)
    print(result%1000000007)

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

N, M = map(int, input().split())
_is_ok = [True for i in range(N + 1)]
for i in range(M):
    _is_ok[int(input())] = False
ways = [0 for i in range(N + 1)]
ways[0] = 1
if _is_ok[1]:
    ways[1] = 1
for i in range(N - 1):
    if _is_ok[i + 2]:
        ways[i + 2] = ways[i + 1] + ways[i]
    ways[i + 2] %= mod
print(ways[N])

Solution (Python):
n,m = map(int,input().split())
stair = []
mod = int(1e9+7)
for i in range(m):
    stair.append(int(input()))
dp = [0] * (n+1)
dp[0] = 1
stair.append(int(1e10))
k = 0
for i in range(1, n+1):
    if i == stair[k]:
        dp[i] = 0
        k += 1
    elif i == 1:
        dp[1] = 1
    else:
        dp[i] = (dp[i-1] + dp[i-2])%mod
print(dp[-1])

Solution (Python):
n,m = map(int,input().split())
stair = []
mod = int(1e9+7)
ans = 1
for i in range(m):
    stair.append(int(input()))
dp = [0] * (n+1)
dp[0] = dp[1] = 1
stair.append(int(1e10))
if n == 1:
    print(1)
    exit()
k = 0
for i in range(1, n+1):
    if i == stair[k]:
        dp[i] = 0
        k += 1
    elif i == 1:
        dp[1] = 1
    else:
        dp[i] = (dp[i-1] + dp[i-2])%mod
print(dp[-1])

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

Solution (Python):
MOD = 10**9 + 7
N, M = map(int, input().split())
stairs = [0]*(N+1)
for _ in range(M):
    stairs[int(input())] = 1
if N == 1:
    print(1)
    exit()
ans = [0]*(N+1)
ans[1] = 1 if stairs[1] == 0 else 0
ans[2] = 1 + ans[1] if stairs[2] == 0 else 0
for i in range(3,N+1):
    if stairs[i] == 1:
        ans[i] = 0
        continue
    ans[i] = (ans[i-1] + ans[i-2]) % MOD
print(ans[N])

Solution (Python):
n,m = map(int, input().split())
num = list(int(input()) for _ in range(m))

count = [-1]*(n+1)
for stair in num:
  count[stair] = 0
  
count[0] = 1
count[1] = 1 if 1 not in num else 0

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

Solution (Python):
n,m = map(int,input().split())
dp=[1 for _ in range(n+1)]
for i in range(m):
    a = int(input())
    dp[a] = 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]%(10**9+7))

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

Solution (Python):
import math
import string
import collections
from collections import Counter
from collections import deque
import sys
sys.setrecursionlimit(2*10**5)
INF = 2**60


def readints():
    return list(map(int, input().split()))


def nCr(n, r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))


def has_duplicates2(seq):
    seen = []
    for item in seq:
        if not(item in seen):
            seen.append(item)
    return len(seq) != len(seen)


def divisor(n):
    divisor = []
    for i in range(1, n+1):
        if n % i == 0:
            divisor.append(i)
    return divisor



dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]

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

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


dp = [0]*(N+2)

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

    if not(safe[i]):
        dp[i] = 0

print(dp[N] % 1000000007)

Solution (Python):
import sys
input=sys.stdin.readline














N,M = map(int,input().split())
dicti = {i:True for i in range(N+2)}
for i in range(M):
    a = int(input())
    dicti[a] = False
ans = [0] * (N+3)
ans[0] = 1
for i in range(N):
    if dicti[i]:
        ans[i+1] += ans[i]
        ans[i+1] = ans[i+1] % 1000000007
        ans[i+2] += ans[i]
        ans[i+2] = ans[i+2] % 1000000007
    else:
        ans[i] = 0
print(ans[N])

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

Solution (Python):
n,m = map(int,input().split())
A =[int(input()) for _ in range(m)]
dict = {i:False for i in range(n)}
for a in A:
    dict[a]=True
dp = [0 for _ in range(n+2)]
dp[0] = 1
MOD = 1000000007
for i in range(n):
    if not dict[i]:
        dp[i+1] = (dp[i]+dp[i+1])%MOD
        dp[i+2] = (dp[i]+dp[i+2])%MOD
print(dp[n])

Solution (Python):
n,m=map(int,input().split())
a=[int(input()) for _ in range(m)]
a=[-1]+a+[n+1]
d=[a[i+1]-a[i]-2 for i in range(m+1)]
def fib(x):
    if x==1:
        return [1,1]
    else:
        ans=[1,1]
        for i in range(2,x+1):
            ans.append(ans[-1]+ans[-2])
        return ans
md=max(d)
l=fib(md)
ans=1
for i in range(m+1):
    if d[i]==-1:
        ans=0
        break
    else:
        ans=ans*l[d[i]]
print(ans%1000000007)

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

f=[True]*(n+1)
for _ in range(m):
    f[int(input())]=False

for i in range(1,n+1):
    if f[i]==False:
        continue
    else:
        if dp[i-1] != 0:
            dp[i] += dp[i-1]
        if i > 1:
            if dp[i-2] != 0:
                dp[i] += dp[i-2]

print(dp[-1]%1000000007)

Solution (Python):
n,m = map(int, input().split())
a = set([int(input()) 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:continue
    dp[i] = (dp[i-1]+dp[i-2])%1000000007
print(dp[n])

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

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

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

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

print(dp[n])

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

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

isSafe = [True] * (N+1)
for _ in range(M):
    a = int(input())
    isSafe[a] = False

dp = [0] * (N +1)

dp[0] = 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]

print(dp[N]%(10**9+7))

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

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

for i in range(N):
    if i == 0:
        ans.append(broken[0])
    else:
        ans.append(ans[i] * broken[i-1] + ans[i-1] * broken[i-2])
        
print((ans[N]) % mod)

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

Solution (Python):
N,M=map(int,input().split())
def steps(N,M):
	a=[]
	b=[1,1]
	for j in range(N):
		b.append(b[-1]+b[-2])
	if M==0:
		return print(b[N]%1000000007)
	else:
		for i in range(M):
			a.append(int(input()))
		for i in range(M-1):
			if a[i+1]-a[i]==1:
				return print(0)
		ans=1
		a.append(N+1)
		a.insert(0,-1)
		for i in range(M+1):
				c=a[i+1]-a[i]-2
				ans*=(b[c])
		return print(ans%1000000007)
steps(N,M)

Solution (Python):
import math
import string
import collections
from collections import Counter
from collections import deque


def readints():
    return list(map(int, input().split()))


def nCr(n, r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))


def has_duplicates2(seq):
    seen = []
    for item in seq:
        if not(item in seen):
            seen.append(item)
    return len(seq) != len(seen)


def divisor(n):
    divisor = []
    for i in range(1, n+1):
        if n % i == 0:
            divisor.append(i)
    return divisor



dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]

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

dp = [0]*(N+1)




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

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

print(dp[N] % 1000000007)

Solution (Python):
N, M = map(int, 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 now in range(N):
    for next in range(now+1, min(N, now+2)+1):
        if oks[next]:
            dp[next] += dp[now]
            dp[next] %= 10**9 + 7

print(dp[N])

Solution (Python):


import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

n,m=MI()
brs=[]
for i in range(m):
    brs.append(int(input()))
brs.append(0)
dp=[0 for i in range(n+2)]
dp[0]=0
dp[1]=1
i=2
while i<n+2:
    if i==brs[0]+1:
        dp[i]==0
        brs.remove(brs[0])
        
        i=i+1
    else:
        dp[i]=dp[i-1]+dp[i-2]
        i=i+1
print(dp[-1]%(10**9+7))

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

Solution (Python):
import sys
IS = lambda: sys.stdin.readline().rstrip()
II = lambda: int(IS())
MII = lambda: list(map(int, IS().split()))

def main():
    n, m = MII()
    a_lst = [II() for _ in range(m)]
    DIV = 10**9+7
    stairs = [1]*2 + [0]*(n-1)
    for a in a_lst:
        stairs[a] = 'NG'
    cnt = 0
    for i in range(2, n+1):
        if cnt == 2:
            print(0)
            exit(0)
        if stairs[i] == 'NG': cnt += 1; continue
        cnt = 0
        a = stairs[i-1] if stairs[i-1] != 'NG' else 0
        b = stairs[i-2] if stairs[i-2] != 'NG' else 0
        stairs[i] = a + b
    print(stairs[n]%DIV)

if __name__ == '__main__':
    main()

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

MOD = 10 ** 9 + 7

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

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

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

print(dp[N] % MOD)

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

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

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

print(dp[N])

Solution (Python):
def fib(n):
    if n == 1:
        return 1
    if n == 2:
        return 2
    else:
        a,b = 0,1
        for i in range(n):
            a,b = b,a+b
        return b

n,m = map(int,input().split())
mod = 10**9+7
ans = 1
a = -1
for i in range(m):
    b = int(input())
    if a != -1 and b-a == 1:
        print(0)
        break
    ans *= fib(b-a-2)
    a = b
else:
    ans *= fib(n-a-1)
    print(ans%mod)

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

Solution (Python):
N,M=map(int,input().split())
now=0
a=0
MOD=10**9+7
p=[1,0]
A=[int(input()) for i in range(M)]+[-1]
while now<N:
  if now==A[a]-1:
    p=[0,p[0]]
    a+=1
  else:
    p=[(p[0]+p[1])%MOD, p[0]%MOD]
  now+=1
print(p[0]%MOD)

Solution (Python):


import sys
import math
import collections
import itertools
INF = 10 ** 13
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def gcd(x, y) : return y if x % y == 0 else gcd(y, x % y)
def lcm(x, y) : return (x * y) // gcd(x, y)
def I() : return int(input())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def LS() : return input().split()
def RS(N) : return [input() for _ in range(N)]
def LRS(N) : return [input().split() for _ in range(N)]
def PL(L) : print(*L, sep="\n")

N, M = LI()
A = RI(M)

dp = [0] * (N+10)
dp[0] = 1
j = 0
for i in range(N):
    if j < M and i == A[j]:
        j += 1
        continue

    dp[i+1] = ((dp[i] % MOD) + (dp[i+1] % MOD)) % MOD
    dp[i+2] = ((dp[i] % MOD) + (dp[i+2] % MOD)) % MOD

print(dp[N])

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

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

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

n, m = [int(i) for i in input().split()]
fibo_l = [1] + [None] * n
a = set([int(input()) for i in range(m)])

def fibo(x):
    if x not in a and x >= 0:
            if fibo_l[x] is None:
                fibo_l[x] = fibo(x-1) % 1000000007 + fibo(x-2) % 1000000007
            return fibo_l[x]
    else: return 0
    
print(fibo(n) % 1000000007)

Solution (Python):
N,M = map(int, input().split())
a = set([int(input()) 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):
  dp[i] = (dp[i-1] + dp[i-2])%(10**9+7) if i not in a else 0
print(dp[N])

Solution (Python):
n , m = map(int,input().split())
u = 1000000007
p = {i for i in range(n)}
y = [0 for i in range(n)]
q = {int(input()) - 1 for i in range(m)}
f = list(p - q)
for i in f:
    if i == 0:
        y[0] = 1
    elif i == 1:
        y[1] = y[0] + 1
    else:
        y[i] = (y[i-1] + y[i-2])%u

print(y[n-1])

Solution (Python):

import sys
input = sys.stdin.readline









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

mod = 10**9+7


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


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

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

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())
nums = [0, 1]
broken = set()
for i in range(m):
    broken.add(int(input()))
def fib(n):
    for i in range(n):
        if i+1 in broken:
            nums.append(0)
        else:
            a = nums[i]
            b = nums[i+1]
            nums.append((a+b)%1000000007)
    return nums[-1]
print(fib(n))

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

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

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

ret_list = [0] * (n + 1)

ret_list[0] = 1
ret_list[1] = 0 if 1 in a_set else 1

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

print(ret_list[-1])

Solution (Python):

import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 10 ** 9 + 7
N, M = lr()
A = set(ir() for _ in range(M))
dp = [0] * (N+1)
dp[0] = 1
for i in range(N):
    if i+2 not in A and i+2 <= N:
        dp[i+2] += dp[i]
    if i+1 not in A:
        dp[i+1] += dp[i]

print(dp[-1]%MOD)

Solution (Python):
import collections
import itertools
import numpy as np
import sys
sys.setrecursionlimit(100000000)
MOD = 10**9+7

def binary_search(a,val):
    n = len(a)
    low = 0
    high = n-1
    mid =(low+high)//2
    cnt = 1
    while low < high + 1:
        if a[mid] == val:
            return True
        elif a[mid]>val:
            high = mid - 1
        else:
            low = mid + 1
        mid =(low+high)//2
        cnt += 1
    return False

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

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

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

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,M = map(int,readline().split())
A = [True] * (N+10)
MOD = 10 ** 9 + 7
for _ in range(M):
  x = int(readline())
  A[x] = False


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

for i in range(N):
  if not A[i]:
    continue
  
  if A[i+1]:
    DP[i+1] += DP[i]
    DP[i+1] %= MOD
  if A[i+2]:
    DP[i+2] += DP[i]
    DP[i+2] %= MOD
       
print(DP[N]%MOD)

Solution (Python):
mod = 10 ** 9 + 7
mod2 = 2**61+1
from collections import deque
import heapq
from bisect import bisect_left, insort_left, bisect_right

def iip(listed=True):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def iip_ord():
    return [ord(i) - ord("a") for i in input()]


def main():
    ans = solve()
    if ans is not None:
        print(ans)

def solve():
    N, M = iip(False)
    A = [iip(False) for i in range(M)]

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

    for i in A:
        dp[i] = False

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

        if dp[i] is False:
            continue

        if a is False:
            a = 0
        if b is False:
            b = 0

        dp[i] = (a+b) % mod

        
    print(dp[-1] % mod)




def YesNo(s):
    if s:
        print("Yes")
    else:
        print("No")


def fprint(s):
    for i in s:
        print(i)

def split_print_space(s):
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p, mod_= mod):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


if __name__ == "__main__":
    main()

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

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

print(dp[-2])

Solution (Python):

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

from collections import deque
stack_deque = deque(a)

def pl():
    try:
        return stack_deque.popleft()
    except:
        return -1

MOD = 10**9+7

dp = [0] * (n+1)
dp[0]=1
min_a = pl()
if min_a!=1:
    dp[1]=1
else:
    min_a = pl()
for i in range(2,n+1):
    if i == min_a:
        dp[i]=0
        min_a = pl()
    else:
        dp[i]=(dp[i-1]%MOD+dp[i-2]%MOD) % MOD
print(dp[-1])