Problem:


Score : 300 points

Problem Statement

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

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

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

Constraints

1 \leq N \leq 10^5

0 \leq M \leq N-1

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

Input

Input is given from Standard Input in the following format:

N M
a_1
a_2
 .
 .
 .
a_M

Output

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

Sample Input 1

6 1
3

Sample Output 1

4

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

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

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

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

0 \to 2 \to 4 \to 6

Sample Input 2

10 2
4
5

Sample Output 2

0

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

Sample Input 3

100 5
1
23
45
67
89

Sample Output 3

608200469

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



Sample input:
6 1
3


Sample output:
4

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
A=[int(input()) for i in range(m)]
l=[A[i]-0 if i==0 else A[i]-A[i-1]-1 for i in range(m)]
l.append(n-A[-1])
#print(l)

def fib(N):
  ans=[]
  for i in range(N):
    if i<2:
      ans.append(1)
    else:
      ans.append(ans[i-1]+ans[i-2])
  if len(ans)==0:
    return 0
  else:
    return ans[-1]

if 0 in l[1:]:
  print(0)
else:
  lp=[fib(item) for item in l]
#  print(lp)
  s=1
  for item in lp:
    s*=item
  print(s%1000000007)

Submission status: Runtime Error

Solution code:
# C
# Typical Stairs

N_M = input()

N = int(N_M.split(" ")[0])
M = int(N_M.split(" ")[1])

a = []

for i in range(M):

    a.append(int(input()))

#print(a)

stairs = [0] * (N + 1)

if 1 in a and 2 not in a:

    stairs[1] = 0
    stairs[2] = 1

elif 2 in a and 1 not in a:

    stairs[1] = 1
    stairs[2] = 0

elif 1 in a and 2 in a:

    stairs[1] = 0
    stairs[2] = 0

else:

    stairs[1] = 1
    stairs[2] = 2

for i in range(N + 1):
    
    if i in a:

        stairs[i] = 0
    
    elif i > 2:

        stairs[i] = int(stairs[i - 1] + stairs[i - 2])

print(stairs[-1] % 1000000007)

Submission status: Runtime Error

Solution code:
from collections import deque

def num_way(n):
    memo = [0]*(n+1)

    def _fib(n):
        if n <= 1:
            return n
        if memo[n] != 0:
            return memo[n]
        memo[n] = _fib(n-1) + _fib(n-2)
        return memo[n]

    return _fib(n)

N, M = map(int,input().split())
a = deque([0])
path_poss = 1
ans = 1
for m in range(M):
  start = a.popleft()
  buff = int(input())
  end = buff-1
  if (end-start) <= -1:
    path_poss = 0
    break
  a.append(buff+1)
  ans *= num_way(end-start)
  ans %= 1000000007

if path_poss == 0:
  print(0)
else:
  start = a.popleft()
  end = N
  if (end-start) <= -1:
    path_poss = 0
  if path_poss == 0:
    print(0)
  else:
  	ans *= num_way(end-start)
  	print(ans%1000000007)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
A=[int(input()) for i in range(m)]
l=[A[i]-0 if i==0 else A[i]-A[i-1]-1 for i in range(m)]
l.append(n-A[-1])
#print(l)

def fib(N):
  ans=[]
  for i in range(N):
    if i<2:
      ans.append(1)
    else:
      ans.append(ans[i-1]+ans[i-2])
  if len(ans)==0:
    return 1
  else:
    return ans[-1]

if 1 in l[1:]:
  print(0)
else:
  lp=[fib(item) for item in l]
#print(lp)
  s=1
  for item in lp:
    s*=item
  print(s%1000000007)

Submission status: Runtime Error

Solution code:
from collections import deque

def num_way(stair):
  memo = ["EMPTY"]*(stair+1)
  def _fib(stair):
    if stair == 1 or stair == 0:
      return 1
    elif stair == 2:
      return 2
    elif memo[stair] != "EMPTY":
      return memo[stair]
    else:
      memo[stair] = _fib(stair-1)+_fib(stair-2)
      return memo[stair]
  return _fib(stair)

N, M = map(int,input().split())
a = deque([0])
path_poss = 1
ans = 1
for m in range(M):
  start = a.popleft()
  buff = int(input())
  end = buff-1
  if (end-start) <= -1:
    path_poss = 0
    break
  a.append(buff+1)
  ans *= num_way(end-start)
  ans %= 1000000007

if path_poss == 0:
  print(0)
else:
  start = a.popleft()
  end = N
  if (end-start) <= -1:
    path_poss = 0
  if path_poss == 0:
    print(0)
  else:
  	print(num_way(end-start))

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
A=[int(input()) for i in range(m)]
l=[A[i]-0 if i==0 else A[i]-A[i-1]-1 for i in range(m)]
l.append(n-A[-1])
#print(l)

def fib(N):
  ans=[]
  for i in range(N):
    if i<2:
      ans.append(1)
    else:
      ans.append(ans[i-1]+ans[i-2])
  if len(ans)==0:
    return 0
  else:
    return ans[-1]

if 1 in l[1:]:
  print(0)
else:
  lp=[fib(item) for item in l]
#print(lp)
  s=1
  for item in lp:
    s*=item
  print(s%1000000007)

Submission status: Runtime Error

Solution code:
# C
# Typical Stairs

N_M = input()

N = int(N_M.split(" ")[0])
M = int(N_M.split(" ")[1])

a = []

for i in range(M):

    a.append(int(input()))

#print(a)

stairs = [0] * (N + 1)

if 1 in a:

    stairs[1] = 0
    stairs[2] = 1

elif 2 in a:

    stairs[1] = 1
    stairs[2] = 0

elif 1 in a and 2 in a:

    stairs[1] = 0
    stairs[2] = 0

else:

    stairs[1] = 1
    stairs[2] = 2

for i in range(N + 1):
    
    if i in a:

        stairs[i] = 0
    
    elif i > 2:

        stairs[i] = int(stairs[i - 1] + stairs[i - 2] % 1000000007)

    #print(stairs)

print(stairs[-1])

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
A=[int(input()) for i in range(m)]
l=[A[i]-0 if i==0 else A[i]-A[i-1]-1 for i in range(m)]
l.append(n-A[-1])
#print(l)

def fib(N):
  ans=[]
  for i in range(N):
    if i<2:
      ans.append(1)
    else:
      ans.append(ans[i-1]+ans[i-2])
  return ans[-1]

lp=[fib(item) for item in l]
#print(lp)
s=1
for item in lp:
  s*=item
print(s%1000000007)

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
a=[]
for i in range(M):
    a.append(int(input()))
j=M-1
if a[0]==1:
    f1=0
    f2=1
elif a[0]==2:
    f1=1
    f2=1
else:
    f1=1
    f2=2
def f(n,a,j):
    if n>2:
        if (n-1)!=a[j] and (n-2)!=a[j]:
            if n>3 and n-3==a[j]:
                return f(n-1,a,j)+f(n-2,a,j-1)
            else:
                return f(n-1,a,j)+f(n-2,a,j)
        elif (n-1)==a[j]:
             if n>3 and j>0 and n-3==a[j-1]:
                return f(n-2,a,j-1)
             else:
                return f(n-2,a,j)
        elif (n-2)==a[j]:
            return f(n-1,a,j-1)
    elif n==1:
        return f1
    else:
        return f2
print(f(N,a,j))

Submission status: Runtime Error

Solution code:
# C
# Typical Stairs

N_M = input()

N = int(N_M.split(" ")[0])
M = int(N_M.split(" ")[1])

a = []

for i in range(M):

    a.append(int(input()))

#print(a)

stairs = [0] * (N + 1)

if 1 in a:

    stairs[1] = 0
    stairs[2] = 1

elif 2 in a:

    stairs[1] = 1
    stairs[2] = 0

elif 1 in a and 2 in a:

    stairs[1] = 0
    stairs[2] = 0

else:

    stairs[1] = 1
    stairs[2] = 2

for i in range(N + 1):
    
    if i in a:

        stairs[i] = 0
    
    elif i > 2:

        stairs[i] = int(stairs[i - 1] + stairs[i - 2]) % 1000000007

    print(stairs)

print(stairs[-1])

Submission status: Runtime Error

Solution code:
from collections import deque

def num_way(stair):
  memo = ["EMPTY"]*(stair+1)
  def _fib(stair):
    if stair == 1 or stair == 0:
      return 1
    elif stair == 2:
      return 2
    elif memo[stair] != "EMPTY":
      return memo[stair]
    else:
      memo[stair] = _fib(stair-1)+_fib(stair-2)
      return memo[stair]
  return _fib(stair)

N, M = map(int,input().split())
a = deque([0])
path_poss = 1
ans = 1
for m in range(M):
  start = a.popleft()
  buff = int(input())
  end = buff-1
  if (end-start) <= -1:
    path_poss = 0
    break
  a.append(buff+1)
  ans *= num_way(end-start)
  ans %= 1000000007

if path_poss == 0:
  print(0)
else:
  start = a.popleft()
  end = N
  if (end-start) <= -1:
    path_poss = 0
  if path_poss == 0:
    print(0)
  else:
  	ans *= num_way(end-start)
  	print(ans%1000000007)

Submission status: Runtime Error

Solution code:
# C
# Typical Stairs

N_M = input()

N = int(N_M.split(" ")[0])
M = int(N_M.split(" ")[1])

a = []

for i in range(M):

    a.append(int(input()))

#print(a)

import numpy as np

stairs = list(np.zeros(N + 1))

if 1 in a:

    stairs[1] = 0
    stairs[2] = 1

elif 2 in a:

    stairs[1] = 1
    stairs[2] = 0

elif 1 in a and 2 in a:

    stairs[1] = 0
    stairs[2] = 0

else:

    stairs[1] = 1
    stairs[2] = 2

for i in range(N + 1):
    
    if i in a:

        stairs[i] = 0
    
    elif i > 2:

        stairs[i] = int(stairs[i - 1] + stairs[i - 2]) % 1000000007

    #print(stairs)

print(stairs[-1])

Submission status: Runtime Error

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

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

a_set=set()

for index in range(m):
    a_set.add(int(input()))

ans_list = []

ans_list = 0 * (n + 1)

for index in range(n + 1):
    if index == 0:
        ans_list[index] += 1
        continue
    if index == 1 and (index not in a_set):
        ans_list[index] += ans_list[index - 1]
        continue
    
    if index not in a_set:
        if (index - 1) not in a_set:
            ans_list[index] += ans_list[index - 1]
            ans_list[index] %= 1000000007
        if (index - 2) not in a_set:
            ans_list[index] += ans_list[index - 2]
            ans_list[index] %= 1000000007

print(ans_list[n])

Submission status: Runtime Error

Solution code:
from collections import deque

def num_way(stair):
  memo = ["EMPTY"]*(stair+1)
  def _fib(stair):
    if stair == 1 or stair == 0:
      return 1
    elif stair == 2:
      return 2
    elif memo[stair] != "EMPTY":
      return memo[stair]
    else:
      memo[stair] = _fib(stair-1)+_fib(stair-2)
      return memo[stair]
  return _fib(stair)

N, M = map(int,input().split())
a = deque([0])
path_poss = 1
ans = 1
for m in range(M):
  start = a.popleft()
  buff = int(input())
  end = buff-1
  if (end-start) <= -1:
    path_poss = 0
    break
  a.append(buff+1)
  ans *= num_way(end-start)
  ans %= 1000000007

if path_poss == 0:
  print(0)
else:
  start = a.popleft()
  end = N
  if(end-start) <= -1:
    path_poss = 0
  if path_poss == 0:
    print(0)
  else:
  	ans *= num_way(end-start)
  	print(ans%1000000007)

Submission status: Runtime Error

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

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

a_set=set()

for index in range(m):
    a_set.add(int(input()))

ans_list=[0 * (n+1)]

for index in range(n + 1):
    if index == 0:
        ans_list[index] += 1
        continue
    if index == 1 and (index not in a_set):
        ans_list[index] += ans_list[index - 1]
        continue
    
    if index not in a_set:
        if (index - 1) not in a_set:
            ans_list[index] += ans_list[index - 1]
            ans_list[index] %= 1000000007
        if (index - 2) not in a_set:
            ans_list[index] += ans_list[index - 2]
            ans_list[index] %= 1000000007

print(ans_list[n])

Submission status: Runtime Error

Solution code:
from collections import deque

def num_way(stair):
  memo = ["EMPTY"]*(stair+1)
  def _fib(stair):
    if stair == 1 or stair == 0:
      return 1
    elif stair == 2:
      return 2
    elif memo[stair] != "EMPTY":
      return memo[stair]
    else:
      memo[stair] = _fib(stair-1)+_fib(stair-2)
      return memo[stair]
  return _fib(stair)

N, M = map(int,input().split())
a = deque([0])
path_poss = 1
ans = 1
for m in range(M):
  start = a.popleft()
  buff = int(input())
  end = buff-1
  if (end-start) <= -1:
    path_poss = 0
    break
  a.append(buff+1)
  ans *= num_way(end-start)
  ans %= 1000000007

if path_poss == 0:
  print(0)
else:
  start = a.popleft()
  end = N
  ans *= num_way(end-start)
  print(ans%1000000007)

Submission status: Runtime Error

Solution code:
# C
# Typical Stairs

N_M = input()

N = int(N_M.split(" ")[0])
M = int(N_M.split(" ")[1])

a = []

for i in range(M):

    a.append(int(input()))

print(a)

import numpy as np

stairs = list(np.zeros(N + 1))

if 1 in a:

    stairs[1] = 0
    stairs[2] = 1

elif 2 in a:

    stairs[1] = 1
    stairs[2] = 0

elif 1 in a and 2 in a:

    stairs[1] = 0
    stairs[2] = 0

else:

    stairs[1] = 1
    stairs[2] = 2

for i in range(N + 1):
    
    if i in a:

        stairs[i] = 0
    
    elif i > 2:

        stairs[i] = int(stairs[i - 1] + stairs[i - 2])

    #print(stairs)

print(stairs[-1] % 1000000007)

Submission status: Runtime Error

Solution code:
a = list(map(int, input().split()))
#print(a)
b=[0]*1234567
c=[0]*1234567
b[0]=int(input())
c[0]=b[0]-0
for x in range(a[1]-1):
    b[x+1]=int(input())
    c[x+1]=b[x+1]-b[x]-1
c[-1]=a[0]-b[-1]
max = 0
min = a[0]+10000
for x in c:
    if x>max:
        max=x
    if x<min:
        min=x
        
#print(c)
#print(max," ",min)
if min==0:
    print(0)
else:
    num=[0]*1234567
    for x in range(max):
        if x==0:
            num[0]=1
        elif x==1:
            num[1]=1
        else:
            num[x]=num[x-1]+num[x-2]
        #print("num[",x,"]=",num[x])
        
    answer=1
    for x in c:
        answer *=num[x-1]
        if answer==0:
            print(0)
            break
        else:
            answer%=1000000007
    print(answer)

Submission status: Runtime Error

Solution code:
from collections import deque

def num_way(stair):
  if stair == 1 or stair == 0:
    return 1
  elif stair == 2:
    return 2
  else:
    return num_way(stair-1) + num_way(stair-2)

N, M = map(int,input().split())
a = deque([0])
path_poss = 1
ans = 1
for m in range(M):
  start = a.popleft()
  buff = int(input())
  end = buff-1
  if (end-start) <= -1:
    path_poss = 0
    break
  a.append(buff+1)
  ans *= num_way(end-start)
  ans %= 1000000007

if path_poss == 0:
  print(0)
else:
  start = a.popleft()
  end = N
  ans *= num_way(end-start)
  print(ans%1000000007)

Submission status: Runtime Error

Solution code:
a = list(map(int, input().split()))
#print(a)
b=[0]*(a[1]+5000)
c=[0]*(a[1]+1+5000)
b[0]=int(input())
c[0]=b[0]-0
for x in range(a[1]-1):
    b[x+1]=int(input())
    c[x+1]=b[x+1]-b[x]-1
c[-1]=a[0]-b[-1]
max = 0
min = a[0]+100
for x in c:
    if x>max:
        max=x
    if x<min:
        min=x
        
#print(c)
#print(max," ",min)
if min==0:
    print(0)
else:
    num=[0]*(max+5000)
    for x in range(max):
        if x==0:
            num[0]=1
        elif x==1:
            num[1]=1
        else:
            num[x]=num[x-1]+num[x-2]
        #print("num[",x,"]=",num[x])
        
    answer=1
    for x in c:
        answer *=num[x-1]
        if answer==0:
            print(0)
            break
        else:
            answer%=1000000007
    print(answer)

Submission status: Runtime Error

Solution code:
from collections import deque

def num_way(stair):
  if stair == 1 or stair == 0:
    return 1
  elif stair == 2:
    return 2
  else:
    return num_way(stair-1) + num_way(stair-2)

N, M = map(int,input().split())
a = deque([0])
path_poss = 1
ans = 1
for m in range(M):
  start = a.popleft()
  buff = int(input())
  end = buff-1
  if (end-start) <= -1:
    path_poss = 0
    break
  a.append(buff+1)
  ans *= num_way(end-start)

if path_poss == 0:
  print(0)
else:
  start = a.popleft()
  end = N
  ans *= num_way(end-start)
  print(ans%1000000007)

Submission status: Runtime Error

Solution code:
from math import factorial
def c(n):
    c = 0
    if n != 0:
        for i in range(n):
            if n - i < i:
                pass
            else:
                x = n - i
                r = i
                c += factorial(x) / factorial(r) / factorial(x - r)
    return c
N, M = map(int,input().split())
ans = 1
pre_a = 0
for j in range(M+1):
    if j != M:
        a = int(input())

    else:
        if pre_a != N-1:
            a = N
        else:
            a = N+1
    n = a - pre_a - 1
    if a == 1:
        ans *= 1
    else:
        ans *= c(n)
    pre_a = a
print(int(ans%1000000007))

Submission status: Runtime Error

Solution code:
from math import factorial
def c(n):
    c = 0
    if n != 0:
        for i in range(n):
            if n - i < i:
                pass
            else:
                x = n - i
                r = i
                c += factorial(x) / factorial(r) / factorial(x - r)
    return c
N, M = map(int,input().split())
ans = 1
pre_a = 0
for j in range(M+1):
    if j != M:
        a = int(input())

    else:
        a = N
    n = a - pre_a - 1
    if a == 1:
        ans *= 1
    else:
        ans *= c(n)
    pre_a = a
print(int(ans%1000000007))

Submission status: Runtime Error

Solution code:
a = list(map(int, input().split()))
#print(a)
b=[0]*a[1]
c=[0]*(a[1]+1)
b[0]=int(input())
c[0]=b[0]-0
for x in range(a[1]-1):
    b[x+1]=int(input())
    c[x+1]=b[x+1]-b[x]-1
c[-1]=a[0]-b[-1]
max = 0
min = a[0]+100
for x in c:
    if x>max:
        max=x
    if x<min:
        min=x
        
#print(c)
#print(max," ",min)
if min==0:
    print(0)
else:
    num=[0]*(max)
    for x in range(max):
        if x==0:
            num[0]=1
        elif x==1:
            num[1]=1
        else:
            num[x]=(num[x-1]+num[x-2])%1000000007
        #print("num[",x,"]=",num[x])
        
    answer=1
    for x in c:
        answer *=num[x-1]
        if answer==0:
            print(0)
            break
        else:
            answer%=1000000007
    print(answer)

Submission status: Runtime Error

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

MOD = 1000000007

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

count = [-1] * (n+1)
for i in range(m):
    count[int(input())] = 0

for i in range(1,n+1):
    if count[i] == 0:
        continue
    
    if i == 1:
        count[i] = 1 
    elif i == 2:
        count[i] = count[i-1] + 1
    else:
        count[i] = (count[i-1] + count[i-2]) % MOD

print(count[n])

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
mod=10**9+7
a = [int(input()) for i in range(m)]
block=[0,1]
x=[True for i in n]
for j in a:
  x[j-1]=False

for i in range(1,n+1):
  if x[i-1]==False:
    block=block[1:]+[0]
  else:
    block=block[1:]+[sum(block)%mod]
print(block[-1])

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
mod=10**9+7
a = [int(input()) for i in range(m)]
block=[0,1]
x=[True for i in n]
for j in a:
  x[j-1]=False

for i in range(1,n+1):
  if x[i-1]==True:
    block=block[1:]+[0]
  else:
    block=block[1:]+[sum(block)%mod]
print(block[-1])

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
pre_a = -1
k = []
ef = True
for i in range(M):
    a = int(input())
    if (a-pre_a == 1):break
    k.append(a-pre_a-2)
    pre_a = a
else:
    ef = False
    k.append(N-a-1)
nk = sorted(k)
def org_fib(t):
    t1 = 1
    t2 = 2
    fib = 0
    if t == 1:
        return t1
    elif t == 2:
        return t2
    else:
        for _ in range(t-2):
            fib = t1+t2
            t1 = t2
            t2 = fib
    return fib

if ef:print(0)
else:
    g = 1
    for nnkk in nk:
        if nnkk == 0:
            pass
        else:
            g = (g * org_fib(nnkk)) % 1000000007
    print(g)

Submission status: Runtime Error

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

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

for i in range(1,n+1):
    if i in a:
        dp[i]=0
        continue

    dp[i]=dp[i-1]
    if i>1:dp[i]+=dp[i-2]
    dp[i]%=1000000007
print(dp[-1])

Submission status: Runtime Error

Solution code:
n,m = (int(x) for x in input().split())
a = []
for i in range(m):
    a.append(int(input()))
 
total = [0 for _ in range(n)]
one = [0 for _ in range(n)]
two = [0 for _ in range(n)]
 
if 1 not in a:
    one[0] = 1
if 2 not in a:
    one[1] = 1
    two[1] = 1
total[1] = one[1]+two[1]
 
for i in range(2,n):
    if total[i-1] == 0 and total[i-2] == 0:
        print(0)
        exit()
    if (i+1) not in a:
        one[i] = total[i-1]
        two[i] = total[i-2]
        total[i] = (one[i]+two[i])
print(total[-1] % 1000000007)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
ana = [0] * M
for i in range(M):
  ana[i] = input()
ans = [0] * N
ans[0] = 1# 一段目まで登る方法は一通り
ans[1] = 2# 二段目まで登る方法は二通り
 
for i in range(2,N):
    tmp = i+1
    tmp2 = str(tmp)
    if tmp2 in ana:
        continue
    else:
        ans[i] = (ans[i-1] + ans[i-2]) % 1000000007
 
print(ans[N-1])

Submission status: Runtime Error

Solution code:
OK = 0
BRO = 1

N,M=map(int, input().split())
Broken=[int(input()) for i in range(M)]
#K = "".join(list(BRO if i in Broken else OK for i in range(N+1)))
K = list(0 for i in range(N+1))
for i in range(M):
  K[Broken[i]] = 1
  
if BRO+BRO in K:
  print(0)
else:
  c=[0 for i in range(N+1)]
  if K[N-1]==OK:
    c[1]=1
  if K[N-2]==OK and K[N-1]==OK:
    c[2]=2
  if K[N-2]==OK and K[N-1]==BRO:
    c[2]=1

  for i in range(3,N+1):
    if K[N-i]==OK:
      if K[N-i+1]==OK and K[N-i+2]==OK:
        c[i]=c[i-1]+c[i-2]
      if K[N-i+1]==OK and K[N-i+2]==BRO:
        c[i]=c[i-1]
      if K[N-i+1]==BRO and K[N-i+2]==OK:
        c[i]=c[i-2]
    c[i]%=1000000007
  
  print(c[N] % 1000000007)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
ana = []
for _ in range(M):
  ana.append(input())
ans = [0] * N
ans[0] = 1# 一段目まで登る方法は一通り
ans[1] = 2# 二段目まで登る方法は二通り
 
for i in range(2,N):
    tmp = i+1
    tmp2 = str(tmp)
    if tmp2 in ana:
        ans[i] = 0
    else:
        ans[i] = (ans[i-1] + ans[i-2]) % 1000000007
 
print(ans[N-1])

Submission status: Runtime Error

Solution code:
import queue

N,M = map(int,input().split(" "))
A = queue.Queue()

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

oneBreak = False
for m in range(M):
    inp = int(input())
    if inp == 1:
        oneBreak = True
    else:
        A.put(inp)


DP = [0] * (N+1)

DP[0] = 1

if(oneBreak):
    DP[1] = 0
else:
    DP[1] = 1
#壊れている階段の時は判定をスキップ（DPテーブルは0のまま）

if(M != 0):
    nowA = A.get()

for n in range(2,N + 1):
    if(nowA == n):
        if(not A.empty()):
            nowA = A.get()
        else:
            nowA = -1
    else:
        DP[n]  = (DP[n-1] + DP[n-2]) 
print(DP[n]%1000000007)

Submission status: Runtime Error

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

f = 0
if bre[0] == 0 or bre[0] == 1:
	f_2 = 0
	f_1 = 1
else:
	f_1 = 1
	f_2 = 1

f = f_1+f_2

if N == 1:
	print(1)
if N == 2:
	print(f)

num = 0
for i in range(2,N):
	if num < len(bre) and i+1 == bre[num]:
		f_2 = f_1
		f_1 = f
		f = 0
		if  num>1 and bre[num] == bre[num-1]:
			print(0)
			sys.exit()
		num += 1
	else:
		f_2 = f_1
		f_1 = f
		f = f_1 + f_2

print(f%1000000007)

Submission status: Runtime Error

Solution code:
import sys
N, M = map(int, input().split())
a = 0
bre = [int(input())]
for i in range(1, M):
	bre.append(int(input()))
	if bre[i]-bre[i-1] == 1:
		print(0)
		sys.exit()

f = 0
if bre[0] == 0 or bre[0] == 1:
	f_2 = 0
	f_1 = 1
else:
	f_1 = 1
	f_2 = 1

f = f_1+f_2

if N == 1:
	print(1)
if N == 2:
	print(f)

num = 0
for i in range(2,N):
	if num < len(bre) and i+1 == bre[num]:
		f_2 = f_1
		f_1 = f
		f = 0
		num += 1
	else:
		f_2 = f_1
		f_1 = f
		f = f_1 + f_2

print(f%1000000007)

Submission status: Runtime Error

Solution code:
import sys
N, M = map(int, input().split())
a = 0
bre = [int(input())]
for i in range(1, M):
	bre.append(int(input()))
	if bre[i]-bre[i-1] == 1:
		print(0)
		sys.exit()

f = 0
if bre[0] == 0 or bre[0] == 1:
	f_2 = 0
	f_1 = 1
else:
	f_1 = 1
	f_2 = 1

f = f_1+f_2

num = 0
for i in range(2,N):
	if num < len(bre) and i+1 == bre[num]:
		f_2 = f_1
		f_1 = f
		f = 0
		num += 1
	else:
		f_2 = f_1
		f_1 = f
		f = f_1 + f_2

print(f%1000000007)

Submission status: Runtime Error

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

for m in range(M):
    A.append(int(input()))


DP = [0] * (N+1)

DP[0] = 1
DP[1] = 1
#壊れている階段の時は判定をスキップ（DPテーブルは0のまま）

for n in range(2,N + 1):
    if not (n in A):
        DP[n]  = (DP[n-1] + DP[n-2]) 
print(DP[n])

Submission status: Runtime Error

Solution code:
d = 1000000007
N, M = list(map(int, input().split()))
a = [int(input()) for i in range(M)]
safe = [True for i in range(N+1)]
for ai in a:
  safe[ai] = False
dp = [0 for i in range(N+1)]
dp[1] = 1 if safe[1] else 0
dp[2] = 1+dp[1] if safe[2] else 0
for i in range(3, N+1):
  dp[i] = (dp[i-2]+dp[i-1]) % d if safe[i] else 0
print(dp[N])

Submission status: Runtime Error

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

N, M = map(int, input().split())
L = set([int(input()) - 1 for _ in range(M)])
ans = [0] * N

if 0 not in L:
    ans[0] = 1
    
if 1 not in L:
    ans[1] = ans[0] + 1

for i in range(2, N):
    if i in L:
        continue
    
    if ans[i - 2] != 0 or ans[i - 1] != 0:
        ans[i] = ans[i - 2] + ans[i - 1]
        
print(ans[-1] % (1000000007))

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
pre_a = -1
k = []
ef = False
for i in range(M):
    a = int(input())
    if a == 1:pre_a = 1
    else:
        if a-pre_a == 1:
            ef = True
            break
        #print(a,pre_a)
        k.append(a-pre_a-2)
        #print(k)
        pre_a = a
else:
    if a < N:k.append(N-a-1)
#print(k)
nk = sorted(k)
#print('nk:',nk)
def fib(sorted_lis):
    t1 = 1
    t2 = 2
    retl = []
    fi = 0
    i = 0
    for k in range(max(sorted_lis)+1):
        if k == 0:fi = 1
        elif k == 1:fi = t1
        elif k == 2:fi = t2
        else:
            fi = t1 + t2
            t1 = t2
            t2 = fi
        while (i < len(sorted_lis)) and (sorted_lis[i] == k):
            retl.append(fi % 1000000007)
            i += 1
    return retl
if ef:print(0)
else:
    cl = fib(nk)
    #print(cl)
    g = 1
    for kk in cl:g = (g * kk) % 1000000007
    print(g)

Submission status: Runtime Error

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

ans=[0]*100001
ans[0]=1
if a[1]:
    ans[1]=0
else:
    ans[1]=1

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

Submission status: Runtime Error

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

mod = 10 ** 9 + 7

dp = [0] * 100010

j = 0
dp[0] = 1
if a[0] == 1:
    dp[1] = 0
    j += 1
else:
    dp[1] = 1

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

print(dp[N] % mod)

Submission status: Runtime Error

Solution code:
OK = "O"
BRO = "B"

N,M=map(int, input().split())
Broken=[int(input()) for i in range(M)]
K = "".join(list(BRO if i in Broken else OK for i in range(N+1)))
        
if BRO+BRO in K:
  print(0)
else:
  c=[0 for i in range(N+1)]
  if K[N-1]==OK:
    c[1]=1
  if K[N-2]==OK and K[N-1]==OK:
    c[2]=2
  if K[N-2]==OK and K[N-1]==BRO:
    c[2]=1

  for i in range(3,N+1):
    c[i]=(c[i-1]+c[i-2])%1000000007
  print(c[N])

Submission status: Runtime Error

Solution code:
import math
from functools import lru_cache

MOD = 1000000007


@lru_cache(None)
def fibo(x):
    if x <= 1:
        return 1
    return fibo(x - 2) + fibo(x - 1)


n, m = list(map(int, input().split(" ")))
a_list = [int(input()) for _ in range(m)]
ngs = [i in a_list for i in range(n)]
ngs.append(False)
for i in range(n):
    if ngs[i] and ngs[i + 1]:
        print(0)
        exit()
cnts = []
cnt = 0

for ng in ngs:
    if ng:
        cnts.append(cnt)
        cnt = 0
        continue
    cnt += 1
cnts.append(cnt)
ans = 1
for c in cnts:
    if c != 0:
        ans *= fibo(c - 1)
# print(ngs)
# print(cnts)
print(ans % MOD)

Submission status: Runtime Error

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

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

memo = [0] * (N)
def routes(n):
    if n == 1:
        if is_stairs[0]:
            return 1
        else:
            return 0
    if n == 2:
        if is_stairs[0] and is_stairs[1]:
            return 2
        elif not is_stairs[0] and is_stairs[1]:
            return 1
        else:
            return 0
    else:
        if memo[n-1]:
            return memo[n-1]
        else:
            if is_stairs[n-1]:
                memo[n-1] = routes(n-1) + routes(n-2)
                return memo[n-1]
            else:
                return 0

total = routes(N)
print(total % 1000000007)

Submission status: Runtime Error

Solution code:
OK = "O"
BRO = "B"

N,M=map(int, input().split())
Broken=[int(input()) for i in range(M)]
K = "".join(list(BRO if i in Broken else OK for i in range(N+1)))
        
if BRO+BRO in K:
  print(0)
else:
  c=[0 for i in range(N+1)]
  if K[N-1]==OK:
    c[1]=1
  if K[N-2]==OK and K[N-1]==OK:
    c[2]=2
  if K[N-2]==OK and K[N-1]==BRO:
    c[2]=1

  for i in range(3,N+1):
    if K[N-i]==OK:
      if K[N-i+1]==OK and K[N-i+2]==OK:
        c[i]=c[i-1]+c[i-2]
      if K[N-i+1]==OK and K[N-i+2]==BRO:
        c[i]=c[i-1]
      if K[N-i+1]==BRO and K[N-i+2]==OK:
        c[i]=c[i-2]
    c[i]%=1000000007
  
  print(c[N] % 1000000007)

Submission status: Runtime Error

Solution code:
OK = "O"
BRO = "B"

N,M=map(int, input().split())
Broken=[int(input()) for i in range(M)]
#K = "".join(list(BRO if i in Broken else OK for i in range(N+1)))
K = ""
for i in range(N+1):
    if i in Broken:
        K += BRO 
    else:
        K += OK
        
if BRO+BRO in K:
  print(0)
else:
  c=[0 for i in range(N+1)]
  if K[N-1]==OK:
    c[1]=1
  if K[N-2]==OK and K[N-1]==OK:
    c[2]=2
  if K[N-2]==OK and K[N-1]==BRO:
    c[2]=1

  for i in range(3,N+1):
    if K[N-i]==OK:
      if K[N-i+1]==OK and K[N-i+2]==OK:
        c[i]=c[i-1]+c[i-2]
      if K[N-i+1]==OK and K[N-i+2]==BRO:
        c[i]=c[i-1]
      if K[N-i+1]==BRO and K[N-i+2]==OK:
        c[i]=c[i-2]
  print(c[N] % 1000000007)

Submission status: Runtime Error

Solution code:
OK = "O"
BRO = "B"

N,M=map(int, input().split())
Broken=[int(input()) for i in range(M)]
K = "".join(list(BRO if i in Broken else OK for i in range(N+1)))

if BRO+BRO in K:
  print(0)
else:
  c=[0 for i in range(N+1)]
  if K[N-1]==OK:
    c[1]=1
  if K[N-2]==OK and K[N-1]==OK:
    c[2]=2
  if K[N-2]==OK and K[N-1]==BRO:
    c[2]=1

  for i in range(3,N+1):
    if K[N-i]==OK:
      if K[N-i+1]==OK and K[N-i+2]==OK:
        c[i]=c[i-1]+c[i-2]
      if K[N-i+1]==OK and K[N-i+2]==BRO:
        c[i]=c[i-1]
      if K[N-i+1]==BRO and K[N-i+2]==OK:
        c[i]=c[i-2]
  print(c[N] % 1000000007)

Submission status: Runtime Error

Solution code:
STR = input().split()
N = int(STR[0])
M = int(STR[1])
Flag = True
a = []
a.append(-1)
for i in range(M):
    a.append(int(input()))
a.append(N+1)

for i in range(M+1):
    if (a[i+1]-a[i]) == 1:
        Flag = False

fib = []
fib.append(1)
fib.append(1)

for i in range(2,N):
    fib.append(fib[i-1] + fib[i-2])

SUM = 1
num = 0
for i in range(1,M+2):
    num = a[i]-1 - (a[i-1] +1)
    #print(a[i]-1)
    #print(a[i-1]+1)
    SUM = SUM * fib[num] % 1000000007
    #print(num)
    
if Flag:
    print(SUM)
else:
    print(0)

Submission status: Runtime Error

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

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

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

print(dp[n]%1000000007)