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:
MAX_N = 10**5+1
DP = [None] * (MAX_N + 1)  # 計算結果を保存する配列
DP[0] = 0  # 定義より
DP[1] = 1  # 定義より

def fib(n):
    # フィボナッチ数を2からnまで順に求めていく
    for i in range(2, n + 1):
        DP[i] = DP[i-1] + DP[i-2]
    return DP[n]

MOD = 10**9 + 7

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

ans = fib(a[0])
for i in range(M-1):
    ans *= fib(a[i+1] - a[i] - 1)
    ans %= MOD
ans *= fib(N - a[M-1])
ans %= MOD

print(ans)

Submission status: Runtime Error

Solution code:
MAX_N = 10**5
DP = [None] * (MAX_N + 1)  # 計算結果を保存する配列
DP[0] = 0  # 定義より
DP[1] = 1  # 定義より

def fib(n):
    # フィボナッチ数を2からnまで順に求めていく
    for i in range(2, n + 1):
        DP[i] = DP[i-1] + DP[i-2]
    return DP[n]

MOD = 10**9 + 7

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

ans = fib(a[0])
for i in range(M-1):
    ans *= fib(a[i+1] - a[i] - 1)
    ans %= MOD
ans *= fib(N - a[M-1])
ans %= MOD

print(ans)

Submission status: Runtime Error

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

step = [0]*N

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

mod = int(1e9+7)

dp = [0]*N

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

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
from sys import exit
class Fib:
  def __init__(self):
    self.memo = {}
  def calc(self, n):
    if n == 1 or n == 2:
      self.memo[n] = 1
      return 1
    if n <= 0:
      self.memo[n] = 0
      return 0
    if n in self.memo.keys():
      return self.memo[n]
    self.memo[n] = self.calc(n - 1) + self.calc(n - 2)
    return self.memo[n]

N, M = map(int, input().split())
ans = 1
mod = 10 ** 9 + 7
pre = -1
for i in range(M):
  a = int(input())
  if a == 1:
    pre = a
    continue
  if a == pre + 1 and pre != 0:
    print(0)
    exit()
  ans *= Fib().calc(a - pre - 1) % mod
  pre = a
ans *= Fib().calc(N - pre) % mod
print(ans % mod)

Submission status: Runtime Error

Solution code:
from sys import exit
class Fib:
  def __init__(self):
    self.memo = {}
  def calc(self, n):
    if n == 1 or n == 2:
      self.memo[n] = 1
      return 1
    if n <= 0:
      self.memo[n] = 0
      return 0
    if n in self.memo.keys():
      return self.memo[n]
    self.memo[n] = self.calc(n - 1) + self.calc(n - 2)
    return self.memo[n]

N, M = map(int, input().split())
ans = 1
mod = 10 ** 9 + 7
pre = 0
for i in range(M):
  a = int(input())
  if a == 1:
    pre = a
    continue
  if a == pre + 1 and pre != 0:
    print(0)
    exit()
  ans *= Fib().calc(a - pre - 1) % mod
  pre = a
ans *= Fib().calc(N - pre) % mod
print(ans % mod)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
memo = [0]*(N+1)
memo[1] = 1
memo[2] = 2
mod = 10**9+7

for _ in range(M):
    ai = int(input())
    memo[ai] = None

if memo[1] == None:
    memo[2] = 1

for i in range(3, N+1):
    tmp = 0
    if memo[i] == None:
        continue
    if memo[i-1] != None:
        tmp += memo[i-1]
    if memo[i-2] != None:
        tmp += memo[i-2]
    memo[i] = tmp

print(memo[N]%mod)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)
def num_steps(steps, cache={}):
    if steps in out or steps < 0 :
        return 0
    elif steps == 0:
        return 1

    if steps in cache:
        return cache[steps]
    else:
        one = num_steps(steps-1, cache)
        two = num_steps(steps-2, cache)
        ans = one + two
        cache[steps] = ans

        return ans%mod

n, m = map(int, input().split())
out = set(int(input()) for _ in range(m))
mod = 1000000007

print(num_steps(n))

Submission status: Runtime Error

Solution code:
def num_steps(steps, cache={}):
    if steps in out or steps < 0 :
        return 0
    elif steps == 0:
        return 1

    if steps in cache:
        return cache[steps]
    else:
        one = num_steps(steps-1, cache)
        two = num_steps(steps-2, cache)
        ans = one + two
        cache[steps] = ans

        return ans%mod

n, m = map(int, input().split())
out = set(int(input()) for _ in range(m))
mod = 1000000007

print(num_steps(n))

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
#a = [int(input()) for _ in range(m)]
a = [0] * (10 ** 5)
for i in range(m):
    a[int(input())] = 1


MOD = 10 ** 9 + 7
# ---------------------------
dp = [0] * (n + 1)
dp[0] = 1
# if (1 in a):
if (a[1] == 1):
    dp[1] = 0
else:
    dp[1] = 1
# dp approach

for i in range(2, n + 1):
    # if (i in a):
    if (a[i] == 1):
        # (x in list)で探索すると、時間がかかるっぽい
        #dp[i] = 0
        continue
    elif (dp[i - 1] == 0 and dp[i - 2] == 0):
        print(0)
        exit()
    else:
        dp[i] = (dp[i - 1] + dp[i - 2]) % MOD


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

Submission status: Runtime Error

Solution code:
import numpy as np
import math

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

aList = [int(input()) for _ in range(M)]

aList.insert(0,-1)
aList.append(N+1)

#print(aList)

aArray = np.array(aList)

katamari = []

for i in range(M+1):
    katamari.append(aArray[i+1] - aArray[i] - 1)

#print(katamari)

ans = 1
for i in range(M):
    ans *=  (1 / math.sqrt(5)) * (((1 + math.sqrt(5)) / 2) ** katamari[i] - ((1 - math.sqrt(5)) / 2) ** katamari[i])

print(int(ans) % 1000000007)

Submission status: Runtime Error

Solution code:
n,m=[int(x) for x in input().rstrip().split()]
a=[int(input()) for i in range(m)]
oks=[True for i in range(n+1)]

mod=10**9+7
dp=[0 for i in range(n+1)]
for i in a:
  oks[i]=False

if oks[1]==True:
  dp[1]=1
if oks[2]==True:
  dp[2]=dp[1]+1

for i in range(3,n+1):
  if oks[i]==True:
    dp[i]=dp[i-2]+dp[i-1]
print(dp[n]%mod)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
MOD=10**10+7
n,m = list(map(int, input().split()))
a = set([int(input()) for _ in range(m)])

dp = [0] * (n+1)

if 1 in a and 2 in a:
    print(0)
    exit()
elif 1 in a:
    dp[2]=1
    dp[3]=2
    start=4
elif 2 in a:
    dp[1]=1
    dp[3]=2
    start=4
else:
    dp[1]=1
    dp[2]=2
    start=3
    
for step in range(start, n+1):
    if dp[step-1]==0 and dp[step-2]==0:
        break
    if step not in a:
        dp[step] = (dp[step-1] + dp[step-2])%MOD
print(dp[-1])

Submission status: Runtime Error

Solution code:
import sys
MOD = 10**9 + 7
n, m = map(int, input().split())
a = [int(x) for x in sys.stdin.readlines()]
ans = [0 for i in range(n)]
if 1 not in a:
    ans[0] = 1
if 2 not in a:
    ans[1] = ans[0] + 1

for i in range(2, n):
    if i+1 not in a:
        ans[i] = (ans[i-1] + ans[i-2])%MOD
    else:
        ans[i] = 0

print(ans[-1])

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, 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, insort, insort_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()
a = [INT() for _ in range(M)]

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

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

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

print(dp[N])

Submission status: Runtime Error

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

Submission status: Runtime Error

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

n, m = list(map(int, input().split()))

if m != 0:
    a = [int(input()) for _ in range(m)]

mod = 1000000007

if n == 1:
    print(1)
    exit()
elif n == 2:
    if m != 0 and a[0] == 1:
        print(1)
    else:
        print(2)
    exit()

if a[0] == 1:
    a_2, a_1 = 1, 0
    index = 1
else:
    a_2, a_1 = 1, 1
    index = 0

for i in range(2, n+1):
    if index < len(a):
        if i == a[index]:
            a_now = 0
            index += 1
            a_1, a_2 = a_now, a_1
            continue

    a_now = (a_1+a_2) % mod
    # print(a_now)
    a_1, a_2 = a_now, a_1
    # print(a_now)
print(a_now % mod)

# 0, 1, 2, 3, 4, 5, 6

# 1, 1, 2, 0, 2, 2, 4

Submission status: Runtime Error

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

n, m = list(map(int, input().split()))

if m != 0:
    a = [int(input()) for _ in range(m)]

mod = 1000000007

if n == 1:
    print(1)
    exit()
elif n == 2:
    if a[0] == 1:
        print(1)
    else:
        print(2)
    exit()

if a[0] == 1:
    a_2, a_1 = 1, 0
    index = 1
else:
    a_2, a_1 = 1, 1
    index = 0

for i in range(2, n+1):
    if index < len(a):
        if i == a[index]:
            a_now = 0
            index += 1
            a_1, a_2 = a_now, a_1
            continue

    a_now = (a_1+a_2) % mod
    # print(a_now)
    a_1, a_2 = a_now, a_1
    # print(a_now)
print(a_now % mod)

# 0, 1, 2, 3, 4, 5, 6

# 1, 1, 2, 0, 2, 2, 4

Submission status: Runtime Error

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

n, m = list(map(int, input().split()))

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

mod = 1000000007

if n == 1:
    print(1)
    exit()
elif n == 2:
    if a[0] == 1:
        print(1)
    else:
        print(2)
    exit()

if a[0] == 1:
    a_2, a_1 = 1, 0
    index = 1
else:
    a_2, a_1 = 1, 1
    index = 0

for i in range(2, n+1):
    if index < len(a):
        if i == a[index]:
            a_now = 0
            index += 1
            a_1, a_2 = a_now, a_1
            continue

    a_now = (a_1+a_2) % mod
    # print(a_now)
    a_1, a_2 = a_now, a_1
    # print(a_now)
print(a_now % mod)

# 0, 1, 2, 3, 4, 5, 6

# 1, 1, 2, 0, 2, 2, 4

Submission status: Runtime Error

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

n, m = list(map(int, input().split()))

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

mod = 1000000007


if a[0] == 1:
    a_2, a_1 = 1, 0
    index = 1
else:
    a_2, a_1 = 1, 1
    index = 0

for i in range(2, n+1):
    if index < len(a):
        if i == a[index]:
            a_now = 0
            index += 1
            a_1, a_2 = a_now, a_1
            continue

    a_now = (a_1+a_2) % mod
    # print(a_now)
    a_1, a_2 = a_now, a_1
    # print(a_now)
print(a_now % mod)

# 0, 1, 2, 3, 4, 5, 6

# 1, 1, 2, 0, 2, 2, 4

Submission status: Runtime Error

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

n, m = list(map(int, input().split()))

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

mod = 1000000007

a_2, a_1 = 1, 0

if a[0] == 1:
    a_1 = 0
    index = 1
else:
    a_1 = 1
    index = 0

for i in range(2, n+1):
    if index < len(a):
        if i == a[index]:
            a_now = 0
            index += 1
            a_1, a_2 = a_now, a_1
            continue

    a_now = (a_1+a_2)
    # print(a_now)
    a_1, a_2 = a_now, a_1
    # print(a_now)
print(a_now % mod)

# 0, 1, 2, 3, 4, 5, 6

# 1, 1, 2, 0, 2, 2, 4

Submission status: Runtime Error

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

for i in range(m-1):
    r.append((a[i+1]-a[i])-2)
    if a[i+1] - a[i] == 1:
        print(0)
        exit()
else:
    r.append(n-a[-1]-1)

    for i in range(n):
        fibo.append((fibo[-1]+fibo[-2])%1000000007)

    ans = 1

    for i in range(len(r)):
        ans = (fibo[r[i]] * ans)%1000000007

    print(ans)

Submission status: Runtime Error

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

for i in range(m-1):
    r.append((a[i+1]-a[i])-2)
    if a[i+1] - a[i] == 1:
        print(0)
        exit()
else:
    r.append(n-a[-1]-1)

    for i in range(max(r)+2):
        fibo.append((fibo[-1]+fibo[-2])%1000000007)

    ans = 1

    for i in range(n):
        ans = (fibo[r[i]] * ans)%1000000007

    print(ans)

Submission status: Runtime Error

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

for i in range(m-1):
    r.append((a[i+1]-a[i])-2)
    if a[i+1] - a[i] == 1:
        print(0)
        exit()
else:
    r.append(n-a[-1]-1)

    for i in range(max(r)+2):
        fibo.append((fibo[-1]+fibo[-2])%1000000007)

    ans = 1

    for i in range(len(r)):
        ans = (fibo[r[i]] * ans)%1000000007

    print(ans)

Submission status: Runtime Error

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

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

r.append(n-a[-1]-1)

for i in range(max(r)+2):
    fibo.append((fibo[-1]+fibo[-2])%1000000007)

ans = 1

for i in range(len(r)):
    ans = (fibo[r[i]] * ans)%1000000007

print(ans)

Submission status: Runtime Error

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

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

r.append(n-a[-1]-1)

for i in range(max(r)):
    fibo.append((fibo[-1]+fibo[-2])%1000000007)

ans = 1

for i in range(len(r)):
    ans = (fibo[r[i]] * ans)%1000000007

print(ans)

Submission status: Runtime Error

Solution code:
def main():
    N, M = map(int, input().split())
    a = [0] * (1 + 10 ** 5)
    for _ in range(M):
        a[int(input())] = 1
    dp = [0] * (N + 1)
    dp[0] = 1
    if not a[1]:
        dp[1] = 1

    for i in range(2, N + 1):
        if not a[i]:
            dp[i] += dp[i-1] + d[i-2]
            dp[i] %= 1000000007

    print(dp[N])

main()

Submission status: Runtime Error

Solution code:
def main():
    N, M = map(int, input().split())
    a = [0] * (1 + 10 ** 5)
    for _ in range(M):
        a[int(input())] = 1
    dp = [0] * (N + 1)
    dp[0] = 1
    if not a[1]:
        dp[1] = 1

    for i in range(2, N + 1):
        if not a[i]:
            dp[i] = 0
        else:
            dp[i] += dp[i-1] + d[i-2]
            dp[i] %= 1000000007

    print(dp[N])

main()

Submission status: Runtime Error

Solution code:
def main():
    N, M = map(int, input().split())
    a = {int(input()): 1 for _ in range(M)}
    dp = [0] * (N + 1)
    dp[0] = 1
    if 1 not in a:
        dp[1] = 1

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

    print(dp[N])

main()

Submission status: Runtime Error

Solution code:
def main():
    N, M = map(int, input().split())
    a = {int(input()): 1 for _ in range(M)}
    dp = [0] * (N + 1)
    dp[0] = 1
    if 1 not in a:
        dp[1] = 1

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

    print(dp[N])

main()

Submission status: Runtime Error

Solution code:
def main():
    N, M = map(int, input().split())
    a = {int(input()): 1 for _ in range(M)}
    dp = [0] * (N + 1)
    dp[0] = 1
    if 1 not in a:
        dp[1] = 1

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

    print(dp[N])

main()

Submission status: Runtime Error

Solution code:
mod=10**9+7

N,M=map(int,input().split())
a=[int(input()) for _ in range(M)]
dp=[1,1]
m=0
if a[0]==1:
    dp[1]=0
    m+=1
for i in range(2,N+1):
    if m<M and i==a[m]:
        dp.append(0)
        m+=1
    else:
        dp.append((dp[-1]+dp[-2])%mod)
print(dp[-1])

Submission status: Runtime Error

Solution code:
from collections import deque

mod=10**9+7

N,M=map(int,input().split())
dp=[1,1]
a=deque()
for i in range(M):
    a.append(int(input()))
if a[0]==1:
    dp[1]=0
    a.popleft()
for i in range(2,N+1):
    if len(a)>0 and i==a[0]:
        dp.append(0)
        a.popleft()
    else:
        dp.append((dp[-1]+dp[-2])%mod)
print(dp[-1])

Submission status: Runtime Error

Solution code:
def resolve():
    # 整数 1 つ
    n, m = int(input())
    # 整数複数個
    # a, b = map(int, input().split())
    # 整数 N 個 (改行区切り)
    # N = [int(input()) for i in range(N)]
    # 整数 N 個 (スペース区切り)
    A = list(map(int, input().split()))
    # 整数 (縦 H 横 W の行列)
    # A = [list(map(int, input().split())) for i in range(H)]

    Route = [0] * (n+1)
    Route[0] = 1
    for i in range(n):
        if i+1 not in A:
            Route[i+1] += Route[i]
            Route[i+1] %= 10**9 + 7
        if i+2 not in A and i+2 <= n:
            Route[i+2] += Route[i]
            Route[i+2] %= 10**9 + 7

    print(Route[n+1])


resolve()

Submission status: Runtime Error

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

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

dp = [0] * (n + 1)

for i in range(1, 3):
    if (i not in a):
        dp[i] = dp[i-1] + 1
    else:
        pass

flag = True

for i in range(3, n + 1):
    if (i not in a):
        if (dp[i - 1] == 0 and dp[i - 2] == 0):
            flag = False
            break
        else:
            dp[i] = dp[i - 1] + dp[i - 2]

    else:
        pass


if (flag is True):
    ans = dp[n] % MOD
else:
    ans = 0


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

Submission status: Runtime Error

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

mod = 1000000007

dp = [0] * (N + 1)

if len(dp) <= 2:
  return 1

dp[-1] = 1
dp[-2] = 1 if N - 1 not in A else 0

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

print(dp[0] % mod)

Submission status: Runtime Error

Solution code:
large_p = 10**9 + 7
a = []
kazu_memo = {}
def f(target_step):
    global kazu_memo
    #print(target_step)
    if target_step in a:
        return 0
    elif target_step < 0:
        return 0
    elif target_step == 0:
        return 1
    else:
        if kazu_memo[target_step] > 0:
            return kazu_memo[target_step]
        else:
            kazu_tmp = 0
            kazu_tmp += f(target_step - 1)
            kazu_tmp += f(target_step - 2)
            kazu_memo[target_step] = kazu_tmp % large_p
            return kazu_tmp % large_p

def main():
    global a, kazu_memo
    n, m = map(int, input().split())
    a = [int(input()) for _ in range(m)]

    kazu_memo = {e: -1 for e in range(1, n + 1)}
    r = f(n)
    print(r % large_p)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
large_p = 10**9 + 7
a = []
kazu_memo = {}
def f(target_step):
    global kazu_memo
    #print(target_step)
    if target_step in a:
        return 0
    elif target_step < 0:
        return 0
    elif target_step == 0:
        return 1
    else:
        if kazu_memo[target_step] > 0:
            return kazu_memo[target_step]
        else:
            kazu_tmp = 0
            kazu_tmp += f(target_step - 1)
            kazu_tmp += f(target_step - 2)
            kazu_memo[target_step] = kazu_tmp
            return kazu_tmp

def main():
    global a, kazu_memo
    n, m = map(int, input().split())
    a = [int(input()) for _ in range(m)]

    kazu_memo = {e: -1 for e in range(1, n + 1)}
    r = f(n)
    print(r % large_p)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

dp = [0] * N

ans = None

if N == 1:
  ans = 1

if N == 2:
  ans = 2 if 1 not in A else 1

if ans:
  print(ans)
  
dp[-1] = 1 if N-1 not in A else 0
dp[-2] = dp[-1] + 1 if N-2 not in A else dp[-1]

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

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

mod = 10**9 + 7
for i in range(m):
    dp[int(input())] = -1 # 壊れているので、-1としておこう?

dp[0] = 0 # 0段目にいるとしよう
# 1段目が行けなかったら...?
dp[1] = 1 if dp[1] != -1 else -1 # 1段目にいく方法は1通り?
dp[2] = 2 if dp[1] != -1 else (1 if dp[2] != -1 else -1) # 2段目に行く方法は2通り?
for i in range(3,n+1):
    if dp[i] != -1 and dp[i-1] != -1:
        dp[i] += dp[i-1]
        dp[i] %= mod
    if i > 1:
        if dp[i] != -1 and dp[i-2] != -1:
            dp[i] += dp[i-2]
            dp[i] %= mod
print(dp[n]%mod)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
a_n = [int(input()) for i in range(M)]
def Fib(n):    
    if n == 1:
        return 0
    elif n == 2:
        return 1
    else:
        return Fib(n-1)+Fib(n-2)
now = 0
before = -9999
answer = 1

for a in a_n:
    if a - before == 1:
        answer = 0
        break    
    answer *= Fib( a - 1 - now + 2 )
    answer %= 1000000007
    now = a + 1
    before = a

if answer > 0:
    answer *= Fib( N - now + 2)
    answer %= 1000000007

print(answer)

Submission status: Runtime Error

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

def Fib(n):    
    if n == 1:
        return 0
    elif n == 2:
        return 1
    else:
        return Fib(n-1)+Fib(n-2)
      
now = 0
before = -9999
answer = 1

for a in a_n:
    if a - before == 1:
        answer = 0
        break    
    answer *= Fib( a - 1 - now + 2 )
    now = a + 1
    before = a

if answer > 0:
    answer *= Fib( N - now + 2)

print(answer % 1000000007)

Submission status: Runtime Error

Solution code:
def Fib(n, memo={}):
    if n < 2:
        return 1
    elif n in memo:
        return memo[n]
    else:
        memo[n] = Fib(n - 1, memo) + Fib(n - 2, memo)
        return memo[n]


def resolve():
    N, M = [int(i) for i in input().split()]
    aa = []
    for _ in range(M):
        aa.append(int(input()))
    # fib_l = list(Fib(i) for i in range(N + 1))

    ans = 1
    now = 0
    for a in aa:
        if now == a:
            ans = 0
            break
        tmp = a - now - 1
        # ans = ans * fib_l[tmp]
        ans = ans * Fib(tmp)
        now = a + 1
    else:
        # ans = ans * fib_l[N - now]
        ans = ans * Fib(N - now)
    print(ans % (10**9 + 7))


resolve()

Submission status: Runtime Error

Solution code:
def Fib(n, memo={}):
    if n < 2:
        return 1
    elif n in memo:
        return memo[n]
    else:
        memo[n] = Fib(n - 1, memo) + Fib(n - 2, memo)
        return memo[n]


def resolve():
    N, M = [int(i) for i in input().split()]
    aa = []
    for _ in range(M):
        aa.append(int(input()))
    fib_l = list(Fib(i) for i in range(N))

    ans = 1
    now = 0
    for a in aa:
        if now == a:
            ans = 0
            break
        tmp = a - now - 1
        ans = ans * fib_l[tmp]
        now = a + 1
    else:
        ans = ans * fib_l[N - now]
    print(ans % (10**9 + 7))


resolve()

Submission status: Runtime Error

Solution code:
import sys
N,M=map(int,input().split())
dp=[1]*N
listA=[]
for i in range(M):
  a=int(input())
  listA+=[a]
  dp[a-1]=0
for i in range(1,M):
  if listA[i]==listA[i-1]:
    print(0)
    sys.exit()
setA=set(listA)    
if (1 not in setA) and (2 not in setA):
  dp[1]=2
for i in range(2,N):
  if i+1 not in setA:
    dp[i]=dp[i-1]+dp[i-2]
ans=dp[-1]%(10**9+7)
print(ans)

Submission status: Runtime Error

Solution code:
def main():
    MOD = 1_000_000_007
    N, M = map(int, input().split())
    a = [int(input()) for _ in range(M)]
    table = [1]*(N+1)
    for broken in a:
        table[broken] = 0
    table[1] = table[0] * table[1]
    if N > 1:
        for n in range(2, N+1):
            table[n] = ((table[n-2] + table[n-1]) * table[n]) % MOD
    print(table[-1])
main()

Submission status: Runtime Error

Solution code:
def main():
    MOD = 1_000_000_007
    N, M = map(int, input().split())
    a = [int(input()) for _ in range(M)]
    table = [1]*(N+1)
    for broken in a:
        table[broken] = 0
    table[1] = table[0] * table[1]
    for n in range(2, N+1):
        table[n] = ((table[n-2] + table[n-1]) * table[n]) % MOD
    print(table[-1])
main()

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
n,m,*a=map(int,open(0).read().split())
mod=10**9+7
p=[1]
a=iter(a)
b=a.__next__()
if 1==b:
    p.append(0)
    b=next(a,-1)
else:
    p.append(1)
for i in range(2,n+1):
    if i==b:
        p.append(0)
        b=next(a,-1)
        print(i)
    else:
        p.append((p[i-1]+p[i-2])%mod)
print(p[-1])

Submission status: Runtime Error

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

#dp=[0]*(n+1)
dp=[-1]*(n+1)
dp[0]=1
if 1 not in mList:
  dp[1]=1

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

def calc(i):
  if dp[i]!=-1: return dp[i]
  if i in mList:
    dp[i]=0
    return dp[i]
  dp[i]=calc(i-1)+calc(i-2)
  dp[i]%=1000000007
  return dp[i]

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

Submission status: Runtime Error

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

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

def calc(i):
  if dp[i]!=-1: return dp[i]
  if i in mList:
    dp[i]=0
    return dp[i]
  if i==1:
    dp[i]=calc(i-1)
    return dp[i]
  dp[i]=calc(i-1)+calc(i-2)
  return dp[i]

print(calc(n)%1000000007)