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.



Sample input:
6 1
3


Sample output:
4

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
a_lst = set(int(input()) for i in range(m))
dp = [0]*(n+1)
dp[0] = 1
x = 10**9 + 7

for i in range(1,n+1):
    if i in a_lst:
        continue
    else:
        if i==1:
            dp[i] = dp[i-1]
        elif i>1:
            dp[i] = (dp[i-2] + dp[i-1]) % x

answer = dp[-1]

print(answer)

Submission status: Accepted

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

mod=10**9+7

oks = [True]*(n+1)
for i in range(m):
    oks[a[i]] = False

dp=[0]*(n+1)
dp[0]=1
for now in range(0,n):
    for nex in range(now+1,min(n,now+2)+1):
        if oks[nex]:
            dp[nex]+=dp[now]
            dp[nex]%=mod
print(dp[n])

Submission status: Accepted

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

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

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

print(dp[n])

Submission status: Accepted

Solution code:

MOD = 1000000007

def main():
    n,m = map(int,input().split())
    al = [False for _ in range(n+1)]
    for i in range(m):
        a = int(input())
        al[a] = True
    
    dp = [0 for _ in range(n+1)]
    dp[0] = 1
    dp[1] = 1 if al[1] == False else 0

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

    print(dp[n])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:

MOD = 1000000007

def main():
    n,m = map(int,input().split())
    al = [False for _ in range(n+1)]
    for i in range(m):
        a = int(input())
        al[a] = True
    
    dp = [0 for _ in range(n+1)]
    dp[0] = 1
    dp[1] = 1 if al[1] == False else 0

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

    print(dp[n] % MOD)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=[]
mod=1e9+7
oks=[True]*(n+1)
for i in range(m):
    a.append(int(input()))
    oks[a[i]]=False
dp=[0]*(n+1)
dp[0]=1
for i in range(n):
    for j in range(i+1, min(n,i+2)+1):
        if oks[j]:
            dp[j]+=dp[i]
            dp[j]%=mod

print(int(dp[n]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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
    if i >= 2:
        dp[i] = (dp[i - 1] + dp[i - 2]) % mod
    else:
        dp[i] = dp[i - 1]
print(dp[-1])

Submission status: Accepted

Solution code:
def main():
    n, m = map(int, input().split())
    num_list = [int(input()) for _ in range(m)]

    dp = [0] * (n+1)
    dp[0] = 1
    
    for num in num_list:
        dp[num] = -1

    if dp[1] != -1:
        dp[1] = 1
    else:
        dp[1] = 0

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

    print(dp[n]%1000000007)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

INF=-float("inf")

n,m=mii()

arr=lin(m)

dp=[0]*(n+1)

for i in arr:
    dp[i]=INF

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

if dp[1]!=INF:
    dp[1]=1

if dp[1]==INF and dp[2]!=INF:
    dp[2]=1

elif dp[1]==INF and dp[2]==INF:
    print(0)
    exit()
elif dp[1]!=INF and dp[2]!=INF:
    dp[2]+=dp[1]
    

for i in range(2,n+1):
    if dp[i]!=INF:
        if dp[i-1]!=INF and dp[i-2]==INF:
            dp[i]+=dp[i-1]
        elif dp[i-1]==INF and dp[i-2]!=INF:
            dp[i]+=dp[i-2]
        elif dp[i-1]!=INF and dp[i-2]!=INF:
            dp[i]+=dp[i-1]+dp[i-2]
        else:
            dp[i]=0
#print(dp)
print(dp[-1]%mod)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
a = [False]*(n+1)
for i in range(m):
  ii = int(input())
  a[ii] = True
  
dp = [0]*(n+1)
dp[0] = 1

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

print(dp[-1])

Submission status: Accepted

Solution code:


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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
broken=[]
for i in range(m):
  broken.append(int(input()))
b=set(broken)
l=[1]
for j in range(1,n+1):
  if j in b:
    l.append(0)
  elif j==1:
    l.append(1)
  else:
    l.append(l[j-2]+l[j-1])
print(l[n]%(10**9+7))

Submission status: Accepted

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

broken = set(a)
mod = 10**9 + 7

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

for i in range(1,n +1):
    if i in broken:
        continue

    if i == 1:
        dp[1] = dp[0]
        continue

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

print(dp[n])

Submission status: Accepted

Solution code:
from functools import lru_cache
import sys
sys.setrecursionlimit(1000000)

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

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

@lru_cache()
def f(x):
    v = 0
    if x<0:
        return 0
    if x == 0:
        return 1
    if a[x-1]:
        v += f(x-1)
    if a[x-2]:
        v += f(x-2)
    v %= mod
    return v

print(f(N))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
li = [True]*(n+1)

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

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

for j in range(1,n+1):
    if li[j]:
        dan[j] += dan[j-1]
        if j >= 2:
            dan[j] += dan[j-2]

print(dan[n]%(10**9+7))

Submission status: Accepted

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

p = [True for _ in range(n+1)]

p[0] = 1
p[1] = 1

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

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

print(p[n]%(10**9+7))

Submission status: Accepted

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

p = [True for _ in range(n+1)]

p[0] = 1
p[1] = 1

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

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

print(p[n]%(10**9+7))

Submission status: Accepted

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

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

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

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

print(dp[-1])

Submission status: Accepted

Solution code:
import sys

MOD = 10 ** 9 + 7

n, m, *a = map(int, sys.stdin.read().split())
broken = set(a)

def main():
    res = [None] * (n + 1)
    res[0] = 1
    res[1] = 0 if 1 in broken else 1
    
    for i in range(2, n+1):
        if i in broken:
            res[i] = 0
        else:
            res[i] = res[i-2] + res[i-1]
            res[i] %= MOD
    
    return res[n]
    
if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
n,m = map(int,input().split())
a = [int(input()) for _ in range(m)]
dp = [-1]*(n+2)#dp[k]はk-1段目に到達する方法
dp[0] = 0
dp[1] = 1
mod = 10**9+7
for i in a:
    dp[i+1] = 0
for i in range(n+2):
    if dp[i] == -1:#already visited or prepared
        dp[i] = (dp[i-1]+dp[i-2])
#print(dp)
print(dp[n+1]%mod)

Submission status: Accepted

Solution code:
import os, sys, re, math, queue

def run_it():
	N,M = list(map(int,input().split(' ')))
	divider = 1000000007
	n_max = 100000
	memo = [0] * (n_max + 1)
	memo[0] = 1
	memo[1] = 1
	for i in range(2,n_max+1):
		memo[i] = (memo[i-2] + memo[i-1]) % divider
	
	cur = 0
	ret = 1
	for m in range(M+1):
		if m < M:
			a = int(input())
		else:
			a = N + 1
		
		if a == cur:
			ret = 0
			break
		ret *= memo[a-cur-1]
		ret %= divider
		cur = a + 1

	print(ret)

if sys.platform == 'ios':
	for i in range(3):
		sys.stdin = open('Ctest' + str(i) + '.txt')
		run_it()
else:
	run_it()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
A=set(int(input()) for i in range(m))
 
x=[0]*(n+1)
x[0]=1
if 1 in A:
    x[1]=0
else:
    x[1]=1
 
for j in range(2,n+1):
    if j in A:
        x[j]=0
    else:
        x[j]=(x[j-1]+x[j-2])%(10**9+7)
        
 
print(x[n])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n, m = list(map(int, input().split(' ')))
aaa = [0] * (n + 3)
for i in range(m):
    aaa[int(input())] = True

dp = [1] * (n + 3)
for i in range(1, n+1):  # 1e5
    if not aaa[i]:
        dp[i]  = dp[i-1]
        if i >= 2:
            dp[i] += dp[i-2]
        dp[i] = dp[i] % int(1e9 + 7)
    else:
        dp[i] = 0
print(dp[n])

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
A = list()
for i in range(m):
    a = int(input())
    A.append(a)
dp = [0]*(n+1)
dp[0] = 1
if 1 in A:
  del A[0]
else:
  dp[1] = 1
for i in range(2,n+1):
    if len(A) != 0:        
        if i != A[0]:
            dp[i] = dp[i-2] + dp[i-1]
            dp[i] = dp[i]%1000000007
        else:
          del A[0]
    else:
        dp[i] = dp[i-2] + dp[i-1]
        dp[i] = dp[i]%1000000007
print(dp[-1]%1000000007)

Submission status: Accepted

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

if N == 1:
    if M == 0:
        print(1)
    elif M == 1:
        print(0)
else:
    cost = [0 for _ in range(N + 1)]
    cost[0] = 1

    cnt = 0
    A.append([0])
    for i in range(1, N + 1):
        if i == A[cnt]:
            cnt += 1
            continue
        else:
            cost[i] = cost[i - 1] + cost[i - 2]

    print(cost[-1] % q)

Submission status: Accepted

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

if N == 1:
    if M == 0:
        print(1)
    elif M == 1:
        print(0)
else:
    cost = [0 for _ in range(N + 1)]
    cost[0] = 1

    cnt = 0
    A.append([0])
    for i in range(1, N + 1):
        if i == A[cnt]:
            cost[i] = 0
            cnt += 1
        else:
            cost[i] = (cost[i - 1] + cost[i - 2]) % q

    print(cost[-1])

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
lst = [True] * (n + 1)
for _ in range(m):
    a = int(input())
    lst[a] = False
dp = [0] * (n + 1)
dp[0] = 1
div = 10 ** 9 + 7
for i in range(1, n + 1):
    if  lst[i]:
        dp[i] += dp[i - 1]
        dp[i] = dp[i] % div
        if i > 1:
            dp[i] += dp[i - 2]
            dp[i] = dp[i] % div

print(dp[n])

Submission status: Accepted

Solution code:
mod = 10**9 + 7

n, m = map(int, input().split())
fib = [1] * (n+1)
for i in range(2, n+1):
  fib[i] = (fib[i-1] + fib[i-2]) % mod
count = 1
start = 0
for _ in range(m):
  a = int(input())
  stop = a-1
  if start > stop:
    count = 0
    break
  count = count * fib[stop - start] % mod
  start = a+1
stop = n
count = count * fib[stop - start] % mod
print(count)

Submission status: Accepted

Solution code:
# 数え上げ問題

NM = input()
N = int(NM.split(' ')[0])
M = int(NM.split(' ')[1])

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

a = sorted(a)
a.append(0)

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


for i in range(1,N+1):
    # 階段が壊れていたらそこに至る手段の数は０
    if(a[0] == i):
        dp[i] = 0
        del a[0]
        continue

    if(i>1):
        dp[i] = dp[i-1] + dp[i-2]
    else:
        dp[i] = dp[i-1]

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:

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

mod = 1000000007;

# dpテーブル, 壊れた階段を記録するテーブル用意
dp = [0]*(N+1)
broken = [0]*(N+1)

# 初期化
dp[0] = 1
dp[1] = 1

# 壊れている階段は-1で定義
for _ in range(M) :
    broken[int(input())] = -1

# 漸化式から求めていく
for i in range(2, N+1):
        
    if (broken[i-1] != -1):
        dp[i] += dp[i-1]
    
    if (broken[i-2] != -1):
        dp[i] += dp[i-2]
    
    dp[i] %= mod

print(dp[-1])

Submission status: Accepted

Solution code:
MOD = 10**9 + 7

import sys
input = sys.stdin.readline

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

# i段目にたどり着く方法
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1 if a[1] == 0 else 0

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

print(dp[-1])

Submission status: Accepted

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

dp[0] = 1
dp[1] = 1 if isSafe[1] == 0 else 0

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

print(dp[len(dp)-1])

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
BrokenSteps = [int(input()) for _ in range(M)]
 
MOD = 1000000007
 
# DPテーブル
dp = [0]*(N+1)
dp[0] = 1
if 1 not in BrokenSteps:  # 1段目が壊れている場合もあるので注意
    dp[1] = 1

steps = list(range(2, N+1))  # 0,1段目は計算済みなので2段目以降
NoBrokenSteps = list(set(steps) - set(BrokenSteps))
    
for i in NoBrokenSteps:
    dp[i] = (dp[i - 1] + dp[i - 2]) % MOD
        
print(dp[-1])

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
DP = [0]*(N+2)
DP[0] = 1
A = []
for i in range(M):
    a = int(input())
    DP[a] = -1

mod = 1000000007

# print(N, M, A)

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

Submission status: Accepted

Solution code:
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 i in range(n+1):
    for j in range(i+1,min(n+1,i+3)):
        if oks[j]:
            dp[j] += dp[i]
            dp[j] %= 1000000007
print(dp[n])

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
mod = int(1e9 + 7)
notbroken = [True for _ in range(n+1)]

for i in a:
  notbroken[i] = False

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

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

print(dp[n])

Submission status: Accepted

Solution code:
n, m = [int(i) for i in input().split(" ")]

l = list(range(1, n+1))
divider = 10**9 + 7
ans = [0]*(n + 1)
broken = [False]*(n+1)
ans[0] = 1
ans[1] = 1

for i in range(m):
    a = int(input())
    broken[a] = True
    if a == 1:
        ans[1] = 0
    
for i in range(2,n+1):
    if broken[i] == False:
        ans[i] = ans[i-1] + ans[i-2]
    
   
print(ans[n] % divider)

Submission status: Accepted

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

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


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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
a = set()
for i in range(m):
    a.add(int(input()))
dp = [0] * (n+1)
dp[0] = 1
if not(1 in a):
    dp[1] = 1

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

Submission status: Accepted

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

is_broken=[True]*(n+1)
for i in range(m):
  is_broken[broken[i]]=False
   
dp=[0]*(n+1)
dp[0]=1
if is_broken[1]:
  dp[1]=dp[0]
  
for i in range(2,n+1):
    if is_broken[i]:
       dp[i]=dp[i-1]+dp[i-2]
       dp[i]%=mod
    else:
      dp[i]=0
      
print(dp[n])

Submission status: Accepted

Solution code:
def fibonacci(n):
    if n<0:
        return 0
    else:
        a=1
        b=1
        if n==0:
            return a
        elif n==1:
            return b
        else:
            i=n-2
            while i>=0:
                x=a
                a=b
                b=x+b
                i=i-1
            return b

N,M=map(int,input().split())
a=[]
for _ in range(0,M):
    a.append(int(input()))
a.append(N+1)
m=1
for i in range(0,M+1):
    if i==0:
        m=fibonacci(a[i]-1)
    else:
        m=m*fibonacci(a[i]-a[i-1]-2)

print(m%(10**9+7))

Submission status: Accepted

Solution code:
Num = 10 ** 9 + 7
N, M = map(int, input().split())
danger = -1
if M != 0:
  danger = int(input())
count = 1
l = [1, 1]
for i in range(1, N):
  if i == danger:
    l[1] = 0
    if count < M:
      danger = int(input())
      count += 1
  l = [l[1] % Num, l[0] + l[1]]
  if l == [0, 0]:
    break
if N == danger:
  l[1] = 0
print(l[1] % Num)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
mod = 10**9+7
N,M = [int(i) for i in input().split()]
a = [0] * M
for i in range(M) :
    a[i] = int(input())
dp = [0] * (N+1)
dp[0] = 1
A = set(a)
for i in range(1,N+1) :
    if i in A:
        continue
    else :
        if i == 1 :
            dp[i] += dp[i-1]
        else :
            dp[i] = dp[i-1] + dp[i-2]
print(dp[N] % mod)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
MOD = 10**9 + 7

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

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

Submission status: Accepted

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

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

for i in range(m):
   b[int(input())] = -1

for i in range(n):
   if (b[i] != -1):
      if (b[i+1] != -1):
         b[i+1] += b[i]
      if (b[i+2] != -1):
         b[i+2] += b[i]

print(b[n] % 1000000007)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
a = [True for _ in range(N)]
MOD = 10**9+7
for i in range(M):
    a[int(input())] = False
dp = [0 for _ in range(N+1)]
dp[0] = 1
if a[0] == True:
    dp[1] = 1
for i in range(2, N+1):
    if a[i-2] == True:
        dp[i] += dp[i-2]
    if a[i-1] == True:
        dp[i] += dp[i-1]
    dp[i] %= MOD
print(dp[N])

Submission status: Accepted

Solution code:
n, m = [int(x) for x in input().split()]
a = set([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[n])

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
a = set([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[n])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main(N,M,a):
    dp = [-1]*N
    dp[0] = 1
    if N != 1:
        dp[1] = 2
    for i in a:
        if i == 1:
            dp[0] = 0
            dp[1] = 1
        else:
            dp[i-1] = 0
    for i in range(2,N):
        if dp[i] != 0:
            dp[i] = dp[i-1] + dp[i-2]
    return dp[-1]
N,M = map(int, input().split())
a = list(int(input()) for i in range(M))

print(main(N,M,a) % 1000000007)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
a = [0] * m
for i in range(m):
    a[i] = int(input())

dp = [999] * (n + 1)
if 0 not in a:
    dp[0] = 1
if 1 not in a:
    dp[1] = 1
if 2 not in a and n >= 2:
    if 1 in a:
        dp[2] = 1
    else:
        dp[2] = 2

mod = 10**9+7

for i in range(len(a)):
    dp[a[i]] = 0

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

print(dp[-1])

Submission status: Accepted

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

Submission status: Accepted

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

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

#初期化
dp=[-1]*N
dp[0]=1

for i in a:
    dp[i-1] = 0

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

print(dp[N-1]%1000000007)

Submission status: Accepted

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

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

#初期化
dp=[-1]*N
dp[0]=1

for i in a:
    dp[i-1] = 0

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

print(dp[N-1]%1000000007)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
broken=[False for i in range(n+1)]
for i in range(m):
    a=int(input())
    broken[a]=True
ans=[1]
if broken[1]:
    ans.append(0)
else:
    ans.append(1)
for i in range(2,n+1):
    if broken[i]:
        ans.append(0)
    else:
        ans.append((ans[i-1]+ans[i-2])%1000000007)
print(ans[n])

Submission status: Accepted

Solution code:

def main(N, M, a):
    dp = [-1] * (N+1)
    dp[0] = 1
    dp[1] = 1
    for i in a :
        dp[i] = 0
    for i in range(2, len(dp)):
        dp[i] = dp[i-1] + dp[i-2] if dp[i] != 0 else 0
    return dp[-1] % (10**9+7)

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

Submission status: Accepted

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

for i in range(m-1):
    if a[i] + 1 == a[i+1]:
        print(0)
        exit()
dp=[0]*(n+1)
dp[0]=1

for i in range(1,n+1):
    if len(a)!=0 and i == a[0]:
        dp[i]=0
        a.pop(0)
        continue
    dp[i]=dp[i-1]+dp[i-2]
    dp[i] = dp[i] % (10**9+7)

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

Submission status: Accepted

Solution code:
def calculate(n, bindexes):
    arr = []
    for i in range(n):
        if bindexes.get(i):
            arr.append(0)
            continue

        if i == 0:
            arr.append(1)
        elif i == 1:
            arr.append(arr[i-1] + 1)
        else:
            arr.append(arr[i-1] + arr[i-2])
    return arr

S = input().split(" ")

n = int(S[0])
m = int(S[1])
brokenStairIndexes = {}

for i in range(m):
    brokenStairIndexes.setdefault(int(input())-1, True)


arr = calculate(n,brokenStairIndexes)

print(arr[n-1] % 1000000007)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
s = 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 s:
        continue
    x = dp[i - 1]
    if i > 1:
        x += dp[i - 2]
    dp[i] = x % MOD

print(dp[n])

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
s = [int(input()) for _ in range(m)]
s.append(n+1)

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

for i in range(n - 1):
    dp[i + 2] = dp[i + 1] + dp[i]
mae = 0
ans = 1
for i in s:
    if i == mae:
        ans=0
    else:
        ans *= dp[i - 1 - mae]

    mae = i + 1
print(ans % (10 ** 9 + 7))

Submission status: Accepted

Solution code:
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

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
answer = dp[N]
print(answer)

Submission status: Accepted

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

dp = [1] * (n + 10)
for i in range(len(a)):
    dp[a[i]] = 0

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

print(dp[n] % 1000000007)

Submission status: Accepted

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

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

print(dp[n]%mod)

Submission status: Accepted

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

dp=[True]*(N+2)
S=list(int(input()) for _ in range(M))
for i in S:
    dp[i]=False
num=[0]*(N+2)
MOD=1000000007
num.insert(0,1)
for i in range(0,N):
    if dp[i]:
        num[i+1]+=num[i]
        num[i+1]%=MOD
        num[i+2]+=num[i]
        num[i+2]%=MOD
print(num[N])

Submission status: Accepted

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

Submission status: Accepted

Solution code:

n,m=map(int,input().split())
broken=[False for i in range(n+1)]
const=1000000007
for i in range(m):
    a=int(input())
    broken[a]=True
n_way=[1,1]
if broken[1]:
    n_way=[1,0]
for i in range(2,n+1):
    if not broken[i] :
        n_way.append((n_way[i-1]+n_way[i-2])%const)
    else:
        n_way.append(0)
print(n_way[n])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

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

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

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

#print(dp)
print(dp[-1]%mod)

Submission status: Accepted

Solution code:
import sys

N, M = list(map(int, input().split()))
if M == 0:
  h = []
else:
  h = sys.stdin.readlines()
  h = set(map(int, list(set(h))))

if N==1:
  print(1)
elif N==2:
  if M==1:
    print(1)
  else:
    print(2)
else:
  DP = []
  DP.append(1)
  if 1 in h:
    DP.append(-1)
  else:
    DP.append(1)
  for i in range(2,N+1):
    if DP[i-2]<0 and DP[i-1]<0:
      print(0)
      exit()
    DP.append(0)
    if i in h:
      DP[i] = -1
    else:
      if DP[i-1]>=0:
        DP[i] += DP[i-1]
      if DP[i-2]>=0:
        DP[i] += DP[i-2]
      DP[i] = DP[i] % 1000000007
  print(int(DP[N]))

Submission status: Accepted

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

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

print(dp[n] % 1000000007)