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 numpy as np
n,m = map(int,input().split())
a = [int(input()) for i in range(m)]

dp = [0] * (n+1)
for i in range(n+1):
     if i in a:
          dp[i] = 0
     elif i == 0 or i == 1:
          dp[i] = 1
     else:
          dp[i] = (dp[i-1] + dp[i-2])%1000000007
print(dp[n])

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import math
n, m = map(int,input().split())
a = []
for i in range(m):
    a.append(int(input()))

if m == 0:
    dp = [0 for _ in range(n)] #i + 1段目に登る方法の数
    dp[0] = 1
    if n >= 2:
        dp[1] = 2
    for i in range(2, n):
        dp[i] = dp[i - 1] + dp[i - 2]
    print(dp[n - 1])
    exit()

tmp = 0
dp = [0 for _ in range(n)]
if 1 == a[tmp]:
    dp[0] = 0
    tmp += 1
else:
    dp[0] = 1
if n >= 2 and 2 == a[tmp]:
    dp[1] = 0
    tmp += 1
elif n >= 2 and 2 != a[tmp]:
    dp[1] = dp[0] + 1

for i in range(2, n):
    if tmp < m and i + 1 == a[tmp]:
        dp[i] = 0
        tmp += 1
    else:
        dp[i] = (dp[i - 1] + dp[i - 2]) % (pow(10, 9) + 7)
#print(dp)
print(dp[n - 1] % (pow(10, 9) + 7))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import math
n, m = map(int,input().split())
a = []
for i in range(m):
    a.append(int(input()))

if m == 0:
    dp = [0 for _ in range(n)] #i + 1段目に登る方法の数
    dp[0] = 1
    dp[1] = 2
    for i in range(2, n):
        dp[i] = dp[i - 1] + dp[i - 2]
    print(dp[n - 1])
    exit()

tmp = 0
dp = [0 for _ in range(n)]
if 1 == a[tmp]:
    dp[0] = 0
    tmp += 1
else:
    dp[0] = 1
if n >= 2 and 2 == a[tmp]:
    dp[1] = 0
    tmp += 1
elif n >= 2 and 2 != a[tmp]:
    dp[1] = dp[0] + 1

for i in range(2, n):
    if tmp < m and i + 1 == a[tmp]:
        dp[i] = 0
        tmp += 1
    else:
        dp[i] = (dp[i - 1] + dp[i - 2]) % (pow(10, 9) + 7)
#print(dp)
print(dp[n - 1] % (pow(10, 9) + 7))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import math
n, m = map(int,input().split())
a = []
for i in range(m):
    a.append(int(input()))

tmp = 0
dp = [0 for _ in range(n)]
if 1 == a[tmp]:
    dp[0] = 0
    tmp += 1
else:
    dp[0] = 1
if n >= 2 and 2 == a[tmp]:
    dp[1] = 0
    tmp += 1
else:
    dp[1] = dp[0] + 1

for i in range(2, n):
    if tmp < m and i + 1 == a[tmp]:
        dp[i] = 0
        tmp += 1
    else:
        dp[i] = (dp[i - 1] + dp[i - 2]) % (pow(10, 9) + 7)
#print(dp)
print(dp[n - 1] % (pow(10, 9) + 7))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import math
n, m = map(int,input().split())
a = []
for i in range(m):
    a.append(int(input()))

ans = 1
dp = [0 for _ in range(n)]
if 1 in a:
    dp[0] = 0
elif not 1 in a:
    dp[0] = 1
if 2 in a:
    dp[1] = 0
elif not 2 in a:
    dp[1] = dp[0] + 1

for i in range(2, n):
    if i + 1 in a:
        dp[i] = 0
    else:
        dp[i] = (dp[i - 1] + dp[i - 2]) % (pow(10, 9) + 7)
#print(dp)
print(dp[n - 1] % (pow(10, 9) + 7))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import math
n, m = map(int,input().split())
a = []
for i in range(m):
    a.append(int(input()))

ans = 1
dp = [0 for _ in range(n)]
if 1 in a:
    dp[0] = 0
elif not 1 in a:
    dp[0] = 1
if 2 in a:
    dp[1] = 0
elif not 2 in a:
    dp[1] = dp[0] + 1

for i in range(2, n):
    if i + 1 in a:
        dp[i] = 0
    else:
        dp[i] = dp[i - 1] + dp[i - 2]
#print(dp)
print(dp[n - 1] % (pow(10, 9) + 7))

Submission status: Runtime Error

Solution code:
MOD=10**9+7

N,_,*a = map(int, open(0).read().split())
A=set(a)
dp = [0 for _ in range(N+1)]
for i in range(1,3):
    if i not in A:
        dp[i]=dp[i-1]+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])

Submission status: Runtime Error

Solution code:
MOD=10**9+7

N,_,*a = map(int, open(0).read().split())
A=set(a)
dp = [0 for _ in range(N+1)]
for i in range(1,3):
    if i not in A: dp[i]=dp[i-1]+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])

Submission status: Runtime Error

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

n,m = MAP()
a = [INT() for _ in range(m)]
dp = [0 for _ in range(n+2)]
dp[0] = 0
dp[1] = 1
j = 0
for i in range(2, n+2):
    if a[j] != i - 1:
        dp[i] = dp[i-1] + dp[i-2]
        dp[i] %= mod
    else:
        dp[i] = 0
        if j < m - 1:
            j += 1
print(dp[n+1])

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
dp = [1]*(N+1)
for _ in range(M):
    a, = map(int, input().split())
    dp[a] = 0
    A.append(a)
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:
import sys
sys.setrecursionlimit(3000)

a=open(0)
N,_,*a = map(int, a.read().split())

dp = [-1 for _ in range(150000)]
dp[0] = 0
def rec(i):
    if dp[i] >= 0:
        return dp[i]
    if i in a:
        dp[i] = 0
        return 0
    if i<3:
        dp[i] = rec(i-1) + 1
        return dp[i]
    dp[i] = (rec(i-1)+rec(i-2))%1000000007
    return dp[i]
    
print(rec(N))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(2000)

a=open(0)
N,_,*a = map(int, a.read().split())

dp = [-1 for _ in range(150000)]
dp[0] = 0
def rec(i):
    if dp[i] >= 0:
        return dp[i]
    if i in a:
        dp[i] = 0
        return 0
    if i<3:
        dp[i] = rec(i-1) + 1
        return dp[i]
    dp[i] = (rec(i-1)+rec(i-2))%1000000007
    return dp[i]
    
print(rec(N))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split(' '))
dp = [0 for _ in range(N + 1)]
for _ in range(M):
    i = int(input())
    dp[i] = -float('inf')

dp[0] = 1
for i in range(N+1):
    if 0 <= i-1 < N and dp[i-1] != -float('inf'):
        dp[i] += dp[i-1]

    if 0 <= i-2 < N and dp[i-2] != -float('inf'):
        dp[i] += dp[i-2]

print(dp[N] % 1000000007 )

Submission status: Runtime Error

Solution code:
import sys

read = sys.stdin.read

n, m, *a = map(int, read().split())
mod = 1000000007
dp = [0] * (n+1)
dp[0] = 1
if a[0] == 1:
    dp[1] = 0
    a.pop(0)
else:
    dp[1] = 1
for i in range(2, n+1):
    if a and i == a[0]:
        a.pop(0)
        dp[i] == 0
    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())
IN = [int(input()) for _ in range(m)]
a = [0 for _ in range(n+1)]
for i in IN:
    a[i] = 1

dp = [-1 for _ in range(n+1)]
dp[-1], dp[-2], dp[-3] = 0, 1, 2

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

Submission status: Runtime Error

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

dp = [-1 for _ in range(n+1)]
dp[-1], dp[-2], dp[-3] = 0, 1, 2

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

Submission status: Runtime Error

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

dp = [-1 for _ in range(n+1)]
dp[-1], dp[-2], dp[-3] = 0, 1, 2

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

memo = [None] * (N+1)
memo[0] = 0 #0番目にたどり着く方法は0通りと定義する。
memo[1] = 1 if not a[1] else 0
if a[2] != True:
  if memo[1] == 0:
    memo[2] = 1
  else:
    memo[2] = 2
else:
  memo[2] = 0

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

print(memo[N] % 1000000007)

Submission status: Runtime Error

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

def d(n: int) -> int:
    if n == N or n == N-1:
        return 1
    
    if not(n+1 in a) and not(n+2 in a):
        return d(n+1) + d(n+2)
    elif n+1 in a and not (n+2 in a):
        return d(n+2)
    else:
        return d(n+1)

flag = 0
for i in range(M-1):
    if a[i] == a[i+1]:
        flag = 1
        break
        
if flag == 1:
    print(0)
else:
    print(d(0) % 1000000007)

Submission status: Runtime Error

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

broken = [False] * (n + 1)
for i in range(m):
    broken[int(input())] = True

mod = 1_000_000_007

dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 0 if broken[1] else 1

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

print(dp[n])

Submission status: Runtime Error

Solution code:
ans=10**10
n=int(input())
w=list(map(int,input().split()))
for i in range(1,n):
    ans=min(ans,abs(sum(w[:i])-sum(w[i:])))

print(ans)AC

Submission status: Runtime Error

Solution code:
def main():
  import sys
  input = sys.stdin.readline
  n,m=map(int,input().split())
  mod=pow(10,9)+7
  ans=[1]*(n+1)
  for _ in [0]*m:
    ans[int(input())]=0
  ans[2]=ans[1]+1 if ans[2]!=0 else 0
  for i in range(3,n+1):
    if ans[i]>0:
      ans[i]=(ans[i-1]+ans[i-2])%mod
  print(ans[-1])
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
  import sys
  input = sys.stdin.readline
  n,m=map(int,input().split())
  a=[int(input()) for _ in [0]*m]
  mod=pow(10,9)+7
  ans=[0]*n
  ans[0]=1
  for i in range(n):
    if a.count(i+1)==1:
      ans[i]=0
    else:
      if i==1:
        ans[i]=ans[0]+1
      else:
        ans[i]=(ans[i-1]%mod+ans[i-2]%mod)%mod
  print(ans[-1])
if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
n, m = [int(i) for i in input().split()]
a = []
broken = [False] * (n+1)
for _ in range(m):
    i = int(input())
    a.append(i)
    broken[i] = True

ways = [0] * 3
ways[1] = 0 if broken[1] else 1
ways[2] = 0 if broken[2] else ways[1] + 1
for i in range(3, n+1):
    if broken[i]:
        ways.append(0)
    else:
        ways.append((ways[-2]+ways[-1])%(10**9+7))

print(ways[n])

Submission status: Runtime Error

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

ways = [0] * 3
ways[1] = 0 if 1 in a else 1
ways[2] = 0 if 2 in a else ways[1] + 1
for i in range(3, n+1):
    if i in a:
        ways.append(0)
    else:
        ways.append((ways[-2]+ways[-1])%(10**9+7))
    print(ways)

print(ways[n])

Submission status: Runtime Error

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

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

#2連続穴がある場合
for i in range(len(lst)-1):
    if lst[i]+1 == lst[i+1]:
        print(0)
        exit()

lst2 = []
for i in range(len(lst)):
    if i==0:
        lst2.append(lst[0]-1)
    else:
        lst2.append(lst[i]-lst[i-1]-2)
lst2.append(n-lst[-1]-1)



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

ans = 1
for i in lst2:
    ans *= dp[i]
    ans %= mod

print(ans)

Submission status: Runtime Error

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


a = [True] * (N)
for _ in range(M):
    a[int(input())-1] = False


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

print(dp[N-1])

Submission status: Runtime Error

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

f = [1,1]
for i in range(2, n):
    f.append(f[i-2]+f[i-1])

cur = 0
ans = 1
for i in range(m):
    a = int(input())
    if a==cur:
        print(0)
        exit(0)
    ans *= f[a-cur-1]
    ans %= MOD
    cur = a+1
ans *= f[n-cur]
ans %= MOD
print(ans)

Submission status: Runtime Error

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

inf = 10**9+7

def comb(cur,ai):
    if ai - cur == 1:
        return 1
    elif ai - cur == 2:
        return 2
    elif ai <= cur:
        return 0
    return((comb(cur, ai-1)+comb(cur,ai-2))%inf)

cur = 0
if a[0] == 1: cur += 2
cnt = 1
for i in range(M+1):
    if a[0] == 1 and i == 0: continue
    if cur == a[i]:
        cnt = 0
        break
    cnt *= comb(cur,a[i]-1)%inf
    cnt = cnt%inf
    cur = a[i]+1

print(cnt%inf)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
#A = [int(input()) for i in range(M)]
flag = [0]*N
for i in range(M):
    flag[int(input())-1] = 1
#A = [i*3 for i in range(N//3)]
#for i in range(N//3):
    #flag[i] = 1

mod = 10**9+7

dp = [0] * N

if flag[0]==0:
#if 1 not in A:
    dp[0] = 1
    if flag[1]==0 and N>1:
    #if (2 not in A) and N > 1:
        dp[1] = 2
elif N > 1:
    if flag[1]==0:
    #if 2 not in A:
        dp[1] = 1
    else:
        dp[1] = 0

loop = []
'''
for i in range(2, N):
    if i not in A:
        loop.append(i)
'''
for i in range(2, N):
    if flag[i]==0:
        dp[i] = (dp[i-2] + dp[i-1]) % mod
        #dp[i] = (sum(dp[i-2:i])) % mod

print(dp[N-1])
#print(dp)

Submission status: Runtime Error

Solution code:
import sys
from functools import lru_cache
sys.setrecursionlimit(100001)

N, M = map(int, input().split())
b = tuple([int(input()) for i in range(M)])

mod = 10**9+7

@lru_cache(maxsize=None)
def Fib(n, a):
    if n == 1:
        return 0
    elif n == 2:
        return 1
    elif (n-2 in a) and n!=0:
        return 0
    else:
        return (Fib(n-1, a) + Fib(n-2, a)) % mod

print(Fib(N+2, b))

Submission status: Runtime Error

Solution code:
from functools import lru_cache

N, M = map(int, input().split())
b = tuple([int(input()) for i in range(M)])

mod = 10**9+7

@lru_cache(maxsize=None)
def Fib(n, a):
    if n == 1:
        return 0
    elif n == 2:
        return 1
    elif (n-2 in a) and n!=0:
        return 0
    else:
        return (Fib(n-1, a) + Fib(n-2, a)) % mod

print(Fib(N+2, b))

Submission status: Runtime Error

Solution code:
from functools import lru_cache

N, M = map(int, input().split())
b = tuple([int(input()) for i in range(M)])

mod = 10**9+7

@lru_cache(maxsize=None)
def Fib(n, a):
    if n == 1:
        return 0
    elif n == 2:
        return 1
    elif n-2 in a:
        return 0
    else:
        return (Fib(n-1, a) + Fib(n-2, a)) % mod

print(Fib(N+2, b))

Submission status: Runtime Error

Solution code:
from functools import lru_cache

N, M = map(int, input().split())
b = tuple([int(input()) for i in range(M)])

mod = 10**9+7

@lru_cache(maxsize=None)
def Fib(n, a):
    if n-2 in a:
        return 0
    elif n == 1:
        return 0
    elif n == 2:
        return 1
    else:
        return (Fib(n-1, a) + Fib(n-2, a)) % mod

print(Fib(N+2, b))

Submission status: Runtime Error

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

mod = 10**9+7
dp = [0] * N
if 1 not in A:
    dp[0] = 1
    if 2 not in A:
        dp[1] = 2
elif 2 not in A:
    dp[1] = 1
else:
    dp[1] = 0

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

print(dp[N-1])

Submission status: Runtime Error

Solution code:
n, m = (int(x) for x in input().split())
ab = []
for _ in range(m):
    a=int(input())
    ab.append(a)
dp = [0]*(n+1)
dp[0] = 1
ana = ab.pop(0)

for i in range(1,n+1):
    dp[i] += (dp[i-1]+dp[i-2])%1000000007
    if i == ana:
        dp[i] = 0
        if len(ab):
            ana = ab.pop(0)
print(dp[-1])

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
a=[]
for i in range(0,M):
    a.append(int(input()))
if M==0:
    a=[-1]
ans=1
s=[-1]*(N+1)
s[0]=1
def dp(n):
    if n==0:
        return 1
    elif n==1:
        return 0 if 1 in a else 1
    if s[n-1]!=-1:
        c=s[n-1]
    elif n-1 in a:
        s[n-1]=0
        c=0
    else:
        c=dp(n-1)%1000000007
        s[n-1]=c
    if s[n-2]!=-1:
        b=s[n-2]
    elif n-2 in a:
        s[n-2]=0
        b=0
    else:
        b=dp(n-2)%1000000007
        s[n-2]=b
    return (c+b)%1000000007
print(dp(N)%1000000007)

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
a=[]
for i in range(0,M):
    a.append(int(input()))
ans=1
s=[-1]*(N+1)
s[0]=1
def dp(n):
    if n==0:
        return 1
    elif n==1:
        return 0 if 1 in a else 1
    if s[n-1]!=-1:
        c=s[n-1]
    elif n-1 in a:
        s[n-1]=0
        c=0
    else:
        c=dp(n-1)%1000000007
        s[n-1]=c
    if s[n-2]!=-1:
        b=s[n-2]
    elif n-2 in a:
        s[n-2]=0
        b=0
    else:
        b=dp(n-2)%1000000007
        s[n-2]=b
    return (c+b)%1000000007
print(dp(N)%1000000007)

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
a=[]
for i in range(0,M):
    a.append(int(input()))
ans=1
s=[-1]*(N+1)
s[0]=1
def dp(n):
    if n==0:
        return 1
    elif n==1:
        return 0 if 1 in a else 1
    if s[n-1]!=-1:
        c=s[n-1]
    elif n-1 in a:
        s[n-1]=0
        c=0
    else:
        c=dp(n-1)
        s[n-1]=c
    if s[n-2]!=-1:
        b=s[n-2]
    elif n-2 in a:
        s[n-2]=0
        b=0
    else:
        b=dp(n-2)
        s[n-2]=b
    return c+b
print(dp(N)%1000000007)

Submission status: Runtime Error

Solution code:

MOD = 10_0000_0007

def main():
    n,m = map(int,input().split())
    al = [False for _ in range(n+1)]
    for i in range(m):
        a = int(input())
        al[a] = True
    
    dp = [0 for _ in range(n+1)]
    dp[0] = 1
    dp[1] = 1 if al[1] == False else 0

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

    print(dp[n] % MOD)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
N, M = map(int,input().split())
a = list(map(int,input().split()))
p = 10**9 + 7
a.insert(0, -1)
a.append(N+1)

def mod(n,p):
    return n % p

nk = [1]
for i in range(1,N+1):
    nk.append(mod((nk[-1] * i), p))

#ある数をAで割ったとき，その数をpで割ったときの余りを求めるのにかけるべき数を返す
def bunbo(A, p): 
    # p-2を2進数にする
    pp = p-2
    pb = list(str(format(pp, 'b')))
    # ひっくりかえす
    pb.reverse()
    # pbの要素の数lとして，A^1, A^2, A^4, A^8, ..., A^(2^l)をpで割った余りを求める
    lpp = [mod(A,p)]
    for _ in range(len(pb)-1):
        lpp.append(mod((lpp[-1] ** 2), p))
    # 必要なやつだけ足して，x=(A^(p-2)をpで割った余り)を求める
    x = 1
    for i in range(len(pb)):
        if pb[i] == '1':
            x *= lpp[i]
    return mod(x, p)
    
def nckp(a, b, c, p):
    # 0!, 1!, 2!, 3!, ..., n!をリストに入れる
    return mod((a * bunbo(b, p) * bunbo(c, p)),p)



for i in range(len(a)-2):
    if a[i+1] - a[i] == 1:
        print(0)
        break
else:
    ans = 1
    for j in range(len(a)-1):
        if a[j] != N:
            up = a[j+1] - a[j] - 2
            step = 0
            for l in range(up//2 + 1):
                way = nckp(nk[up-l], nk[l], nk[up-2*l], p)
                step += way
            ans *= step
    print(mod(ans, p))

Submission status: Runtime Error

Solution code:
N, M = map(int,input().split())
a = list(map(int,input().split()))
p = 10**9 + 7
a.insert(0, -1)
a.append(N+1)

def mod(n,p):
    return n % p

nk = [1]
for i in range(1,N+1):
    nk.append(mod((nk[-1] * i), p))

#ある数をAで割ったとき，その数をpで割ったときの余りを求めるのにかけるべき数を返す
def bunbo(A, p): 
    # p-2を2進数にする
    pp = p-2
    pb = list(str(format(pp, 'b')))
    # ひっくりかえす
    pb.reverse()
    # pbの要素の数lとして，A^1, A^2, A^4, A^8, ..., A^(2^l)をpで割った余りを求める
    lpp = [mod(A,p)]
    for _ in range(len(pb)-1):
        lpp.append(mod((lpp[-1] ** 2), p))
    # 必要なやつだけ足して，x=(A^(p-2)をpで割った余り)を求める
    x = 1
    for i in range(len(pb)):
        if pb[i] == '1':
            x *= lpp[i]
    return mod(x, p)
    
def nckp(a, b, c, p):
    # 0!, 1!, 2!, 3!, ..., n!をリストに入れる
    return mod((a * bunbo(b, p) * bunbo(c, p)),p)



for i in range(M-2):
    if a[i+1] - a[i] == 1:
        print(0)
        break
else:
    ans = 1
    for j in range(len(a)-1):
        if a[j] != N:
            up = a[j+1] - a[j] - 2
            step = 0
            for l in range(up//2 + 1):
                way = nckp(nk[up-l], nk[l], nk[up-2*l], p)
                step += way
            ans *= step
    print(mod(ans, p))

Submission status: Runtime Error

Solution code:
N, M = map(int,input().split())
a = list(map(int,input().split()))
p = 10**9 + 7
a.insert(0, -1)
a.append(N+1)

def mod(n,p):
    return n % p

nk = [1]
for i in range(1,N+1):
    nk.append(mod((nk[-1] * i), p))

#ある数をAで割ったとき，その数をpで割ったときの余りを求めるのにかけるべき数を返す
def bunbo(A, p): 
    # p-2を2進数にする
    pp = p-2
    pb = list(str(format(pp, 'b')))
    # ひっくりかえす
    pb.reverse()
    # pbの要素の数lとして，A^1, A^2, A^4, A^8, ..., A^(2^l)をpで割った余りを求める
    lpp = [mod(A,p)]
    for _ in range(len(pb)-1):
        lpp.append(mod((lpp[-1] ** 2), p))
    # 必要なやつだけ足して，x=(A^(p-2)をpで割った余り)を求める
    x = 1
    for i in range(len(pb)):
        if pb[i] == '1':
            x *= lpp[i]
    return mod(x, p)
    
def nckp(a, b, c, p):
    # 0!, 1!, 2!, 3!, ..., n!をリストに入れる
    return mod((a * bunbo(b, p) * bunbo(c, p)),p)



for i in range(M-2):
    if a[i+1] - a[i] == 1:
        print(0)
        break
else:
    ans = 1
    for j in range(len(a)-1):
        if a[j] != N:
            up = a[j+1] - a[j] - 2
            step = 0
            for l in range(up//2 + 1):
                way = nckp(nk[up-l], nk[l], nk[up-2*l], p)
                step += way
            ans *= step
    print(mod(ans, p))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

INF=-float("inf")

n,m=mii()

arr=lin(m)

dp=[0]*(n+1)

for i in arr:
    dp[i]=INF

if dp[1]!=INF:
    dp[1]=1

if dp[1]==INF and dp[2]!=INF:
    dp[2]=1

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

for i in range(2,n+1):
    if dp[i]!=INF:
        if dp[i-1]!=INF and dp[i-2]==INF:
            dp[i]+=dp[i-1]
        elif dp[i-1]==INF and dp[i-2]!=INF:
            dp[i]+=dp[i-2]
        elif dp[i-1]!=INF and dp[i-2]!=INF:
            dp[i]+=dp[i-1]+dp[i-2]
        else:
            dp[i]=0
#print(dp)
print(dp[-1]%mod)

Submission status: Runtime Error

Solution code:
from functools import lru_cache
N, M = map(int, input().split())

mod = 10**9+7

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

@lru_cache()
def f(x):
    v = 0
    if x<0:
        return 0
    if x == 0:
        return 1
    if a[x-1]:
        v += f(x-1)
    if a[x-2]:
        v += f(x-2)
    v %= mod
    return v

print(f(N))

Submission status: Runtime Error

Solution code:
def fiv(n):
    return int((((1+(5)**(1/2))/2)** (n + 1) - ((1-(5)**(1/2))/2)** (n + 1))//(5**(1/2)))

n, m = map(int, input().split())
broken = []
for i in range(m):
	broken.extend(map(int, input()))

p = [0] * (m + 1) #broken間の登り方list

for i in range(m + 1):
    if i == 0: #a1 さいしょ
        if broken[0] == 1:
            p[0] = 1
        else:
            p[0] = fiv(broken[0] - 1)
    if i == m: #am さいご
        if broken[m - 1] == n - 1:
            p[m] = 1
        else:
            p[m] = fiv(n - broken[0] - 1)
    
    else:
        if broken[i] - broken[i - 1] - 1 == 0:
            print('0')
            exit()
        else:
            p[i] = fiv(broken[i] - broken[i - 1] - 1)

ans = 1
for i in range(m + 1):
    ans = ans * p[i] 
if ans < 0:
    ans = ans * -1
ans = ans % 1000000007

print(int(ans))

Submission status: Runtime Error

Solution code:
def fiv(n):
    return (((1+(5)**(1/2))/2)** (n + 1) - ((1-(5)**(1/2))/2)** (n + 1))/(5**(1/2))

n, m = map(int, input().split())
broken = []
for i in range(m):
	broken.extend(map(int, input()))

p = [0] * (m + 1) #broken間の登り方list

for i in range(m + 1):
    if i == 0: #a1 さいしょ
        if broken[0] == 1:
            p[0] = 1
        else:
            p[0] = fiv(broken[0] - 1)
    if i == m: #am さいご
        if broken[m - 1] == n - 1:
            p[m] = 1
        else:
            p[m] = fiv(n - broken[0] - 1)
    
    else:
        if broken[i] - broken[i - 1] - 1 == 0:
            print('0')
            exit()
        else:
            p[i] = fiv(broken[i] - broken[i - 1] - 1)

ans = 1
for i in range(m + 1):
    ans = ans * p[i] / 1000000007

print(ans)

Submission status: Runtime Error

Solution code:
def fiv(n):
    return (((1+(5)**(1/2))/2)** (n + 1) - ((1-(5)**(1/2))/2)** (n + 1))/(5**(1/2))

n, m = map(int, input().split())
broken = []
for i in range(m):
	broken.extend(map(int, input()))

p = [0] * (m + 1) #broken間の登り方list

for i in range(m + 1):
    if i == 0: #a1 さいしょ
        if broken[0] == 1:
            p[0] = 1
        else:
            p[0] = fiv(broken[0] - 1)
    if i == m: #am さいご
        if broken[m] == n - 1:
            p[m] = 1
        else:
            p[m] = fiv(n - broken[0] - 1)
    
    else:
        if broken[i] - broken[i - 1] - 1 == 0:
            print('0')
            exit()
        else:
            p[i] = fiv(broken[i] - broken[i - 1] - 1)

ans = 1
for i in range(m + 1):
    ans = ans * p[i]

print(ans)

Submission status: Runtime Error

Solution code:
def fiv(n):
    return (((1+(5)**(1/2))/2)** (n + 1) - ((1-(5)**(1/2))/2)** (n + 1))/(5**(1/2))

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

p = [0] * (m + 1) #broken間の登り方list

for i in range(m + 1):
    if i == 0: #a1 さいしょ
        if broken[0] == 1:
            p[0] = 1
        else:
            p[0] = fiv(broken[0] -1)
    if i == m: #am さいご
        if broken[m] == n - 1:
            p[m] = 1
        else:
            p[m] = fiv(n - broken[0] - 1)
    
    else:
        if broken[i] - broken[i - 1] - 1 == 0:
            print('0')
            exit()
        else:
            p[i] = fiv(broken[i] - broken[i - 1] - 1)

ans = 1
for i in range(m + 1):
    ans = ans * p[i]

print(ans)

Submission status: Runtime Error

Solution code:
def fiv(n):
    return (((1+(5)**(1/2))/2)** n - ((1-(5)**(1/2))/2)** n)/(5**(1/2))

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

p = [0] * (m + 1) #broken間の登り方list

for i in range(m + 1):
    if i == 0: #a1 さいしょ
        if broken[0] == 1 or 2:
            p[0] = 1
        else:
            p[0] = fiv(broken[0] -1)
    if i == m: #am さいご
        if broken[m] == n - 1 or m - 2:
            p[m] = 1
        else:
            p[m] = fiv(n - broken[0])
    
    else:
        if broken[i] - broken[i - 1] - 1 == 0:
            print('0')
            exit()
        else:
            p[i] = fiv(broken[i] - broken[i - 1] - 1)

ans = 1
for i in range(m + 1):
    ans = ans * p[i]

print(ans)