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:
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:
        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:
N, M = [int(s) for s in input().split(' ')]
steps = [1] * (N + 1)
for m in range(M):
    a = int(input())
    steps[a] = -1
patterns = 1
mod = 1_000_000_007
d = {
    0: 1,
    1: 1,
    2: 2,
}

def mcn(m, n):
    mm = 1
    nn = 1
    for i in range(n):
        mm *= (m - i)
        nn *= (n - i)
    return mm // nn

def doit(n):
    if n in d:
        return d[n]
    ret = 0
    for two in range(n // 2 + 1):
        one = n - two * 2
        if one < 0:
            break
        ret += mcn(one + two, two)
    d[n] = ret
    return ret

conts = []
ret = 1
cont = 0
for step in steps:
    if cont == 0:
        cont += step
    elif cont > 0:        
        if step == 1:
            cont += step
        else:
            conts.append(cont)
            cont = step
    else:  # cont < 0
        if step == -1:
            cont += step
            ret *= 0
        else:
            conts.append(cont)
            cont = step
conts.append(cont)

for cont in conts:
    if cont < 0:
        continue
    ret *= doit(cont - 1)

print(ret % mod)

Submission status: Runtime Error

Solution code:
import numpy as np

N, M = map(int, input().split())
A = np.array([int(input()) for _ in range(M)])
q = 1000000007

cost = np.zeros(N + 1, dtype=np.int64)
cost[0] = 1
cost[1] = 1
cost[A] = 0
cost[2] = cost[0] + cost[1]

for i in range(1, N + 1):
    cost[A] = 0
    cost[i] = (cost[i - 1] + cost[i - 2]) % q

print(cost[-1])

Submission status: Runtime Error

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

def rec(i, sum):
  if sum == n:
    global ans
    ans += 1
    return False
  elif sum in a:
    return False
  elif sum > n:
    return False
  elif rec(i+1, sum+1):
    return True
  elif rec(i+1, sum+2):
    return True
  else:
    return False

rec(0, 0)
print(ans%1000000007)

Submission status: Runtime Error

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

def rec(i, sum):
  if sum == n:
    global ans
    ans += 1
    return False
  elif sum in a:
    return False
  elif sum > n:
    return False
  elif rec(i+1, sum+1):
    return True
  elif rec(i+1, sum+2):
    return True
  else:
    return False

rec(0, 0)
print(ans)

Submission status: Runtime Error

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

if a[0] == 1:
    x = [1,0]
else:
    x = [1,1]

for i in range(2,n+1):
    if i in a:
        x.append(0)

    else:
        x.append(x[i-1] + x[i-2])

if x[-1] == 0:
    print(0)
else:
    print(x[-1]%1000000007)

Submission status: Runtime Error

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

if a[0] == 1:
    x = [1,0]
else:
    x = [1,1]

for i in range(2,n+1):
    if i in a:
        x.append(0)

    else:
        x.append(x[i-1] + x[i-2])

print(x[-1]%1000000007)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

is_broken=[True]*(n+1)
for i in range(m):
  is_broken[broken[i]]=False
   
dp=[0]*(n+1)

if  is_broken[1]:
  dp[1],dp[2]=1,2
else:
  if is_broken[2]:
    dp[2]=1

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

Submission status: Runtime Error

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

is_broken=[True]*(n+1)
for i in range(m):
  is_broken[broken[i]]=False
   
dp=[0]*(n+1)

if  is_broken[1]:
  dp[1],dp[2]=1,2
else:
  if is_broken[2]:
    dp[2]=1

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

Submission status: Runtime Error

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

is_broken=[True]*(n+1)
for i in range(m):
  is_broken[broken[i]]=False
   
dp=[0]*(n+1)
if  is_broken[1]:
  dp[1],dp[2]=1,2
else:
  if is_broken[2]:
    dp[2]=1

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

Submission status: Runtime Error

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

dp=[0]*(n+1)
if 1 not in broken:
  dp[1],dp[2]=1,2
else:
  if 2 not in broken:
    dp[2]=1

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

Submission status: Runtime Error

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

N,M=map(int,input().split())
a=[]
for _ in range(0,M):
    a.append(int(input()))
a.append(N+1)
m=1
for i in range(0,M+1):
    if i==0:
        m=fibonacci(a[i]-1)
    else:
        m=m*fibonacci(a[i]-a[i-1]-2)

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

Submission status: Runtime Error

Solution code:
Num = 10 ** 9 + 7
N, M = map(int, input().split())
if M != 0
  danger = int(input())
count = 1
l = [1, 1]
for i in range(1, N):
  if i == danger:
    l[1] = 0
    if count < M:
      danger = int(input())
      count += 1
  l = [l[1] % Num, l[0] + l[1]]
  if l == [0, 0]:
    break
if N == danger:
  l[1] = 0
print(l[1] % Num)

Submission status: Runtime Error

Solution code:
Num = 10 ** 9 + 7
N, M = map(int, input().split())
danger = int(input())
count = 1
l = [1, 1]
for i in range(1, N):
  if i == danger:
    l[1] = 0
    if count < M:
      danger = int(input())
      count += 1
  l = [l[1] % Num, l[0] + l[1]]
  if l == [0, 0]:
    break
if N == danger:
  l[1] = 0
print(l[1] % Num)

Submission status: Runtime Error

Solution code:
def fibonacci(n):
    if n<0:
        return 0
    if n==1 or n==0:
        return 1
    else:
        return fibonacci(n-1)+fibonacci(n-2)

N,M=map(int,input().split())
a=[]
for _ in range(0,M):
    a.append(int(input()))
a.append(N+1)
m=1
for i in range(0,M+1):
    if i==0:
        m=fibonacci(a[i]-1)
    else:
        m=m*fibonacci(a[i]-a[i-1]-2)

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

Submission status: Runtime Error

Solution code:
def fibonacci(n):
    if n==-1:
        return 0
    if n==1 or n==0:
        return 1
    else:
        return fibonacci(n-1)+fibonacci(n-2)

N,M=map(int,input().split())
a=[]
for _ in range(0,M):
    a.append(int(input()))
a.append(N+1)
m=1
for i in range(0,M+1):
    if i==0:
        m=fibonacci(a[i]-1)
    else:
        m=m*fibonacci(a[i]-a[i-1]-2)

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
def main(N,M,a):
    dp = [-1]*N
    dp[0] = 1
    dp[1] = 2
    for i in a:
        if i == 1:
            dp[0] = 0
            dp[1] = 1
        else:
            dp[i-1] = 0
    for i in range(2,N):
        if dp[i] != 0:
            dp[i] = dp[i-1] + dp[i-2]
    return dp[-1]
N,M = map(int, input().split())
a = list(int(input()) for i in range(M))

print(main(N,M,a) % 1000000007)

Submission status: Runtime Error

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

dp = [0] * (n + 1)
if 0 not in a:
    dp[0] = 1
if 1 not in a:
    dp[1] = 1
if 2 not in a:
    if 1 in a:
        dp[2] = 1
    else:
        dp[2] = 2

mod = 10**9+7

for i in range(3,n+1):
    if i-1 in a and i-2 in a:
        dp[i] = 0
    elif i-1 in a:
        dp[i] = dp[i-2] % mod
    elif i-2 in a:
        dp[i] = dp[i-1] % mod
    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())

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

#初期化
dp=[-1]*N
dp[0]=1

for i in a:
    dp[i-1] = 0

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

print(dp[N-1]%1000000007)

Submission status: Runtime Error

Solution code:
def Fib(n):    
    if n == 1:
        return 0
    elif n == 2:
        return 1
    else:
        return Fib(n-1)+Fib(n-2)

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

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

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

num_list = []
rest = N
cnt = 0

if M == 0:
    num_list.append(N+1)
else:
    list.sort(reverse = True)
    rest = N + 1
    for i in list:
        num_list.append(rest - i - 1)
        rest = i
    num_list.append(list[-1])

ans = 1
for i in num_list:
    ans = ans * Fib(i+1)
print(ans % 1000000007)

Submission status: Runtime Error

Solution code:
def Fib(n):    
    if n == 1:
        return 0
    elif n == 2:
        return 1
    else:
        return Fib(n-1)+Fib(n-2)

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

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

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

num_list = []
rest = N
cnt = 0

list.sort(reverse = True)
rest = N + 1
for i in list:
    num_list.append(rest - i - 1)
    rest = i
num_list.append(list[-1])

ans = 1
for i in num_list:
    ans = ans * Fib(i+1)
print(ans % 1000000007)

Submission status: Runtime Error

Solution code:
def Fib(n):    
    if n == 1:
        return 0
    elif n == 2:
        return 1
    else:
        return Fib(n-1)+Fib(n-2)

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

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

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

num_list = []
rest = N
cnt = 0
for i in range(N+1):
    if i in list:
        num_list.append(cnt)
        cnt = 0
    elif i == N:
        num_list.append(cnt + 1)
    else:
        cnt += 1

ans = 1
for i in num_list:
    ans = ans * Fib(i+1)
print(ans % 1000000007)

Submission status: Runtime Error

Solution code:
import sys

N, M = map(int, input().split())
li = [int(input()) for i in range(M)]
flag = False

dp = [0] * (N+1)

if 1 in li and N > 1:
  dp[1] = 0
  dp[2] = 1
else:
  dp[1] = 1
  dp[2] = 2
  
if 2 in li and N > 1:
  dp[2] = 0

for n in range(1, N+1):
  if n == 1 or n == 2:
    continue
  
  if n in li:
    if flag:
      print(0)
      sys.exit()
    
    flag = True
    continue
  
  dp[n] = (dp[n-1] + dp[n-2]) % 1000000007
  flag = False
  
print(dp[N])

Submission status: Runtime Error

Solution code:
import sys

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

count = 0
flag = False

dp = [0] * (N+1)

if 1 in li:
  dp[1] = 0
  dp[2] = 1
else:
  dp[1] = 1
  dp[2] = 2
  
if 2 in li:
  dp[2] = 0

for n in range(1, N+1):
  if n == 1 or n == 2:
    continue
  
  if n in li:
    if flag:
      print(0)
      sys.exit()
    
    flag = True
    continue
  
  dp[n] = (dp[n-1] + dp[n-2]) % 1000000007
  flag = False
  
print(dp[N])

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
xx = [int(input()) for _ in range(m)]
mod = 10**9+7
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]%mod)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
temp = [0] * (n + 1)
temp[0] = 0
temp[1] = 1
temp[2] = 2
for i in range(3, n + 1):
  temp[i] = temp[i-1] + temp[i-2]

mod = 10 ** 9 + 7
start = 0
cnt = 1
for i in range(m):
  ko = int(input())
  if ko == 1:
    start = ko + 1
    continue
  end = ko - 1
  diff = end - start
  if diff < 0:
    diff = 0
  if diff == 0:
    start = ko + 1
    continue
  cnt = cnt * temp[diff]
  start = ko + 1

if n - start != 0:
  cnt = cnt * temp[n - start]
print(cnt % mod)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
temp = [0] * (n + 1)
temp[0] = 0
temp[1] = 1
temp[2] = 2
for i in range(3, n + 1):
  temp[i] = temp[i-1] + temp[i-2]

mod = 10 ** 9 + 7
start = 0
cnt = 1
for i in range(m):
  ko = int(input())
  if ko == 1:
    start = ko + 1
    continue
  end = ko - 1
  diff = end - start
  if diff < 0:
    diff = 0
  cnt = cnt * temp[diff]
  start = ko + 1

if n - start != 0:
  cnt = cnt * temp[n - start]
print(cnt % mod)

Submission status: Runtime Error

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

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 1 in a:
    dp[1] = 0
else:
    dp[1] = 1

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

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

Submission status: Runtime Error

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

t2 = 1
t1 = 0 if 1 in l else 1

for i in range(2,n+1):
  t0 = 0 if i in l else (t2+t1)%mod
  t2 = t1
  t1 = t0

print(t0)

Submission status: Runtime Error

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

DP = [-1 for i in range(N+1)]
stair = [0 for i in range(N+1)]
DP[0] = DP[1] = 1
stair[0] = stair[1] = 1
MOD = 10**9 + 7

for i in range(M):
    index = int(input())
    stair[index] = 0
    DP[index] = 0

def DP_top_down(num):

    if (DP[num] == 0): # broken
        return(0)

    elif (DP[num] == 1): # done
        answer = stair[num]
    
    else:
        answer = DP_top_down(num-2) + DP_top_down(num-1)
        stair[num] = answer # I forgot this operation!
        DP[num] = 1        

    return(answer)

answer = DP_top_down(N)
print(answer%MOD)

Submission status: Runtime Error

Solution code:
def kjou(kkk):
    ka=1
    for km in range(kkk):
        ka=ka*(km+1)    
    return ka

def fcof(ad):
    k=ad//2
    if k==0 :
        return 1
    kcnt=0
    for kk in range(k+1):
        ar=ad-(kk)*2
        dk=kjou(kk+ar)/kjou(kk)/kjou(ar)
        kcnt=kcnt+ dk
        print(ad,k,kk,ar)
    return kcnt       

n,m=map(int,input().split())
n=20
m=2
a1=int(input())
a1=3
icnt=1
for i in range(m):
    a2=int(input())
    a2=11
    ad=a2-a1-1
    if ad<=0:
        print(0)
    fcof1=fcof(ad) 
    icnt=icnt*fcof1
    a1=a2
    print(icnt)

Submission status: Runtime Error

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

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

ans = 0
def dfs( i, s ):
  global ans
  if i >= n:
    ans += 1 % 1000000007
  else:
    next_left = i + 1
    if not( next_left in a ):
      dfs( next_left, s + str( next_left ) )
    next_right = i + 2
    if not( next_right in a ):
      dfs( next_right, s + str( next_right ) )

dfs( 0, "0" )

print( ans )

Submission status: Runtime Error

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

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

ans = 0
def dfs( i, s ):
  global ans
  if i == n:
    ans += 1
  elif i > n:
    return 0
  else:
    next_left = i + 1
    if not( next_left in a ):
      dfs( next_left, s + str( next_left ) )
    next_right = i + 2
    if not( next_right in a ):
      dfs( next_right, s + str( next_right ) )

dfs( 0, "0" )

print( ans % 1000000007 )

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import _collections
import string
from functools import lru_cache

class cin():
    def int():
        return int(sys.stdin.readline().rstrip())
    def string():
        return sys.stdin.readline().rstrip()
    def mapInt():
        return [int(x) for x in cin.string().split()]
    def stringList(n):
        return [input() for i in range(n)]
    def intListList(n):
        return [cin.mapInt() for i in range(n)]
    def intColsList(n):
        return [int(input()) for i in range(n)]
        
class Math():
    def gcd(a,b):
        if b == 0:
            return a
        return Math.gcd(b,a % b)
    def roundUp(a,b):
        return -(-a // b)
    def toUpperMultiple(a,x):
        return Math.roundUp(a,x) * x
    def toLowerMultiple(a,x):
        return (a // x) * x
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

MOD = int(1e09) + 7

def main():
    N ,M = cin.mapInt()
    A = cin.intColsList(M)

    p = 0
    dp = [0] * (N + 1)
    dp[0] = 1
    for i in range(N):
        if A[p] - 1 == i:
            p += 1
            if p == M:
                p = 0
        else:
            dp[i + 1] = dp[i] + dp[i - 1]
        dp[i + 1] %= MOD
    print(dp[N])
    return

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import _collections
import string
from functools import lru_cache

class cin():
    def int():
        return int(sys.stdin.readline().rstrip())
    def string():
        return sys.stdin.readline().rstrip()
    def mapInt():
        return [int(x) for x in cin.string().split()]
    def stringList(n):
        return [input() for i in range(n)]
    def intListList(n):
        return [cin.mapInt() for i in range(n)]
    def intColsList(n):
        return [int(input()) for i in range(n)]
        
class Math():
    def gcd(a,b):
        if b == 0:
            return a
        return Math.gcd(b,a % b)
    def roundUp(a,b):
        return -(-a // b)
    def toUpperMultiple(a,x):
        return Math.roundUp(a,x) * x
    def toLowerMultiple(a,x):
        return (a // x) * x
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

MOD = int(1e09) + 7

@lru_cache(maxsize=None)
def fib(n):
    if n == 0:
        return 1
    if n == 1:
        return 1
    return (fib(n - 1) + fib(n - 2)) % MOD

def main():
    N ,M = cin.mapInt()
    A = cin.intColsList(M)

    for i in range(M - 1):
        if A[i + 1] - A[i] == 1:
            print(0)
            return
    if M == 0:
        print(fib(N))
        return
    A.insert(0,-1)
    A.append(N + 1)

    ans = 1
    for i in range(M + 1):
        n,m = A[i] + 1,A[i + 1] - 1,
        ans *= fib(m - n)
        ans %= MOD
    print(ans)
    return

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from scipy.misc import comb

def LI():
  return [int(s) for s in input().split()]

def dansu(a,b):
    one_count = b - a
    two_count = 0
    count = 1
    for i in range((b-a) // 2):
        one_count -= 2
        two_count += 1
        count += comb(one_count+two_count,one_count,exact = True)
        
    return count
        
N,M = LI()
MOD = 10**9 + 7

total_count = 1

m1 = 0
m2 = int(input())

total_count = (total_count * dansu(m1,m2-1)) % MOD

m1 = m2 + 1

for i in range(1,M+1):  
  m2 = N if i == M else (int(input()) - 1)

  if m2 - m1 <= 0:
    print(0)
    exit()
    
  total_count *= (dansu(m1,m2) % MOD)
  m1 = m2 + 2
  
print(total_count % MOD)

Submission status: Runtime Error

Solution code:
from scipy.misc import comb

def LI():
  return [int(s) for s in input().split()]

def dansu(a,b):
    one_count = b - a
    two_count = 0
    count = 1
    for i in range((b-a) // 2):
        one_count -= 2
        two_count += 1
        count += comb(one_count+two_count,one_count,exact = True)
        
    return count
        
N,M = LI()
MOD = 10**9 + 7

total_count = 1

m1 = 0
m2 = int(input())

total_count = (total_count * dansu(m1,m2-1)) % MOD

m1 = m2 + 1

for i in range(1,M+1):  
  m2 = N if i == M else (int(input()) - 1)

  if m2 - m1 <= 0:
    print(0)
    exit()
    
  total_count *= (dansu(m1,m2) % MOD)
  m1 = m2 + 2
  
print(total_count % MOD)

Submission status: Runtime Error

Solution code:
def ways_to_climb(total_steps, broken_steps):
	steps = [0] * (total_steps + 1)
	steps[1] = 1 if 1 not in broken_steps else 0
	steps[2] = 2 if 2 not in broken_steps else 0

	for i in range(3, len(steps)):
		if i not in broken_steps:
			steps[i] = steps[i - 1] + steps[i - 2]
		else:
			steps[i] = 0

	return steps[-1] % (10**9 + 7)

if __name__ == '__main__':
	n, m = tuple(input().split())
	n = int(n)
	m = int(m)

	broken = set()
	for i in range(m):
		broken.add(int(input()))

	print(ways_to_climb(n, broken))

Submission status: Runtime Error

Solution code:
import numpy as np
n, m = map(int, input().split())
stairs = set([int(input()) for i in range(m)])
ans = np.ones(n+1)
mod = 10**9 + 7
if 1 in stairs:
    ans[1] -= 1
for i in range(2, n+1):
    if i in stairs:
        ans[i] = 0
    else:
        ans[i] = ans[i-1] + ans[i-2]

print(int(ans[-1]) % mod)

Submission status: Runtime Error

Solution code:
import numpy as np
n, m = map(int, input().split())
stairs = set([int(input()) for i in range(m)])
ans = np.ones(n+1)
mod = 10**9 + 7
if 1 in stairs:
    ans[1] -= 1
for i in range(2, n+1):
    if i in stairs:
        ans[i] = 0
    else:
        ans[i] = ans[i-1] + ans[i-2]

print(int(ans[-1] % mod))

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
hole_ids = {int(input()) - 1: 0 for _ in range(m)}
X = 1000000007


def solve(n, hole_ids):
    nums = []
    # nums = [0] * n
    for i in range(n):
        if i in hole_ids:
            nums.append(0)
            # nums[i] = 0
            continue

        if i == 0:
            nums.append(1)
            # nums[i] = 1
        elif i == 1:
            # 1つ前から1段上がるから2つ前から2個飛ばし
            nums.append(nums[-1] + 1)
            # nums[i] = nums[i-1] + 1
        else:
            nums.append((nums[-1] % X + nums[-2] % X) % X)
            # nums[i] = (nums[i-1] + nums[i-2]) % X
    return nums[-1]


print(solve(n, hole_ids))
n, m = map(int, input().split())
hole_ids = {int(input()) - 1: 0 for _ in range(m)}
X = 1000000007


def solve(n, hole_ids):
    nums = []
    # nums = [0] * n
    for i in range(n):
        if i in hole_ids:
            nums.append(0)
            # nums[i] = 0
            continue

        if i == 0:
            nums.append(1)
            # nums[i] = 1
        elif i == 1:
            # 1つ前から1段上がるから2つ前から2個飛ばし
            nums.append(nums[-1] + 1)
            # nums[i] = nums[i-1] + 1
        else:
            nums.append((nums[-1] % X + nums[-2] % X) % X)
            # nums[i] = (nums[i-1] + nums[i-2]) % X
    return nums[-1]


print(solve(n, hole_ids))

Submission status: Runtime Error

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

mod = int(1e9+7)

dp = [0]*N

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

print(dp[N-1]%mod)

Submission status: Runtime Error

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

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

if ls[0] == 1:
	dp[1] = 0
	del ls[0]
else:
	dp[1] = 1

ls.append(0)

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

Submission status: Runtime Error

Solution code:
from math import factorial
from operator import mul
from functools import reduce
from math import sqrt

def c(n,r):
  r = min(n-r,r)
  if r == 0 or r == n:
    return 1
  else:
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under
def num(k): # k段昇る場合の数
  return int((((1+sqrt(5))/2) ** k - ((1-sqrt(5))/2) ** k) / sqrt(5))
  """
  l,r = k // 2, 0
  for i in range(l+1):
    r += c(k-i,i)
    r %= mod
  return r
  """

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

if m == 0:
  print(num(n) % mod)
  exit()

a=[int(input()) for i in range(m)] # 壊れてる段

# ここから先 m > 0
a = [-1] + a + [n+1] # len(a)=m+2
sa = [a[i+1]-a[i]-2 for i in range(len(a)-1)]
ans = 1
#print(sa)
for i in sa:
  ans *= num(i)
  ans %= mod
print(ans)

Submission status: Runtime Error

Solution code:
from math import factorial
from operator import mul
from functools import reduce
from math import numpy

def c(n,r):
  r = min(n-r,r)
  if r == 0 or r == n:
    return 1
  else:
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under
def num(k): # k段昇る場合の数
  return int((((1+sqrt(5))/2) ** k - ((1-sqrt(5))/2) ** k) / sqrt(5))
  """
  l,r = k // 2, 0
  for i in range(l+1):
    r += c(k-i,i)
    r %= mod
  return r
  """

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

if m == 0:
  print(num(n) % mod)
  exit()

a=[int(input()) for i in range(m)] # 壊れてる段

# ここから先 m > 0
a = [-1] + a + [n+1] # len(a)=m+2
sa = [a[i+1]-a[i]-2 for i in range(len(a)-1)]
ans = 1
#print(sa)
for i in sa:
  ans *= num(i)
  ans %= mod
print(ans)

Submission status: Runtime Error

Solution code:
from math import factorial
from operator import mul
from functools import reduce
from math import sqrt

def c(n,r):
  r = min(n-r,r)
  if r == 0 or r == n:
    return 1
  else:
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under
def num(k): # k段昇る場合の数
  return int((((1+sqrt(5))/2) ** k - ((1+sqrt(5))/2) ** k) / sqrt(5))
  """
  l,r = k // 2, 0
  for i in range(l+1):
    r += c(k-i,i)
    r %= mod
  return r
  """

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

if m == 0:
  print(num(n) % mod)
  exit()

a=[int(input()) for i in range(m)] # 壊れてる段

# ここから先 m > 0
a = [-1] + a + [n+1] # len(a)=m+2
sa = [a[i+1]-a[i]-2 for i in range(len(a)-1)]
ans = 1
#print(sa)
for i in sa:
  ans *= num(i)
  ans %= mod
print(ans)

Submission status: Runtime Error

Solution code:
from math import factorial
from operator import mul
from functools import reduce
from math import numpy

def c(n,r):
  r = min(n-r,r)
  if r == 0 or r == n:
    return 1
  else:
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under
def num(k): # k段昇る場合の数
  return int((((1+sqrt(5))/2) ** k - ((1+sqrt(5))/2) ** k) / sqrt(5))
  """
  l,r = k // 2, 0
  for i in range(l+1):
    r += c(k-i,i)
    r %= mod
  return r
  """

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

if m == 0:
  print(num(n) % mod)
  exit()

a=[int(input()) for i in range(m)] # 壊れてる段

# ここから先 m > 0
a = [-1] + a + [n+1] # len(a)=m+2
sa = [a[i+1]-a[i]-2 for i in range(len(a)-1)]
ans = 1
#print(sa)
for i in sa:
  ans *= num(i)
  ans %= mod
print(ans)

Submission status: Runtime Error

Solution code:
from math import factorial
from operator import mul
from functools import reduce

def c(n,r):
  r = min(n-r,r)
  if r == 0 or r == n:
    return 1
  else:
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under
def num(k): # k段昇る場合の数
  return int((((1+sqrt(5))/2) ** k - ((1+sqrt(5))/2) ** k) / sqrt(5))
  """
  l,r = k // 2, 0
  for i in range(l+1):
    r += c(k-i,i)
    r %= mod
  return r
  """

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

if m == 0:
  print(num(n) % mod)
  exit()

a=[int(input()) for i in range(m)] # 壊れてる段

# ここから先 m > 0
a = [-1] + a + [n+1] # len(a)=m+2
sa = [a[i+1]-a[i]-2 for i in range(len(a)-1)]
ans = 1
#print(sa)
for i in sa:
  ans *= num(i)
  ans %= mod
print(ans)

Submission status: Runtime Error

Solution code:
from math import factorial
from operator import mul
from functools import reduce

def c(n,r):
  r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under
def num(k): # k段昇る場合の数
  l,r = k // 2, 0
  for i in range(l+1):
    r += c(k-i,i)
    r %= mod
  return r

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

if m == 0:
  print(num(n) % mod)
  exit()

a=[int(input()) for i in range(m)] # 壊れてる段

# ここから先 m > 0
a = [-1] + a + [n+1] # len(a)=m+2
sa = [a[i+1]-a[i]-2 for i in range(len(a)-1)]
ans = 1
#print(sa)
for i in sa:
  ans *= num(i)
  ans %= mod
print(ans)