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_lis = [int(input()) for _ in range(M)]
a_lis.insert(0, -1) # size: M+1
a_lis.append(N+1) # size: M+2

dif = [a_lis[j+1]-a_lis[j]-2 for j in range(M+1)]
fib_lis = []

def fib(n):
  for k in range(n+1):
    if k==0 or k==1:
      fib_lis.append(1)
    else:
      fib_lis.append(fib_lis[k-2]+fib_lis[k-1])

  return fib_lis[-1]

max_ = max(dif)
fib(max_)
  
t = 1

for d in dif:
  if d < 0:
    t *= 0
  else:
    t *= fib_lis[d]
  t = t % 1000000007
  
print(t)

Submission status: Accepted

Solution code:
#ABC129C-TypicalStairs.py

#import list
import numpy as np
from sys import stdin, setrecursionlimit
from functools import lru_cache

input = stdin.readline
setrecursionlimit(1000)

#constant
#N = int(input())
N, M = list(map(int,input().split()))
A = {int(input()) for _ in range(M)}

#variable
rootList = np.array([1]+[0]*(N))

#function

#class

#main function
def main():
    for i in range(N):
        rootList[i+1] = (rootList[i]+rootList[i-1])%1000000007
        if i+1 in A:
            rootList[i+1] = 0
    print(rootList[N])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
MOD = 1000000007 
D=[0] * (n + 1)
for _ in range(m):
    D[int(input())] = -1
for i in range(n+1):
    if D[i] == -1:
        continue
    if i in (0, 1):
        D[i] = 1
        continue
    if D[i-1] != -1:
        D[i] += D[i-1]
    if D[i-2] != -1:
        D[i] += D[i-2]
    D[i]%=MOD
print(D[i] % MOD)

Submission status: Accepted

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

Submission status: Accepted

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

for n, i in enumerate(a):
    if n > 0:
        if (a[n] - a[n-1]) == 1:
            print(0)
            exit()

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

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

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


print(dp[0]%1000000007)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)

def dfs(heights: int, a_index:int, a_n_1, a_n_2):
    if n < heights:
        return
    
    if m != 0 and a_index <= len(a) -1 and a[a_index] == heights:
        memo[2] = 0
        a_index += 1
        #print("10",heights)
    else:
        memo[2] = a_n_1 + a_n_2 #memo[1] + memo[0]
        #print("13",heights)
    dfs(heights+1,a_index,memo[2],a_n_1)
    return
    

n,m = list(map(int, input().split()))
memo = [1]*(3)
a = []
a_index = 0
if m != 0:
    for i in range(m):
        tmp = int(input())
        if i >= 1 and tmp -1 == a[len(a)-1]:
            print(0)
            sys.exit()
        else:
            a.append(tmp)
            #print(i,a)

    if a[0] == 1:
        memo[1] = 0
        a_index += 1
#a = list(set(a))
#a.sort()
dfs(2,a_index,memo[1],memo[0])
#print(memo)
print(memo[2] % (10**9+7))

Submission status: Accepted

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

dp=[0 for i in range(N+1)]
#dp[今どこにいるか] = 何通りあるか
dp[0] = 1

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

ans = dp[N]%1000000007

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
a = list(int(input()) for _ in range(M))

MOD = pow(10, 9) + 7

MAP = [0] * (N + 1)

for x in a:
    MAP[x] = -1

MAP[0] = 1 
for i in range(N):
    if MAP[i] < 0:
        continue

    MAP[i] %= MOD
    if i + 1 <= N and MAP[i+1] >= 0:
        MAP[i+1] += MAP[i]
    if i + 2 <= N and MAP[i+2] >= 0:
        MAP[i+2] += MAP[i]

print(MAP[N] % MOD)

Submission status: Accepted

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

mod_num = 10 ** 9 + 7
a = [0] * M

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

val = [0,1]
j = 0
for i in range(1, N + 1):
    ans = (val[0] + val[1]) % mod_num
    val[0] = val[1]
    val[1] = ans
    if i in a:
        val[1] = 0

 
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

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

broken = set(map(int, sys.stdin))

mod = 10 ** 9 + 7
f2, f1 = 0, 1
for i in range(1, N + 1):
  if i in broken:
    if i - 1 in broken:
      print(0)
      exit()
    f2 = f1
    f1 = 0
    continue
  f = f2 + f1
  f2 = f1
  f1 = f
print(f % mod)

Submission status: Accepted

Solution code:
mod = 1000000007

N, M = [int(i) for i in input().split()]
A = [-1] + [int(input()) for _ in range(M)] + [N + 1]

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

fib = [-1] * (N + 1)
fib[0] = 1
fib[1] = 1
for i in range(2, len(fib)):
    fib[i] = fib[i - 1] + fib[i - 2]

ans = 1
for i in range(1, len(A)):
    f = fib[A[i] - A[i - 1] - 2]
    ans = (ans * f) % mod
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
al=set([int(input()) for i in range(m)])
mod=1000000007
ansl=[0,1]
for i in range(1,n+1):
    if i in al:
        ansl.append(0)
    else:
        ansl.append((ansl[-2]+ansl[-1])%mod)
print(ansl[-1]%mod)

Submission status: Accepted

Solution code:
def fib_memo(n,broken):
    memo = [0]*(n+1)
    memo[0] = 1
    for x in range(1,n+1):
        if x < 1:
            continue
        if broken[x]==1:
            continue
        memo[x] = (memo[x-1] + memo[x-2])%1000000007

    return memo[n]

n,m = map(int,input().split())
a =[]
pos = 0
result = 1
last = -1
broken = [0]*(n+1)
for i in range(m):
    x = int(input())
    if (last+1) == x:
        print(0)
        exit(0)
    last = x
    a.append(x)
    broken[x] = 1

result = fib_memo(n,broken)

print(result)

Submission status: Accepted

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

#通れない箇所を示す配列の作成
a = [0 for i in range(N+1)] #0で初期化

#通れない箇所にフラグを立てる
for mi in range(M):
    a[int(input())] = 1
#print(a)

cnt = 0

#通れるパターンを示す配列の作成
s = [0 for i in range(N+1)] #0で初期化
s[0] = 1  #フィボナッチlikeに　n-1, n-2を参照して計算するので，はじめは1とする
#print(s)

if a[1] == 0:  #配列aで通れるのなら1
    s[1] = 1
else:
    s[1] = 0   #配列aで通れないのなら0
#print(s)
for ni in range(2,N+1):  #フィボナッチlikeなので[2]から計算開始
    if a[ni] == 0:  #通れる場合
        s[ni] = (s[ni-1] + s[ni-2]) % 1000000007
    else: #通れない場合
        s[ni] = 0
#print(s)

print(s[N]) #配列の最後が答え

Submission status: Accepted

Solution code:
import sys

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

if M == 0:
    alist = set()
else:
    # Input below rows
    alist = set(map(int, sys.stdin))

dp = [0] * (N + 1)
dp[0] = 1
dp[1] = 1 if 1 not in alist else 0

MOD = 10**9 + 7
for i in range(2, N + 1):
    if i in alist:
        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_num = 10 ** 9 + 7
a = [0] * N

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

val = [0,1]
j = 0
for i in range(1, N + 1):
    ans = (val[0] + val[1]) % mod_num
    val[0] = val[1]
    val[1] = ans
    if len(a) > 0:
        if i == a[j]:
            val[1] = 0
            if len(a) - 1 != j:
                j += 1
 
print(ans)

Submission status: Accepted

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

if M == 0:
    alist = set()
else:
    alist = set(int(input()) for _ in range(M))

dp = [0] * (N + 1)
dp[0] = 1
dp[1] = 1 if 1 not in alist else 0

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

print(dp[N])

Submission status: Accepted

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

dp = [0 for _ in range(N+1)]
P = 10**9 + 7

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

Submission status: Accepted

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


dp = [-1]*(n+1)
dp[0] = 1
for i in para :
    dp[i] = 0
import sys
sys.setrecursionlimit(200000)
def dps(cnt,cantvisit):
    if cnt == n + 1 :
        return 

    else :
        if cnt == 1 :
            if cnt in cantvisit :
                dp[1] = 0
                cnt += 1
            else : 
                dp[1] = 1
                cnt += 1
        else :
            if dp[cnt] != 0 :  
                dp[cnt] = (dp[cnt-1] + dp[cnt-2]) % mod
                cnt += 1
            else :
                cnt += 1
        return dps(cnt,cantvisit)

dps(1,para)
print("{}".format(dp[-1]%mod))

Submission status: Accepted

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

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

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

print(howmany_list[n])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
def lmi(): return list(map(int, input().split()))

n, m = lmi()
a = [1] * (n+1)
for i in range(m):
    a[int(input())] = 0
k = [0] * (n+1)
k[0] = 1
for i in range(1,n+1):
    if i == 1 and a[1]:
        k[1] = 1
    elif i >= 2 and a[i]:
        k[i] = k[i-1] + k[i-2]
        k[i] %= 10 ** 9 + 7

print(k[n])

Submission status: Accepted

Solution code:
def func(n):
    if n==0: return 1
    if n==1: return 1
    if dp[n]!=-1: return dp[n]
    f1 = func(n-1) if n-1 not in a else 0
    f2 = func(n-2) if n-2 not in a else 0
    dp[n] = (f1 + f2) % 1000000007
    return dp[n]
import sys
sys.setrecursionlimit(1000000)
n,m = map(int, input().split())
a={int(input()) for i in range(m)}
dp=[-1]*(n+1)
print(func(n))

Submission status: Accepted

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

mod_num = 10 ** 9 + 7
a = [0] * N

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

val = [0,1]
for i in range(1, N + 1):
    ans = (val[0] + val[1]) % mod_num
    val[0] = val[1]
    val[1] = ans
    if len(a) > 0:
        if i == a[0]:
            val[1] = 0
            a.pop(0)
 
print(ans)

Submission status: Accepted

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


def main():
    mod = 1000000007
    N, M = map(int, input().split())
    # 計算用にidx=-1を追加する
    a = [0 for i in range(0, N+2)]

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

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

        if a[i-1] != -1:
            a[i] += a[i-1]

        if a[i-2] != -1:
            a[i] += a[i-2]

        a[i] %= mod

    print(a[-1])


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

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

mod_num = 10 ** 9 + 7
a = []
for _ in range(M):
    a.append(int(input()))

val = [0,1]
for i in range(1, N + 1):
    ans = (val[0] + val[1]) % mod_num
    val[0] = val[1]
    val[1] = ans
    if len(a) > 0:
        if i == a[0]:
            val[1] = 0
            a.pop(0)
 
print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
A=set([int(input()) for __ in range(M)])
ans=[0]*(N+1)
ans[0] = 1

if 1 in A:
    ans[1]=0
else:
    ans[1]=1

for n in range(N+1):
    if n>1:
        if n-1 in A and n in A:
            print(0)
            break
        elif n in A:
            ans[n]=0
        else:
            ans[n]=(ans[n-1]+ans[n-2]) % 1000000007
else:
    print(ans[N])

Submission status: Accepted

Solution code:
import sys
 
n, m = list(map(int, input().split()))
if m > 0:
    aaa = set(map(int, sys.stdin))
else:
    aaa = set()
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1 if 1 not in aaa else 0
MOD = 10 ** 9 + 7
 
for i in range(2, n + 1):
    if i in aaa:
        continue
    dp[i] = (dp[i - 2] + dp[i - 1]) % MOD
print(dp[n])

Submission status: Accepted

Solution code:

N, M = input().split()

N = int(N)
M = int(M)
a = []
c = []

for i in range(M):

    anew = int(input())
    a.append(anew)

now_a = 0
a.append(-1)
ans = 0

for i in range( N + 1 ):

    if (i == 0):
        c.append(1)
        
    elif (i == 1):

        if (a[now_a] == i):
            c.append(0)
            now_a += 1
        else:
            c.append(1)

    else:

        if (a[now_a] == i):
            c.append(0)
            now_a += 1
        else:
            c.append( c[i - 1] + c[i - 2])
        

ans = c[N] % 1000000007

print (ans)

Submission status: Accepted

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

patterns = [1]
if stairs[1]:
    patterns.append(0)
else:
    patterns.append(1)

for i in range(2, n + 1):
    if stairs[i]:
        patterns.append(0)
    else:
        patterns.append(patterns[i - 1] + patterns[i - 2])

print(patterns[-1] % 1000000007)

Submission status: Accepted

Solution code:
NM = [int(i) for i in input().split()]
a = [0] * NM[0]
for _ in range(NM[1]):
    a[int(input()) - 1] = -1

for i in range(NM[0]):
    if (i == 0):
        if(a[i] != -1):
            a[i] = 1
        else:
            a[i] = 0
    elif(i == 1):
        if(a[i] != -1):
            a[i] = a[i - 1] + 1
        else:
            a[i] = 0
    else:
        if(a[i] != -1):
            a[i] = a[i-1] + a[i - 2]
        else:
            a[i] = 0

print(a[NM[0]-1] % (10**9 + 7))

Submission status: Accepted

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

mod=10**9+7

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

b = defaultdict(int)
b[0]=1

for i in range(1,N+1):
    if f[i]==1:
        b[i]=(f[i-1]*b[i-1]+f[i-2]*b[i-2])%mod

print(b[N])

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

n, m = map(int, input().split())
a_set = set([int(input()) for _ in range(m)])
comb_list = [1, 1]
if 1 in a_set:
    comb_list[1] = 0
for i in range(2, n+1):
    if i in a_set:
        comb_list.append(0)
    else:
        comb_list.append((comb_list[-2]+comb_list[-1])%(10**9+7))
print(comb_list[n])

Submission status: Accepted

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

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

Submission status: Accepted

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

dp = [0] * (N+1)
dp[0] = 1
for i in range(N+1):
    for j in range(i+1, min(i+2, N)+1):
        if oks[j]:
            dp[j] += dp[i]
            dp[j] %= int(1e9+7)


print(dp[N])

Submission status: Accepted

Solution code:
import sys

mod = 10**9 + 7

def fibo(n):
    a, b = 0, 1
    if n == 1:
        return 1
    else:
        for i in range(n):
            a0 = a
            a = b
            b = a0 + b
        return b
        
N, M = map(int, input().split())
a = []
 
if M == 0:
    print(fibo(N) % mod)
    sys.exit()
 
for i in range(M):
    a.append(int(input()))
    
for j in range(len(a)-1):
    if a[j+1] - a[j] == 1:
        print(0)
        sys.exit()
    
hole = 0
pattern = 1
 
for i, k in enumerate(a):
    if i == 0:
        pattern *= fibo(k-1)
    else:
        if i > 0:
            pattern *= fibo(a[i]-a[i-1]-2)
        
pattern *= fibo(N-a[-1]-1)
print(pattern % mod)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
import sys
sys.setrecursionlimit(10000000)

mod = 1000000007

memo = [-1] * (N+1)

for _ in range(M):
    broken_step = int(input())
    memo[broken_step] = 0
    
memo[0] = 1
if memo[1] == -1:
    memo[1] = 1

def step_memo(N):
    
    if memo[N] != -1:
        return memo[N]
    
    memo[N] =  (step_memo(N-1) + step_memo(N-2)) % mod
    return (step_memo(N-1) + step_memo(N-2)) % mod
  
print(step_memo(N))

Submission status: Accepted

Solution code:
from sys import setrecursionlimit
from functools import lru_cache

setrecursionlimit(999999)
@lru_cache(maxsize=None)
def calc(n):
    if n <= 1:
        return 1
    elif n == 2:
        return 2
    return calc(n - 1) + calc(n - 2)


K = 10 ** 9 + 7

n, m = map(int, input().split())
broken = []
no_reachable = False
for _ in range(m):
    a = int(input())
    if len(broken) and a == broken[-1] + 1:
        no_reachable = True
        break
    broken.append(a)

if not no_reachable:
    a = 0
    cb = 1
    for b in broken:
        stairs = b - a - 1
        cb *= calc(stairs)
        a = b + 1
    cb *= calc(n - a)
    print(cb % K)
else:
    print(0)

Submission status: Accepted

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

MOD = 1000000007

def fib(n):
    dp_list = [0] * n
    dp_list[0] = 1
    if n == 1:
        return 1
    dp_list[1] = 2
    
    for i in range(2, n):
        dp_list[i] = dp_list[i - 1] + dp_list[i - 2]
    return dp_list[n - 1]

if M == 0:
    print(fib(N) % MOD)
    sys.exit()

a_list = [0] * M

for m in range(M):
    a_list[m] = int(input())

for m in range(M - 1):
    if a_list[m] + 1 == a_list[m + 1]:
        print(0)
        sys.exit()
    else:
        continue

range_list = [i for i in range(1, N + 1)]
new_list = [0] * (M + 1)


new_list[0] = [0] + range_list[0: a_list[0] - 1]
new_list[M] = range_list[a_list[M - 1]:]

if M - 1 >= 1:
    for m in range(1, M):
        new_list[m] = range_list[a_list[m - 1]: a_list[m] - 1]

count = 1
for item in new_list:
    if not item or len(item) == 1:
        continue
    else:
        count *= (fib(len(item) - 1) % MOD)
        count %= MOD
        #print(count)
print(count)

Submission status: Accepted

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

Submission status: Accepted

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

  s=[0]*n
  if a[0]==1 and a[1] == 1:
    s[0] = 0
    s[1] = 0
  elif a[0] == 1:
    s[0] = 0
    s[1] = 1
  elif a[1] == 1:
    s[0] = 1
    s[1] = 0
  else:
    s[0] = 1
    s[1] = 2

  for i in range(2,n):
    #壊れている
    if a[i] == 1:
      s[i] = 0
    else:
      s[i] = s[i-1]+s[i-2]
  print(s[n-1]%1000000007)
else:
  print(1)

Submission status: Accepted

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

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

val = [0,1]
for i in range(1, N + 1):
    ans = val[0] + val[1]
    val[0] = val[1]
    val[1] = ans
    if len(a) > 0:
        if i == a[0]:
            val[1] = 0
            a.pop(0)

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

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 = map(int, input().split())
A = []
for i in range(M):
	curr = int(input())
	A.append(curr)

mod = 1000000007

ans = [0] * (N + 1)

ans[0] = 1

for a in A:
	ans[a] = -1

for i in range(len(ans)):
	if ans[i] == -1:
		continue
	if(i+1 < len(ans) and ans[i+1] != -1):
		ans[i+1] += ans[i]
		ans[i+1] %= mod
	if(i+2 < len(ans) and ans[i+2] != -1):
		ans[i+2] += ans[i]
		ans[i+2] %=mod

print(ans[N])

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
tmp = []

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 = map(int,input().split())
para = [int(input()) for i in range(m)]
mod = 10**9+7
dp = [-1]*(n+1)
for i in para:
    dp[i] = 0
for i in range(n+1):
    if  dp[i] != 0 :
        if i == 1 or i==0:
            dp[i] = 1
        else:
            dp[i] = (dp[i-1] + dp[i-2])%mod



print("{}".format(dp[-1]))

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
tmp = []

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

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:
def exec_ncr(max_step, record_dict):
    for i in range(2, max_step+1):
        record_dict[i] = record_dict[i-1] + record_dict[i-2]


num_stair, num_wet = map(int, input().split(' '))

last_wet = -1
num_pattern = 1
d = {0: 1, 1: 1}
exec_ncr(num_stair, d)

for i in range(0, num_wet):
    wet = int(input())
    dry_step = wet - last_wet - 1
    last_wet = wet

    if dry_step <= 0:
        print('0')
        exit(0)

    elif dry_step == 1 or dry_step == 2:
        continue

    else:
        num_pattern *= d[dry_step-1]

# last step
dry_step = num_stair - last_wet

num_pattern *= d[dry_step-1]

print(num_pattern % 1000000007)
exit(0)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
a = [0] * N
for _ in range(M):
    a[int(input())-1] = '!'

for i in range(N):
    if i == 0:
        if a[i] != '!':
            a[i] = 1
        else:
            a[i] = 0
    elif i == 1:
        if a[i] != '!':
            a[i] = a[i-1] + 1
        else:
            a[i] = 0
    else:
        if a[i] != '!':
            a[i] = (a[i-1] + a[i-2]) % 1000000007
        else:
            a[i] = 0

print(a[N-1] % 1000000007)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)

def intinput(): return map(int,sys.stdin.readline().split())

fib={0:0,1:1,2:1}
for i in range(3,100003):
    fib[i]=fib[i-1]+fib[i-2]
  #  fib.append(fib[i-1]+fib[i-2])

n,m=intinput()
mod=10**9+7
a=[int(sys.stdin.readline()) for _ in range(m)]
if m!=0:
    l=[a[0]]
    for i in range(len(a)-1):
        l.append(a[i+1]-a[i]-1)
    l.append(n-a[-1])
    k=1
    for i in l:
        k=fib[i]*k%mod
    print(k%mod)
else:
    print(fib[n+1]%mod)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

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


N, M = acinput()
a = [0]*(N+1)
for i in range(M):
    a[int(input())] = 1


Mod = 1000000007


def solve(x):
    global dp, Mod
    if dp[x] >= 0:
        return dp[x]

    if x < 0:
        return 0

    res = 0
    zeroflg = True

    if  a[x-2] != 1:
        res += solve(x-2) 
        zeroflg = False

    if a[x-1] != 1:
        res += solve(x-1)
        zeroflg = False

    if zeroflg:
        return 0
    dp[x] = res% Mod
    return res


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

print(solve(N) % Mod)


'''
5 1
1
'''

Submission status: Accepted

Solution code:
from itertools import*
from math import*
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float("inf")
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

N,M = map(int,input().split())
bool = [True]*(N+1)
dp = [0]*(N+1)
for i in range(M):
    a = int(input())
    bool[a] = False
dp[0],dp[1]=1,1
for i in range(2,N+1):
    if bool[i-1]:
        dp[i] += dp[i-1]
        dp[i] %= mod
    if bool[i-2]:
        dp[i] += dp[i-2]
        dp[i] %= mod
print(dp[-1])

Submission status: Accepted

Solution code:
n,b,*a=map(int,open(0).read().split())
a=set(a)
d=i=0
c=1
while i<n:i+=1;b=(c+d)%(10**9+7)*(not{i}&a);c,d=b,c
print(b)

Submission status: Accepted

Solution code:
def calc(n):
    if n <= 1:
        return 1
    elif n == 2:
        return 2
    else:
        a, b = 1, 2
        for _ in range(n - 2):
            b, a = a + b, b
        return b


K = 10 ** 9 + 7

n, m = map(int, input().split())
broken = []
no_reachable = False
for _ in range(m):
    a = int(input())
    if len(broken) and a == broken[-1] + 1:
        no_reachable = True
        break
    broken.append(a)

if not no_reachable:
    a = 0
    cb = 1
    for b in broken:
        stairs = b - a - 1
        cb *= calc(stairs)
        a = b + 1
    cb *= calc(n - a)
    print(cb % K)
else:
    print(0)

Submission status: Accepted

Solution code:
def fib(n):
  a, b = 0, 1
  for i in range(n):
    a, b = b, a + b
    if b > 1000000007:
      b -= 1000000007
  return b

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

Submission status: Accepted

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

if 1 in danger:
    steps[1]=0
else:
    steps[1]=1

for this_step in range(2,n+1):
    if this_step in danger:
        ap=0
    else:
        steps[this_step]=steps[this_step-1]+steps[this_step-2]

print(steps[-1]%1000000007)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,b,*a=map(int,open(0).read().split())
a=set(a)
d=i=0
c=1
while i<n:i+=1;b=(c+d)%(10**9+7)*(not i in a);c,d=b,c
print(b)

Submission status: Accepted

Solution code:
import math
n, m = [int(i) for i in input().split()]
p = [0 for i in range(n + 1)]
for _ in range(m):
    p[int(input())] = 1
    
a = []
a.append(1)
if p[1] == 1:
    a.append(0)
else:
    a.append(1)
for i in range(2, n + 1):
    if p[i] == 1:
        a.append(0)
    else:
        a.append((a[i - 2] + a[i - 1]) % 1000000007)
    
print(a[n])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n, m = map(int, input().split())
BIGNUM = 10 ** 9 + 7

k = list()
last_ana = -1
for _ in range(m):
    ana = int(input())
    k.append(ana - last_ana - 1)
    last_ana = ana
k.append(n - last_ana)

if 0 in k:
    ans = 0
else:
    k_max = max(k)
    c = [1, 1]
    for i in range(2, k_max):
        c_tmp = c[i - 1] + c[i - 2]
        c.append(c_tmp % BIGNUM)

    ans = 1
    for num in k:
        ans *= c[num - 1]
        ans %= BIGNUM
        if ans == 0:
            break

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from math import factorial

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

def fibo(dan):
    tmp = [1, 1]
    for i in range(2, dan+1):
        tmp.append(tmp[i-1] + tmp[i-2])
    return tmp[dan]

routes = 1
prev = 0
for x in a:
    if x == prev:
        routes = 0
        break
    else:
        dan = (x-1) - prev
        routes = (routes * fibo(dan)) % 1000000007
        prev = x+1

routes = (routes * fibo(N-prev)) % 1000000007
print(int(routes))

Submission status: Accepted

Solution code:
def c_typical_stairs(N, M, A, MOD=10**9 + 7):
    a = set(A)
    way_go_up_the_stairs = [1] + [0] * (N)
    for i in range(1, N + 1):
        if i not in a:
            way_go_up_the_stairs[i] = (
                way_go_up_the_stairs[i]
                + (way_go_up_the_stairs[i - 1] if i - 1 >= 0 else 0)
                + (way_go_up_the_stairs[i - 2] if i - 2 >= 0 else 0)) % MOD
    return way_go_up_the_stairs[N]

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