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:
from collections import deque

n,m=map(int,input().split())
step=list(range(2,n+1))
broken=[]
for i in range(m):
    broken+=[int(input())]
mod=10**9+7
dp=[0]*(n+1)
dp[0]=1
if m==0:
    dp[1]=1
elif not broken[0]==1:
    dp[1]=1
b=deque(broken)
if len(broken) != 0:
    bad_one = b.popleft()
    if bad_one==1 and len(b) != 0:
        bad_one=b.popleft()
else:
    bad_one = -1
for i in step:
    if i != bad_one:
        dp[i]=(dp[i-1]+dp[i-2])%mod
    elif i == bad_one and len(b) != 0:
        bad_one = b.popleft()
print(dp[n])

Submission status: Accepted

Solution code:
from collections import deque

n,m = map(int,input().split())
step = [i for i in range(2, n+1)]
broken = []
for i in range(m):
    broken += [int(input())]

mod = pow(10,9) + 7 #10**9+7
dp = [0 for _ in range(n+1)]
dp[0] = 1

if m == 0:
    dp[1] = 1
    for i in step:
        dp[i] = dp[i-1] + dp[i-2]
else:
    b = deque(broken)
    if not broken[0] == 1:
        dp[1] = 1
    elif len(b) > 1:
        b.popleft()
    if len(broken) != 0:
        bad_one = b.popleft()
    for i in step:
        if i != bad_one:
            dp[i] = (dp[i-1]+dp[i-2]) % mod
        elif i == bad_one and len(b) != 0:
            bad_one = b.popleft()
print(dp[n] % mod)

Submission status: Accepted

Solution code:
#!/usr/local/bin python
# -*- coding: utf-8 -*-
#
# ~/PycharmProjects/atcoder/C-TypicalStairs.py
#
N, M = map(int, input().split())
arr = [int(input()) for _ in range(M)]
MOD = 10**9 + 7
stairs = [True for _ in range(0, N+1)]
for x in arr:
    stairs[x] = False

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

dp[0] = 1 if 0 not in arr else 0
dp[1] = 1 if 1 not in arr else 0

for i in range(2, N+1):
    if dp[i-1] == 0 and dp[i-2] == 0:
        break
    if stairs[i-1]: dp[i] += dp[i-1]
    if stairs[i-2]: dp[i] += dp[i-2]

    dp[i] %= MOD

print(dp[-1] % MOD)

Submission status: Accepted

Solution code:
N,M = map(int, input().split())
arr = [int(input()) for _ in range(0,M)]
MOD = 10**9 + 7
stairs = [True for _ in range(0,N+1)]
for x in arr:
    stairs[x] = False

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

dp[0] = 1 if 0 not in arr else 0
dp[1] = 1 if 1 not in arr else 0

for i in range(2,N+1):
    if dp[i-1] == 0 and dp[i-2] == 0:
        break
    if stairs[i-1]: dp[i] += dp[i-1]
    if stairs[i-2]: dp[i] += dp[i-2]

    dp[i] %= MOD

print(dp[-1] % MOD)

Submission status: Accepted

Solution code:
import sys
from collections import deque
def input(): return sys.stdin.readline().strip()
mod = 10**9+7


def main():
    N, M = map(int, input().split())
    A = deque([int(input()) for _ in range(M)])
    
    if N == 1:
        print(1)
        return
    
    prepre = 1
    pre = 1
    if A and A[0] == 1:
        pre = 0
        A.popleft()

    for i in range(2, N + 1):
        if A and A[0] == i:
            pre, prepre = 0, pre
            A.popleft()
        else:
            pre, prepre = (pre + prepre) % mod, pre
        #print("i={}, val={}".format(i, pre))
    print(pre)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1


def II(): return int(input())


def MI(): return map(int, input().split())


def MI1(): return map(int1, input().split())


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


def LLI(rows_number): return [LI() for _ in range(rows_number)]


def Fibo(n, memo={}):
    if n == 1:
        return 0
    elif n == 2:
        return 1
    elif n in memo:
        return memo[n]
    else:
        memo[n] = Fibo(n - 1, memo) + Fibo(n - 2, memo)
        return memo[n]


def solve():
    n, m = MI()

    s = 0
    mod = 1000000007
    ans = 1
    for _ in range(m):
        t = II() - 1
        d = t - s
        if d < 0:
            keiro = 0
        else:
            keiro = Fibo(d + 2)
        # print(s, t, d, keiro)
        ans = ans * keiro % mod
        s = t + 2
    d = n - s
    if d < 0:
        keiro = 0
    else:
        keiro = Fibo(d + 2)

    ans = ans * keiro % mod
    print(ans % mod)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1


def II(): return int(input())


def MI(): return map(int, input().split())


def MI1(): return map(int1, input().split())


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


def LLI(rows_number): return [LI() for _ in range(rows_number)]


def Fibo(n, memo={}):
    if n == 1:
        return 0
    elif n == 2:
        return 1
    elif n in memo:
        return memo[n]
    else:
        memo[n] = Fibo(n - 1, memo) + Fibo(n - 2, memo)
        return memo[n]


def solve():
    M = list(MI())
    if len(M) == 2:
        n, m = M
    else:
        n = M[0]
        m = 0

    s = 0
    mod = 1000000007
    ans = 1
    for _ in range(m):
        t = II() - 1
        d = t - s
        if d < 0:
            keiro = 0
        else:
            keiro = Fibo(d + 2)
        # print(s, t, d, keiro)
        ans = ans * keiro % mod
        s = t + 2
    d = n - s
    if d < 0:
        keiro = 0
    else:
        keiro = Fibo(d + 2)

    ans = ans * keiro % mod
    print(ans % mod)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
 
sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7
 
 
def input():
    return sys.stdin.readline().strip()
 
 
def main():
    N, M = map(int, input().split())
    dp = [0] * (N + 1)
    safe = [True] * (N + 1)
    for _ in range(M):
        a = int(input())
        safe[a] = False
 
    dp[0] = 1
    for i in range(1, N + 1):
        if i == 1 and safe[i]:
            dp[i] = dp[i - 1]
        else:
            if safe[i]:
                dp[i] = dp[i - 1] + dp[i - 2]
                dp[i] %= MOD
 
    print(dp[-1])
 
 
if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

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

for i in range(m):
    dp[a[i]] = 0

for i in range(2, n+1):
    
    if dp[i] > 0:
        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)]
mod=10**9 +7
dp=[1]*(n+1)
dp[0]=1
dp[1]=1

for i in range(m):
    dp[a[i]] = 0

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

print(dp[n]%mod)

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

a=set(a)
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:
import sys
N, M = map(int, sys.stdin.readline().split())
a = [int(sys.stdin.readline()) for _ in range(M)]

MOD = 10 ** 9 + 7

list = [0] * N

if M > 0:
    j = 0
    for i in range(N):
        if i == 0:
            if a[j] == 1:
                list[i] = 0
            else:
                list[i] = 1
        elif i == 1:
            if a[j] == 2:
                list[i] = 0
            elif a[0] == 1:
                list[i] = 1
            else:
                list[i] = 2
        else:
            if a[j] == i + 1:
                list[i] = 0
            else:
                list[i] = (list[i - 1] + list[i - 2]) % MOD
        if i + 1 == a[j] and j < M - 1:
            j += 1

else:
    for i in range(N):
        if i == 0:
            list[i] = 1
        elif i == 1:
            list[i] = 2
        else:
            list[i] = (list[i - 1] + list[i - 2]) % MOD
            
ans = list[N - 1]
print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N, M = map(int, input().split())
    dp = [0] * (N + 1)
    safe = [True] * (N + 1)
    for _ in range(M):
        a = int(input())
        safe[a] = False

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

    print(dp[-1])


if __name__ == "__main__":
    main()

Submission status: Accepted

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

for i in a:
    b[i] = 0

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

print(b[-1])

Submission status: Accepted

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

for i in a:
    b[i] = 0

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

print(b[-1]%(10**9 + 7))

Submission status: Accepted

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

# 0段目
dp=[1] * (n +1)

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

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

    dp[i] = (dp[i+1] + dp[i+2]) %p

print(dp[0])

Submission status: Accepted

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

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

b = [1]*(n + 1)

for i in a:
    b[i] = 0

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

print(b[-1])

Submission status: Accepted

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

import sys
# import math
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product                # product(iter, repeat=n)
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4


def main():
    mod = 1000000007                  # 10^9+7
    inf = float('inf')
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():  return int(input())
    def mi():  return map(int, input().split())
    def mi_0(): return map(lambda x: int(x)-1, input().split())
    def lmi(): return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():  return list(input())
    
    
    n, m = mi()
    L = [ii() for _ in range(m)]

    FIBO = [0] * (n+1)    # FIBO[i] = k 段目から k+i 段目に行く場合の数
    for i in range(n+1):
        if i == 0 or i == 1:
            FIBO[i] = 1
        else:
            FIBO[i] = (FIBO[i-1] + FIBO[i-2]) % mod

    prev = 0
    ans = 1
    for broken_step in L:
        if prev == broken_step:
            print(0)
            exit()
        ans = (ans * FIBO[broken_step - 1 - prev]) % mod
        prev = broken_step + 1
    ans = (ans * FIBO[n - prev]) % mod
    print(ans)





if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,m=list(map(int,input().split(" ")))
a=[]
dp=[float("inf") for i in range(n+1)]
for i in range(m):
  a=int(input())
  dp[a]=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]
print(dp[n]%1000000007)

Submission status: Accepted

Solution code:
n, m = [int(x) for x in input().split()]
a_list = [0] * m
for i in range(m):
    a_list[i] = int(input())

mod = 1000000007

temp_list = [0] * (n + 1)
temp_list[0] = 1
temp_list[1] = 1
j = 0
if j < m and a_list[0] == 1:
    temp_list[1] = 0
    j = 1

for i in range(2, n + 1):
    if j < m and i == a_list[j]:
        j += 1
        continue
    temp_list[i] = (temp_list[i - 2] + temp_list[i - 1]) % mod
print(temp_list[n])

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
mod = 10**9 + 7
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])%mod
 
print(dp[n])

Submission status: Accepted

Solution code:
# coding: utf-8

n, m = map(int, input().split())
z = 10**9 + 7

ans = [1]
if m != 0:
    a_i = int(input())
else:
    a_i = 0
m_count = 1
if a_i == 1:
    ans.append(0)
    if m_count < m:
        a_i = int(input())
        m_count += 1
else:
    ans.append(1)
        
for i in range(2, n+1):
    if a_i == i:
        ans.append(0)
        if m_count < m:
            a_i = int(input())
            m_count += 1
    else:
        ans.append(ans[i-1]+ans[i-2])
        
# print(ans, ans[67])
print(int(ans[-1]%z))

Submission status: Accepted

Solution code:
# C - Typical Stairs

n, m = map(int, input().split())
mod = 10**9 + 7
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])%mod

print(dp[n])

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
    
def main():
    n,m=map(int,input().split())
    A=[int(input())for _ in range(m)]
    flag=[True]*(n+2)
    for a in A:
        flag[a]=False
    mod=10**9+7
    dp=[0]*(n+1)
    dp[0]=1
    for i in range(n):
        if flag[i+1]:
            dp[i+1]+=dp[i]%mod
        if flag[i+2] and i<n-1:
            dp[i+2]+=dp[i]%mod
    print(dp[n]%mod)

if __name__=='__main__':
    main()

Submission status: Accepted

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

ban = [False]* (n+1)

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

li = []
for mi in range(m):
    i = int(input())
    ban[i] = True

for i in range(n):
    if ban[i]:
        dp[i]=0
        continue
    if i+1 <n+1:
        dp[i+1] += dp[i]
    if i+2 <n+1:
        dp[i+2] += dp[i]
print(dp[n]%(10**9+7))

Submission status: Accepted

Solution code:
N,M,*a=map(int,open(0).read().split())

dp=[1]*(N+1)

for i in a:
  	dp[i]=0

for n in range(2,N+1):
    dp[n]=(dp[n-1]+dp[n-2])%1000000007*dp[n]

print(dp[N])

Submission status: Accepted

Solution code:
n,m,*a=map(int,open(0).read().split())
b=[1]*(n+1)
for i in a:
    b[i]=0
for i in range(2,n+1):
    b[i]=(b[i-1]+b[i-2])%1000000007*b[i]
print(b[-1])

Submission status: Accepted

Solution code:
MOD = 10**9 + 7

N,M = map(int,input().split())
dp = [0]*(N+1)
dp[0] = 1
A = set(int(input()) for _ in range(M)) # 禁止地帯

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

answer = dp[N]
print(answer)

Submission status: Accepted

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

for i in range(2, N+1):
    if dp[i] != False:
        dp[i] = (dp[i-1]+dp[i-2]) % MOD
print(dp[N])

Submission status: Accepted

Solution code:
from collections import defaultdict
N, M = map(int, input().split())
A = {i:0 for i in range(N+1)}
for _ in range(M):
  A[int(input())] = 1

mod = 10**9 + 7
dp = [0]*(N+1)
dp[0] = 1
for i in range(N):
  if A[i+1] != 1: 
    dp[i+1] += dp[i]
    dp[i+1] %= mod
  if i+2 >= N+1:
    continue
  if A[i+2] != 1:
    dp[i+2] += dp[i]
    dp[i+2] %= mod

print(dp[N])

Submission status: Accepted

Solution code:
def main():
    n,m=map(int,input().split())
    res=[1,1]
    flg=0
    mod=10**9+7
    a=n
    gap=[]
    if m!=0:
        a=int(input())
        gap.append(a-1)
        for i in range(m-1):
            b=int(input())
            dif=b-a-1
            if dif==0:
                flg=1
                break
            else:
                gap.append(dif-1)
                a=b
        gap.append(n-a-1)
    else:
        gap.append(n)
    if flg==1:
        print(0)
    else:
        for i in range(2,max(gap)+1):
            res.append((res[i-1]+res[i-2])%mod)
        ans=1
        for i in gap:
            ans=(ans*res[i])%mod
        print(ans)
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
from itertools import product

INF = 1000000007

def mat2_mul(X, Y):
        z = [[0, 0], [0, 0]]
        for (i, j, k) in product(range(2), range(2), range(2)):
                z[i][j] += X[i][k] * Y[k][j]
        return z

def mat2_pow(X, n):
        if n == 0:
                return [[1, 0], [0, 1]]
        elif n % 2:
                return mat2_mul(X, mat2_pow(X, n - 1))
        else:
                half_pow = mat2_pow(X, n / 2)
                return mat2_mul(half_pow, half_pow)

def fib(n):
        if n == 0:
                return 0
        else:
                f = [[0, 1], [1, 1]]
        return mat2_pow(f, n - 1)[1][1]


N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
ans, start = 1, 0

for k in a:
        ans *= fib(k - start)
        ans %= INF
        start = k + 1

ans *= fib(N - start + 1)
print(ans % INF)

Submission status: Accepted

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

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

for i in range(N+1):
    if A.get(i+1) == 0:
        dp[i + 1] += dp[i]
    if A.get(i+2) == 0:
        dp[i + 2] += dp[i]

print(dp[N]%mod)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()
A = {i: False for i in range(N+1)}
for m in range(M):
    a = ir()
    A[a] = True
C = [0 for _ in range(N+1)]
C[0] = 1
for i in range(len(C)):
    if A[i]:
        continue
    if i >= 2:
        C[i] += C[i-2]
        C[i] += C[i-1]
        C[i] %= 1000000007
    elif i >= 1:
        C[i] += C[i-1]
        C[i] %= 1000000007

print(C[N] % 1000000007)

Submission status: Accepted

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

cnt = 0
dp_table = [0 for i in range(n + 10)]
dp_table[0] = 1
dp_table[1] = 1

for i in range(m):
    dp_table[a[i]] = -10 ** 9 + 7

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

print(dp_table[n])

Submission status: Accepted

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

ban = [False] * (n + 1)#踏めない階段の配列、最初は全てOK

for i in range(m):
    a = int(input())
    ban[a] = True#壊れている段をTrueに変える

dp = [0] * (n+1)#DPテーブルは余裕が必要
dp[0] = 1#最初は１通り
for i in range(n):
    dp[i] %= MOD#MODで割っておく
    if(ban[i]):dp[i] = 0#壊れている段に行く方法は無い
    if i + 1 <= n:#上がれるのは１段、または２段
        dp[i+1] += dp[i]#配る配列
    if i + 2 <= n:
        dp[i+2] += dp[i]

print(dp[n] % MOD)#n段目に行くのは何通りか

Submission status: Accepted

Solution code:
from sys import exit
from collections import deque

n, m = map(int,input().split())
a = deque(int(input()) for i in range(m))

if len(a) != 0:
    base = a.popleft()
else:
    base = -1

p = 10 ** 9 + 7

dp = [1] * (n+1)

if base == 0:
    print(0)
    exit()

for i in range(1, n+1):
    if base == i:
        dp[i] = 0
        if len(a) != 0:
            base = a.popleft()
        continue
    if i == 1:
        dp[i] = 1
    else:
        dp[i] = (dp[i-2] + dp[i-1]) % p
    if dp[i] == 0:
        print(0)
        exit()

print(dp[n])

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=[int(input()) for _ in range(m)]
def fb(num):
    a,b = 1,0
    for _ in range(num+1):
        a,b = a+b,a
    return b
if m==0:
    print(fb(n)%(10**9+7))
    exit()
if m>1:
    for i in range(m-1):
        if a[i+1]-a[i]==1:
            print(0)
            exit()
c=0
for i in range(m):
    if i==0 and a[0]==1:
        c+=1
    elif i==0:
        c+=fb(a[0]-1)
    else:
        c*=(fb(a[i]-a[i-1]-2)%(10**9+7))
c*=fb(n-a[-1]-1)%(10**9+7)
print(c%(10**9+7))

Submission status: Accepted

Solution code:
MOD = 10**9 + 7

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

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

ans = dp[N] % MOD
print(ans)

Submission status: Accepted

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

c=[0]*(n+1)
c[0]=1
if 1 in a:
    c[1]=0
else:
    c[1]=1

for i in range(2,n+1):
    if check[i]!=0:
        
        continue
    else:
        c[i] = (c[i - 1] + c[i - 2]) % MOD

print(c[n])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
p = 1000000007
n, m = (int(x) for x in input().split())
seq = [1 for i in range(n+1)]
for i in range(m):
    a = int(input())
    seq[a] = 0
ans = 1
for i in range(2,n+1):
    if seq[i] == 0:
        continue
    seq[i] = (seq[i-1] + seq[i-2]) % p
print(seq[-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, groupby
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()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()

def Fibo(n):
	S = [1, 1]
	if n == 1:
		return 1
	for i in range(1, n):
		S.append(S[i] + S[i-1])

	return S[n]

if M == 0:
	print(Fibo(N)%mod)
	exit()

a = [INT()]
for i in range(1, M):
	a.append(INT())
	if a[i] == a[i-1]+1:
		print(0)
		exit()
m = [a[0]-1]
for i in range(1, M):
	m.append(a[i]-a[i-1]-2)
m.append(N-a[M-1]-1)



ans = 1
for n in m:
	ans *= Fibo(n)

print(ans%mod)

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
a = [int(input()) for _ in range(m)]
mod = 1000000007
fib = [1,1,2]
for i in range(3,n+1):
    fib.append((fib[i-2]+fib[i-1])%mod)
if (m==0):
    print(fib[n])
    exit()
ans = 0
ans += fib[a[0]-1]

for i in range(1,m):
    if (a[i]-a[i-1]!=1):
        ans *= fib[a[i]-a[i-1]-2]
        ans %= mod
    else:
        print(0)
        exit()
ans *= fib[n-a[m-1]-1]
print(ans%mod)

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))

safe = [1]*(n+1)
for aa in a:
    safe[aa]=0

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

if safe[1]:dp[1]=1

for i in range(2,n+1):
    if not safe[i]:
        continue

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

print(dp[-1]%p)

Submission status: Accepted

Solution code:
import numpy as np

MOD = 10**9+7

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

An = np.zeros(N+1,dtype=int)
An[0] = 1

for _ in range(M):
    m = int(input())
    An[m] = -1

# 1段目だけは特別に
if An[1] == -1:
    An[1] = 0
else:
    An[1] = 1

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

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

print(An[N])

Submission status: Accepted

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

mod=10**9+7
for i in range(m):
  a=int(input())
  dp[a-1]=0

ans=[]
ans.append(1 if dp[0]==1 else 0)
if len(dp)>1 and dp[0]==1 and dp[1]==1:
    ans.append(2)
elif len(dp)>1 and dp[0]==1 and dp[1]==0:
    ans.append(0)
elif len(dp)>1 and dp[0]==0 and dp[1]==1:
    ans.append(1)
elif len(dp)>1 and dp[0]==0 and dp[1]==0:
    print(0)
    exit()
for i in range(2,n):
    ans.append((ans[i-1]+ans[i-2])*dp[i]%mod)
print(ans[-1]%mod)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=[]
for _ in range(m):
    a.append(int(input()))
ans=1
a.sort()
d={0:1,1:1,2:2,3:3,4:5,5:8,6:13,99500:49759705584609,99501:49760296517401}
def func(n):
    if n in d:
        return d[n]
    else:
        v = (func(n-1)+func(n-2))%(10**9+7)
        d[n]=v
        return v
ps=-1
a.append(n+1)
for ai in a:
    c=ai-ps-2
    ps=ai
    if c<0:
        print(0)
        exit()
    c=func(c)
    ans*=c
    ans%=10**9+7

print(ans%(10**9+7))

Submission status: Accepted

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

Submission status: Accepted

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

a = []
for i in range(m):
    a.append(int(input()))

dp = []
for dpi in range(n):
    dp.append(0)

k = 0
a.append(0)
for j in range(n):
    if j+1 == a[k]:
        k += 1
        continue
    if j == 0:
        dp[j] = 1
    elif j == 1:
        dp[j] = dp[j-1] + 1
    elif j > 1:
        dp[j] = dp[j-1] + dp[j-2]

print(dp[n-1] % 1000000007)

Submission status: Accepted

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

dp = [0] * (n+1)
# 0段目と1段目は1通り（但し、１段目が壊れていない場合）（0 段目は「なにもしない」という から1 通り）
dp[:2] = 1, 1 if 1 not in a else 0 

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

print(dp[-1] % (10**9+7))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
MOD = 10**9 + 7

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

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

start = 0
ans = 1
for w in wlist:
  end = w - 1
  if end - start > 0:
    ans *= dp[w - 1 - start]
  elif end -start == 0:
    pass
  else :
    ans = 0
    break
  ans %= MOD
  start = w + 1
if not start == n:
  ans *= dp[n - start]
  ans %= MOD
print(ans)

Submission status: Accepted

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

dp = [0] * (N + 1)

#0段目と1段目は1通り（但し、１段目が壊れていない場合）（0 段目は「なにもしない」という から1 通り）
dp[:2] = 1, 1 if 1 not in A else 0 


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

print(dp[-1] % MOD)

Submission status: Accepted

Solution code:
def resolve():
	modu = 1000000007
	n, m = map(int, input().split())
	a = [False]*n
	for _ in range(m):
		a[int(input())] = True
	dp = [0]*(n+1)
	dp[0], dp[1] = 1, 1
	for i in range(2, n+1):
		if i < n and a[i]:
			continue
		multi = []
		if not a[i-1]:
			multi.append(dp[i-1])
		if not a[i-2]:
			multi.append(dp[i-2])
		dp[i] = sum(multi) % modu
	print(dp[-1])
resolve()

Submission status: Accepted

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

mod=1e9+7

inf=float('inf')

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

for i in a:
    dp[i]=0

for i in range(2,n+1):
    dp[i] = min(dp[i], dp[i-1]+dp[i-2]) % mod

print(int(dp[-1]))

Submission status: Accepted

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