Problem:
 Score : 300 points    Problem Statement There is a staircase with N steps. Takahashi is now standing at the foot of the stairs, that is, on the 0 -th step.
He can climb up one or two steps at a time.  However, the treads of the a_1 -th, a_2 -th, a_3 -th, \ldots , a_M -th steps are broken, so it is dangerous to set foot on those steps.  How many are there to climb up to the top step, that is, the N -th step, without setting foot on the broken steps?
Find the count modulo 1\ 000\ 000\ 007 .      Constraints  1 \leq N \leq 10^5  0 \leq M \leq N-1  1 \leq a_1 < a_2 <  ...  < a_M \leq N-1         Input Input is given from Standard Input in the following format:  N  M  a_1  a_2  .  .  .  a_M       Output Print the number of ways to climb up the stairs under the condition, modulo 1\ 000\ 000\ 007 .        Sample Input 1 6 1
3      Sample Output 1 4  There are four ways to climb up the stairs, as follows:   0 \to 1 \to 2 \to 4 \to 5 \to 6  0 \to 1 \to 2 \to 4 \to 6  0 \to 2 \to 4 \to 5 \to 6  0 \to 2 \to 4 \to 6        Sample Input 2 10 2
4
5      Sample Output 2 0  There may be no way to climb up the stairs without setting foot on the broken steps.       Sample Input 3 100 5
1
23
45
67
89      Sample Output 3 608200469  Be sure to print the count modulo 1\ 000\ 000\ 007 .

Solution (Python):

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

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

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

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


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


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

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

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

for x in a:
    is_broken[x] = 1

for i in range(n):
    for j in range(i+1, min(n, i+2) + 1):
        if not is_broken[j]:
            dp[j] += dp[i]
            dp[j] %= MOD

print(dp[n])

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

Solution (Python):
import math
from math import gcd,pi,sqrt
INF = float("inf")
MOD = 10**9 + 7

import sys
sys.setrecursionlimit(10**6)
import itertools
import bisect
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]


def main():
    n,m = i_map()
    a = set([i_input() for i in range(m)])

    dp = [INF] * (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  not in a:
            dp[i] = dp[i-1] + dp[i-2]
        else:
            dp[i] = 0
    print(dp[n]%MOD)




if __name__=="__main__":
    main()

Solution (Python):
n, m = map(int, input().split())
A = []; broken = [True] * n
for i in range(m):
    a = int(input())
    A.append(a)
    broken[a] = False 
dp = [0] * (n+1)
dp[0] = 1
mod = 10**9 + 7
for i in range(1, n+1):
    if broken[i-1] :
        dp[i] += dp[i-1]
    if i >= 2 and broken[i-2] :
        dp[i] += dp[i-2]
    dp[i] %= mod
print(dp[n])

Solution (Python):

url = "https://atcoder.jp//contests/abc129/tasks/abc129_c"

def main():
    n, m = list(map(int, input().split()))
    isbreak = [False] * (n+1)
    for _ in range(m):
        isbreak[int(input())] = True

    dp = [0] * (n + 1)
    dp[0] = 1
    for i in range(n):
        for j in range(i+1, min(i+3, n+1)):
            if not isbreak[j]:
                dp[j] += dp[i]
                dp[j] %= 1000000007
    print(dp[-1])




if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = lambda: sys.stdin.readline().strip()
n, m = [int(x) for x in input().split()]
can = [True for i in range(n + 1)]
for i in range(m):
    ai = int(input())
    can[ai] = False
C = [0 for i in range(n + 1)]
for i in range(n + 1):
    if i == 0:
        C[i] = 1
    else:
        C[i] = sum(C[j] if j >= 0 and can[j] else 0 for j in (i - 1, i - 2)) % (10**9 + 7)
print(C[n])

Solution (Python):

import sys
input = lambda: sys.stdin.readline().strip()
n, m = [int(x) for x in input().split()]
can = [True for i in range(n + 1)]
for i in range(m):
    ai = int(input())
    can[ai] = False
C = [0 for i in range(n + 1)]
for i in range(n + 1):
    if i == 0:
        C[i] = 1
    else:
        C[i] = sum(C[j] if j >= 0 and can[j] else 0 for j in (i - 1, i - 2)) % (10**9 + 7)
print(C[n])

Solution (Python):
def main():
    N, M = [int(i) for i in input().split()]

    pos = 0
    ans = 1

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

    for _ in range(M):

        a = int(input())

        if a == pos:
            ans = 0
            pos = N
            break
        elif a == pos + 1:
            pos = a + 1
        else:
            ans *= fib[(a - 1 - pos)]
            pos = a + 1

    if pos + 1 < N:
        ans *= fib[(N - pos)]

    print(ans % 1_000_000_007)



if __name__ == "__main__":
    main()

Solution (Python):
def main():
    N, M = [int(i) for i in input().split()]

    pos = 0
    ans = 1

    fib = [1 for _ in range(100002)]
    for i in range(2, 100002):
        fib[i] = fib[i-1] + fib[i-2]

    for _ in range(M):

        a = int(input())
        if a == pos:
            ans = 0
            pos = N
            break
        elif a == pos + 1:
            pos = a + 1
        else:
            ans *= fib[(a - 1 - pos)]
            pos = a + 1

    if pos + 1 < N:
        ans *= fib[(N - pos)]

    print(ans % 1_000_000_007)



if __name__ == "__main__":
    main()

Solution (Python):
N,M=map(int,input().split())
a=[0]*(N+1)
INF=10**100
NUM=7+10**9
dp=[0]*(N+1)

for _ in range(M):
    tmp=int(input())
    a[tmp]=1

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

print(dp[N])

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

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

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


for i in range(1,N+1):
    lis[i] = (lis[i-1] + lis[i-2])%(10**9+7)
    if i in A:
        lis[i] = 0

print(lis[N])

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

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

print(dp[n] % 1000000007)

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

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

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

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

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

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

    if i+1<=n and dp[i+1]!=-1:
        dp[i+1]=(dp[i+1]+dp[i])%MOD
    if i+2<=n and dp[i+2]!=-1:
        dp[i+2]=(dp[i+2]+dp[i])%MOD

print(dp[-1])

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

dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1 if not broken[1] else 0
MOD = 10 ** 9 + 7

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

print(dp[n])

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

dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1 if not broken[1] else 0
MOD = 10 ** 9 + 7

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

print(dp[n])

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

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

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

print(dp[n])

Solution (Python):
def getval():
    n,m = map(int,input().split())
    a = [int(input()) for i in range(m)]
    return n,m,a

def main(n,m,a):
    dp = [0 for i in range(n+1)]
    mod = 10**9 + 7
    dp[0] = 1
    it1 = iter(a)
    it2 = iter(a)
    d = dict(zip(it1,it2))
    for i in range(1,n+1):
        if i in d:
            continue
        if i==1:
            dp[1] = dp[0]
        else:
            dp[i] = (dp[i-1] + dp[i-2]) % mod

    print(dp[n])
    

if __name__=="__main__":
    n,m,a = getval()
    main(n,m,a)

Solution (Python):





MOD = 10 ** 9 + 7



INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))

def do():
    n,m=INTM()
    b_sts=[False]*n
    for i in range(m):
        b=INT()
        b-=1
        b_sts[b]=True
        
    step=[0]*(n+2)
    step[1]=1
    for i in range(n):
        if b_sts[i]:
            continue
        else:
            step[i+2]=(step[i+1]+step[i])%MOD
    print(step[-1]%MOD)

if __name__=='__main__':
    do()

Solution (Python):

_INPUT = """\
10 2
4
5
"""
"""
K = int(input())
H, W, K = map(int, input().split())
a = list(map(int, input().split()))
xy = [list(map(int, input().split())) for i in range(N)]
p = tuple(map(int,input().split()))
"""
def main():
    N, M = map(int, input().split())
    a = set([int(input()) for i in range(M)])
    inf = 10**9+7

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

     
if __name__ == '__main__':
    import io
    import sys
    import math
    import itertools
    from collections import deque

    
    main()

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

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

    print(dp[-1] % mod)


if __name__ == "__main__":
    main()

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

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

    print(dp[-1] % mod)


if __name__ == "__main__":
    main()

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

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

    print(dp[-1] % mod)


if __name__ == "__main__":
    main()

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

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

mod = 10**9 + 7

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

print(dp[-1])

Solution (Python):
def main():
    N,M = map(int,input().split())
    mod = 10**9 + 7
    a = [0]*(N+1)
    a[0] = 1
    banned = [False]*(N+1)
    for x in range(M):
        n = int(input())
        banned[n] = True
    for i in range(1,N+1):
        res = 0
        if not banned[i-1]:
            res += a[i-1]
        if not banned[i-2]:
            res += a[i-2]
        a[i] = res
    print(a[-1]%mod)
    return

main()

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

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

if n>1:
    if not a[2]:
        dp[2]=dp[1]+1

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

print(dp[n]%mod)

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
mod = 1000000007
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(dp[N])

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

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



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] %= 10**9+7
    
print(dp[N])

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


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


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] %= 10**9+7
    
print(dp[N])

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

issafe = [1] * (N+1)
for i in range(M):
  a = int(input())
  issafe[a] = 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):
import sys
readline = sys.stdin.readline

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

broken = set([int(readline()) for i in range(M)])

dp = [0] * (N + 1)
dp[0] = 1
if 1 not in broken:
  dp[1] = 1
  
DIV = 10 ** 9 + 7

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

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

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

dp=[0]*(n+1)
dp[0]=1
dp[1]=1
for i in range(2,n+1):
    dp[i]=dp[i-1]+dp[i-2]
    dp[i]%=mod
if m==0:
    ans=dp[n]
else:
    begin=0
    end=a[0]-1
    for i in range(m):
        end=a[i]-1
        ans*=dp[end-begin]
        
        if(i+1<m and a[i+1]==a[i]+1):
            ans=0
            break
            
        else:
            begin=end+2

    ans*=dp[n-a[m-1]-1]

print(ans%mod)

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

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


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


if __name__ == '__main__':
    main()

Solution (Python):
N, M = map(int, input().split())
MOD = 10 ** 9 + 7
s = 0

def comb(n, k):
  if k > n - k:
    k = n - k
  de = 1
  nu = 1
  for i in range(k):
    de *= (n - i)
    de = de % MOD
    nu *= (i + 1)
    nu = nu % MOD
  nu = pow(nu, -1, MOD)
  return (de * nu) % MOD

def calc_from_step(step):
  temp = 0
  for i in range(1 + (step // 2)):
    temp += comb(step-i, i)
  return temp


arr = [1, 1]
steps = []
step = 0
s = 0
for i in range(M):
  l = int(input()) - 1
  steps.append(l-s)
  if s > l:
    print(0)
    exit()
  if step < l - s:
    step = l - s
  s = l + 2
l = N
steps.append(l-s)
if step < l - s:
  step = l - s

for i in range(step - 1):
  arr.append((arr[i] + arr[i+1])%MOD)
ans = 1

for i in steps:
  ans *= arr[i]
  ans = ans % MOD
print(ans)

Solution (Python):
MOD=1000000007
N,M=map(int,input().split())
cnt=[0 for _ in range(N+1)]
cnt[0]=1
for _ in range(M):
    a=int(input())
    cnt[a]=-1
for i in range(1,N+1):
    if cnt[i]==-1:
        cnt[i]=0
        continue
    if i==1:
        cnt[i]=cnt[i-1]
    else:
        cnt[i]=(cnt[i-1]+cnt[i-2])%MOD
print(cnt[N])

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

Solution (Python):
n,m=map(int,input().split())
a1=0
ans=1
for i in range(m+1):
    if i==m:
        a2=n+1
    else:
        a2=int(input())
    l=a2-a1
    if l==0:
        print(0)
        exit()
    if l>2:
        fst=1
        snd=1
        for _ in range(l-2):
            nfst=snd
            snd=fst+nfst
            fst=nfst
        ans*=snd
    a1=a2+1
print(ans%(10**9+7))

Solution (Python):
import sys
INF = 1 << 60
MOD = 10**9 + 7 
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    n, m = map(int, input().split())
    S = set(int(input()) for _ in range(m))

    a, b = 0, 1 
    for i in range(1, n + 1):
        if i in S:
            a, b = b, 0
        else:
            a, b = b, (a + b) % MOD

    print(b)
resolve()

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

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

dp[0], dp[1] = 1, 1 
if not A[0]: 
  dp[1] = 0

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

Solution (Python):

"""
Created on Sun Sep 13 12:37:37 2020

@author: liang
"""

"""
フィボナッチ数列生成
【DP(?)】　: 配列を使用することで計算量が爆発するのを防ぐ
【小さいものから計算する】の原則

【方針】
　通常の配列を用いたフィボナッチ数列の生成方法の応用版
 壊れた階段のフィボナッチ数列の値を　0 にすることで、実質遷移を止めることが出来る。
"""
key = 10**9 + 7
N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]+[-1]

fibs = [0]*(N+1)
index = 0
for i in range(N+1):
    
    if i == A[index]:
        fibs[i] = 0
        index += 1
    elif i == 0 or i == 1:
        fibs[i] = 1
    else:
        fibs[i] = (fibs[i-1] + fibs[i-2])%key
        

print(fibs[N])

Solution (Python):

"""
Created on Sun Sep 13 12:06:59 2020

@author: liang
"""


key = 10**9 + 7
N, M = map(int, input().split())

A = [int(input()) for _ in range(M)]
A.sort()
A += [-1]

def solve():
    steps = list()
    count = 0
    index = 0
    
    for i in range(N+1):
        if i == A[index]:
            if count == 0:
                return 0
            else:
                steps.append(count)
                count = 0
                if index < M:
                    index += 1
        else:
            count += 1
    else:
         steps.append(count)
         count = 0
        
    smax = max(steps)
    fibs = [0] * smax
    
    for i in range(smax):
        if i == 0 or i == 1:
            fibs[i] = 1
        else:
            fibs[i] = fibs[i-1] + fibs[i-2]  
    else:
        ans = 1
        for s in steps:
            
            ans *= fibs[s-1]
            
            ans %= key
    
    
    
    return ans

ans = solve()        
print(ans)

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

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

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

mod = 10**9+7
a.append(float('INF'))
a = a[::-1]
dp = [0] * (n+1)
dp[0] = 1
if a[-1] != 1:
    dp[1] = 1
else:
    a.pop()
for i in range(2, n+1):
    if i == a[-1]:
        a.pop()
        continue
    dp[i] = dp[i-1] + dp[i-2]
    dp[i] %= mod
print(dp[n])

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

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

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

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

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

print(dp[n])

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

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

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

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


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

print(memo[-1]%mod)

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

mod = 1000000007

memo = [-1]*(n+1)
memo[0] = 0

for k in range(m):
    memo[a[k]] = 0

for i in range(1, n+1):
    if memo[i] != -1:
        pass 
    elif i <= 2:
        memo[i] = memo[i-1] + 1
    else:
        memo[i] = memo[i-1] + memo[i-2]
print(memo[-1]%mod)

Solution (Python):
N, M = map(int, input().split())
A = set(list(int(input()) for _ 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[-1])

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

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

print(lst[n])

Solution (Python):

def input2():
	return map(int,input().split())

def Fib(n):
	a,b=0,1
	if n==1:
		return a
	elif n==2:
		return b
	else:
		for i in range(n-2):
			a,b=b,a+b
		return b

n,m=input2()
A=[int(input()) for _ in range(m)]
INF = 1000000007

start=0 
ans=1 
for a in A:
	tmp=a-start
	if tmp>1:
		fib=Fib(tmp+1)
		ans*=fib
		ans%=INF
	elif tmp==0:
		ans=0
		break
	start=a+1

if n-start>1:
	ans*=Fib(n-start+2)
	ans%=INF
print(ans)

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

p = 10**9+7
dp = [0]*(n+1)
dp[0] = 1

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

Solution (Python):
import sys
from sys import exit
from collections import deque
from bisect import bisect_left, bisect_right, insort_left, insort_right 
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import sin, cos, tan, asin, acos, atan, degrees, radians

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def powmod(n,i,mod):
    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)
def div2(x):
    return x.bit_length()
def div10(x):
    return len(str(x))-(x==0)
def perm(n,mod=None):
    ans = 1
    for i in range(1,n+1):
        ans *= i
        if mod!=None:
            ans %= mod
    return ans
def intput():
    return int(input())
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x,d=1):
        self.setdefault(x,0)
        self[x] += d
class comb():
    def __init__(self, n, mod=None):
        self.l = [1]
        self.n = n
        self.mod = mod
    def get(self,k):
        l,n,mod = self.l, self.n, self.mod
        k = n-k if k>n//2 else k
        while len(l)<=k:
            i = len(l)
            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)
        return l[k]

N,M = mint()
A = set()
for _ in range(M):
    A.add(intput())
dp = [1]+[0]*N
for i in range(N):
    if i+1 not in A:
        dp[i+1] += dp[i]
    if i+2<=N and i+2 not in A:
        dp[i+2] += dp[i]
print(dp[N]%MOD)

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

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

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

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

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

if __name__ == "__main__":
    main3()

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

Solution (Python):
import sys
pin=sys.stdin.readline
sys.setrecursionlimit(10000000)

def f(n):
  if n==0:
    return 1
  if n==1:
    if dp[n]==0:
      return 0
    return 1
  if dp[n]==0:
    return 0
  if dp[n-1]==-1:
    dp[n-1]=f(n-1)
  if dp[n-2]==-1:
    dp[n-2]=f(n-2)
  return dp[n-1]+dp[n-2]


N,M=map(int,pin().split())
mod=1000000007
dp=[-1]*(N+1)
dp[0]=1
for i in range(M):
  dp[int(pin())]=0
print(f(N)%mod)

Solution (Python):
n, m = map(int, input().split())
step = [True] * n
r = [0,1]
MOD = 10**9 + 7
for _ in range(m):
    broken = int(input())
    step[broken - 1] = False
for i, tf in enumerate(step):
    if tf:
        r += [(r[i] + r[i+1]) % MOD]
    else:
        r += [0]
print(r[-1])

Solution (Python):

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

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


if __name__ == '__main__':
    main()

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())
mod = pow(10, 9) + 7
dp = [0] * (n + 5)
for _ in range(m):
    a = int(input())
    dp[a] = -1
dp[0] = 1
for i in range(n):
    if not dp[i] == -1:
        dp[i] %= mod
    else:
        continue
    if not dp[i + 1] == -1:
        dp[i + 1] += dp[i]
    if not dp[i + 2] == -1:
        dp[i + 2] += dp[i]
ans = dp[n] % mod
print(ans)

Solution (Python):
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy


import heapq
sys.setrecursionlimit(10**6)

INF = 10**18
import bisect
import statistics
mod = 10**9+7


N, M = map(int, input().split())
a = set()
for i in range(M):
    a.add(int(input()))

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

print(dp[N] % mod)

Solution (Python):
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy


import heapq
sys.setrecursionlimit(10**6)

INF = 10**18
import bisect
import statistics
mod = 10**9+7


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

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

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

ans = 1
a = -1
for i in range(M):
    b = int(input())
    c = b - a - 2
    if c < 0:
        print (0)
        sys.exit()
    else:
        ans = (ans * dp[c]) % mod
        a = b

ans = (ans * dp[N-a-1]) % mod

print(ans)

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