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:
n, m = [int(i) for i in input().split()]
a = [-1] + [int(input()) for _ in range(m)] + [n+1]

fib_l = [-1] * n

def fib(step):
    if fib_l[step] != -1:
        return fib_l[step]
    if 0 <= step <= 1:
        return 1
    else:
        t = fib(step-1) + fib(step-2)
        fib_l[step] = t
        return t

ret = 1
for i in range(m+1):
    ret *= fib(a[i+1] - a[i] - 2)
print(ret % 1000000007)

Submission status: Runtime Error

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

if N == 1:  print(1)
elif N == 2:
    if 1 in a:  print(1)
    else:   print(2)
else:
    temp1, temp2 = 0,0
    if 1 not in a:  temp1 = 1
    if 2 not in a:  temp2 = 1 + temp1
    
    for i in range(2,N):
        temp = 0
        if i+1 not in a:    temp = temp1 + temp2
        temp1 = temp2
        temp2 = temp

print( int(temp % 1000000007) )

Submission status: Runtime Error

Solution code:


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

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

for i in range(N):
    c=l[i]%1000000007
    if i<=N-2:
        if i not in a:
            l[i+1]+=c
    elif i not in a:
        l[i+1]+=c
        l[i+2]+=c

print(l[N]%1000000007)

Submission status: Runtime Error

Solution code:
n,m = [int(i) for i in input().split()]
a = {int(input()) for i in range(m)}
dp = {}
def stairs(step):
  if step in a:
    return 0
  if step == 1:
    return 1
  if step == 2:
    return stairs(step-1) + 1
  if step in dp.keys():
    return dp[step]
  else:
    dp[step] = stairs(step-1) + stairs(step-2)
    return dp[step]
print(int(stairs(n)%1000000007))

Submission status: Runtime Error

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

b = [0]*N

if 1 not in a:
    b[0] = 1

if 2 not in a:
    if b[0] == 1:
        b[1] = 2
    else:
        b[1] = 1

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

print(b[N-1]%1000000007)

Submission status: Runtime Error

Solution code:
def up_stairs(N, a, now):
  
  if now == N:
    return 1
  if now > N:
    return 0
  if (now in a):
    return 0
  
  return up_stairs(N, a, now + 1) + up_stairs(N, a, now + 2)


N,M = (int(x) for x in input().split())

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

print(int(up_stairs(N, a, 0) / 1000000007))

Submission status: Runtime Error

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

b = [0]*N

if 1 not in a:
    b[0] = 1

if 2 not in a:
    if b[0] == 1:
        b[1] = 2
    else:
        b[1] = 1

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

Submission status: Runtime Error

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

mod = 1000000007

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

Submission status: Runtime Error

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

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

N, M = [int(x) for x in input().strip().split()]
A = [1] * N
for _ in range(M):
    A[int(input())] = 0
solve(N, M, A)

Submission status: Runtime Error

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

memo = {}
def dfs(height):
    if height in memo:
        return memo[height]
    if height == N:
        memo[height] = 1
        return 1
    elif height > N:
        return 0
    if height in a:
        memo[height] = 0
        return 0
    step1 = dfs(height + 1)
    step2 = dfs(height + 2)
    if step1 == 0 and step2 == 0:
        memo[height] = 0
        return 0
    else:
        memo[height] = step1 + step2
        return step1 + step2
        
print(dfs(0) % 1000000007)

Submission status: Runtime Error

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

inf = 1000000007
index = 0
n_way = [0 for i in range(N+2)]
n_way[0] = 1

for i in range(N):
    if a[index] == i:
        index += 1
        index = min(index,len(a)-1)
    else:
        n_way[i+1] += n_way[i]
        n_way[i+1] = n_way[i+1]%inf
        n_way[i+2] += n_way[i]
        n_way[i+2] = n_way[i+2]%inf

print(n_way[N])

Submission status: Runtime Error

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

dp[0] = 1
dp[1] = 1
dp[2] = 1

t = 0
if A[0] == 1:
    t += 1
    dp[1] = 0

for k in range(2,N+1):
    if t < len(A) and A[t] == k:
        dp[k] = 0
        t += 1
    else:
        dp[k] = dp[k-1] + dp[k-2]
        dp[k] %= MOD
print(dp[N])

Submission status: Runtime Error

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

dp=[0]*(n+1)
dp[0]=1
if a[0]!=1:
    dp[1]=1
else:
    dp[1]=0
    cnt+=1

for i in range(n-1):
    if a[cnt]==i+2:
        dp[i+2]=0
        if cnt!=(m-1):
            cnt+=1
    else:
        dp[i+2]=dp[i+1]+dp[i]

print(dp[n]%(1000000007))

Submission status: Runtime Error

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

ans = [0]*(N+1)
ans[0] = 1
if s == 1:
    ans[1] = 0
else:
    ans[1] = 1


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

Submission status: Runtime Error

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

broken = [0]*M
ans = [0]*(N+1)

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

ans[0] = 1
if(broken[0] == 1):
    ans[1] = 0
else:
    ans[1] = 1

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

print(ans[N]%1000000007)

Submission status: Runtime Error

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

if 1 in a and 2 in a:
  print(0)
elif 1 in a:
  k = [0, 1]
elif 2 in a:
  k = [1, 0]
else:
  k = [1, 2]

for i in range(3, N+1): #インデックスは-1
  if i in a:
    k.append(0)
  else:
    k.append(k[i-3]+k[i-2])
    
print(k[-1]%1000000007)

Submission status: Runtime Error

Solution code:
def patterns(start_n, broken_n):
    # start;自分がいる場所，こわれていない．一つ前はこわれている
    diff = broken_n - start_n
    if diff == 1 or diff == 2:
        return 1
    return patterns(start_n, broken_n - 1) + patterns(start_n, broken_n - 2)


inp = input()
split_input = inp.split()
n = int(split_input[0])
m = int(split_input[1])
start = 0
patterns_count = 1
# broken_number = -1
for i in range(m+1):
    if i == m:
        broken = n + 1
    else:
        inp = input()
        broken = int(inp)
    if broken == start:
        # 二つ連続でと通れない
        print(0)
        exit()
    # print(start, broken)
    p = patterns(start, broken)
    patterns_count = patterns_count * p % 1000000007
    start = broken + 1

print(patterns_count)

Submission status: Runtime Error

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

N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
dp = [0] * (N+1)
mod = 10**9 + 7

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

dp[0] = 1
if dp[1] != -1 and dp[2] != -1:
    dp[1] = 1
    dp[2] = dp[0] + dp[1]
elif dp[1] == -1 and dp[2] != -1:
    dp[2] = 1
elif dp[1] != -1 and dp[2] == -1:
    dp[1] = 1
else:
    print(0)
    exit()

for i in range(3, N+1):
    if dp[i] == -1:
        continue
    elif dp[i-1] == -1 and dp[i-2] != -1:
        dp[i] = dp[i-2]
    elif dp[i-1] != -1 and dp[i-2] == -1:
        dp[i] = dp[i-1]
    elif dp[i-1] != -1 and dp[i-2] != -1:
        dp[i] = dp[i-1] + dp[i-2]
    else:
        print(0)
        exit()

print(dp[N] % mod)

Submission status: Runtime Error

Solution code:
#
import sys
import math
import numpy as np
import itertools

# いくつか入力
n,m = (int(i) for i in input().split())  

# n行の数をリストに
a = [int(input()) for i in range(m)] 
a.append(9999999) # sentinel
dame=0

b=[1]
if a[dame]==1:
    dame += 1
    b.append(0)
MOD = 1000000007

for i in range(2,n+1):
    if i==a[dame]:
        dame += 1
        b.append(0)
    else:
        c=(b[i-1]+b[i-2])%MOD
        b.append(c)

#print(a,b)
print(b[n])

Submission status: Runtime Error

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

class comb():
  F = [1, 1]
  Fi = [1, 1]
  I = [0, 1]
  def __init__(self, num, mod):
    self.MOD = mod
    for i in range(2, num + 1):
      self.F.append((self.F[-1] * i) % mod)
      self.I.append(mod - self.I[mod % i] * (mod // i) % mod)
      self.Fi.append(self.Fi[-1] * self.I[i] % mod)
  def com(self, n, k):
    if n < k: return 0
    if n < 0 or k < 0: return 0
    return self.F[n] * (self.Fi[k] * self.Fi[n - k] % self.MOD) % self.MOD


MOD = 10 ** 9 + 7

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

com = comb(N, MOD)
ans = 1
x = 0
a = a + [N + 1]

for i in a:
  t = i - 1 - x
  at = 0
  for j in range(t // 2 + 1):
    k = t - j
    at = at + com.com(k, j) % MOD
  ans = ans * at % MODs
  x = i + 1
  

print(ans)

Submission status: Runtime Error

Solution code:
def func(n):
  if n==1:return 1
  if n==0: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
  return f1+f2

n,m=map(int,input().split())
a=[int(input()) for i in range(m)]
dp=[-1]*(n+1)
print(func(n)%1000000007)

Submission status: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
N, M = map(int,input().split())
a_lists = []
for m in range (M):
    temp = int(input())
    a_lists.append(temp-1)
    
datas = [0]*N
if 0 in a_lists:
    datas[0] = 0
else:
    datas[0]=1

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

print(datas[-1]%1000000007)

Submission status: Runtime Error

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

r = 1
a = 0
for i in M:
	b = int(input())
	r = r * int((b-a)*(b-a)/4)
	a = b
	r = r%1000000007

r = r*int((N-a)*(N-a)/4)
r = r%1000000007

print(r)

Submission status: Runtime Error

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

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

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

Submission status: Runtime Error

Solution code:
import collections as c
from math import gcd
ip = lambda : map(int, input().split())
# ##############
mod = 1e9+7
N,M = ip()
a = set()
for i in range(M):
    a.add(int(input()))
dp = [0]*(N+1)
dp[0] = 1
if 1 in a:
    pass
else:
    dp[1] = dp[0]
if N>1:
    for i in range(2,N+1):
        if i in a:
            continue
        dp[i] += dp[i-2] + dp[i-1]
        dp[i] = int(dp[i] % mod)
print(dp[N])

Submission status: Runtime Error

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

Submission status: Runtime Error

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

broken = []
ans = [0]*(N+1)

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

ans[0] = 1
if(broken[0] == 1):
    ans[1] = 0
else:
    ans[1] = 1

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

print(ans[N]%1000000007)

Submission status: Runtime Error

Solution code:
N,M = (int(x) for x in input().split())
a_arr = [-1]
for _ in range(M):
    a_arr.append(int(input()))
a_arr.append(N+1)

n_dp = [0]*(N+1)
n_dp[0] = 1
n_dp[1] = 0
n_dp[2] = 1
for i in range(3,N+1):
    n_dp[i] = (n_dp[i-2]+n_dp[i-1]) % 1000000007

ans = 1
for i in range(1,len(a_arr)):
    a_diff = a_arr[i]-a_arr[i-1]
    ans *= n_dp[a_diff]
    ans = ans % 1000000007

print(ans)

Submission status: Runtime Error

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

import sys
sys.dont_write_bytecode = True
stdin = sys.stdin
input = stdin.readline
#sys.setrecursionlimit(100000)

#import numpy as np
#import scipy as sp

# Python 3 modules: https://docs.python.org/3/library/

import math, itertools, operator
from math import *
from math import factorial as fact
from operator import itemgetter, attrgetter
from itertools import permutations, combinations
from functools import reduce, lru_cache
# Use scipy for stats: https://docs.scipy.org/doc/scipy/reference/stats.html
# Before Python 3.5.  Import from math after it.
from fractions import gcd
from fractions import Fraction as Frac

inf = float('inf')

def lcm(a, b):
    return a * b // gcd(a,b)

def perm(a, b):
    import scipy.special
    return scipy.special.perm(a, b, exact = True)

def comb(a, b):
    import scipy.special
    return scipy.special.comb(a, b, exact = True)

def dfact(n):
    import scipy.special
    return scipy.special.factorial2(n, exact = True)

def prod(l):
    return reduce(operator.mul, l)

def input_ints(func = input, sep = None, conv = int):
    return list(map(conv, func().split(sep = sep)))

################################################################################

N, M = list(map(int, input().split()))
A = [None for i in range(M)]
for i in range(M):
    A[i] = int(input())
#A = list(map(int, stdin.read().split()))

BROKEN = [False for i in range(N)]
for a in A:
    BROKEN[a] = True

@lru_cache(maxsize = None)
def dp(cur):
    if cur > N:
        return 0
    if cur == N:
        return 1
    if BROKEN[cur]:
        return 0
    return dp(cur + 1) + dp(cur + 2)

print(dp(0) % 1000000007)

Submission status: Runtime Error

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


if __name__ == "__main__":
    [n, m] = li()
    broken = [int(input()) for _ in range(m)]

    pattern = [0] * (n + 1)
    pattern[0] = 1
    pattern[1] = 1 if broken[0] != 1 else 0
    for i in range(2, n + 1):
        if broken.count(i) == 0:
            pattern[i] = (pattern[i - 2] + pattern[i - 1]) % (10 ** 9 + 7)
        else:
            pattern[i] = 0
    print(pattern[-1])

Submission status: Runtime Error

Solution code:
import bisect
mod = 1000000007

n, m = list(map(int, input().split()))
nums = [int(input()) for _ in range(m)]
 
dp = [1] + [0 for _ in range(n)]

if nums[0] != 1:
	dp[1] = 1
	idx = bisect.bisect_right(nums, 1)
	nums = nums[idx:]

for i in range(2, n + 1):
	if i in nums:
		dp[i] = 0
		idx = bisect.bisect_right(nums, 1)
		nums = nums[idx:]
	else:
		dp[i] = (dp[i - 1] + dp[i - 2])  % mod

print(dp[-1])

Submission status: Runtime Error

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

MOD = pow(10, 9) + 7

memo = [0 for _ in range(n)]
memo[0] = 0 if 1 in alist else 1
is_reach = True
if 1 in alist and 2 in alist:
  is_reach = False
  memo[0] = 0
elif 1 in alist:
  memo[1] = 1
else:
  memo[1] = 2

for i in range(2, n):
  if i+1 in alist:
    memo[i] = 0
  elif i in alist and i-1 in alist:
    memo[i] = 0
    is_reach = False
    break
  elif i in alist:
    memo[i] = memo[i-2]
  elif i-1 in alist:
    memo[i] = memo[i-1]
  else:
    memo[i] = (memo[i-1] + memo[i-2]) % MOD

if is_reach:
  print(memo[-1])
else:
  print(0)

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop, heapify, heapreplace
from collections import defaultdict


class Solution:
    def main(self):
        N, M =map(int, input().split())
        self.A = set()
        for _ in range(M):
            self.A.add(int(input()))
        self.memo = {0: 1}
        res = self.rec(N)
        print(res%1000000007)

    def rec(self, n):
        if n in self.A or n < 0:
            return 0
        elif n in self.memo:
            return self.memo[n]
        else:
            val = self.rec(n-1) + self.rec(n-2)
            self.memo[n] = val
            return val


if __name__ == '__main__':
    Solution().main()

Submission status: Runtime Error

Solution code:

from collections import defaultdict

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

A = [0] * (N + 1)
for _ in range(M):
    A[int(input())] = 1

dp = defaultdict(lambda: -1)
def dfs(n):
    if n > N:
        return 0
    if A[n] == 1:
        return 0
    if n == N:
        return 1
    if dp[n] != -1:
        return dp[n]
        
    count = 0
    count += dfs(n + 1)
    count += dfs(n + 2)
    
    dp[n] = count
    
    return count
    
print(dfs(0) % (1000000007))

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
mod = 10**9+7
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
k = [0]*(N+1)
k[0]=1
cnt = 0
if a[0]!=1:
    k[1]=1
else:
    cnt+=1
for i in range(2, N+1):
    if cnt<M and i ==a[cnt]:
        cnt+=1
        continue
    else:
        k[i]=k[i-1]+k[i-2]
print(k[N]%mod)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

mod = int(1e9+7)

if N == 1:
  print(1)
  exit()

solver = [1]

## 1段目の処理
if A[0] == 1:
  solver.append(0)
else:
  solver.append(1)

for i in range(2,N+1): ## i段目の処理
  if i in A:
    solver.append(0)
  else:
    var = (solver[i-2] + solver[i-1]) % mod
    solver.append(var)
    
print(solver[-1])

Submission status: Runtime Error

Solution code:
from collections import deque

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

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

before1 = 1
before2 = 0
ai = a.popleft()
for i in range(N):
    if i == (ai-1):
        before2 = before1
        before1 = 0
        if len(a)>0:
            ai = a.popleft()
    else:
        current = divmod(before1 + before2, 10**9+7)[1]
        before2 = before1
        before1 = current
    
print(before1)

Submission status: Runtime Error

Solution code:
n, m = list(map(int, input().split()))
a = []
for i in range(m):
	a.append(int(input()))
a.sort()
f0 = 1
if a[0] == 1:
	f1 = 0
else:
	f1 = 1
k = 0
for i in range(2, n + 1):
	while k < len(a) and a[k] < i:
		k += 1
	if k == len(a) or a[k] != i:
		f = (f0 + f1) % 1000000007
	else:
		f = 0
	f0 = f1
	f1 = f
	if f0 == f1 == 0:
		break
print(f1)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
As = [int(input()) for i in range(M)]
As = set(As)
MOD = 1000000007

cache = dict()
def n_steps(n):
    if n not in cache:
        if n in As:
            value = 0
        
        elif n in {0, 1}:
            value = 1

        else:
            value = n_steps(n - 1) + n_steps(n - 2)
            value %= MOD

        cache[n] = value
    return cache[n]


print(n_steps(N))

Submission status: Runtime Error

Solution code:
N,M = (int(i) for i in input().split())
a = [int(input()) for i in range(M)]
hoge = [0] * N
hoge[0] = 1
for i in range(N):
    if i = 0:
        hoge[i] = 0
    elif (i-1) in a and (i-2) in a:
        hoge[i] = 0
    elif (i-1) in a:
        hoge[i] = hoge[i - 2]
    elif (i-2) in a:
        hoge[i] = hoge[i - 1]
    else hoge[i] = hoge[i-1] + hoge[i-2]
print(hoge[N])

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

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

Submission status: Runtime Error

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