Problem:


Score : 300 points

Problem Statement

There is a staircase with N steps. Takahashi is now standing at the foot of the stairs, that is, on the 0-th step.
He can climb up one or two steps at a time.

However, the treads of the a_1-th, a_2-th, a_3-th, \ldots, a_M-th steps are broken, so it is dangerous to set foot on those steps.

How many are there to climb up to the top step, that is, the N-th step, without setting foot on the broken steps?
Find the count modulo 1\ 000\ 000\ 007.

Constraints

1 \leq N \leq 10^5

0 \leq M \leq N-1

1 \leq a_1 < a_2 <  ...  < a_M \leq N-1

Input

Input is given from Standard Input in the following format:

N M
a_1
a_2
 .
 .
 .
a_M

Output

Print the number of ways to climb up the stairs under the condition, modulo 1\ 000\ 000\ 007.

Sample Input 1

6 1
3

Sample Output 1

4

There are four ways to climb up the stairs, as follows:

0 \to 1 \to 2 \to 4 \to 5 \to 6

0 \to 1 \to 2 \to 4 \to 6

0 \to 2 \to 4 \to 5 \to 6

0 \to 2 \to 4 \to 6

Sample Input 2

10 2
4
5

Sample Output 2

0

There may be no way to climb up the stairs without setting foot on the broken steps.

Sample Input 3

100 5
1
23
45
67
89

Sample Output 3

608200469

Be sure to print the count modulo 1\ 000\ 000\ 007.



Sample input:
6 1
3


Sample output:
4

Submission status: Runtime Error

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

total_time = 0
for i in range(N-1):
    total_time = S[i]+C[i]
    for j in range(i+1,N-1):
        if total_time < S[j]:
            total_time = S[j]
        elif total_time % F[j] != 0:
            total_time = S[j]+F[j]
        total_time += C[j]
    print(total_time)
print(0)

Submission status: Runtime Error

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

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

A = set(a)
 
for i in range(2,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:
N,M = map(int,input().split())
A = []

#フィボナッチ数列
from functools import lru_cache
@lru_cache(maxsize=None)
def Fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    elif n == 2:
        return 1
    else:
        return Fib(n-1) + Fib(n-2)
 
for i in range(M):
  a = int(input())
  A.append(a)
#ans = {0~a1-1 a1+1~a2-1 ... a(M-1)+1~aM-1 の行き方の積}
#各a(i)+1~a(i+1)-1への行き方は1通り
#i ~ i+Nへの行き方 Fib(N+1)通り

#REになっていたのはFib(0)が定義されていなかったから
if(N == 1): 
 ans = 1
elif(M == 0): 
 ans = Fib(N+1)
else: 
 ans = 0
 for i in range(M):  
    if(i == 0): #0~ a1-1 // ai+1 = A[i]
      n = (A[i]-1)-0
      #print(0,A[i]-1)
    else:
      n = (A[i]-1)-(A[i-1]+1) 
      #print(A[i-1]+1,A[i]-1)
      
    if(i != 0): #「渡れない箇所が二連続」が存在するなら0通り
     dif = A[i]-A[i-1]
     if(dif == 1):
       ans = 0
       break
          
    if(ans == 0): ans += (Fib(n+1)%(10**9 + 7))
    else: ans = ans*(Fib(n+1)%(10**9 + 7))

 n = N - (A[M-1]+1)#最後にaM + 1 ~ N のルートも考慮する
 ans = ans*(Fib(n+1)%(10**9 + 7))
 #print(A[M-1]+1,N)
            
ans = ans%(10**9 + 7)
print(ans)

Submission status: Runtime Error

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

#フィボナッチ数列
from functools import lru_cache
@lru_cache(maxsize=None)
def Fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    elif n == 2:
        return 1
    else:
        return Fib(n-1) + Fib(n-2)
 
for i in range(M):
  a = int(input())
  A.append(a)
#ans = {0~a1-1 a1+1~a2-1 ... a(M-1)+1~aM-1 の行き方の積}
#各a(i)+1~a(i+1)-1への行き方は1通り
#i ~ i+Nへの行き方 Fib(N+1)通り

#REになっていたのはFib(0)が定義されていなかったから
if(N == 1): 
 ans = 1
elif(M == 0): 
 ans = Fib(N)
else: 
 ans = 0
 for i in range(M):  
    if(i == 0): #0~ a1-1 // ai+1 = A[i]
      n = (A[i]-1)-0
      #print(0,A[i]-1)
    else:
      n = (A[i]-1)-(A[i-1]+1) 
      #print(A[i-1]+1,A[i]-1)
      
    if(i != 0): #「渡れない箇所が二連続」が存在するなら0通り
     dif = A[i]-A[i-1]
     if(dif == 1):
       ans = 0
       break
          
    if(ans == 0): ans += (Fib(n+1)%(10**9 + 7))
    else: ans = ans*(Fib(n+1)%(10**9 + 7))

 n = N - (A[M-1]+1)#最後にaM + 1 ~ N のルートも考慮する
 ans = ans*(Fib(n+1)%(10**9 + 7))
 #print(A[M-1]+1,N)
            
ans = 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)]
dp = [0] * (N+1)
dp[0] = 1
e = 1e9 + 7
for i in range(1, N+1):
    if i not in A:
        if i == 1:
            dp[i] = 1
            continue
        else:
            dp[i] = (dp[i-1] + dp[i-2]) % e
print(int(dp[N])

Submission status: Runtime Error

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

def fib(n):
    if n == 0:
        return 0
    elif n <= 2:
        return 1
    else:
        return fib(n-1)+fib(n-2)

a = []
for i in range(m):
    a.append(int(input()))
ans = fib(a[0])
for i in range(m-1):
    ans *= fib(a[i+1]-a[i]-1)
    ans %= 1000000007
ans *= fib(n-a[-1])
print(ans%1000000007)

Submission status: Runtime Error

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

def fib(n):
    r5 = 5**0.5
    f = 1/r5*((0.5+r5/2)**n-(0.5-r5/2)**n)
    return int(f)

a = []
for i in range(m):
    a.append(int(input()))
ans = fib(a[0])
for i in range(m-1):
    ans *= fib(a[i+1]-a[i]-1)
    ans %= 1000000007
ans *= fib(n-a[-1])
print(ans%1000000007)

Submission status: Runtime Error

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

def fib(n):
    r5 = 5**0.5
    f = 1/r5*((0.5+r5/2)**n-(0.5-r5/2)**n)
    return int(f)

a = []
for i in range(m):
    a.append(int(input()))
ans = fib(a[0])
for i in range(m-1):
    ans *= fib(a[i+1]-a[i]-1)
ans *= fib(n-a[-1])
print(ans%1000000007)

Submission status: Runtime Error

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

#フィボナッチ数列
from functools import lru_cache
@lru_cache(maxsize=None)
def Fib(n):
    if n == 1:
        return 1
    elif n == 2:
        return 1
    else:
        return Fib(n-1) + Fib(n-2)

      
for i in range(M):
  a = int(input())
  A.append(a)
#ans = {0~a1-1 a1+1~a2-1 ... a(M-1)+1~aM-1 の行き方の積}
#各a(i)+1~a(i+1)-1への行き方は1通り
#i ~ i+Nへの行き方 Fib(N+1)通り



ans = 0
for i in range(M+1):
  if(i == 0):
    n = (A[i]-1) - 0
    #print(0,(A[i]-1))  
  elif(i == M):
    n = N-(A[M-1]+1)
    #print(N,A[M-1]+1)
  else:
    n = (A[i]-1)-(A[i-1]+1)
    #print((A[i]-1),(A[i-1]+1))
    
  if(n < 0):
    ans = 0
    break
    
  if(n != 0):
   if(ans == 0): ans += (Fib(n+1))%(10**9+7)
   else: ans = (ans*Fib(n+1))%(10**9+7)
print(ans)

Submission status: Runtime Error

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

#フィボナッチ数列
from functools import lru_cache
@lru_cache(maxsize=None)
def Fib(n):
    if n == 1:
        return 1
    elif n == 2:
        return 1
    else:
        return Fib(n-1) + Fib(n-2)

      
for i in range(M):
  a = int(input())
  A.append(a)
#ans = {0~a1-1 a1+1~a2-1 ... a(M-1)+1~aM-1 の行き方の積}
#各a(i)+1~a(i+1)-1への行き方は1通り
#i ~ i+Nへの行き方 Fib(N+1)通り

ans = 0
for i in range(M+1):
  if(i == 0):
    n = (A[i]-1) - 0
    #print(0,(A[i]-1))  
  elif(i == M):
    n = N-(A[M-1]+1)
    #print(N,A[M-1]+1)
  else:
    n = (A[i]-1)-(A[i-1]+1)
    #print((A[i]-1),(A[i-1]+1))
    
  if(n < 0):
    ans = 0
    break
    N,M = map(int,input().split())
A = []

#フィボナッチ数列
from functools import lru_cache
@lru_cache(maxsize=None)
def Fib(n):
    if n == 1:
        return 1
    elif n == 2:
        return 1
    else:
        return Fib(n-1) + Fib(n-2)

      
for i in range(M):
  a = int(input())
  A.append(a)
#ans = {0~a1-1 a1+1~a2-1 ... a(M-1)+1~aM-1 の行き方の積}
#各a(i)+1~a(i+1)-1への行き方は1通り
#i ~ i+Nへの行き方 Fib(N+1)通り



ans = 0
for i in range(M+1):
  if(i == 0):
    n = (A[i]-1) - 0
    #print(0,(A[i]-1))  
  elif(i == M):
    n = N-(A[M-1]+1)
    #print(N,A[M-1]+1)
  else:
    n = (A[i]-1)-(A[i-1]+1)
    #print((A[i]-1),(A[i-1]+1))
    
  if(n < 0):
    ans = 0
    break
    
  if(n != 0):
   if(ans == 0): ans += (Fib(n+1))%(10**9+7)
   else: ans = (ans*Fib(n+1))%(10**9+7)
print(ans)
    
    
  
  if(n != 0):
   if(ans == 0): ans += Fib(n+1)%(10**9+7)
   else: ans = (ans*Fib(n+1))%(10**9+7)
print(ans)

Submission status: Runtime Error

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

#フィボナッチ数列
from functools import lru_cache
@lru_cache(maxsize=None)
def Fib(n):
    if n == 1:
        return 1
    elif n == 2:
        return 1
    else:
        return Fib(n-1) + Fib(n-2)

      
for i in range(M):
  a = int(input())
  A.append(a)
#ans = {0~a1-1 a1+1~a2-1 ... a(M-1)+1~aM-1 の行き方の積}
#各a(i)+1~a(i+1)-1への行き方は1通り
#i ~ i+Nへの行き方 Fib(N+1)通り

ans = 0
for i in range(M+1):
  if(i == 0):
    n = (A[i]-1) - 0
    #print(0,(A[i]-1))  
  elif(i == M):
    n = N-(A[M-1]+1)
    #print(N,A[M-1]+1)
  else:
    n = (A[i]-1)-(A[i-1]+1)
    #print((A[i]-1),(A[i-1]+1))
    
  if(n < 0):
    ans = 0
    break
    
  if(n != 0):
   if(ans == 0): ans += Fib(n+1)%(10**9+7)
   else: ans = (ans*Fib(n+1))%(10**9+7)
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
MOD = 1000000007
def F(n):
  root = np.sqrt(5)
  return int(1/root * (((1+root)/2)**n - ((1-root)/2)**n))

n,m = map(int, input().split())
a = [0] + [int(input()) for _ in range(m)] + [n]
dif = [0]*(m+1)
for i in range(m+1):
  dif[i] = F(a[i+1] - a[i] - 1)%MOD

print(np.cumprod(dif)[-1])

Submission status: Runtime Error

Solution code:
#C問題
mod = 10**9+7
N,M = map(int,input().split())

step = []
for i in range(N+1):
    if i <= 1:
        step.append(1)
    elif i == 2:
        step.append(1)
    else:
        step.append(step[i-1]+step[i-2])
    
A = []
for j in range(M):
    A.append(int(input()))

stairs = []
nowlen = 1
flag = 0
for i in range(N):
    I = i+1
    if I in A:
        if nowlen == 0:
            flag = 1
            break
        stairs.append(nowlen)
        nowlen = 0
    else:
        nowlen+=1
stairs.append(nowlen)
if flag == 1:
    print(0)
else:
    ans = 1
    for s in stairs:
        ans*=step[s]
        
    print(ans%mod)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
a = list(int(input()) for hoge in range(m))
dan = [a[0]]
ans = 1
for i in range(m-1):
         if (a[i+1]-(a[i]+1)) == 0:
                  print(0)
                  exit()
         dan.append(a[i+1]-(a[i]+1))
dan.append(n-(a[m-1]))
for j in range (len(dan)):
         ans *= ((2 ** (dan[j] //2)))
print(ans%((10 ** 9) +7))

Submission status: Runtime Error

Solution code:
from sys import stdin
from itertools import accumulate

a,b = [int(x) for x in stdin.readline().rstrip().split()]
li = [int(stdin.readline().rstrip()) for _ in range(b)]

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

elif a == 2:
    if b == 0:
        print(2)
        exit()
    else:
        print(1) 
        exit()

for k in range(len(li)-1):
    if li[k] +1 == li[k+1]:
        print(0)
        exit()

def stair_cal(x):
    if x == 1:
        return(x)
    elif x == 2:
        return(x)
    elif x == 0:
        return(1)
    lin = [1,2]
    for i in range(2,x):
        lin.append(lin[i-2]+lin[i-1])
    return(lin[-1])

li2 = []

li2.append(li[0]-1)

for i in range(1,b):
    li2.append(li[i]-li[i-1]-1)

li2.append(a-li[-1])

point = 1

for e in range(len(li2)):
    point = point*stair_cal(li2[e])%(10**9+7)

print(point)

Submission status: Runtime Error

Solution code:
from sys import stdin
from itertools import accumulate

a,b = [int(x) for x in stdin.readline().rstrip().split()]
li = [int(stdin.readline().rstrip()) for _ in range(b)]

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

elif a == 2:
    if b == 0:
        print(0)
        exit()
    else:
        print(1) 
        exit()

for k in range(len(li)-1):
    if li[k] +1 == li[k+1]:
        print(0)
        exit()

def stair_cal(x):
    if x == 1:
        return(x)
    elif x == 2:
        return(x)
    elif x == 0:
        return(1)
    lin = [1,2]
    for i in range(2,x):
        lin.append(lin[i-2]+lin[i-1])
    return(lin[-1])

li2 = []

li2.append(li[0]-1)

for i in range(1,b):
    li2.append(li[i]-li[i-1]-1)

li2.append(a-li[-1])

point = 1

for e in range(len(li2)):
    point = point*stair_cal(li2[e])%(10**9+7)

print(point)

Submission status: Runtime Error

Solution code:
s=list(map(int,input().split()))
t=[int(input()) for i in range(s[1])]
list=[]
mod=1000000007
d=1
for k in range(s[0]+4):
  list.append(0)
def fib(x):
  list[0]=list[1]=0
  list[2]=list[3]=1
  for l in range(4,x+3):
    list[l]=list[l-1]+list[l-2]
fib(s[0])
for j in range(s[1]+1):
  if j==0:
    d*=list[t[j]+1]
    d=d%mod
    e=t[j]
  elif j==s[1]:
    d*=list[s[0]-t[j-1]+1]
    d=d%mod
  else:
    d*=list[t[j]-t[j-1]]
    d=d%mod
print(d)

Submission status: Runtime Error

Solution code:
s=list(map(int,input().split()))
t=[int(input()) for i in range(s[1])]
list=[]
mod=1000000007
d=1
for k in range(1010):
  list.append(0)
def fib(x):
  list[0]=list[1]=0
  list[2]=list[3]=1
  for l in range(4,x+3):
    list[l]=list[l-1]+list[l-2]
fib(1000)
for j in range(s[1]+1):
  if j==0:
    d*=list[t[j]+1]
    d=d%mod
    e=t[j]
  elif j==s[1]:
    d*=list[s[0]-t[j-1]+1]
    d=d%mod
  else:
    d*=list[t[j]-t[j-1]]
    d=d%mod
print(d)

Submission status: Runtime Error

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


def Fib(num):
    a, b = 1, 0
    for _ in range(num):
        a, b = (a + b) % 1000000007, a % 1000000007
    return (a)


def stepcount(x, y):
    if y - x <= 1:
        return 1
    else:
        return Fib(y - x)


answer = Fib(outlist[0] - 1)

for i in range(m - 1):
    answer *= stepcount(outlist[i] + 1, outlist[i + 1] - 1)
    answer = answer % 1000000007

answer = (answer * stepcount(outlist[m - 1] + 1, n)) % 1000000007

for i in range(m - 1):
    if outlist[i + 1] - outlist[i] == 1:
        answer = 0

print(answer)

Submission status: Runtime Error

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

def Fib(num):
    a, b = 1, 0
    for _ in range(num):
        a, b = (a + b) % 1000000007, a % 1000000007
    return(a)

def stepcount(x,y):
    if y-x <= 1:
        return 1
    else:
        return Fib(y-x)

answer = Fib(outlist[0]-1)

for i in range(m-1):
    answer *= stepcount(outlist[i]+1,outlist[i+1]-1)
    answer = answer % 1000000007

answer = (answer * stepcount(outlist[m-1]+1, n)) % 1000000007

for i in range(m-1):
    if outlist[i+1] - outlist[i] == 1:
        answer = 0

print(answer)

Submission status: Runtime Error

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

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

#0の場合はここで0を出力して終える
for i in range(m-1):
    if list_f[i+1] - list_f[i] == 1:
        print(0)
        exit()

list_score = []
for i in range(m):
    if i == 0:
        val = list_f[i]
    else:
        val = list_f[i] - list_f[i-1] - 1
    list_score.append(val)

list_score.append(n - list_f[-1])

# print(list_score)

from functools import lru_cache
@lru_cache(maxsize=1000)
def test(n):
    if n == 1:
        return 1

    if n == 2:
        return 1
        
    return((test(n - 1)%1000000007 + test(n - 2)%1000000007))

score = 1
for i in list_score:
    score = score * test(i)

print(score%1000000007)

Submission status: Runtime Error

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

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

#0の場合はここで0を出力して終える
for i in range(m-1):
    if list_f[i+1] - list_f[i] == 1:
        print(0)
        exit()

list_score = []
for i in range(m):
    if i == 0:
        val = list_f[i]
    else:
        val = list_f[i] - list_f[i-1] - 1
    list_score.append(val)

list_score.append(n - list_f[-1])

# print(list_score)

from functools import lru_cache
@lru_cache(maxsize=1000)
def test(n):

    if n == 1:
        return 1

    if n == 2:
        return 1
        
    return((test(n - 1) + test(n - 2))%1000000007)

score = 1
for i in list_score:
    score = score * test(i)

print(score%1000000007)

Submission status: Runtime Error

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

    
def fib(j):
    if j==1:
        return 1
    if j==2:
        return 2
    return fib(j-1)+fib(j-2)


ans=1
now=0

for i in range(m):
    a=int(input())
    if a==now:
        ans=0
        break
    if a-1==now:
        now=a+1
        continue
    ans*=fib((a-now-1))
    ans=ans%mod
    now=a+1

if now!=n:
    ans*=fib((n-now))
    ans=ans%mod
print(ans)

Submission status: Runtime Error

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

    
def fib(j):
    if j==1:
        return 1
    if j==2:
        return 2
    return fib(j-1)+fib(j-2)


ans=1
now=0

for i in range(m):
    a=int(input())
    if a==now:
        ans=0
        break
    if a-1==now:
        now=a+1
        continue
    ans*=fib((a-now-1))
    ans=ans%mod
    now=a+1

ans*=fib((n-now))
ans=ans%mod
print(ans)

Submission status: Runtime Error

Solution code:
import math
N,M=map(int,input().split())
broken=[]
for i in range(M):
  broken.append(int(input()))
def count(A,B):
  ans=0
  if A==B or B-A==1:
    return 1
  elif B<A:
    return 0
  if (A%2==0 and B%2==0) or (A%2==1 and B%2==1):
    for i in range((B-A)//2+1):
      n=B-A-2*i+i
      ans+=math.factorial(n)/math.factorial(i)/math.factorial(n-i)
    return int(ans)
  else:
    return count(A+1,B)+count(A+2,B)
if M!=0:
  V=1
  for i in range(M):
    if i==0:
      V*=count(0,broken[i]-1)
    else:
      V*=count(broken[i-1]+1,broken[i]-1)
  V*=count(broken[-1]+1,N)
  print(V%(10**9+7))
else:
  print(count(0,N))

Submission status: Runtime Error

Solution code:
import math
N,M=map(int,input().split())
broken=[]
for i in range(M):
  broken.append(int(input()))
def count(A,B):
  ans=0
  if A==B or B-A==1:
    return 1
  elif B<A:
    return 0
  if (A%2==0 and B%2==0) or (A%2==1 and B%2==1):
    for i in range((B-A)//2+1):
      n=B-A-2*i+i
      ans+=math.factorial(n)/math.factorial(i)/math.factorial(n-i)
    return int(ans)
  else:
    return count(A+1,B)+count(A+2,B)
V=1
for i in range(M):
  if i==0:
    V*=count(0,broken[i]-1)
  else:
    V*=count(broken[i-1]+1,broken[i]-1)
V*=count(broken[-1]+1,N)
print(V%(10**9+7))

Submission status: Runtime Error

Solution code:
from collections import deque
N,M=map(int,input().split())
broken=[]
for i in range(M):
  broken.append(int(input()))
ans=0
def dfs(start,goal,ans,d):
  if len(d)==0:
    return ans
  now=d.pop()
  if now==goal:
    ans+=1
    return dfs(start,goal,ans,d)
  else:
    if (now+1 in broken) and (now+2 in broken):
      return 0 
    else:
      if now+1 not in broken:
        if now+1<=goal:
          d.append(now+1)
      if now+2 not in broken:
        if now+2<=goal:
          d.append(now+2)
      return dfs(start,goal,ans,d)
V=1
for i in range(M):
  d=deque()
  if i==0:
    start=0
    goal=broken[i]-1
    d.append(start)
    V*=dfs(start,goal,ans,d)
  else:
    start=broken[i-1]+1
    goal=broken[i]-1
    d.append(start)
    V*=dfs(start,goal,ans,d)
Start=broken[i]+1
Goal=N
d_=deque()
d_.append(Start)
V*=dfs(Start,Goal,ans,d_)
print(V%(10**9+7))

Submission status: Runtime Error

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


MOD = 1000000007

dp = [0 for _ in range(N + 1)]

dp[0] = 1



next_ng_index = 0

for index in range(N):
    current = index + 1
    if current == A[next_ng_index]:
        next_ng_index += 1
        if next_ng_index == M:
            next_ng_index = 0
        continue

    pre_stair = current - 1
    dp[current] += dp[pre_stair]

    prepre_stair = current -2
    if prepre_stair >= 0:
        dp[current] += dp[prepre_stair]

    dp[current] %= MOD

print(dp[-1]%MOD)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(200000)
N, M = map(int, input().split())
if N == 1:
    print(1) 
    
elif M == 0:
    print(dp[N-1])
    
else:
    dp = [0]*N
    dp[0] = 1
    dp[1] = 2
    for i in range(N-2):
        dp[i+2] = dp[i]+dp[i+1]
        
    a = [int(input()) for _ in range(M)]
    
    for i in range(M-1):
        if a[i+1] == a[i] + 1:
            ans = 0
            break
    else:
        if a[0] == 1:
            ans == 1
        else:
            ans = dp[a[0]-2]
                
    for i in range(M-1):
        if a[i+1]-a[i] >= 3:
            ans *= dp[a[i+1]-a[i]-3]
    if N-a[M-1]-2 >= 0:
        ans *= dp[N-a[M-1]-2] 
    print(ans%1000000007)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)
N, M = map(int, input().split())

dp = [0]*(N+2)
dp[0] = 1
dp[1] = 2
for i in range(N):
    dp[i+2] = dp[i]+dp[i+1]
        
if M == 0:
    print(dp[N-1])
        
else:
    a = [int(input()) for _ in range(M)]
    
    for i in range(M-1):
        if a[i+1] == a[i] + 1:
            ans = 0
            break
    else:
        if a[0] == 1:
            ans == 1
        else:
            ans = dp[a[0]-2]
                
    for i in range(M-1):
        if a[i+1]-a[i] >= 3:
            ans *= dp[a[i+1]-a[i]-3]
    if N-a[M-1]-2 >= 0:
        ans *= dp[N-a[M-1]-2] 
    print(ans%1000000007)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
a = [int(input()) 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 i in a: continue
  dp[i] =dp[i-1]+dp[i-2]
  print(dp)
print(dp[-1])

Submission status: Runtime Error

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

dp = [0]*(N+1)
if 1 in a: continue
else: dp[1]=1

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

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
if N <= 2 and M != 0:
    print(N-1)
elif N <= 2:
    print(N)
    
else:
    dp = [0]*N
    dp[0] = 1
    dp[1] = 2
    for i in range(N-2):
        dp[i+2] = dp[i]+dp[i+1]
        
    if M == 0:
        print(dp[N-1])
        
    else:
        a = [int(input()) for _ in range(M)]
    
        for i in range(M-1):
            if a[i+1] == a[i] + 1:
                ans = 0
                break
        else:
            if a[0] == 1:
                ans == 1
            else:
                ans = dp[a[0]-2]
                
        for i in range(M-1):
            if a[i+1]-a[i] >= 3:
                ans *= dp[a[i+1]-a[i]-3]
        if N-a[M-1]-2 >= 0:
            ans *= dp[N-a[M-1]-2] 
        print(ans%1000000007)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

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

for i in range(M-1):
    if a[i+1] == a[i] + 1:
        print(0)
        break
else:
    if a[0] == 1:
        ans = 1
    else:
        ans = dp[a[0]-2]
    for i in range(M-1):
        if a[i+1]-a[i] >= 3:
            ans *= dp[a[i+1]-a[i]-3]
    if N-a[M-1]-2 >= 0:
        ans *= dp[N-a[M-1]-2] 
    print(ans%1000000007)

Submission status: Runtime Error

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

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

list_score = []
for i in range(m):
    if i == 0:
        val = list_f[i]
    else:
        val = list_f[i] - list_f[i-1] - 1
    list_score.append(val)

# print([n - list_f[-1]])
list_score.append(n - list_f[-1])

# print(list_score)

from functools import lru_cache
@lru_cache(maxsize=1000)
def test(n):

    if n == 1:
        return 1

    if n == 2:
        return 1
        
    return((test(n - 1) + test(n - 2))%1000000007)

score = 1
for i in list_score:
    score = score * test(i)

print(score%1000000007)

Submission status: Runtime Error

Solution code:
import sys
n,m=map(int,input().split())
l=[]
for i in range(m):
    l.append(int(input()))
if n==1:
    if 1 in l:
        print(0)
    else:
        print(1)
    sys.exit()
ans1=0
ans2=0
if 1 in l:
    if 2 in l:
        print(0)
        sys.exit()
    else:
        ans2=1
else:
    ans1=1
    if 2 in l:
        pass
    else:
        ans2=2
ans=[0,ans1,ans2]
S=2
while S<n:
    S+=1
    if S in l:
        ans.append(0)
    else:
        ans.append((ans[-1]+ans[-2])%1000000007)
print(ans[-1])
//print(ans)

Submission status: Runtime Error

Solution code:
#C
import sys
sys.setrecursionlimit(1000000)
mod=10**9+7
n,m=map(int,input().split())
a=[int(input()) for i in range(m)]
def f(x):
    b=1
    c=1
    if x==1 or x==0:
        return 1
    else:
        for i in range(x-1):
            b,c=(b+c)%mod,b
        return b
s=f(a[0]-1)
for i in range(1,m):
    if a[i]-a[i-1]==1:
        print(0)
        break
    s=(s*f(a[i]-a[i-1]-2))%mod
else:
    s=(s*f(n-a[m-1]-1))%mod
    print(s)

Submission status: Runtime Error

Solution code:
#C
import sys
sys.setrecursionlimit(1000000)
mod=10**9+7
n,m=map(int,input().split())
a=[int(input()) for i in range(m)]
def f(x):
    if x==1 or x==0:
        return 1
    else:
        return (f(x-1)+f(x-2))
s=f(a[0]-1)
for i in range(1,m):
    if a[i]-a[i-1]==1:
        print(0)
        break
    s=(s*f(a[i]-a[i-1]-2))%mod
else:
    s=(s*f(n-a[m-1]-1))%mod
    print(s)

Submission status: Runtime Error

Solution code:
#C
import sys
sys.setrecursionlimit(1000000)
mod=10**9+7
n,m=map(int,input().split())
a=[int(input()) for i in range(m)]
def f(x):
    if x==1 or x==0:
        return 1
    else:
        return (f(x-1)+f(x-2))%mod
s=f(a[0]-1)
for i in range(1,m):
    if a[i]-a[i-1]==1:
        print(0)
        break
    s=(s*f(a[i]-a[i-1]-2))%mod
else:
    s=(s*f(n-a[m-1]-1))%mod
    print(s)

Submission status: Runtime Error

Solution code:
#C
import sys
sys.setrecursionlimit(100000)
mod=10**9+7
n,m=map(int,input().split())
a=[int(input()) for i in range(m)]
def f(x):
    if x==1 or x==0:
        return 1
    else:
        return (f(x-1)+f(x-2))%mod
s=f(a[0]-1)
for i in range(1,m):
    if a[i]-a[i-1]==1:
        print(0)
        break
    s=(s*f(a[i]-a[i-1]-2))%mod
else:
    s=(s*f(n-a[m-1]-1))%mod
    print(s)

Submission status: Runtime Error

Solution code:
#C
mod=10**9+7
n,m=map(int,input().split())
a=[int(input()) for i in range(m)]
def f(x):
    if x==1 or x==0:
        return 1
    else:
        return (f(x-1)+f(x-2))%mod
s=f(a[0]-1)
for i in range(1,m):
    if a[i]-a[i-1]==1:
        print(0)
        break
    s=(s*f(a[i]-a[i-1]-2))%mod
else:
    s=(s*f(n-a[m-1]-1))%mod
    print(s)

Submission status: Runtime Error

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

print(f(dan,*l))

Submission status: Runtime Error

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

print(f(dan,*l))

Submission status: Runtime Error

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

print(f(dan,*l))

Submission status: Runtime Error

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

print(f(dan,*l))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
dp = [int(input()) for i in range(N+1)]
for i in range(M):
    A = int(input())
    dp[A] = -1
dp[0] = 1
for j in range(2, N + 1):
    if dp[j] == -1:
        dp[j] = 0
        continue
    dp[j] = dp[j-2] + dp[j-1]

print(dp[N] % 1000000007)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
dp = [int(input()) for i in range(N+1)]
for i in range(M):
    A = int(input())
    dp[A] = -1
dp[0] = 1
for j in range(2, N + 1):
    if dp[j] == -1:
        dp[j] = 0
        continue
    dp[i] = dp[i-2] + dp[i-1]

print(dp[N] % 1000000007)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
b = [False]*(n+1)
dp = [None]*(n+1)
M = 10**9+7
dp[0] = 1
dp[1] = 1

def up(x):
    if b[x] == True:
        return 0
    res = 0
    if dp[x-1] == None:
        dp[x-1] = up(x-1)
    res += dp[x-1]
    if dp[x-2] == None:
        dp[x-2] = up(x-2)
    res += dp[x-2]
    return (res%M)

for i in range(m):
    a = int(input())
    b[a] = True
if b[1] == True:
    dp[1] = 0
if n == 1:
    if b[1] == True:
        print(0)
    else:
        print(1)
    exit()
print(up(n))

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
b = [False]*(m+1)
dp = [None]*(n+1)
M = 10**9+7
dp[0] = 1
dp[1] = 1

def up(x):
    if b[x] == True:
        return 0
    res = 0
    if dp[x-1] == None:
        dp[x-1] = up(x-1)
    res += dp[x-1]
    if dp[x-2] == None:
        dp[x-2] = up(x-2)
    res += dp[x-2]
    return (res%M)

for i in range(m):
    a = int(input())
    b[a] = True
if b[1] == True:
    dp[1] = 0
if n == 1:
    if b[1] == True:
        print(0)
    else:
        print(1)
    exit()
print(up(n))

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
b = [False]*(m+1)
dp = [None]*(n+1)
M = 10**9+7
dp[0] = 1
dp[1] = 1

def up(x):
    if b[x] == True:
        return 0
    res = 0
    if dp[x-1] == None:
        dp[x-1] = up(x-1)
    res += dp[x-1]
    if dp[x-2] == None:
        dp[x-2] = up(x-2)
    res += dp[x-2]
    return (res%M)

for i in range(m):
    a = int(input())
    b[a] = True
if b[1] == True:
    dp[1] = 0
if n = 1:
    if b[1] == True:
        print(0)
    else:
        print(1)
    exit()
print(up(n))

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
b = [False]*(n+1)
dp = [None]*(n+1)
M = 10**9+7
dp[0] = 1
dp[1] = 1

def up(x):
    if b[x] == True:
        return 0
    res = 0
    if dp[x-1] == None:
        dp[x-1] = up(x-1)
    res += dp[x-1]
    if dp[x-2] == None:
        dp[x-2] = up(x-2)
    res += dp[x-2]
    return (res%M)

for i in range(m):
    a = int(input())
    b[a] = True
if b[1] == True:
    dp[1] = 0

print(up(n))

Submission status: Runtime Error

Solution code:
from functools import lru_cache

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

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

@lru_cache(maxsize=1000)
def test(n):
    if n in list_f:
        return 0 

    if n == 1:
        return 1

    if n == 2:
        return 1
        
    return((test(n - 1) + test(n - 2))%1000000007)

print(test(n))

Submission status: Runtime Error

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

print(f(dan,l))