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
input=sys.stdin.buffer.readline
n,m=map(int,input().split())
mod=10**9+7
dp=[0]*(n+1)
for _ in range(m):
    a=int(input())
    dp[a]=-1
dp[0]=1
for i in range(n):
    if dp[i]>=0:
        if i+1<=n:
            if dp[i+1]>=0:
                dp[i+1]+=dp[i]
                dp[i+1]%=mod
        if i+2<=n:
            if dp[i+2]>=0:
                dp[i+2]+=dp[i]
                dp[i+2]%=mod
print(dp[n] if dp[n]>0 else 0)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
from decimal import Decimal
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,m = inpl()
s = set([inp() for i in range(m)])
dp = [0] * (n+1)
dp[0] = 1
for i in range(n):
    if i+1 in s:
        dp[i+1] = 0
        continue
    if i == 0:
        dp[i+1] += dp[i]
    else:
        dp[i+1] += dp[i] + dp[i-1]
        dp[i+1] %= mod
print(dp[-1])

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] * (10 ** 5 + 10)
dp[0] = 1
for i in range(N):
    dp[i] %= MOD
    if broken[i]:
        dp[i] = 0
    dp[i + 1] += dp[i]
    dp[i + 2] += dp[i]
print(dp[N] % MOD)

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(1, N+1):
    if broken[i]:
        dp[i] = 0
        continue
    if i == 1:
        dp[i] = dp[i - 1]
    else:
        dp[i] = dp[i - 1] + dp[i - 2]
    dp[i] %= MOD

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
dp = [-1]*(n+1)
dp[0] = dp[1] = 1

for x in a:
    dp[x] = 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])

Submission status: Accepted

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

for x in a:
    dp[x] = 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] if dp[n] != INF else 0)

Submission status: Accepted

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

dp[0] = dp[1] = 1

for x in a:
    dp[x] = 0

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

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


print(dp[n] if dp[n] != INF else 0)

Submission status: Accepted

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

dp[0] = dp[1] = 1

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

for x in a:
    dp[x] = 0

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

    if dp[i-1] == INF and dp[i-2] == INF:
        break
    elif dp[i-1] == INF or dp[i-2] == INF:
        dp[i] = min(dp[i-1], dp[i-2])
    else:
        dp[i] = dp[i-1]+dp[i-2]
    dp[i] %= MOD


print(dp[n] if dp[n] != INF else 0)

Submission status: Accepted

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

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

for now in range(n):
    for next in range(now + 1, min(n + 1, now + 3)):
        if a[next]:
            dp[next] += dp[now]
            dp[next] %= 1000000007

print(dp[n])

Submission status: Accepted

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

dp[0] = dp[1] = 1

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

for x in a:
    dp[x] = 0

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

    if dp[i-1] == INF and dp[i-2] == INF:
        break
    elif dp[i-1] == INF or dp[i-2] == INF:
        dp[i] = max(dp[i-1], dp[i-2])
    else:
        dp[i] = dp[i-1]+dp[i-2]
    dp[i] %= MOD


print(dp[n] if dp[n] != INF else 0)

Submission status: Accepted

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

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

p[0] = 1
for now in range(0,n):
	for next in range(now+1,min(n,now+2)+1):
		if p_ok[next]:
			p[next] += p[now]
			p[next] %= mod


ans = p[n]
print(ans%mod)

Submission status: Accepted

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

# a = [int(input()) for _ in range(M)]
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
    else:
        dp[i] = dp[i - 1] + dp[i - 2]
        dp[i] %= 1000000007

print(dp[-1])

Submission status: Accepted

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

for i in range(m):
    broken = int(input())
    ok_step[broken] = False

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

Submission status: Accepted

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

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

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

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

    dp[i] = dp[i] % MOD

print(dp[N])

Submission status: Accepted

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

if m == 0:
  l = [-1]
else:
  l = [int(input())-1 for _ in range(m)]
res = [0, 1]
skip = 0

for i in range(n):
  if i == l[skip]:
    res[0] = res[1]
    res[1] = 0
    if skip < m-1:
      skip += 1
  else:
    tmp = res[1]
    res[1] += res[0]
    res[0] = tmp
    res[1] %= 10**9 + 7
    res[0] %= 10**9 + 7
      
print(res[1])

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
l = [int(input())-1 for _ in range(m)]
res = [0, 1]
skip = 0

if m != 0:
  for i in range(n):
    if i == l[skip]:
      res[0] = res[1]
      res[1] = 0
      if skip < m-1:
        skip += 1
    else:
      tmp = res[1]
      res[1] += res[0]
      res[0] = tmp
      res[1] %= 10**9 + 7
      res[0] %= 10**9 + 7
else:
  for i in range(n):
    tmp = res[1]
    res[1] += res[0]
    res[0] = tmp
    res[1] %= 10**9 + 7
    res[0] %= 10**9 + 7
      
print(res[1])

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
#import sys
MOD = 10 ** 9 + 7
INFI = 10**10
#input = sys.stdin.readline
import math

import itertools

#import bisect

import copy
from functools import lru_cache

def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

#    h,w,a,b = map(int, input().split())
#    c = [[0 for j in range(n)] for i in range(n)]




def main():
    n,m=map(int,input().split())
    broken=set(int(input()) for _ in range(m))
    dp=[0]*(n+5)
    dp[0]=1
    dp[1]=1
    ans=0
    for i in range(2,n+1):
        if i-1 not in broken:
            dp[i]+=dp[i-1]%MOD
        if i-2 not in broken:
            dp[i]+=dp[i-2]%MOD
    if n==1:
        print(1)
    else:
        print(dp[n]%MOD)

if __name__ == "__main__":

    main()

Submission status: Accepted

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

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

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

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-2]+dp[i-1])%1000000007
    if i in a:
        dp[i]=0
print(dp[n])

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
broken_step = [0] * (N + 1)
for _ in range(M):
    n = int(input())
    broken_step[n] = 1

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

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

print(dp[-1] % 1000000007)

Submission status: Accepted

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

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[n]%1000000007)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import collections
mod = 10 ** 9 + 7
N, M = map(int, input().split())
a = collections.deque([])
for _ in range(M):
    a_m = int(input())
    if len(a) > 0 and a_m == a[-1] + 1:
        print(0)
        exit()
    a.append(a_m)

dp = [1]

if len(a) > 0:
    if 1 != a[0]:
        dp.append(1)
    else:
        dp.append(0)
        a.popleft()
else:
    dp.append(1)

for i in range(2, N + 1):
    if len(a) > 0:
        if i != a[0]:
            tmp = dp[0] + dp[1]
        else:
            tmp = 0
            a.popleft()
    else:
        tmp = dp[0] + dp[1]
    dp[0] = dp[1]
    dp[1] = tmp

print(dp[-1] % mod)

Submission status: Accepted

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

Submission status: Accepted

Solution code:

N, M = [int(s) for s in input().split()]
b = [0]*N
for _ in range(M):
    b[int(input().strip())-1] = 1

a = [0]*N

if b[0] == 0:
    a[0] = 1
if N > 1 and b[1] == 0:
    a[1] = 1 + a[0]

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

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()            
A = [INT() for i in range(M)]

dp = [INF] * (N + 1)
dp[0] = 1
dp[1] = 1
for a in A:
    dp[a] = 0

for i in range(1, N+1):
    if dp[i] == 0:
        continue
    if i-2 >= 0:
        dp[i] = min(dp[i], dp[i-1] + dp[i-2])
    elif i - 1 >= 0:
        dp[i] = min(dp[i], dp[i-1])
# print(dp)
print(dp[N] % mod)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
break_step = [INT() for _ in range(M)] + [0]

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

index = 0
for i in range(1, N + 1):
	if break_step[index] == i:
		comb[i] = 0
		index += 1
	else:
		if i == 1:
			comb[i] = 1
		else:
			comb[i] = comb[i - 2] + comb[i - 1]

print(comb[N]%mod)

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
# from fractions import gcd
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from functools import reduce
from bisect import bisect_left, insort_left
from heapq import heapify, heappush, heappop

INPUT = lambda: sys.stdin.readline().rstrip()
INT = lambda: int(INPUT())
MAP = lambda: map(int, INPUT().split())
S_MAP = lambda: map(str, INPUT().split())
LIST = lambda: list(map(int, INPUT().split()))
S_LIST = lambda: list(map(str, INPUT().split()))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


def main():
    N, M = MAP()
    A = [INT() for i in range(M)]

    dp = [1] * (N + 1)
    for a in A:
        dp[a] = 0

    for i in range(N-1):
        dp[i+2] = dp[i+2] * (dp[i] + dp[i+1]) % mod
     
    print(dp[N])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


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

for i in range(M-1):
    if A[i+1] - A[i] == 1:
        print(0)
        exit()

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()

a = [INT() for _ in range(M)]
ng = [0]*(N+1)
for i in a:
	ng[i] = 1

dp = [0]*(N+1)
dp[0] = 1
dp[1] = 1
for i in range(2, N+1):
	for j in range(1, 3):
		if not ng[i-j]:
			dp[i] = (dp[i]+dp[i-j])%mod
print(dp[N])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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

for i in range(2, n + 1):
    if i not in list_score:
        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())
list_score = set([int(input()) for _ in range(m)])

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

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

for i in range(2, n + 1):
    if i not in list_score:
        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 _ in range(m)])
p, q = 0, 1
mod = 10 **9 + 7
for i in range(1, n+1):
    p, q = q, ((p+q)%mod)*(i not in A)
print(q)

Submission status: Accepted

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

dp = [0 for _ in range(n + 2)] #i-1段目に登る方法の数
dp[0] = 0
dp[1] = 1
tmp = 0
if m != 0:
    for i in range(n):
        if i + 1 != a[tmp]:
            dp[i + 2] = (dp[i] + dp[i + 1]) % (pow(10, 9) + 7)
        elif i + 1 == a[tmp]:
            if tmp < m - 1:
                tmp += 1
            dp[i + 2] = 0
elif m == 0:
    for i in range(n):
        dp[i + 2] = (dp[i] + dp[i + 1]) % (pow(10, 9) + 7)
#print(dp)
print(dp[n + 1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import math
n, m = map(int,input().split())
a = []
for i in range(m):
    a.append(int(input()))

if m == 0:
    dp = [0 for _ in range(n)] #i + 1段目に登る方法の数
    dp[0] = 1
    if n >= 2:
        dp[1] = 2
    for i in range(2, n):
        dp[i] = (dp[i - 1] + dp[i - 2]) % (pow(10, 9) + 7)
    print(dp[n - 1])
    exit()

tmp = 0
dp = [0 for _ in range(n)]
if 1 == a[tmp]:
    dp[0] = 0
    tmp += 1
else:
    dp[0] = 1
if n >= 2 and tmp < m and 2 == a[tmp]:
    dp[1] = 0
    tmp += 1
elif n >= 2 and (tmp >= m or 2 != a[tmp]):
    dp[1] = dp[0] + 1

for i in range(2, n):
    if tmp < m and i + 1 == a[tmp]:
        dp[i] = 0
        tmp += 1
    else:
        dp[i] = (dp[i - 1] + dp[i - 2]) % (pow(10, 9) + 7)
#print(dp)
print(dp[n - 1] % (pow(10, 9) + 7))

Submission status: Accepted

Solution code:
MOD=10**9+7

N,_,*a = map(int, open(0).read().split())
A=set(a)
dp = [0 for _ in range(N+1)]
dp[:2] = 1, 0 if 1 in A else 1
for i in range(2,N+1):
    if i not in A:
        dp[i]=(dp[i-1]+dp[i-2])%MOD
    
print(dp[N])

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(2147483647)
INF = float("inf")
MOD = 1000000007

a=open(0)
N,_,*a = map(int, a.read().split())

dp = [-1 for _ in range(100010)]
dp[0] = 0
for i in a: dp[i] = 0
def rec(i):
    if dp[i] > -1:
        return dp[i]
    if i<3:
        dp[i] = rec(i-1) + 1
        return dp[i]
    dp[i] = (rec(i-1)+rec(i-2))%MOD
    return dp[i]
    
print(rec(N))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
p = 10**9 + 7

n, m = map(int, input().split())
A = list(int(input()) for i in range(m))
isHole = [False]*(n+1)


dp = [1]*(n+1)

for a in A:
    isHole[a] = True
    dp[a] = 0


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

print(dp[-1]%p)

Submission status: Accepted

Solution code:
if __name__ == "__main__":
    mod = 10 ** 9 + 7
    n, m = map(int, input().split())
    a = list()
    for i in range(m):
        a.append(int(input()))

    dp = [0] * (n + 1)

    for aa in a:
        dp[aa] = -1

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

    if n > 1:
        if dp[2] != -1:
            dp[2] = 1 + dp[1]
        else:
            dp[2] = 0

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

    print(dp[n])

Submission status: Accepted

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

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

for i in range(1, N+1):
    if i not in out:
        if i == 1:
            check[i] = check[i-1]
        else:
            check[i] = check[i-2] + check[i-1]
    else:
        check[i] = 0

print(check[N] % 1000000007)

Submission status: Accepted

Solution code:
def solve():
    mod = 10 ** 9 + 7
    N, M = map(int, input().split())
    isBreakable = [False] * (N+1)
    for i in range(M):
        a = int(input())
        isBreakable[a] = True

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

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
div = 10 ** 9 + 7
N, M = map(int, input().split())
h = [1] * (N + 1)
for _ in range(M):
    index = int(input())
    h[index] = 0

a = 1
b = h[1]
for i in range(2, N + 1):
    a, b = b, (a + b) * h[i] % div

print(b)

Submission status: Accepted

Solution code:
#abc129 c
mod=1000000007

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

dp=[1]*(n+2) #n段のときn+1個要素必要
dp[n+1]=0 #幻の７段目は０
for i in a:
    dp[i]=0
for i in range(n-1,-1,-1):
    if dp[i]==0:#階段壊れている
        continue
    dp[i]=dp[i+1]+dp[i+2]

ans=dp[0]%mod
print(ans)

Submission status: Accepted

Solution code:
# Problem C - Typical Stars

# input process
N , M = map(int, input().split())
hole_list = [0]*(N+1)
for i in range(M):
    hole_i = int(input())
    hole_list[hole_i] = 1

# initialization
cost_list = [0]*(N+1)
cost_list[0] = 1
MOD = 10**9 + 7

# cumulative sum process
for i in range(1, N+1):
    if hole_list[i]==1: # if current pos is hole
        continue

    if hole_list[i-1]==0:
        cost_list[i] += cost_list[i-1]
        cost_list[i] %= MOD

    if i-2>=0:
        if hole_list[i-2]==0:
            cost_list[i] += cost_list[i-2]
            cost_list[i] %= MOD

# output process
print(cost_list[N])

Submission status: Accepted

Solution code:
MOD = 10**9 + 7

N, M = map(int,input().split())
a = [int(input()) for k in range(M)] + [-1]

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

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

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

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

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

print(dp[-1])

Submission status: Accepted

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

dp = [0]*(N+100)
for i in range(N+1):
  if i == 0:
    dp[i] = 1
    continue
  if i in a:
    continue
  elif i-1 in a:
    dp[i] = dp[i-2]
  elif i-2 in a:
    dp[i] = dp[i-1]
  elif i-1 in a and i-2 in a:
    break
  else:
    dp[i] = dp[i-1] + dp[i-2]
  dp[i] = dp[i]%(7+10**9)
    
print(dp[N]%(7+10**9))

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
for i in range(m):
    dp[a[i]]=-1

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

Submission status: Accepted

Solution code:
MOD = 10**9+7
N,M = map(int,input().split())
DP = [0]*(N+3)
DP[0] = 1
state = [1]*(N+3)
for _ in range(M):
    i = int(input())
    state[i] = 0

for i in range(N):
    for j in range(1,3):
        if state[j+i]:
            DP[j+i] += DP[i]
            DP[j+i] %= MOD

print(DP[N])

Submission status: Accepted

Solution code:
import sys
def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    A = [int(input()) for _ in range(M)] + [-1]
    dp = [Mint() for _ in range(N+1)]
    dp[0] = Mint(1)
    j = 0
    for i in range(1,N+1):
        if i == A[j]:
            j += 1
            continue
        dp[i] += dp[i-1]
        if i >= 2: dp[i] += dp[i-2]

    print(dp[N])

class Mint:
    def __init__(self, value=0, mod=10**9+7):
        self.value = ((value % mod) + mod) % mod
        self.mod = mod

    @staticmethod
    def get_value(x): return x.value if isinstance(x, Mint) else x

    def inverse(self):
        a, b = self.value, self.mod
        u, v = 1, 0
        while b:
            t = a // b
            b, a = a - t * b, b
            v, u = u - t * v, v
        return (u + self.mod) % self.mod

    def __repr__(self): return str(self.value)
    def __eq__(self, other): return self.value == other.value
    def __neg__(self): return Mint(-self.value, self.mod)
    def __hash__(self): return hash(self.value)
    def __bool__(self): return self.value != 0

    def __iadd__(self, other):
        self.value = (self.value + Mint.get_value(other)) % self.mod
        return self
    def __add__(self, other):
        new_obj = Mint(self.value, self.mod)
        new_obj += other
        return new_obj
    __radd__ = __add__

    def __isub__(self, other):
        self.value = (self.value - Mint.get_value(other) + self.mod) % self.mod
        return self
    def __sub__(self, other):
        new_obj = Mint(self.value, self.mod)
        new_obj -= other
        return new_obj
    def __rsub__(self, other):
        new_obj = Mint(Mint.get_value(other), self.mod)
        new_obj -= self
        return new_obj

    def __imul__(self, other):
        self.value = self.value * Mint.get_value(other) % self.mod
        return self
    def __mul__(self, other):
        new_obj = Mint(self.value, self.mod)
        new_obj *= other
        return new_obj
    __rmul__ = __mul__

    def __ifloordiv__(self, other):
        other = other if isinstance(other, Mint) else Mint(other, self.mod)
        self *= other.inverse
        return self
    def __floordiv__(self, other):
        new_obj = Mint(self.value, self.mod)
        new_obj //= other
        return new_obj
    def __rfloordiv__(self, other):
        new_obj = Mint(Mint.get_value(other), self.mod)
        new_obj //= self
        return new_obj

if __name__ == '__main__':
    main()

Submission status: Accepted

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


if __name__ == "__main__":
    solve()