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: Runtime Error

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

#n = int(input())
#l = list(map(int, input().split()))

'''
A=[]
B=[]
for i in range():
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)'''


n,m=map(int, input().split())
fibo = [1, 1]
for i in range(1, 10**5+1):
    fibo.append(fibo[i]+fibo[i-1])
#print(fibo)
a=[]
for i in range(m):
    a.append(int(input()))

flg=True
for i in range(m-1):
    if a[i]+1==a[i+1]:
        flg=False
        break
#print(a[0]==a[1],flg)
if not flg:
    print(0)
else:
    ans=1
    if m==1:
        #print(fibo[a[0]-1],fibo[n-a[0]-1])
        print(fibo[a[0]-1]*fibo[n-a[0]-1] % (10**9+7))
    else:
        for i in range(1,m):
            #print(a[i],a[i-1])
            #print(fibo[21])
            #print(fibo[a[i]-a[i-1]-1])
            ans*=fibo[a[i]-a[i-1]-1]
            print(ans % (10**9+7))

        #print(fibo[a[0]-1],fibo[n-a[m-1]-1],fibo[10])
        print(ans*fibo[a[0]-1]*fibo[n-a[m-1]-1]%(10**9+7))

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
a=[int(input()) for _ in range(M)]
dp=[0]*N
id=0
p=10**9+7
point=a[id]
for i in range(N):
    if i==0:
        if a[id]!=(i+1):
            dp[i]=1
        else:
            id=id+1
    elif i==1:
        if a[id]!=(i+1):
            dp[i]=dp[i-1]+1
        else:
            id=id+1
    else:
        dp[i]=dp[i-1]+dp[i-2]
        if a[id]==i+1:
            dp[i]=0
            if id<len(a)-1:
                id=id+1
print(dp[N-1]%p)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
n,m = map(int, input().split())

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

#`dp[i] = i段目にいる通り数`
dp[0] = 1
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]) % (10 ** 9 + 7)

print(dp[-1])

Submission status: Runtime Error

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

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

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

check = set(a)
if a[0] == 1:
    dp = [0, 0, 1]
else:
    dp = [0, 1, 2]
if N < 3:
    print(dp[N])
    exit()
for i in range(3, N+1):
    if i in check:
        dp.append(0)
    else:
        dp.append((dp[-1] + dp[-2])%1000000007)

print(dp[-1])

Submission status: Runtime Error

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

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

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

check = set(a)
if a[0] == 1:
    dp = [0, 0, 1, 1]
    start = 4
    if N < 4:
        print(dp[N])
        exit()
else:
    dp = [0, 1, 2]
    start = 3
    if N < 3:
        print(dp[N])
        exit()
for i in range(start, N+1):
    if i in check:
        dp.append(0)
    else:
        dp.append((dp[-1] + dp[-2])%1000000007)

print(dp[-1])

Submission status: Runtime Error

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

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

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

check = set(a)
if a[0] == 1:
    dp = [0, 0, 1, 1]
    start = 4
else:
    dp = [0, 1, 2]
    start = 3
for i in range(start, N+1):
    if i in check:
        dp.append(0)
    else:
        dp.append((dp[-1] + dp[-2])%1000000007)

print(dp[-1])

Submission status: Runtime Error

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

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

if M == 0:
    arr = N
else:
    arr = [a[0] - 1]
    for i in range(M-1):
        print(a[i], a[i+1])
        diff = a[i+1] - a[i] - 1
        arr.append(diff)
        if diff == 0:
            print(0)
            exit()
    arr.append(N - a[-1] - 1)

count = [1, 1, 2]
for i in range(3, max(arr)+1):
    count.append(count[-1] + count[-2])

ans = 1
for value in arr:
    ans *= count[value]
    ans = ans % 1000000007

print(ans)

Submission status: Runtime Error

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

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

if M = 0:
    arr = N
else:
    arr = [a[0] - 1]
    for i in range(M-1):
        print(a[i], a[i+1])
        diff = a[i+1] - a[i] - 1
        arr.append(diff)
        if diff == 0:
            print(0)
            exit()
    arr.append(N - a[-1] - 1)

count = [1, 1, 2]
for i in range(3, max(arr)+1):
    count.append(count[-1] + count[-2])

ans = 1
for value in arr:
    ans *= count[value]
    ans = ans % 1000000007

print(ans)

Submission status: Runtime Error

Solution code:
import sys
from collections import Counter
input = sys.stdin.readline

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

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

count = [1, 1, 2]
for i in range(3, max(arr)+1):
    count.append(count[-1] + count[-2])

ans = 1
for value in arr:
    ans *= count[value]
    ans = ans % 1000000007

print(ans)

Submission status: Runtime Error

Solution code:
def Fib(n):
  a,b = 1,2
  if n == 1:
    return a
  elif n == 2:
    return b
  else:
    for i in range(n-2):
      a,b = b,a+b
    return b
N,M = map(int,input().split())
a = list()
flag = True
su = 0
kai = 0
for i in range(M):
  b = int(input())
  a.append(b)
for i in range(M-1):
  if a[i] +1 == a[i+1]:
    flag = False
if flag == True:
  if a[0] != 1:
    for i in range(M):
      su += Fib(a[i]-1-kai)%(10**9+7)
      su %= 10**9 + 7
      kai = a[i]
    su += Fib(N-a[-1] -1)%(10**9+7)
    su %= (10**9+7)
  else:
    kai = 2
    for i in range(M-1):
      su += Fib(a[i+1]-1-kai)%(10**9+7)
      su %= 10**9 + 7
      kai = a[i+1]
    su += Fib(N-a[-1] -1)%(10**9+7)
    su %= (10**9+7)
    
    
    
print(su)

Submission status: Runtime Error

Solution code:
def Fib(n):
  a,b = 1,2
  if n == 1:
    return a
  elif n == 2:
    return b
  else:
    for i in range(n-2):
      a,b = b,a+b
    return b
N,M = map(int,input().split())
a = list()
flag = True
su = 0
kai = 0
for i in range(M):
  b = int(input())
  a.append(b)
for i in range(M-1):
  if a[i] +1 == a[i+1]:
    flag = False
if flag == True:
  if a[0] != 1:
    for i in range(M):
      su += Fib(a[i]-1-kai)%(10**9+7)
      su %= 10**9 + 7
      kai = a[i]
    su += Fib(N-a[-1] -1)%(10**9+7)
    su %= (10**9+7)
  #else:
    
    
    
print(su)

Submission status: Runtime Error

Solution code:
def Fib(n):
  a,b = 1,2
  if n == 1:
    return a
  elif n == 2:
    return b
  else:
    for i in range(n-2):
      a,b = b,a+b
    return b
N,M = map(int,input().split())
a = list()
flag = True
su = 0
kai = 0
for i in range(M):
  b = int(input())
  a.append(b)
for i in range(M-1):
  if a[i] == a[i+1]:
    flag = False
if flag == True:
  if a[0] != 1:
    for i in range(M):
      su += Fib(a[i]-1-kai)%(10**9+7)
      su %= 10**9 + 7
      kai = a[i]
    su += Fib(N-a[-1] -1)%(10**9+7)
    su %= (10**9+7)
  #else:
    
    
    
print(su)

Submission status: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
N,m=map(int,input().split())
s = set()
for i in range(m):
    s.add(int(input()))
memo={0:1}
mod=1000000007
def climb_stairs(n):
    if memo.__contains__(n):
        return memo[n]
    else:
        if s.__contains__(n):
            return 0
        elif n==1:
            return 1
        else:
            memo[n]=(climb_stairs(n-1)%mod + climb_stairs(n-2)%mod)%mod
            return memo[n]
print(climb_stairs(N))

Submission status: Runtime Error

Solution code:
N,m=map(int,input().split())
s = set()
for i in range(m):
    s.add(int(input()))
memo={0:1}
mod=1000000007
def climb_stairs(n):
    if memo.__contains__(n):
        return memo[n]
    else:
        if s.__contains__(n):
            return 0
        elif n==1:
            return 1
        else:
            memo[n]=((climb_stairs(n-1)%mod + (climb_stairs(n-2) %mod)%mod
            return memo[n]
print(climb_stairs(N))

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
s = set()
for i in range(m):
    s.add(int(input()))
memo={0:1}
def climb_stairs(n):
    if memo.__contains__(n):
        return memo[n]
    else:
        if s.__contains__(n):
            return 0
        elif n==1:
            return 1
        memo[n]=(((climb_stairs(n-1))%1000000007+(climb_stairs(n-2))%1000000007)%1000000007)
        return memo[n]
print(climb_stairs(n))

Submission status: Runtime Error

Solution code:
N, M = [int(x) for x in input().split()]
a = [int(input()) for _ in range(M)]
p = 10 ** 9 + 7

fib = [1, 1] + [None] * (N - 1)
for i in range(2, N + 1):
    fib[i] = (fib[i - 1] + fib[i - 2]) % p

for j in range(M):
    if a[j] == N or (j + 1 < M and a[j] + 1 == a[j + 1]):
        ans = 0
        break
        
    if j == 0:
        ans = fib[a[j] - 1]
    else:
        ans *= fib[a[j] - 1 - (a[j - 1] + 1)]
        ans %= p
else:
    ans *= fib[N - a[M - 1] - 1]
    ans %= p

print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(5000)
N,M = map(int,input().split())
def stair(N):
    if(N <0):
        return 0
    if(N == 0):
        return 1
    elif(N == 1):
        return 1
    elif(N == 2):
        return 2
    else:
        return stair(N-1)+stair(N-2)
ans = 1
a = 0
mod = 10**9+7
for i in range(M):
    b = int(input())
    b -=1
    ans = ans*stair(b-a)%mod
    a = b+2
ans = ans*stair(N-a)%mod
print(ans)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
def stair(N):
    if(N <0):
        return 0
    if(N == 0):
        return 1
    elif(N == 1):
        return 1
    elif(N == 2):
        return 2
    else:
        return stair(N-1)+stair(N-2)
ans = 1
a = 0
mod = 10**9+7
for i in range(M):
    b = int(input())
    b -=1
    ans = ans*stair(b-a)%mod
    print(a,b,ans)
    a = b+2
ans = ans*stair(N-a)%mod
print(ans)

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
mod=1000000007
f=[False]*(N+1)
for _ in range(M):
    i=int(input())
    f[i]=True
dp=[0 for _ in range(N+1)]

if f[1] and f[2]:
    print(0)
    exit()
elif f[1]:
    dp[1]=0;dp[2]=1
elif f[2]:
    dp[1]=1;dp[2]=0
else:
    dp[1]=1;dp[2]=2

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

Submission status: Runtime Error

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

MOD = 1000000007

d = [0] * (N+1)
NG = [FALSE]*N
d[0] = 1
if(1 in a):
    d[1] = 0
else:
    d[1] = 1

for i in range(M):
    NG[i] = True


for i in range(2,N+1):
    if(NG[i-1] == False):
        d[i] = d[i-1] + d[i-2]
        d[i] %= MOD
    '''
    if(i in a):
        d[i] = 0
    else:
        d[i] = d[i-1] + d[i-2]
    d[i] %= MOD
    '''

print(d[-1])

Submission status: Runtime Error

Solution code:
#import sys
#sys.setrecursionlimit(10 ** 7)
'''
#import numpy as np
import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, functools, random
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop
from itertools import permutations, combinations, product, accumulate, groupby
from bisect import bisect_left, bisect_right, insort_left, insort_right
from operator import itemgetter as ig
#sys.setrecursionlimit(10 ** 7)
'''
#inf = 10 ** 20
'''
INF = float("INF")
mod = 10 ** 9 + 7
"""dd = [(-1, 0), (0, 1), (1, 0), (0, -1)];
ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)];
ddn9 = ddn + [(0, 0)]
for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""

def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]  # WideIntPoint
def ws(): return sys.stdin.readline().split()
def si(): return int(sys.stdin.readline())  # SingleInt
def ss(): return input()
def hi(n): return [si() for _ in range(n)]
def hs(n): return [ss() for _ in range(n)]  # HeightString
def s_list(): return list(input())
def mi(n): return [wi() for _ in range(n)]  # MatrixInt
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]
def num_grid(n): return [[int(i) for i in sys.stdin.readline().split()[0]] for _ in range(n)]  # NumberGrid
def grid(n): return [s_list() for _ in range(n)]

'''
def binary_search(num_list, target):
    # 「値が何番目にあるか」を確認するための変数
    ans_counter = 0
    while True:
        # 配列の中心にある値を取り出す
        middle = num_list[len(num_list) // 2]
        # 配列の左側
        left = num_list[:len(num_list) // 2]
        # 配列の右側
        right = num_list[len(num_list) // 2:]
        # 中心の値が探索値と一致したら探索終了(探索値発見)
        if middle == target:
            ans_counter += len(left) + 1
            #print("{}は{}番目にありました。".format(target, ans_counter))
            return True
            break
        # 値が最後の1個になっても一致しなかったら探索終了(探索値不存在1)
        # 左の最大値 < 探索値 < 右の最小値となった場合探索終了(探索値不存在2)
        elif len(num_list) == 1 and num_list[0] != target\
                or left[-1] < target < right[0]:
            #print("{}はありませんでした。".format(target))
            return False
            break
        # 左の最大値より探索値が小さい場合、探索範囲を左側に絞る
        elif target <= left[-1]:
            num_list = left
        # 右の最小値より探索値が大きい場合、探索範囲を右側に絞る
        elif right[0] < target:
            ans_counter += len(left)
            num_list = right

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

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

mod=10**9+7
dp=[0]*(n+1)
dp[0]=1
j=0
for i in range(1,n+1):
    if i == a[j]:
        dp[i]=0
        j=min(m-1,j+1)
    else:
        dp[i]=(dp[i-2]+dp[i-1])%mod
print(dp[-1])

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
base = [int(input()) for i in range(m)]
count = 0
now = 0
i= 0
j = 0

dp = [0]*(n+1)
if 1 == base[j]:
  dp[1] = 0
  j = 1
else:
  dp[1] = 1

dp[0] = 1

for i in range(2,n+1):
  if not (i == base[j]):
    dp[i] = dp[i-1] + dp[i-2]
  elif i == base[j]:
    if j < m-1:
      j = j + 1
  
  
print(int(dp[n]%1000000007))

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
base = [int(input()) for i in range(m)]
count = 0
now = 0
i= 0
j = 0

dp = [0]*(n+1)
if 1 == base[j]:
  dp[1] = 0
  if j < m-1:
    j = j + 1
else:
  dp[1] = 1

dp[0] = 1

for i in range(2,n+1):
  if not (i == base[j]):
    dp[i] = dp[i-1] + dp[i-2]
  elif i == base[j]:
    if j < m-1:
      j = j+1
  
  
print(int(dp[n]%1000000007))

Submission status: Runtime Error

Solution code:
import sys
N,M = map(int,input().split())
intact = [True for _ in range(N)]
dp = [0 for _ in range(N+1)]
MOD = 1000000007
for i in range(M):
  a = int(input())
  if N == 1:
    print(1)
    sys.exit(0)
  intact[a] = False
dp[0] = 1
if (intact[1]):
  dp[1] = 1
for i in range(2,N+1):
  if intact[i-2]:
    dp[i] += dp[i-2]
  if intact[i-1]:
    dp[i] += dp[i-1]
  dp[i] %= MOD
print(dp[N])

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
M=10**9+7
f=input
n,m=map(int,f().split())
s,t,u=0,1,int(f())
for i in range(n):
  if i==u-1:
    s,t=t,0
    try: u=int(f())
    except: pass
  else: s,t=t,(s+t)%M
print(t)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
MOD = 10 ** 9 + 7

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

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

    dp = [0] * (N+1)
    dp[1] = 0 if 1 in A else 1
    dp[2] = 0 if 2 in A else dp[1] + 1

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

    return dp[N] % MOD

print(solve())

Submission status: Runtime Error

Solution code:
mod = 10 ** 9 + 7
N,M = map(int,input().split())
X = [1,1]
for i in range(N):
    X.append((X[i]+X[i+1]) % mod)
#print(X)
a = int(input())
ans = X[a - 1]
#print(ans)
tmp = a
check = 0
for _ in range(M-1):
    a = int(input())
    if a - tmp == 1:
        check = 1
    y = a - tmp - 2
    ans *= X[y]
    ans %= mod 
    tmp = a
    #print(ans)
y = N - tmp - 1
ans *= X[y]
ans %= mod 
if check == 1:
    print(0)
else:
    print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque
from collections import Counter
from itertools import product, permutations,combinations
from operator import itemgetter
import math
import sys
input = sys.stdin.readline
#文字列のときはうまく行かないのでコメントアウトすること
sys.setrecursionlimit(2147483647)

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

if __name__ == '__main__':
  main()

Submission status: Runtime Error

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

for x in a:
    dp[x] = 0

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


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

Submission status: Runtime Error

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

dp = [-1 for _ in range(n + 1)]

def checker(s, g):
    if s > g:
        return 0
    elif s == g:
        return 1
    else:
        if dp[g - s] != -1:
            return dp[g - s]
        else:
            ret = checker(s + 1, g) + checker(s + 2, g)
            dp[g - s] = ret
            return ret

if m == 0:
    c = checker(0, n)
else:
    s = 0
    g = a[0] - 1
    if g - s > 0:
        c = checker(s, g)
    else:
        c = 1
    if m == 1:
        s = a[0] + 1
        g = n
    else:
        for i in range(1, m):
            if a[i - 1] + 1 == a[i]:
                c = 0
                break
            else:
                s = a[i - 1] + 1
                g = a[i] - 1
                if g - s > 0:
                    c *= checker(s, g)
                s = a[m - 1] + 1
                g = n
    if g - s > 0:
        c *= checker(s, g)

print(c % 1000000007)

Submission status: Runtime Error

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

dp = [-1 for _ in range(n)]

def checker(s, g):
    if s > g:
        return 0
    elif s == g:
        return 1
    else:
        if dp[g - s] != -1:
            return dp[g - s]
        else:
            ret = checker(s + 1, g) + checker(s + 2, g)
            dp[g - s] = ret
            return ret

if m == 0:
    c = checker(0, n)
else:
    s = 0
    g = a[0] - 1
    if g - s > 0:
        c = checker(s, g)
    else:
        c = 1
    if m == 1:
        s = a[0] + 1
        g = n
    else:
        for i in range(1, m):
            if a[i - 1] + 1 == a[i]:
                c = 0
                break
            else:
                s = a[i - 1] + 1
                g = a[i] - 1
                if g - s > 0:
                    c *= checker(s, g)
                s = a[m - 1] + 1
                g = n
    if g - s > 0:
        c *= checker(s, g)

print(c % 1000000007)

Submission status: Runtime Error

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

dp = [-1 for _ in range(n)]

def checker(s, g):
    if s > g:
        return 0
    elif s == g:
        return 1
    else:
        if dp[g - s] != -1:
            return dp[g - s]
        else:
            ret = checker(s + 1, g) + checker(s + 2, g)
            dp[g - s] = ret
            return ret

s = 0
g = a[0] - 1
if g - s > 0:
    c = checker(s, g)
else:
    c = 1
for i in range(1, m):
    if a[i - 1] + 1 == a[i]:
        c = 0
        break
    else:
        s = a[i - 1] + 1
        g = a[i] - 1
        if g - s > 0:
            c *= checker(s, g)
        s = a[m - 1] + 1
        g = n
if g - s > 0:
    c *= checker(s, g)

print(c % 1000000007)

Submission status: Runtime Error

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

def checker(s, g):
    if s > g:
        return 0
    elif s == g:
        return 1
    else:
        return checker(s + 1, g) + checker(s + 2, g)

s = 0
g = a[0] - 1
if g - s > 0:
    c = checker(s, g)
else:
    c = 1
for i in range(1, m):
    if a[i - 1] + 1 == a[i]:
        c = 0
        break
    else:
        s = a[i - 1] + 1
        g = a[i] - 1
        if g - s > 0:
            c *= checker(s, g)
        s = a[m - 1] + 1
        g = n
if g - s > 0:
    c *= checker(s, g)

print(c % 1000000007)

Submission status: Runtime Error

Solution code:
from scipy.special import comb

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

a = []

for i in range(M):
    a.append(int(input()))

    # 隣接してる場合は、0出力で終了
    if a[i] == a[i - 1] + 1:
        print(0)
        exit(0)

dp = [0] * (N + 1)

dp[0] = 1

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

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

print(dp[-1] % 1000000007)

Submission status: Runtime Error

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

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

Submission status: Runtime Error

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

dp = [0] * N

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

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

print(dp[-1] % 1000000007)

Submission status: Runtime Error

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

if bi < M and 1 == bs[bi]:
    pattern[0] = 0
    bi += 1
else:
    pattern[0] = 1

if bi < M and 2 == bs[bi]:
    pattern[1] = 0
    bi += 1
else:
    pattern[1] = 1 + pattern[0]

for i in range(2, N):
    if bi < M and (i + 1) == bs[bi]:
        pattern[i] = 0
        bi += 1
    else:
        pattern[i] = pattern[i -1] + pattern[i - 2]

print(pattern[-1] % 1000000007)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
broken_steps = [int(input()) for _ in range(M)]
pattern = [-1] * N
pattern[0] = 0 if 1 in broken_steps else 1
pattern[1] = 0 if 2 in broken_steps else 1 + pattern[0]

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

print(pattern[-1] % 1000000007)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
n,m=map(int,input()split())
dp=[1]*(n+1)
for i in range(m):
  dp[int(input())]=0
for i in range(2,n+1):
  if dp[i]>0:
    dp[i]=dp[i-1]+dp[i-2]
print(dp[n])

Submission status: Runtime Error

Solution code:
from collections import deque
import sys
import functools
sys.setrecursionlimit(10000000)
@functools.lru_cache(maxsize=None)
def stairs(n):
  if n==1:
    return 1
  if n==2:
    return 2
  return stairs(n-1)+stairs(n-2)
N,M=map(int,input().split())
A=deque()
for _ in range(M):
  A.append(int(input()))
pos=0
ans=0
while A:
  x=A.popleft()-1
  if len(A)!=0:
    if x+2==A[0]:
      print(0)
      exit()
  ans+=(stairs(x-pos)-1)
  ans%=1000000007
  pos=x+2
ans+=stairs(N-pos)
print(ans+1)

Submission status: Runtime Error

Solution code:
from collections import deque
import sys
import functools
sys.setrecursionlimit(10000000000)
@functools.lru_cache(maxsize=None)
def stairs(n):
  if n==1:
    return 1
  if n==2:
    return 2
  return stairs(n-1)+stairs(n-2)
N,M=map(int,input().split())
A=deque()
for _ in range(M):
  A.append(int(input()))
pos=0
ans=0
while A:
  x=A.popleft()-1
  if len(A)!=0:
    if x+2==A[0]:
      print(0)
      exit()
  ans+=(stairs(x-pos)-1)
  ans%=1000000007
  pos=x+2
ans+=stairs(N-pos)
print(ans+1)

Submission status: Runtime Error

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

dp = [1]

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

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

print(dp[-1] % mod)

Submission status: Runtime Error

Solution code:

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

a = [0]*N

if b[0] == 0:
    a[0] = 1
if b[1] == 0:
    a[1] = 1 + a[0]

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

Submission status: Runtime Error

Solution code:
from functools import lru_cache
dan,ana=map(int,input().split())
l={int(input()) for _ in range(ana)}
@lru_cache(maxsize=100000000000000)
def f(x):
  global l
  if x in l:return 0
  elif x==1:return 1
  elif x==2:return f(1)+1
  else:return (f(x-1)+f(x-2))%(10**9+7)

print(f(dan))

Submission status: Runtime Error

Solution code:
from functools import lru_cache
dan,ana=map(int,input().split())
l={int(input()) for _ in range(ana)}
@lru_cache(maxsize=10000000)
def f(x):
  global l
  if x in l:return 0
  elif x==1:return 1
  elif x==2:return f(1)+1
  else:return (f(x-1)+f(x-2))%(10**9+7)

print(f(dan))

Submission status: Runtime Error

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

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

dp[0] = 1
list_score.sort()
if list_score[0] == 1:
    dp[1] = 0
else:
    dp[1] = 1

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

print(dp[n])

Submission status: Runtime Error

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

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

dp[0] = 1
list_score.sort()
if list_score[0] == 1:
    dp[1] = 0
else:
    dp[1] = 1

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

print(dp[n])

Submission status: Runtime Error

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

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

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

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

print(dp[n])

Submission status: Runtime Error

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

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

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

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

print(dp[n])

Submission status: Runtime Error

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

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

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

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

print(dp[n]%mod)

Submission status: Runtime Error

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

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