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:
import sys
#from collections import defaultdict, deque, Counter
#from bisect import bisect_left
#import heapq
import math
#from itertools import groupby as gb
#from itertools import permutations as perm
#from itertools import combinations as comb
#from fractions import gcd
#import numpy as np

stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)
MIN = -10 ** 9
MOD = 10 ** 9 + 7
INF = float("inf")
IINF = 10 ** 18

#n = int(stdin.readline().rstrip())
#l = list(map(int, stdin.readline().rstrip().split()))
n,m = map(int, stdin.readline().rstrip().split())
#AB = [list(map(int, stdin.readline().rstrip().split())) for _ in range(n)]

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

broke = [0 for _ in range(n+1)]
for i in range(m):
    broke[int(stdin.readline().rstrip())] = 1

for i in range(n):
    if broke[i+1] == 1:
        dp[i+1] = 0
    elif i == 0:
        dp[i+1] = dp[i]
    else:
        dp[i+1] = dp[i] + dp[i-1]

print(dp[n]%MOD)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
ct = [0] * (n+1)
A = [True] * n
for _ in range(m):
    A[int(input())-1] = False

ct[0] = 1
mod = 1000000007
for i in range(1, n+1):
    if A[i-2] == True:
        ct[i] += ct[i-1]
    if i > 1 and A[i-3] == True:
        ct[i] += ct[i-2]
    ct[i] %= mod
print(ct[-1])

Submission status: Accepted

Solution code:
# C - Typical Stairs

MOD = (10 ** 9) + 7
N, M = map(int, input().split())
A = [False] * (N + 1)
for _ in range(M):
    A[int(input())] = True
dp = [0] * (N + 1)
dp[0] = 1
if A[1] == False:
    dp[1] = 1

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

print(dp[N])

Submission status: Accepted

Solution code:
# ABC129C

def fib(m):
    if m < 0:
        return 0
    elif m == 0 or m == 1:
        return 1
    elif m == 2:
        return 2
    else:
        a, b = 1, 1
        for i in range(m - 1):
            a, b = b, a + b
        return b
#
n, m = map(int, input().split())
ans = 1
begin = 0
for i in range(m):
    a = int(input())
    end = a - 1 - begin
    #print("@", begin, end)
    begin = a+1
    ans = ans * (fib(end) % 1000000007) % 1000000007
#print("#", begin, end)
end = n - begin
ans = ans * (fib(end) % 1000000007) % 1000000007
print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
def main():
    N, M, *a = map(int, read().split())
    A = {i for i in a}
    P = (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 i not in A:
            dp[i] = (dp[i-1] + dp[i-2])%P
    print(dp[N])
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
def main():
    N, M, *a = map(int, read().split())
    A = {i for i in a}
    P = (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 i in A:
            continue
        else:
            dp[i] = (dp[i-1] + dp[i-2])%P
    print(dp[N])
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
def main():
    N, M, *a = map(int, read().split())
    A = set()
    P = (10**9)+7
    for i in a:
        A.add(i)

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

    if not (1 in A):
        dp[1] = 1
        

    for i in range(2, N+1):
        if i in A:
            continue
        else:
            dp[i] = (dp[i-1] + dp[i-2])%P
    print(dp[N])
if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

com=1
anow=-1
for i in range(m):
  a=int(input())
  if a-anow==1:
    print(0)
    exit()
  com = (com * fib[a-anow-1]) % 1000000007
  anow=a

com = (com * fib[n-anow]) % 1000000007
print(com)

Submission status: Accepted

Solution code:
import 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)])
if N==1:
    print(1)
    exit()
dp = [0]*(N+1) #1_indexed
dp[1] = 0 if 1 in a else 1
dp[2] = 0 if 2 in a else (1+dp[1])
for i in range(3,N+1):
    if i in a:
        dp[i] = 0
        continue
    dp[i] = (dp[i-2]+dp[i-1])%1000000007
print(dp[-1])

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
a = list(int(input()) for i in range(M))
DP = [0]*(N+1)
pointer = 0
for i in range(N+1):
    if pointer < M:
        if i == a[pointer]:
          DP[i] = 0
          pointer += 1
          continue
    if i == 0 or i == 1:
        DP[i] = 1
    else:
        DP[i] = (DP[i-1]+DP[i-2])
print(DP[-1]%1000000007)

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


print(dp[n])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
def main():
    N, M = map(int, input().split())
    A = deque([int(input()) for i in range(M)])
    if N == 1:
        print(1)
    else:
        dp = [0]*N
        # 一段目と二段目への行き方
        if len(A) != 0:
            out = A.popleft() 
        else:
            out = 0

        if out != 1:
            dp[0] = 1
        else:
            dp[0] = 0
            if len(A) != 0:
                out = A.popleft()
        if out != 2:
            dp[1] = 1+dp[0]
        else:
            dp[1] = 0
            if len(A) != 0:
                out = A.popleft()

        for i in range(2,N):
            if i+1 == out:
                dp[i] = 0
                if len(A) != 0:
                    out = A.popleft()
            else:
                if dp[i-2] != 0 or dp[i-1] != 0:
                    dp[i] = dp[i-2] + dp[i-1]

        if dp[N-1] != 0:
            print(dp[N-1]%(10**9 + 7))
        else:
            print(0)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

for i in range(2,N+1):
    #n-1段目が安全なら
    if a[i-1]==0:
        dp[i]+=dp[i-1]
    #n-2段目が安全なら
    if a[i-2]==0:
        dp[i]+=dp[i-2]
    dp[i] = dp[i]%MOD
print(dp[N])

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
lis=[1]
a=[]
for i in range(m):
  a.append(int(input()))
  
count=0
for i in range(1,n+1):
  try:
    kiken=a[count]
  except IndexError:
    kiken=-1
  if i-2!=-1:
    maemae=lis[i-2]
  else:
    maemae=0
  try:
    mae=lis[i-1]
  except IndexError:
    mae=0
  if i==kiken:
    lis.append(0)
    count+=1
  else:
    lis.append((mae+maemae)%(10**9+7))
    
print(lis[-1])

Submission status: Accepted

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

stair = [True] * N
for i in a:
    stair[i-1] = False

# DP
dp = [0] * N
if stair[0]:
    dp[0] = 1
if N >= 2:
    if stair[1]:
        dp[1] = dp[0] + 1
    else:
        dp[1] = 0

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

print(dp[N-1])

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
flag=list(1 for _ in range(n+1))
count=list(0 for _ in range(n+1))
ans=0
for i in range(m):
    x=int(input())
    flag[x]=0

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

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

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

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

print(dp[n])

Submission status: Accepted

Solution code:
def flog(N, M, a):
  dp = [10**4] * (N + 1)
  dp[0] = 1
  dp[1] = 1
  
  if 1 in a:
    dp[1] = 0

  for j in a:
    dp[int(j)] = 0
    
  for i in range(2, N+1):
    if dp[i] != 0:
      dp[i] = dp[i - 1] + dp[i - 2]
  return dp[N] % INF
      
if __name__ == "__main__":
  N, M = map(int, input().split())
  a = [input() for i in range(M)]
  INF = 1000000007
  print(flog(N, M, a))

Submission status: Accepted

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

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

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

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

print(dp[n])

Submission status: Accepted

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

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

for i in range(ng):
  x = int(input())
  nglist[x] = 1
 
for i in range(1,n+1):

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

  if i==1:
    dp[1] = dp[0]
    continue
  
  dp[i] = (dp[i-2] + dp[i-1]) % MOD

print(dp[n])

Submission status: Accepted

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

dp = [0] * (N + 1)
dp[0] = 1
for now in range(N + 1):
    if now + 1 < N:
        dp[now + 1] += dp[now] if now + 1 not in brokens else 0
        dp[now + 2] += dp[now] if now + 2 not in brokens else 0
    elif now < N:
        dp[now + 1] += dp[now] if now + 1 not in brokens else 0

print(dp[-1] % mod)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    MOD = 10**9 + 7
    N, M = list(map(int, input().split(' ')))
    broken = [0 for _ in range(N + 1)]
    for _ in range(M):
        broken[int(input())] = 1
    dp = [0 for _ in range(N + 1)]
    dp[0] = 1
    for s in range(1, N + 1):
        if broken[s] == 1:
            continue
        n = dp[s - 1]
        if s - 2 >= 0:
            n += dp[s - 2]
        dp[s] += n
        dp[s] %= MOD
    print(dp[N])


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
def main():
  n,m=map(int,input().split())
  a=tuple(int(input()) for _ in range(m))
  a=set(a)
  mod=10**9+7
  pattern=[0]*(n+1)
  pattern[0]=pattern[1]=1
  if 1 in a:
      pattern[1]=0
  for i in range(2,n+1):
      if i in a:
          pattern[i]=0
      else:
          pattern[i]=(pattern[i-1]+pattern[i-2])%mod
  print(pattern[n])
main()

Submission status: Accepted

Solution code:
n,m,*a = map(int,open(0).read().split())
mod = 10**9+7
s = [i-j-2 for i,j in zip(a+[n+1],[-1]+a)]
if -1 in s:
  print(0)
  exit()
f = [1,1]
for i in range(2,max(s)+1):
  f.append(f[i-1]+f[i-2])
ans = 1
for i in s:
  ans = ans*f[i]%mod
print(ans)

Submission status: Accepted

Solution code:
n,m,*a = map(int,open(0).read().split())
mod = 10**9+7
s = [i-j-2 for i,j in zip(a+[n+1],[-1]+a)]
if -1 in s:
  print(0)
  exit()
f = [1,1]
for i in range(2,max(s)+1):
  f.append(f[i-1]+f[i-2])
ans = 1
for i in s:
  ans *= f[i]
print(ans%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+5)
dp[0] = 1
for i in range(n):
    dp[i] %= 1000000007
    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:
import sys
N, M = map(int, input().split())
ok = [True] * (N + 1)
for _ in range(M):
    a = int(sys.stdin.readline())
    ok[a] = False
ans = 0
if N == 1:
    ans = 1
else:
    counts = [0] * (N + 1)
    if ok[1]:
        counts[1] = 1
    if ok[2]:
        counts[2] = counts[1] + 1
    for s in range(3, N + 1):
        if ok[s]:
            count = counts[s-1] + counts[s-2]
            count %= 1000000007
            counts[s] = count
    ans = counts[N]
print(ans)

Submission status: Accepted

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

INF=1000000007
dp=[1]*(n+1)

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

print(dp[-1]%INF)

Submission status: Accepted

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

fact=[0,1]
fact_inv=[0]*(n+1)
for i in range(2,n+1):
  fact.append(fact[-1]*i % MOD)

fact_inv[n] = pow(fact[n],MOD-2,MOD)
for i in range(n-1,-1,-1):
  fact_inv[i] = fact_inv[i+1]*(i+1)%MOD

def comb(n,r):
  return fact[n]*fact_inv[r]*fact_inv[n-r]%MOD

def sigmaComb(dis):
  ans=0
  if dis == 1 or dis == 0:
    return 1
  end=dis//2+1
  for i in range(end):
    t=comb(dis-i,i)
    #print(dis-i,i,t)
    ans+=t
  return ans

hole=[0]
ans=1
for i in range(m):
  t = int(input())
  availLeft=hole[-1]
  availRight=t-1
  dis=availRight-availLeft
  if dis <0:
    ans=0
    break

  ans=ans*sigmaComb(dis)%MOD
  #print("dis=",dis,t,ans)
  hole.append(t+1)
else:
  availLeft=hole[-1]
  availRight=n
  dis=availRight-availLeft
  #print("dis=",dis,hole[-1],ans)
  ans=ans*sigmaComb(dis)%MOD

print(ans%MOD)

Submission status: Accepted

Solution code:

n,m = map(int,input().split())
b = [True] * n
for i in range(m):
    x = int(input())
    b[x-1] = False

dp = [0] * n
if(n == 1):
    print(1)
    exit()
if(b[0]):
    dp[0] = 1
    if(b[1]):dp[1] = 2
else:
    if(b[1]):dp[1] = 1

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

Submission status: Accepted

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

mod = pow(10, 9)+7
point = [0]*(n+1)
point[0] = 1
j = 0
if 1 in a:
    point[1] = 0
    if m >= 2:
        j += 1
else:
    point[1] = 1

if m == 0:
    a = [0]

for i in range(2, n+1):
    if i == a[j]:
        if j < m-1:
            j += 1
    else:
        point[i] = point[i-1]+point[i-2]
        point[i] %= mod

print(point[-1] % mod)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

##### 割り算の切り上げ #####
# tmp = -(-4 // 3)

##### dict の for文 #####
# for k, v in d.items():
#     print(k, v)

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N,M = inputMap()
	ans = [0 for i in range(N+1)]
	ans[0] = 1
	a = []
	for i in range(M):
		tmp = inputInt()
		a.append(tmp)

	a.sort()
	for i,val in enumerate(a):
		if i == 0:
			continue
		if val == a[i-1] + 1:
			print(0)
			sys.exit()

	for i in range(N+1):
		tmp = bisect_left(a, i)
		if tmp < len(a):
			tmp = a[bisect_left(a, i)]
		else:
			tmp = -1
		#print(a[tmp])
		if i+1 <= N:
			if i+1 == tmp:
				pass
			else:
				ans[i+1] = (ans[i+1] + ans[i]) % mod
		if i+2 <= N:
			if i+2 == tmp:
				pass
			else:
				ans[i+2] = (ans[i+2] + ans[i]) % mod

	print(ans[N])


#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)


class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# dfs のサンプル
def dfs(graph,parent,counter,edge):
    stk = []
    stk.append(edge)
    while len(stk) > 0:
        p = stk.pop()
        for e in graph[p]:
            if parent[p] == e:
                continue
            else:
                parent[e] = p
                counter[e] += counter[p]
                stk.append(e)

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
N,m=map(int,input().split())
s= set([int(input()) for i in range(m)])
INF=1000000007

dp=[0]*(N+1)
dp[0]=1
if 1 not in s:
  dp[1]=1
else:
  dp[0]
for i in range(2,N+1):
  if i in s:
    continue
  dp[i]=dp[i-1]+dp[i-2]
  dp[i]=dp[i]%INF
  
print(dp[N])

Submission status: Accepted

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

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

print(dp[n]%1000000007)

Submission status: Accepted

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

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

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

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

if 1 not in A:
    lst[1] = 1


for i in range(2, N + 1):
    if i in A:
        lst[i] = 0
        continue

    lst[i] = lst[i - 1] % MOD + lst[i - 2] % MOD

print(lst[-1] % MOD)

Submission status: Accepted

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

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

print(dp[n])

Submission status: Accepted

Solution code:

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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

num=[0 for i in range(n+2)]
num[0]=0
num[1]=1
mod=10**9+7
for i in range(n):
    if a[i]:
        num[i+2]=(num[i+1]+num[i])%mod

print(num[n+1])

Submission status: Accepted

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

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

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

print(l[-1])

Submission status: Accepted

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

    # i段目に到達するまでのルートの総数
    dp = [1] * (n + 1)

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

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

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

    print(dp[n])
    
resolve()

Submission status: Accepted

Solution code:
import numpy as np
def resolve():
    MOD = 10 ** 9 + 7
    n, m = map(int, input().split())
    a = [int(input()) for _ in range(m)]

    dp = np.array([1] * (n + 1))
    dp[a] = 0

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

    print(dp[n])
    
resolve()

Submission status: Accepted

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

dp = [-float("inf")]*(N+1)
dp[0] = 1
dp[1] = 1

for i in a:
    dp[i] = 0

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

print(dp[N])

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
dp[0] = 1
dp[1] = 0 + (1 not in a)

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

print(dp[n])

Submission status: Accepted

Solution code:
import sys
import functools
sys.setrecursionlimit(10**9)
n,m=map(int,input().split())
a=[1]*(n+1)
for i in range(m):
    a[int(input())]=0
@functools.lru_cache(maxsize=None)
def count(p):
    if p==0 or p==1:
        return a[p]
    if a[p]==1:
        x=count(p-1)+count(p-2)
        return x
    else:
        return 0
print(count(n)%1000000007)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
A = []
for i in range(M):
    A.append(int(input()))
for i in range(M-1):
    if A[i+1]-A[i] == 1:
        print(0)
        exit()
L = []
k = [i for i in range(N+1)]
a = 0
for i in range(M):
    L.append(k[a:A[i]])
    a = A[i]+1
L.append(k[a:N+1])
ans = 1
B = [0,1]
for i in range(N-M):
    B.append(B[-2] + B[-1])
for i in range(len(L)):
    ans *= B[len(L[i])]
print(ans%1000000007)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
a = set([int(input()) for _ in range(m)])
MOD = 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] %= MOD
        
print(dp[n])

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from sys import stdin
N,M = map(int,input().split())
a = [int(stdin.readline()) for _ in range(M)]
A = [0]*(N+1)
mod = 1000000007
A[0] = 1
A[1] = 1
for i in a:
  A[i] = -1
if A[1] == -1:
  A[1] = 0
if not(1 in a):
  A[1] = 1
for i in range(2,N+1):
    if A[i] == -1:
      A[i] = 0
    else:
      A[i] = (A[i-2] + A[i-1]) % mod
print(A[N])

Submission status: Accepted

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

#a = [int(input()) for x in range(m)]
a = set(int(input()) for x in range(m))
_MOD = 1000000007

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

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

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

print(dp[n])

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
DP[1]=1

for a in A:
	DP[a]=-1
	
if DP[1]==-1:DP[1]=0

for i in range(n-1):
		if DP[i+2]<0:
			DP[i+2]=0
		else:
			DP[i+2]=DP[i+1]+DP[i]

print(DP[n]%1000000007)

Submission status: Accepted

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

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

dp = [0]*(n+1)

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

for i in range(2,n+1):
    if i-1 not in a :
      dp[i] += dp[i-1] #n-1 段目が安全なら
    if i-2 not in a :
      dp[i] += dp[i-2] #n-2 段目が安全なら
    dp[i] %= INF

print(dp[n])

Submission status: Accepted

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

total=1
cannot=0
s=-1
if m==0:
    total=fib[n]%(10**9+7)
else:
    for i in range(m):
        t=int(input())
        if t-s == 1:
            cannot+=1
            break
        else:
            total*=fib[t-s-2]
            total%=10**9+7
        s=t



    if n+1-t <= 1:
        cannot+=1
    else:
        total*=fib[n-t-1]
        total%=10**9+7

if cannot != 0:
    print(0)
else:
    print(total)

Submission status: Accepted

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

dp = [-1]*(n+1)
dp[0] = 1
dp[1] = 1
for i in range(m):
    dp[a[i]] = 0
#print(dp)
for i in range(n-1):
    if dp[i+2] == -1:
        dp[i+2] = (dp[i+1] + dp[i]) % mod
    elif dp[i+2] == 0:
        dp[i+2] = 0
#print(dp)
print(dp[n] % mod)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
n,m=map(int,input().split())
a=[1]*(n+1)
for i in range(m):
    a[int(input())]=0
memo={}
def count(p):
    if p in memo:
        return memo[p]
    if p==0:
        return 1
    if p==1:
        return a[p]
    if a[p]==1:
        x=count(p-1)+count(p-2)
        memo[p]=x
        return x
    else:
        memo[p]=0
        return 0
print(count(n)%1000000007)

Submission status: Accepted

Solution code:

n,m=map(int,input().split())
a=[1]*(n+1)
for i in range(m):
    a[int(input())]=0
p0=a[0]
p1=a[1]
for i in range(2,n+1):
    if a[i]==1:
        p2=p0+p1
    else:
        p2=0
    p0,p1=p1,p2
print(p1%1000000007)