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())
mod = 1e9 + 7
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, 1 + min(n, i + 2)):
        if ok[j]:
            dp[j] += dp[i]
            dp[j] %= mod
print(int(dp[-1]))

Submission status: Accepted

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

for i in range(N):
    if i+1 not in a:
        if i+1 == 1:
            count[i] += 1
        elif i+1 == 2:
            count[i] += count[0] + 1
        else:
            count[i] += count[i-1] + count[i-2]

print(count[-1] % mod)

Submission status: Accepted

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

print(dp[n])

Submission status: Accepted

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

Submission status: Accepted

Solution code:

n,m = map(int,input().split())
As = [int(input()) for _ in range(m)]
step = [ 0 for i in range(n+1)]
INF = 1000000007

dp = [0]*(n)

for i in As:
    step[i] = -1

for i in range(n-1):
    if step[i+1] == -1 and step[i+2] == -1:
        print(0)
        exit()
    if step[i+1] != -1:
        step[i+1] +=  1
    if step[i+2] != -1:
        step[i+2] +=  1

step[0] = 1
if step[1] != -1:
    step[1] = 1

for i in range(2,n+1):
    if step[i] == -1 or step[i] == 0:
        continue
    else:
        a = 0
        b = 0
        if step[i-2] != -1:
            a = step[i-2]
        if step[i-1] != -1:
            b = step[i-1]
        step[i] = a + b

print(step[n]%INF)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import copy
from itertools import permutations
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

from itertools import permutations
from math import factorial, hypot

#############
# Main Code #
#############

N, M = getNM()
A = set(getArray(M))

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

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

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
memo = [0]*(N+1)
memo[0] = 1
mod = 10**9+7

for _ in range(M):
    ai = int(input())
    memo[ai] = None

if memo[1] != None:
    memo[1] = 1

for i in range(2, N+1):
    tmp = 0
    if memo[i] == None:
        continue
    if memo[i-1] != None:
        tmp += memo[i-1]
    if memo[i-2] != None:
        tmp += memo[i-2]
    memo[i] = tmp % mod

if memo[N] == None:
    print(0)
else:
    print(memo[N]%mod)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
memo = [0]*(N+1)
memo[0] = 1
mod = 10**9+7

for _ in range(M):
    ai = int(input())
    memo[ai] = None

if memo[1] != None:
    memo[1] = 1

for i in range(2, N+1):
    tmp = 0
    if memo[i] == None:
        continue
    if memo[i-1] != None:
        tmp += memo[i-1]
    if memo[i-2] != None:
        tmp += memo[i-2]
    memo[i] = tmp

if memo[N] == None:
    print(0)
else:
    print(memo[N]%mod)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
memo = [0]*(N+1)
memo[1] = 1
mod = 10**9+7

if N > 1:
    memo[2] = 2

for _ in range(M):
    ai = int(input())
    memo[ai] = None

if N > 1 and memo[1] == None and memo[2] != None:
    memo[2] = 1

for i in range(3, N+1):
    tmp = 0
    if memo[i] == None:
        continue
    if memo[i-1] != None:
        tmp += memo[i-1]
    if memo[i-2] != None:
        tmp += memo[i-2]
    memo[i] = tmp

if memo[N] == None:
    print(0)
else:
    print(memo[N]%mod)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
out = set(int(input()) for _ in range(m))
mod = 1000000007
table = [1,1]
for step in range(2, n+1):
    ans = 0
    if step - 1 not in out:
        ans += table[step-1]
    if step - 2 not in out:
        ans += table[step-2]
    ans %= mod
    table.append(ans)

print(table[n])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(200000)
def num_steps(steps, cache={}):
    if steps in out or steps < 0 :
        return 0
    elif steps == 0:
        return 1

    if steps in cache:
        return cache[steps]
    else:
        one = num_steps(steps-1, cache)
        two = num_steps(steps-2, cache)
        ans = one + two
        cache[steps] = ans

        return ans%mod

n, m = map(int, input().split())
out = set(int(input()) for _ in range(m))
mod = 1000000007

print(num_steps(n))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a = set([])
for i in range(m):
	a.add(int(input()))
"""
壊れてるが2回以上続く→0
壊れてるが1回続く→そこは2段限定,RESET.

let Bn = [n段目に登る通り数]
Ex.1
1 2 3 4 5 6
1 2 # 2 2 4
結局はDPかな？
"""
dp = [0 for _ in range(n+1)]
dp[0] = 1
mod = 10**9+7
for i in range(1,n+1):
	if i in a:
		pass
	elif i==1:
		dp[i] = dp[i-1] % mod
	else:
		dp[i] = (dp[i-1] + dp[i-2]) % mod
print(dp[n] % mod)

Submission status: Accepted

Solution code:
import sys
from collections import Counter
from collections import deque
import heapq
import math
import fractions
import bisect
import itertools
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

mod=1000000007
n,m=mp()
dp=[0]*(n+2)
dp[0]=1
for i in range(m):
    a=int(input())
    dp[a]=-1
for i in range(n):
    if dp[i]==-1:
        continue
    if dp[i+1]>=0:
        dp[i+1]+=dp[i]
        dp[i+1]=dp[i+1]%mod
    if dp[i+2]>=0:
        dp[i+2]+=dp[i]
        dp[i+2]=dp[i+2]%mod
print(dp[-2]%mod)

Submission status: Accepted

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

MOD = 10 ** 9 + 7
# ---------------------------
dp = [0] * (n + 1)
dp[0] = 1
if (1 in a):
    # if (a[1] == 1):
    dp[1] = 0
else:
    dp[1] = 1
# dp approach

for i in range(2, n + 1):
    if (i in a):
        # if (a[i] == 1):
        # (x in list)で探索すると、時間がかかるっぽい
        #dp[i] = 0
        continue
    elif (dp[i - 1] == 0 and dp[i - 2] == 0):
        print(0)
        exit()
    else:
        dp[i] = (dp[i - 1] + dp[i - 2]) % MOD


#print(dp[n] % MOD)
print(dp[n])

Submission status: Accepted

Solution code:
import numpy as np
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect


mod = 1000000007


def nck(n, k, mod):
    bunbo = bunshi = 1
    for i in range(k):
        bunshi = (bunshi * (n-i)) % mod
        bunbo = (bunbo * (i+1)) % mod
    return (bunshi * pow(bunbo, mod-2, mod)) % mod


def patterns(n):
    if (n < 0):
        return 0
    elif (n == 0):
        return 1
    elif (n < 3):
        return n
    ret = [0]*(n+1)
    ret[1] = 1
    ret[2] = 2
    for i in range(3, n+1):
        ret[i] = ret[i-2] + ret[i-1]
    # print('ret', ret[n])
    return ret[n]


N, M = list(map(int, input().split()))
a = [0]*M
for i in range(M):
    a[i] = int(input())
a.append(N+1)
start = 0
ans = 1
for lack in a:
    steps = (lack - 1) - start
    # print('start', start)
    # print('lack', lack)
    # print('input', steps)
    ans = (ans * patterns(steps)) % mod
    # ans = ans % mod
    start = lack + 1
print(ans % mod)

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
# input
stairs, broken = map(int, input().split())
conditions = [1] * (stairs + 1)
for i in range(broken):
  tmp = int(input())
  conditions[tmp] = 0
  
# main
for i in range(2, stairs+1):
  conditions[i] *= (conditions[i-1] + conditions[i-2]) % (10**9+7)

print(conditions[stairs])

Submission status: Accepted

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

MOD = 10**9 + 7
res = [0] * (n+1)
res[0] = 1
res[1] = 0 if a[1] == -1 else 1

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

    # 到達不可能
    if res[i-1] == 0 and res[i-2] == 0:
        break

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

print(res[-1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun May 31 13:40:00 2020

@author: NEC-PCuser
"""
def fibonatch(a, N):
    #d[i][j]: iからjへの最短距離
    n1, n2 = 1, 1
    if N == 0:
        return 1
    elif N == 1:
        return 1
    else:
        for i in range(N - 1):
            if a[i] == 1:
                n1 = 0
            if a[i + 1] == 1:
                n2 = 0
            n1, n2 = n1 + n2, n1
        return (n1) % 1000000007



if __name__ == "__main__":
    N, M = map(int, input().split())
    a = [0] * N
    for i in range(M):
        a[int(input()) - 1] = 1
    
    print(fibonatch(a, N))

Submission status: Accepted

Solution code:
n,m=[int(x) for x in input().rstrip().split()]
a=[int(input()) for i in range(m)]
oks=[True for i in range(n+1)]

mod=10**9+7
dp=[0 for i in range(n+1)]
for i in a:
  oks[i]=False

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

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
broken = [0]*(n+1)
for i 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: continue
    dp[i] = (dp[i+1]+dp[i+2])%1000000007
print(dp[0])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import numpy as np
mod = 1000000007
INF = float("inf")
n,m = map(int,input().split())
dp = [0]*(n+2)
goods = [True] * (n+2)
for _ in range(m):
     x = int(input())
     goods[x] = False

dp[0] = 1
for i in range(n):
    if goods[i]:
        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())
NG = []
a = 10**9+7
NG = [True for _ in range(N + 2)]
for i in range(M):
  NG[int(input())] = False
ans = [0 for _ in range(N + 2)]
ans[0] = 1
for i in range(N):
  if NG[i + 1]:
    ans[i + 1] = (ans[i + 1] + ans[i])%a
  if NG[i + 2]:
    ans[i + 2] = (ans[i + 2] + ans[i])%a
print(ans[N])

Submission status: Accepted

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

Submission status: Accepted

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

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

ok = sorted(set(i for i in range(1, N + 1)) - set(A))

for i in ok:
  if i == 1:
    ans[i] = 1
  else:
    ans[i] = ans[i - 2] + ans[i - 1]
print(ans[-1]%(10**9+7))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
a = [1] * (N+1)
for _ in range(M):
  x = int(input())
  a[x] = 0
# a[n] = 0 なら壊れている。1なら壊れていない。
dp = [0] * (N+1)
dp[0] = 1
if a[1] == 1:
  dp[1] = 1
for i in range(2, N+1):
  if a[i] == 0:
    pass
  else:
    dp[i] = (dp[i-1] + dp[i-2]) % 1000000007
print(dp[N])

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())
    MOD = 10**9 + 7
 
    if n == 1:
        print(1)
        exit()
 
    dp = [0 for _ in range(n+1)]
    dp[0] = 1
    is_broken = [False] * (n+1)
    for i in a:
        is_broken[i] = True
    if 1 in a:
        dp[1] = 0
    else:
        dp[1] = 1
 
    for i in range(2, n + 1):
        if is_broken[i]:
            continue
        else:
            dp[i] = (dp[i - 1] + dp[i - 2]) % MOD
 
    print(dp[-1])
 
if __name__ == '__main__':
    main()

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 = (int(a) for a in input().split())
stair = [1]*(N+1)
for i in range(1 , M+1) :
    a = int(input())
    stair[a] = 0
 
for i in range(2, N+1) :
    stair[i] *= (stair[i-1] + stair[i-2]) % (10**9+7)
         
print(stair[N])

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

import sys
 
N , M = (int(a) for a in input().split())
stair = [1]
brake = []
for i in range(0, N + 1):
    brake.append(False)
for i in range(1 , M+1) :
    a = int(input())
    brake[a] = True

for i in range(1, N+1) :
    if brake[i] :
        stair.append(0)
    elif i == 1 : 
        stair.append(1) 
    else : stair.append((stair[i-1] + stair[i-2]) % (10**9+7))
         
print(stair[N])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import deque
n, m = map(int, input().split())
A = deque([int(input()) for _ in range(m)])
memo = [1, 2] + [0] * (n - 2)
if len(A) > 0:
    if A[0] == 1:
        memo[0] = 0
        memo[1] = 1
        A.popleft()
if len(A) > 0:
    if A[0] == 2:
        memo[1] = 0
        A.popleft()
for i in range(2, n):
    if len(A) > 0:
        if A[0] == i + 1:
            A.popleft()
        else:
            memo[i] = (memo[i - 1] + memo[i - 2]) % 1000000007
    else:
        memo[i] = (memo[i - 1] + memo[i - 2]) % 1000000007
print(memo[n-1])

Submission status: Accepted

Solution code:
import sys
MOD = 10**9 + 7
n, m = map(int, input().split())
a = [int(x) for x in sys.stdin.readlines()]
ans = [1 for i in range(n)]
for x in a:
    ans[x-1] = 0
for i in range(n):
    if i == 0 and ans[i] == 0:
        ans[0] = 0
    elif i == 1:
        if ans[i] == 1:
            ans[1] += ans[0]
        elif ans[i] == 0:
            ans[1] = 0
    elif i >= 2 and ans[i] == 1:
        ans[i] = (ans[i-1] + ans[i-2])%MOD

print(ans[-1])

Submission status: Accepted

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

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

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

print(dp[N])

Submission status: Accepted

Solution code:
# ABC_129 C

def stairs(n, a):
    dp = [0 for _ in range(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
        dp[i] = dp[i-1] + dp[i-2]
            
    result = dp[n] % 1000000007

    print(result)

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


if __name__ == '__main__':
    stairs(n, a)

Submission status: Accepted

Solution code:
# ABC_129 C

def stairs(n, a):
    num_list = set(i for i in range(n+1) if i not in a)
    dp = [0 for _ in range(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
        dp[i] = dp[i-1] + dp[i-2]
            
    result = dp[n] % 1000000007

    print(result)

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


if __name__ == '__main__':
    stairs(n, a)

Submission status: Accepted

Solution code:
# ABC_129 C

def stairs(n, a):
    num_list = set(i for i in range(n+1) if i not in a)
    dp = [0 for _ in range(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]
            
    result = dp[n] % 1000000007

    print(result)

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


if __name__ == '__main__':
    stairs(n, a)

Submission status: Accepted

Solution code:
# ABC_129 C

def stairs(n, a):
    num_list = set(i for i in range(n+1) if i not in a)
    dp = [0 for _ in range(n+1)]
    dp[0] = 1
    if 1 not in a:
        dp[1] = 1
    for i in num_list:
        if i > 1:
            dp[i] = dp[i-1] + dp[i-2]
            
    result = dp[n] % 1000000007

    print(result)

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


if __name__ == '__main__':
    stairs(n, a)

Submission status: Accepted

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

"""
DPを考える
"""

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

print(result[N]%mod)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10000000)
import os
import math
import bisect
import collections
import itertools
import heapq
import re
import queue

# import fractions

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, M = il()
    A = set(iln(M))
    dp = [0]*(N+1)
    dp[0] = 1

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10000000)
import os
import math
import bisect
import collections
import itertools
import heapq
import re
import queue

# import fractions

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, M = il()
    A = set(iln(M))
    dp = [0]*(N+1)
    dp[0] = 1

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

print(dp[n]%1000000007)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
dp=[0]*(N+1)
dp[0]=1
mod=10**9+7
a=[False for _ in range(N+1)]
for _ in range(M):
    a[int(input())]=True
    
for i in range(1,N+1):
    if a[i]:
        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 i in range(M)]
a=set(a)
dp=[0]*(N+1)
dp[0]=1
inf=10**9+7
if 1 not in a:
  dp[1]=1
else:
  dp[1]=0
for i in range(2,N+1):
  if i in a:
    continue
  else:
    dp[i]=dp[i-1]+dp[i-2]
ans=dp[N]%inf
print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_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()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7

N, M = MAP()
a = [INT() for _ in range(M)]
a.append(0)

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

k = 0

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

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

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, tan, asin, acos, atan, radians, degrees#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_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()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7

N, M = MAP()
a = [INT() for _ in range(M)]

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

check = [0]*(N+1)
for i in a:
	check[i] = 1

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

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

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, tan, asin, acos, atan, radians, degrees#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_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()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7

N, M = MAP()
a = [INT() for _ in range(M)]

check = [0]*(N+1)
for i in a:
	check[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 check[i-j]:
			dp[i] = (dp[i] + dp[i-j])%mod

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, tan, asin, acos, atan, radians, degrees#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_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()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7

N, M = MAP()
a = deque([INT() for _ in range(M)])
a.append(0)

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

if a[0] == 1:
	dp[1] = 0
	a.popleft()

q = a.popleft()
for i in range(2, N+1):
	if i == q:
		dp[i] = 0
		q = a.popleft()
	else:
		dp[i] = (dp[i-1] + dp[i-2])%mod

print(dp[N])

Submission status: Accepted

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

print(dp[n])

Submission status: Accepted

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

dp = [0]*(N+1)
dp[0] = 1
A = []
for _ in range(M):
    k = int(input())
    A.append(k)
A = sorted(A,reverse = True)

if len(A)>0:
    a = A.pop()
else: a = -1
        
if a == 1:
    dp[1] = 0
    if len(A)>0:
        a = A.pop()
    if a == 2:
        dp[2] == 0
else:
    dp[1] = 1
    
for i in range(2,N+1):
    if i == a:
        if len(A)>0:
            a = A.pop()
        #continue
    else:
        #if dp[i-1] != 0 and dp[i-2] != 0:
        #    dp[i] = (dp[i-1] + dp[i-2])%mod
        dp[i] = (dp[i-1] + dp[i-2])%mod
        
        #elif dp[i-1] != 0:
        #    dp[i] = dp[i-1]%mod
        #elif dp[i-2] != 0:
        #    dp[i] = dp[i-2]%mod
        #else:
        #    dp[i] = 0
        
print(dp[-1])

Submission status: Accepted

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

dp = [0]*(N+1)
dp[0] = 1
A = []
for _ in range(M):
    k = int(input())
    A.append(k)
A = sorted(A,reverse = True)

if len(A)>0:
    a = A.pop()
else: a = -1
        
if a == 1:
    dp[1] = 0
    if len(A)>0:
        a = A.pop()
    if a == 2:
        dp[2] == 0
else:
    dp[1] = 1
    
for i in range(2,N+1):
    if i == a:
        if len(A)>0:
            a = A.pop()
        #continue
    else:
        if dp[i-1] != 0 and dp[i-2] != 0:
            dp[i] = (dp[i-1] + dp[i-2])%mod
        elif dp[i-1] != 0:
            dp[i] = dp[i-1]%mod
        elif dp[i-2] != 0:
            dp[i] = dp[i-2]%mod
        else:
            dp[i] = 0
        
print(dp[-1])

Submission status: Accepted

Solution code:

def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)
# from sys import setrecursionlimit
# setrecursionlimit(1000000)
# from collections import Counter,deque,defaultdict
# import itertools
# import math
# import networkx
# from bisect import bisect_left,bisect_right
# from heapq import heapify,heappush,heappop
n,m=n1()
A=n2(m)
A.append(n+1)
b=0
d=[0]*(n+1)
d[0]=1
d[1]=1
for i in range(2,n+1):
    d[i]=d[i-1]+d[i-2]

ans=1
for a in A:
    c=a-1-b
    if a==b:
        print(0)
        break
    else:
        ans*=d[c]
        b=a+1
else:
    print(ans%(10**9+7))