Problem:


Score : 300 points

Problem Statement

There is a staircase with N steps. Takahashi is now standing at the foot of the stairs, that is, on the 0-th step.
He can climb up one or two steps at a time.

However, the treads of the a_1-th, a_2-th, a_3-th, \ldots, a_M-th steps are broken, so it is dangerous to set foot on those steps.

How many are there to climb up to the top step, that is, the N-th step, without setting foot on the broken steps?
Find the count modulo 1\ 000\ 000\ 007.

Constraints

1 \leq N \leq 10^5

0 \leq M \leq N-1

1 \leq a_1 < a_2 <  ...  < a_M \leq N-1

Input

Input is given from Standard Input in the following format:

N M
a_1
a_2
 .
 .
 .
a_M

Output

Print the number of ways to climb up the stairs under the condition, modulo 1\ 000\ 000\ 007.

Sample Input 1

6 1
3

Sample Output 1

4

There are four ways to climb up the stairs, as follows:

0 \to 1 \to 2 \to 4 \to 5 \to 6

0 \to 1 \to 2 \to 4 \to 6

0 \to 2 \to 4 \to 5 \to 6

0 \to 2 \to 4 \to 6

Sample Input 2

10 2
4
5

Sample Output 2

0

There may be no way to climb up the stairs without setting foot on the broken steps.

Sample Input 3

100 5
1
23
45
67
89

Sample Output 3

608200469

Be sure to print the count modulo 1\ 000\ 000\ 007.



Sample input:
6 1
3


Sample output:
4

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = [0] * (N + 5)
MOD = 10 ** 9 + 7
dp = [0] * (N + 5)
for i in range(M):
    a = int(input())
    A[a] = 1


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

print(dp[N])

Submission status: Accepted

Solution code:
import sys
from collections import deque
from collections import defaultdict
import math
sys.setrecursionlimit(20000000)
input = sys.stdin.readline
n,m = map(int,input().split())
a = [int(input()) for i in range(m)]
a = set(a)
mod = 10**9+7
dp = [0]*(n+1)
dp[0] = 1
for i in range(1,n+1):
        if i in a:
                continue
        if i == 1:
                dp[i] = 1
                continue
        dp[i] = dp[i-1] + dp[i-2]
        dp[i] %= mod
print(dp[n]%mod)

Submission status: Accepted

Solution code:

MOD =  1000000007

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

a_list = set()
for _ in range(M):
	a_list.add(int(input()))

#print(a_list)

counts = [0] * (N + 3)
counts[0] = 1
for i in range(N):
	if not i in a_list:
		counts[i + 1] = (counts[i + 1] + counts[i]) % MOD
		counts[i + 2] = (counts[i + 2] + counts[i]) % MOD

#print(counts)
print(counts[N])

Submission status: Accepted

Solution code:
def inpl():
    return list(map(int, input().split()))


MOD = 10**9 + 7

N, M = inpl()
A = [False for i in range(N + 1)]
for i in range(M):
    a = int(input())
    A[a] = True
p = 1
pp = 0
ans = 0

for i in range(1, N + 1):
    if A[i] is True:
        pp = p
        p = 0
    else:
        ans = p + pp
        pp = p
        p = ans
    # print(ans)

print(ans % MOD)

Submission status: Accepted

Solution code:
MOD = 1000000007

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

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

print(dp[-1] % MOD)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import math
from itertools import accumulate as acc
MOD=10**9+7
N,M=map(int,input().split())
if N==1: print(1),sys.exit()
a=[0]*(N+1)
for i in range(M):
  a[int(input())]=-1
pat=[0 for i in range(N+1)]
pat[0]=1
if a[1]==0: pat[1]=1

for i in range(2,N+1):
    if a[i]==-1: continue
    if a[i-1]==0 and a[i-2]==0: pat[i]=pat[i-1]+pat[i-2]
    elif a[i-1]==0 and a[i-2]==-1: pat[i]=pat[i-1]
    elif a[i-1]==-1 and a[i-2]==0: pat[i]=pat[i-2]
    else: print(0),sys.exit()
    pat[i]%=MOD
print(pat[N])

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
MOD = 10**9 + 7
a = []
broken = [False for i in range(N+1)]
if M > 0:
	for i in range(M):
		x = int(input())
		a.append(x)
		broken[x] = True

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

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

Submission status: Accepted

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



"""
import sys


def solve(N, M, A):
    MOD = 10**9 + 7
    A = set(A)
    if N == 1:
        return 1 if 1 not in A else 0
        
    dp = [0] * (N+1)
    dp[0] = 1
    dp[1] = 1 if 1 not in A else 0
    for i in range(2, N+1):
        if i in A:
            dp[i] = 0
        else:
            dp[i] = (dp[i-2] + dp[i-1]) % MOD
    return dp[-1]


def main(args):
    N, M = map(int, input().split())
    A = [int(input()) for _ in range(M)]
    ans = solve(N, M, A)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from sys import stdin
# import numpy as np
# import sys
# sys.setrecursionlimit(10**4)

def _li(): return list(map(int, stdin.readline().split()))
def _li_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def _lf(): return list(map(float, stdin.readline().split()))
def _ls(): return stdin.readline().split()
def _i(): return int(stdin.readline())
def _f(): return float(stdin.readline())
def _s(): return stdin.readline()[:-1]


MOD = 10**9+7
N, M = _li()

a_list = []
for _ in range(M):
    a_list.append(_i())
a_list.append(-1)

ans = [1, 1]
a_index = 0
if a_list[a_index] == 1:
    ans[1] = 0
    a_index += 1

for i in range(2, N+1):
    if i == a_list[a_index]:
        ans = [ans[1], 0]
        a_index += 1
    else:
        ans = [ans[1], ans[0] + ans[1] % MOD]
    if ans[0] + ans[1] == 0:
        break
print(ans[1] % MOD)

Submission status: Accepted

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

Submission status: Accepted

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

A = [True for i in range(N + 2)]

dp = [0 for i in range(N + 3)]

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

dp[0] = 1
for i in range(N):
    if A[i] == False:
        continue
    dp[i + 1] += dp[i]
    dp[i + 1] %= 1000000007
    dp[i + 2] += dp[i]
    dp[i + 2] %= 1000000007

print(dp[N])

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
Max = sys.maxsize
def l():
	return list(map(int,input().split()))
def m():
	return map(int,input().split())
def s(x):
	a = []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa == x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x):
	return " ".join(map(str,x))
n,m = m()


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

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

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

Submission status: Accepted

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

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

next_a = a.pop(0)

for i in range(N):
    if next_a == i:
        dp[i] = 0
        next_a = a.pop(0)
    else:
        dp[i+1] += dp[i]
        dp[i+2] += dp[i]
print(dp[N]%1000000007)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

def solve():
    n, m = map(int, input().split())
    am = set(int(input()) for i in range(m))
    ans = [0] * (n + 10)
    ans[0] = 1
    md = 10 ** 9 + 7
    for i in range(n):
        if (i + 1) not in am:
            ans[i + 1] += ans[i]
            ans[i + 1] %= md
        if (i + 2) not in am:
            ans[i + 2] += ans[i]
            ans[i + 2] %= md
    print(ans[n])

if __name__=="__main__":
    solve()

Submission status: Accepted

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

for i in range(n):
    if not ok[i]:
        continue
    for j in range(1,3):
        if i+j <= n:
            dp[i+j] = (dp[i+j] + dp[i])%mod

print(dp[-1])

Submission status: Accepted

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

v = [-1]*(n+1)
v[0] = 1

for t in a:
  v[t] = 0

if v[1] == -1:
  v[1] =1
  
for i in range(2,n+1):
  if v[i] == 0:
    continue
  v[i] = (v[i-1] + v[i-2])%Mod
#print(v)  
print(v[n])

Submission status: Accepted

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

dp = [0] * (n+1)

dp[0] = 1
dp[1] = memo[1]

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

Submission status: Accepted

Solution code:
import sys
import collections
ns = lambda: sys.stdin.readline().rstrip()
ni = lambda: int(ns())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
nsm = lambda: map(str, sys.stdin.readline().split())
nsl = lambda: list(nsm())

mod = 1000000007

n, m = nm()
dp = [0] * (n + 1)
for i in range(m):
    tmp = ni()
    dp[tmp] = -1
dp[0] = 1
for i in range(n):
    if i + 1 < n + 1 and dp[i + 1] != -1 and dp[i] != -1:
        dp[i + 1] += dp[i] % mod
        dp[i + 1] %= mod
    if i + 2 < n + 1 and dp[i + 2] != -1 and dp[i] != -1:
        dp[i + 2] += dp[i] % mod
        dp[i + 2] %= mod
print(dp[n] % mod)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
a = [True] * (N + 3)
a[N + 1] = False
a[N + 2] = False

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

MOD = 10 ** 9 + 7

dp = [0] * (N + 3)
dp[0] = 1
for i in range(N + 1) :
    if a[i + 1] :
        dp[i + 1] = (dp[i + 1] + dp[i]) % MOD
    if a[i + 2] :
        dp[i + 2] = (dp[i + 2] + dp[i]) % MOD
   
print(dp[N])

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
p = 1000000007
L = []
for i in range(M):
  L.append(int(input()))
dp = [float('inf')]*(N+1)
dp[0] = 1
if 1 in L:
  dp[1] = 0
else:
  dp[1] = 1
for j in range(len(L)):
  dp[L[j]] = 0
for i in range(N-1):
  if dp[i+2] == float('inf'):
    dp[i+2] = (dp[i+1]+dp[i])%p
print(dp[N])

Submission status: Accepted

Solution code:
import sys
from collections import Counter, deque, defaultdict
from itertools import accumulate, permutations, combinations, takewhile, compress, cycle
from functools import reduce
from math import ceil, floor, log10, log2, factorial
from pprint import pprint

# sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
# N = int(input())
# A,B,C = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# A = [int(input()) for _ in range(N)]

N, M = [int(x) for x in input().split()]
A = [int(input()) for _ in range(M)]
A = set(A)

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

for i in range(N):
    if i + 1 not in A:
        dp[i + 1] += dp[i]
        # dp[i + 1] %= MOD
    if i + 2 not in A:
        dp[i + 2] += dp[i]
        # dp[i + 2] %= MOD

print(dp[N] % MOD)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7

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

isBroken = [False] * (N+1)
for A in As:
    isBroken[A] = True

dp = [0] * (N+1)
dp[0] = 1
for i in range(1, N+1):
    if isBroken[i]: continue
    if i > 1:
        dp[i] += dp[i-2]
    dp[i] += dp[i-1]
    dp[i] %= MOD

print(dp[N])

Submission status: Accepted

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

for i in range(n):
    if i+1 not in aa:
        l[i+1]+=l[i]
        l[i+1]=l[i+1]%mod
    if i+2 not in aa and i+2<n+1:
        l[i+2]+=l[i]
        l[i+2]=l[i+2]%mod

print(l[n])

Submission status: Accepted

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

def s(generator, splitter, mapper):
    return [ mapper(s) for s in generator().split(splitter) ]

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

MOD = 1000000007

n,m = get_nums_l()
breaks = map(int, sys.stdin.readlines())

dp = [0] * (n+1)

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

dp[n] = 1

for i in range(n-1, -1, -1):
    if dp[i] == -1:
        continue
    
    x = 0
    if dp[i+1] != -1:
        x += dp[i+1]
    
    if i <= (n-2) and dp[i+2] != -1:
        x += dp[i+2]
    
    dp[i] = x % MOD

print(dp[0])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
A = [int(input()) for i in range(m)]
B = [0 for i in range(10**5+10)]
for i in range(len(A)):
    B[A[i]] = 1

mod = 10**9 + 7

DP = [1,1]
if B[1] == 1:
    DP[1] = 0
for i in range(2,n+1):
    p1 = DP[i-2] % mod
    p2 = DP[i-1] % mod
    if B[i-2] == 1:
        p1 = 0
    if B[i-1] == 1:
        p2 = 0
    DP.append((p1+p2)%mod)
print(DP[n])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)


m = Mod(10**9 + 7)


@mt
def slv(N, M, A):
    dp = [0] * (N+3)
    b = [False] * (N+3)
    for a in A:
        b[a] = True

    A.sort(reverse=True)
    dp[0] = 1
    for i in range(N):
        if not b[i+1]:
            dp[i+1] = m.add(dp[i+1], dp[i])
        if not b[i+2]:
            dp[i+2] = m.add(dp[i+2], dp[i])
    return dp[N]


def main():
    N, M = read_int_n()
    A = [read_int() for _ in range(M)]
    print(slv(N, M, A))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

def main():
    N, M = LI()
    A = [0] * (N + 1)
    for _ in range(M):
        A[II()] = 1
    dp = [0] * (N + 1)
    dp[0] = 1
    dp[1] = dp[0] if A[1] == 0 else 0
    for i in range(2, N + 1):
        if A[i] == 1:
            dp[i] = 0
        else:
            dp[i] = (dp[i - 1] + dp[i - 2]) % MOD
    ans = dp[N]
    return ans

print(main())

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
num = [0 for _ in range(N + 1)]
num[0] = num[1] = 1
for n in range(2, N + 1):
    if not A[n]:
        continue
    if A[n - 1]:
        num[n] += num[n - 1]
    if A[n - 2]:
        num[n] += num[n - 2]
    num[n] %= 10 ** 9 + 7
print(num[N] % (10 ** 9 + 7))

Submission status: Accepted

Solution code:
import sys
from collections import deque
from collections import defaultdict
import math
sys.setrecursionlimit(20000000)
input = sys.stdin.readline
n,m = map(int,input().split())
a = [int(input()) for i in range(m)]
a = set(a)
mod = 10**9+7
dp = [0]*(n+5)
dp[0] = 1
for i in range(1,n+1):
        if i in a:
                continue
        if i == 1:
                dp[i] = 1
                continue
        dp[i] = dp[i-1] + dp[i-2]
        dp[i] %= mod
print(dp[n]%mod)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def inpl(): return list(map(int, input().split()))
N, M = inpl()
MOD = 10**9 + 7
A = [1]*(N+3)
for _ in range(M):
    a = int(input())
    A[a] -= 1

DP = [0]*(N+3)
DP[0] = 1
for i in range(N):
    DP[i+1] = ((DP[i+1] + DP[i])*A[i+1])%MOD
    DP[i+2] = ((DP[i+2] + DP[i])*A[i+2])%MOD
print(DP[N])

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = [0] * (N + 2)
MOD = 10 ** 9 + 7
dp = [0] * (N + 2)
for i in range(M):
    a = int(input())
    A[a] = 1


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

print(dp[N])

Submission status: Accepted

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

Submission status: Accepted

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

mod = 10 ** 9 + 7

dp = [0] * (N + 1)
dp[0] = 1
not_use = [False] * (N + 1)
for a in a_list:
    not_use[a] = True

for i in range(N+1):
    not_u = not_use[i]
    if not_u:
        continue
    else:
        if i < N:
            dp[i + 1] += dp[i]
            dp[i + 1] %= mod
        if i < N - 1:
            dp[i + 2] += dp[i]
            dp[i + 2] %= mod

print(dp[N] % mod)

Submission status: Accepted

Solution code:
Q = 1000000007
n, m = map(int, input().split())
a = set([int(input()) for _ in range(m)])
dp = {
    0: 1,
    1: 0 if 1 in a else 1
}

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


print(dp[n])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
mod = 10**9 + 7
n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
ng = [False] * (10**5 + 1)
for x in a:
    ng[x] = True
dp = [0] * (n + 1)
dp[0] = 1
for i in range(n + 1):
    if i > 0 and not ng[i - 1]: dp[i] += dp[i - 1]
    if i > 1 and not ng[i - 2]: dp[i] += dp[i - 2]
    dp[i] %= mod
print(dp[n])

Submission status: Accepted

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

ans = [1]*(N+1) + [0] # ans[n]: n段目まで行く数

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

print(ans[N])

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-


MOD = 1000000007


N,M = map(int, input().split())
dp = [1 for _ in range(N+1)]
for i 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]) % MOD
print(dp[-1])

Submission status: Accepted

Solution code:
from collections import defaultdict
N,M = map(int,input().split())
d = defaultdict(lambda:1)

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
MOD = 10**9 + 7
a = []
broken = [False for i in range(N+1)]
for i in range(M):
	x = int(input())
	a.append(x)
	broken[x] = True

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

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
a = set([int(input()) for _ in range(m)])
ans = 1
dp = [0] * (n + 3)
dp[0] = 1
for i in range(n):
    if i + 1 not in a:
        dp[i + 1] += dp[i]
    if i + 2 not in a:
        dp[i + 2] += dp[i]
print(dp[n] % (10 ** 9 + 7))

Submission status: Accepted

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

for i in range(n):
    if i in s:
        continue
    for j in range(1,3):
        if i+j <= n:
            dp[i+j] = (dp[i+j] + dp[i])%mod

print(dp[-1])

Submission status: Accepted

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



"""
import sys


def solve(N, M, A):
    MOD = 10**9 + 7
    A = set(A)
    dp = [0] * (N+1)
    dp[0] = 1
    dp[1] = 1 if 1 not in A else 0
    for i in range(2, N+1):
        if i in A:
            dp[i] = 0
        else:
            dp[i] = (dp[i-2] + dp[i-1]) % MOD
    return dp[-1]


def main(args):
    N, M = map(int, input().split())
    A = [int(input()) for _ in range(M)]
    ans = solve(N, M, A)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

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

stair = [0 for i in range(N+1)]
notbroken = [1 for i in range(N+1)]
for i in range(M):
    a = int(input())
    notbroken[a] = 0
for i in range(N+1):
    if i == 0:
        stair[i] = 1
        continue
    if i == 1:
        stair[i] = 1
        continue
    stair[i] = (stair[i-1] * notbroken[i-1] + stair[i-2] * notbroken[i-2]) * notbroken[i]
    stair[i] %= 10**9+7

print(stair[N])

Submission status: Accepted

Solution code:
def solve(N, M, A):
    answer = [0] * (N+1)
    answer[0] = 1
    if 1 in A:
        answer[1] = 0
    else:
        answer[1] = 1

    for s in range(2, N+1):
        if s in A:
            answer[s] = 0
        else:
            answer[s] = (answer[s-2] + answer[s-1]) % 1000000007
    print(answer[N])

N, M = [int(x) for x in input().split()]
A = set()
for i in range(M):
    A.add(int(input()))
solve(N, M, A)

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys
from collections import Counter, deque, defaultdict
from itertools import accumulate, permutations, combinations, takewhile, compress, cycle
from functools import reduce
from math import ceil, floor, log10, log2, factorial
from pprint import pprint

# sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
# N = int(input())
# A,B,C = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# A = [int(input()) for _ in range(N)]

N, M = [int(x) for x in input().split()]
A = [int(input()) for _ in range(M)]
A = set(A)

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

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

print(dp[N] % MOD)

Submission status: Accepted

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

#n = int(input())
#s = input()
#a = [int(i) for i in input().split()]
#m = [[int(i) for i in input().split()] for j in range(n)] # 縦「n」行

MOD = 10**9+7

n,m = [int(i) for i in input().split()]
a = {int(input()) for i in range(m)}

#print(a)

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

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

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

Submission status: Accepted

Solution code:
N, M = list(map(int, input().split()))
V = 10 ** 9 + 7
a = [int(input()) for _ in range(M)]
A = set(a)
ANS = [0 for _ in range(N + 5)]

ANS[0] = 1
for i in range(N):
    ANS[i] %= V
    if not i + 1 in A:
        ANS[i + 1] += ANS[i]
    if not i + 2 in A:
        ANS[i + 2] += ANS[i]

print(ANS[N] % V)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from sys import stdin
# import numpy as np
# import sys
# sys.setrecursionlimit(10**4)

def _li(): return list(map(int, stdin.readline().split()))
def _li_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def _lf(): return list(map(float, stdin.readline().split()))
def _ls(): return stdin.readline().split()
def _i(): return int(stdin.readline())
def _f(): return float(stdin.readline())
def _s(): return stdin.readline()[:-1]


MOD = 10**9+7
N, M = _li()

a_list = []
for _ in range(M):
    a_list.append(_i())
a_list.append(-1)

ans = [1, 1]
a_index = 0
if a_list[a_index] == 1:
    ans[1] = 0
    a_index += 1

for i in range(2, N+1):
    if i == a_list[a_index]:
        ans = [ans[1], 0]
        a_index += 1
    else:
        ans = [ans[1], ans[0] + ans[1] % MOD]
    if ans[0] + ans[1] == 0:
        break
print(ans[1] % MOD)

Submission status: Accepted

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

LARGE = 10**9 + 7

r_arr = [0]*(N+1)
r_arr[0] = 1
if a_dict.get(1, 0) == 1:
    r_arr[1] = 0
else:
    r_arr[1] = 1

for i in range(2, N+1):
    if a_dict.get(i, 0) == 1:
        pass
    else:
        r_arr[i] = (r_arr[i-1] + r_arr[i-2]) % LARGE

print(r_arr[-1])

Submission status: Accepted

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

aa = {}
for _ in range(m):
  aa[int(input())] = True

dp = [0] * (n+1)
dp[0] = 1
if 1 in aa:
  dp[1] = 0
else:
  dp[1] = 1

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

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7

N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
bl = [True] * (N + 2)
for aa in a:
    bl[aa] = False

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

for step_frm in range(N):
    if bl[step_frm]:
        dp[step_frm + 2] += dp[step_frm]
        dp[step_frm + 2] %= mod
        dp[step_frm + 1] += dp[step_frm]
        dp[step_frm + 1] %= mod
print(dp[N])

Submission status: Accepted

Solution code:
N, M, *C = map(int, open(0).read().split())
MOD = 10**9 + 7
F = [0]*(N+1)
for c in C:
    F[c-1] = 1

a = 1; b = 0
for i in range(N):
    if F[i]:
        a, b = 0, a
    else:
        a, b = ((a+b) % MOD), a
print(a)

Submission status: Accepted

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


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

print(S[N])

Submission status: Accepted

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

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

for i in range(M) :
    a = int(input())
    dp[a] = -1

dp[0] = 1

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

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

ans = dp[-1]

ans %= (10**9 + 7)

print(ans)

Submission status: Accepted

Solution code:
n, m = [int(i) for i in input().split()]
A = [int(input()) for i in range(m)]
p = int(1e9) + 7

is_broken = [False] * (n + 1)

for a in A:
    is_broken[a] = True

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

for i in range(n):
    if is_broken[i]:
        DP[i] = 0
        continue
    
    DP[i + 1] += DP[i] % p
    DP[i + 2] += DP[i] % p

print(DP[n] % p)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
from collections import deque
from heapq import heappush,heappop
import re

def int_raw():
    return int(input())
 
def ss_raw():
    return input().split()
 
def ints_raw():
    return tuple(map(int, ss_raw()))


DIV=10**9+7

def mod_invs(n,mod=DIV):
    inv=[0]*(n+1)
    inv[0]=1
    inv[1]=1
    for i in range(2,n+1):
        inv[i] = (-(mod//i)*inv[mod%i]) % mod
    return inv



def main():
    N,M = ints_raw()
    As = [int_raw() for _ in range(M)]
    is_breake = [0]*(N+1)
    for a in As:
        is_breake[a]=1
    memo = [0]*(N+1)

    memo[0]=1
    memo[1]=1 if is_breake[1]==0 else 0
    for n in range(2,N+1):
        if is_breake[n]:
            continue
        else:
            memo[n]=(memo[n-2]+memo[n-1])%DIV
    return memo[-1]

print(main())

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n,m = map(int, input().split())
a = set([int(input()) for _ in range(m)])
MOD = 1000000007

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

print(dp[-2])