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 = [int(input()) for _ in range(m)]
dp = [0] * (n + 1)
dp[0] = 1
for obstacle in a:
    dp[obstacle] = -1

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

print(dp[-1] % 1000000007)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
a = [int(input()) for i in range(m)]
step_patern = [0,1]
for i in range(n):
         step_patern.append(step_patern[i] + step_patern[i+1])
kankaku = []
tmp = 0
for i in range(len(a)):
         kankaku.append(a[i] - tmp)
         tmp = a[i] +1
kankaku.append(n + 1 - tmp)
ans = 1
for i in kankaku:
         ans *= step_patern[i]
         ans %= (10 ** 9) +7
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter 
from collections import defaultdict
from collections import deque
import math
import itertools
import heapq
import sys
sys.setrecursionlimit(10**6)

#n=int(input())
#n,m=list(map(int,input().split()))
#a=list(map(int,input().split()))
input_list = lambda : list(map(int,input().split()))

n,m=input_list()
c=[True for _ in range(n+1)]
mod=10**9+7

for _ in range(m):
    num=int(input())
    c[num]=False

fib=[1,1]
if not c[1]:
    fib[1]=0

for i in range(2,n+1):
    if c[i]:
        fib.append((fib[i-1]+fib[i-2])%mod)
    else:
        fib.append(0)


print(fib[-1]%mod)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import itertools
import math
import fractions
import functools
import copy

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

dp = [0]*(n+5)
dp[0] = 1
for i in range(n):
    if i+1 not in a:
        dp[i+1] += dp[i]
    if i+2 not in a:
        dp[i+2] += dp[i]
print(dp[n] % 1000000007)

Submission status: Accepted

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

A = [int(input().strip()) for _ in range(m)]

a0 = 1
if len(A) == 0:
  a1 = 1
else:
  a1 = 1 if A[0] !=1 else 0
mod = 1000000007

ANS=[0]*(n+1)
ANS[0]=a0
ANS[1]=a1
Next = A if a1 !=0 else A[1:]
next = 0
for i in range(2, n+1):
    if next <= len(Next)-1:
        if i == Next[next]:
            ANS[i] = 0
            next += 1
            continue
    ANS[i] = ANS[i-2] + ANS[i-1]

print(ANS[n]%mod)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
"""
N段の階段 M個の階段が壊れている
"""

N, M = map(int, input().split())
arr = [int(input()) for _ in range(M)]
no_step =[0]*N

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

for i in range(M):
    no_step[arr[i]-1]=1

count = [0]*N
if no_step[0]==0:
    count[0]=1

if no_step[1]==1:
    count[1]=0
elif no_step[0]==0 and no_step[1]==0:
    count[1]=2
elif no_step[0]==1 and no_step[1]==0:
    count[1]=1

for i in range(3,N+1,1):
    count[i-1] = count[i-2]+count[i-3]
    if no_step[i-1] == 1:
        count[i-1] = 0

ans =count[N-1]%1000000007
print(ans)

Submission status: Accepted

Solution code:
P = 10 ** 9 + 7

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

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

# N番目に到達する組み合わせの数を保持するテーブル  
table = [0] * (N + 1)
table[0] = 1

for i in range(N):
  if i in broken:
    continue
    
  for step in (1, 2):
    if i + step <= N:
      table[i + step] += table[i]
      table[i + step] %= P

print(table[N])

Submission status: Accepted

Solution code:
import sys

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

# 壊れている床
a = [-1]

for i in range(M):
    a.append(int(input()))
    # 連続して壊れていたら辿り着けない
    if a[i+1] - a[i] == 1:
        print(0)
        sys.exit()
        
# フィボナッチ数値
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

# 階段を登る組み合わせ
combi = 1

for i in range(len(a) - 1):
    # 次の穴との距離
    dis = a[i+1] - a[i]
    combi *= fib(dis)

dis = N+1 - a[-1]
combi *= fib(dis)

print(combi % 1000000007)

Submission status: Accepted

Solution code:
p = 10**9 + 7

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

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

for i in range(N):
  for j in range(i+1,min(N,i+2)+1):
    if ok[j]:
      dp[j] += dp[i]
      dp[j] %= p
      
print(dp[N]%p)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9 + 7
input = sys.stdin.readline

def inp():
    return int(input())
def inpl():
    return list(map(int,input().split()))
def inpm():
    return map(int,input().split())

n,m = inpm()
dp = [0] * (n+2)
for _ in range(m):
    a = int(input())
    dp[a] = -1

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

Submission status: Accepted

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

for _ in range(m):
    a.add(int(input()))

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

mod = 10**9 + 7

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

print(dp[-1] % mod)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
mod = 1000000007

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

memo = [0]*(n+1)

memo[0] = 1

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
MOD = 1000000007

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

dp = [0] * (n + 1)
dp[0] = 1
# i=now, j=next
for i in range(n):
    for j in range(i+1, min(n, i + 2) + 1):
        if not oks[j]:
            continue
        dp[j] += dp[i]
        dp[j] %= MOD

print(dp[n])

Submission status: Accepted

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

Submission status: Accepted

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

st = [1] * (N+1)

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


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

#print(st)
print(st[-1] % 1000000007)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys

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

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

MOD = 10 ** 9 + 7


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

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


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

Submission status: Accepted

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

k = 1000000007


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

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



print(dp[-1])

Submission status: Accepted

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

k = 1000000007


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

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

n = dp[-1] % k

print(n)

Submission status: Accepted

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

Submission status: Accepted

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

s = [1]*(n+1)

if 1 in a:
    s[1] = 0

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

Submission status: Accepted

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

s = [1]*(n+1)

if 1 in a:
    s[1] = 0

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

a = [True]*(n+1)

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

dp = [0]*(n+1)

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

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

print(dp[n])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

print(dp[-1] % mod)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
dp = [0] * (n + 1)
for i in range(m):
    dp[a[i]] = -1
#dp
mod = 10 ** 9 + 7
dp[0] = 1
if dp[1] != -1:
    dp[1] = 1
for i in range(2, n + 1):
    if dp[i - 1] == -1 and dp[i - 2] == -1:
        print(0)
        quit()
    if dp[i] == -1:
        continue
    if dp[i - 1] == -1:
        dp[i] = dp[i - 2]
    elif dp[i - 2] == -1:
        dp[i] = dp[i - 1]
    #dp[i] = max(dp[i - 1], dp[i - 2])
    else:
        dp[i] = dp[i - 1] + dp[i - 2]
    dp[i] %= mod 
    #dp[i] %= mod
#dp[n]
if dp[n] == -1:
    print(0)
else:
    print(dp[n])

Submission status: Accepted

Solution code:
import numpy as np


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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

dp_table = [0] * (n+1)

dp_table[0] = 1


#a[j]と考えるためのj
j = 0
for i in range(1,n+1):
    if j < m and i == a[j]:
        dp_table[i] = 0 #つまり変わらない
        j += 1
    elif i == 1:
        dp_table[i] = dp_table[i-1]
    else:
        dp_table[i] = dp_table[i-1] + dp_table[i-2]

print(dp_table[-1] % 1000000007)

Submission status: Accepted

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

Submission status: Accepted

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

MOD = 10 ** 9 + 7

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

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

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

print(dp[n])

Submission status: Accepted

Solution code:
BIG = 10**9+7

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


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

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

print(dp[-1])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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

print(dp[n])

Submission status: Accepted

Solution code:
#C
n, m = map(int, input().split())
a = [1] * (n + 1)#進めるかどうか
b = [1] * (n + 1)#移動方法
#進めない:0 進める:1
for i in range(m):a[int(input())] = 0
mod = 1e9+7
# print(a)
if a[1] == 0:b[1] = 0
for i in range(2, n+1):b[i] = (b[i - 1] + b[i - 2]) * a[i] % mod
    #b[i]=(b[2段前]+b[1段前])*a[i] 進めるかどうか(1,0)
print(int(b[n]))

Submission status: Accepted

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

Submission status: Accepted

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

mod = 1000000007

dp=[0]*(n+1)

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

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

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

print(dp[-1]%mod)

Submission status: Accepted

Solution code:
# 2020/05/10
# AtCoder Beginner Contest 129 - C

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

dp = [0] * (n+1)

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

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

# Output
print(dp[n])

Submission status: Accepted

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

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

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

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

    return dp[i]

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import itertools,sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,M = LI()
a = set([I() for _ in range(M)])
dp = [0]*(N+1) #1_indexed
dp[0] = 1
dp[1] = 0 if 1 in a else 1
for i in range(2,N+1):
    if i in a:
        dp[i] = 0
        continue
    dp[i] = (dp[i-1]+dp[i-2])%(10**9+7)
print(dp[-1])

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
import itertools,sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,M = LI()
a = set([I() for _ in range(M)])
dp = [0]*(N+1) #1_indexed
dp[0] = 1
dp[1] = 1
for i in range(N+1):
    if i in a:
        dp[i] = 0
        continue
    if i-2>=0:
        dp[i] = (dp[i-1]+dp[i-2])%(10**9+7)
print(dp[-1])

Submission status: Accepted

Solution code:
import itertools,sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,M = LI()
a = set([I() for _ in range(M)])
dp = [0]*(N+1) #1_indexed
dp[0] = 1
dp[1] = 0 if 1 in a else 1
for i in range(N+1):
    if i in a:
        dp[i] = 0
        continue
    if i-2>=0:
        dp[i] = (dp[i-1]+dp[i-2])%(10**9+7)
print(dp[-1])

Submission status: Accepted

Solution code:
import itertools,sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,M = LI()
a = set([I() for _ in range(M)])
dp = [0]*(N+1) #1_indexed
dp[0] = 1
dp[1] = 0 if 1 in a else 1
for i in range(1,N+1):
    if i in a:
        dp[i] = 0
        continue
    if i-2>=0:
        dp[i] = (dp[i-1]+dp[i-2])%(10**9+7)
print(dp[-1])

Submission status: Accepted

Solution code:
# アキュムレータあり再帰
import sys  # 追加
sys.setrecursionlimit(500*500)

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

# 初期値
s0 = 1
if (a[1] == 1):
    s1 = 0
else:
    s1 = 1


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


print(calc(n, s0, s1))

Submission status: Accepted

Solution code:
#! /Library/Frameworks/Python.framework/Versions/3.7/bin/python3
D = 1000000007
n, m = map(int, input().split())
a = [0] * (10**5 + 1)
for i in range(m):
    a[int(input())] += 1

# 初期値
s = [0] * (n + 1)
s[0] = 1
if (a[1] == 1):
    s[1] = 0
else:
    s[1] = 1

# 暫定結果を格納する配列


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


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


solver(n)
print(s[n])

Submission status: Accepted

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


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

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

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

print(dp[n] % MOD)

Submission status: Accepted

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

is_broken = [False] * (N+1)

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

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

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

print(dp[-1])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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


print(dp[-1])

Submission status: Accepted

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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

print(dp[n])

Submission status: Accepted

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

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

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

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
broke = False
if N == 1:
    print('1')
    broke = True
elif 1 in a and 2 not in a:
    dp[1] = 1
elif 1 not in a and 2 in a:
    dp[0] = 1
else:
    dp[0] = 1
    dp[1] = 2
if 1 in a and 2 in a:
    print('0')
    broke = True
else:
    for i in range(3,N+1):
        if i-1 in a and i-2 in a:
            print('0')
            broke = True
            break
        elif i-1 in a:
            dp[i-1] = dp[i-3]
        elif i-2 in a:
            dp[i-1] = dp[i-2]
        else:
            dp[i-1] = (dp[i-2] + dp[i-3]) % 1000000007
if broke == False:
    print(dp[N-1])

Submission status: Accepted

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