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

    a = 0
    b = 1
    j = 0
    tmp = 0
    if N == 1:
        print(1)
    else:
        for i in range(1, N + 1):
            if A[j] == i:
                if tmp == 1:
                    print(0)
                    exit()
                tmp = 1
                j += 1
                a = 0
            else:
                if tmp == 1:
                    b = a + b
                    a = 0
                else:
                    c = a + b
                    a = b
                    b = c
                tmp = 0
        print(c % 1000000007)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

if n+1 < 2*m:
    print(0)
else:
    a = [int(input()) for _ in range(m)]

    pre2 = 0
    pre1 = 0
    cur = 1
    a_id = 0

    for i in range(n):
        pre2 = pre1
        pre1 = cur 
        cur = pre1 + pre2
        if i+1 == a[a_id]:
            a_id += 1 if a_id < m-1 else 0
            cur = 0
        if cur == 0 and pre1 == 0:
            break
    print(cur%1000000007)

Submission status: Runtime Error

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

pre2 = 0
pre1 = 0
cur = 1
a_id = 0

for i in range(n):
    pre2 = pre1
    pre1 = cur 
    cur = pre1 + pre2
    if i+1 == a[a_id]:
        a_id += 1 if a_id < m-1 else 0
        cur = 0
    if cur == 0 and pre1 == 0:
        break
print(cur%1000000007)

Submission status: Runtime Error

Solution code:
n, m = map(int, raw_input().split())
A = [int(raw_input()) for i in range(m)]
def solve(n, A):
  dp = [0] * (n + 1)
  ai = 0
  if ai < len(A) and A[ai] == 1:
    dp[1] = -1
    ai += 1
  else:
    dp[1] = 1
  if ai < len(A) and A[ai] == 2:
    dp[2] = -1
    ai += 1
  elif dp[1] != -1:
    dp[2] = 2
  else:
    dp[2] = 1
  for i in range(3, n + 1):
    if ai < len(A) and A[ai] == i:
      dp[i] = -1
      ai += 1
      continue
    if dp[i-2] != -1:
      dp[i] = dp[i-2] 
    if dp[i-1] != -1:
      dp[i] += dp[i-1]
  return dp[n] % (10**9+7)
print solve(n, A)

Submission status: Runtime Error

Solution code:
import sys

readline = sys.stdin.readline

N, M = map(int, readline().split())
A = [int(readline()) for i in range(M)]
P = 1000000007

A = A + [N + 1]
ans = 1

assert N < 90000

current = 0

_count = 0
for a in A:
    diff = a - 1 - current
    current = a + 1

    if diff < 0:
        ans = 0
        break
    
    s = 1
    s_total = 1
    for x in range(1, diff // 2 + 1):
        _count += 1
        y = diff - x * 2
        s = s * (y + 1) * (y + 2) // (x + y + 1) // x
        s = s % P
        s_total = (s_total + s) % P
    
    ans = (ans * s_total) % P

print(ans)

Submission status: Runtime Error

Solution code:
import sys

readline = sys.stdin.readline

N, M = map(int, readline().split())
A = [int(readline()) for i in range(M)]
P = 1000000007

A = A + [N + 1]
ans = 1

assert N < 99999

current = 0

_count = 0
for a in A:
    diff = a - 1 - current
    current = a + 1

    if diff < 0:
        ans = 0
        break
    
    s = 1
    s_total = 1
    for x in range(1, diff // 2 + 1):
        _count += 1
        y = diff - x * 2
        s = s * (y + 1) * (y + 2) // (x + y + 1) // x
        s_total = s_total + s
    
    ans = (ans * s_total) % P

print(ans)

Submission status: Runtime Error

Solution code:
import sys

readline = sys.stdin.readline

N, M = map(int, readline().split())
A = [int(readline()) for i in range(M)]
P = 1000000007

A = A + [N + 1]
ans = 1

assert N < 95000

current = 0

_count = 0
for a in A:
    diff = a - 1 - current
    current = a + 1

    if diff < 0:
        ans = 0
        break
    
    s = 1
    s_total = 1
    for x in range(1, diff // 2 + 1):
        _count += 1
        y = diff - x * 2
        s = s * (y + 1) * (y + 2) // (x + y + 1) // x
        s_total = s_total + s
    
    ans = (ans * s_total) % P

print(ans)

Submission status: Runtime Error

Solution code:
import sys

readline = sys.stdin.readline

N, M = map(int, readline().split())
A = [int(readline()) for i in range(M)]
P = 1000000007

A = A + [N + 1]
ans = 1

assert N < 90000

current = 0

_count = 0
for a in A:
    diff = a - 1 - current
    current = a + 1

    if diff < 0:
        ans = 0
        break
    
    s = 1
    s_total = 1
    for x in range(1, diff // 2 + 1):
        _count += 1
        y = diff - x * 2
        s = s * (y + 1) * (y + 2) // (x + y + 1) // x
        s_total = s_total + s
    
    ans = (ans * s_total) % P

print(ans)

Submission status: Runtime Error

Solution code:
import sys

readline = sys.stdin.readline

N, M = map(int, readline().split())
A = [int(readline()) for i in range(M)]
P = 1000000007
assert len(A) < 90000
A = A + [N + 1]
ans = 1

current = 0

_count = 0
for a in A:
    diff = a - 1 - current
    current = a + 1

    if diff < 0:
        ans = 0
        break
    
    s = 1
    s_total = 1
    for x in range(1, diff // 2 + 1):
        _count += 1
        y = diff - x * 2
        s = s * (y + 1) * (y + 2) // (x + y + 1) // x
        s_total = s_total + s
    
    ans = (ans * s_total) % P

print(ans)

Submission status: Runtime Error

Solution code:
import sys

readline = sys.stdin.readline

N, M = map(int, readline().split())
A = [int(readline()) for i in range(M)]
P = 1000000007
assert len(A) < 10000
A = A + [N + 1]
ans = 1

current = 0

_count = 0
for a in A:
    diff = a - 1 - current
    current = a + 1

    if diff < 0:
        ans = 0
        break
    
    s = 1
    s_total = 1
    for x in range(1, diff // 2 + 1):
        _count += 1
        y = diff - x * 2
        s = s * (y + 1) * (y + 2) // (x + y + 1) // x
        s_total = s_total + s
    
    ans = (ans * s_total) % P

print(ans)

Submission status: Runtime Error

Solution code:
import sys

readline = sys.stdin.readline

N, M = map(int, readline().split())
A = [int(readline()) for i in range(M)]
P = 1000000007

A = A + [N + 1]
ans = 1

current = 0

_count = 0
for a in A:
    diff = a - 1 - current
    current = a + 1

    if diff < 0:
        ans = 0
        break
    
    s = 1
    s_total = 1
    for x in range(1, diff // 2 + 1):
        _count += 1
        if _count > 1000:
            assert False
        y = diff - x * 2
        s = s * (y + 1) * (y + 2) // (x + y + 1) // x
        s_total = s_total + s
    
    ans = (ans * s_total) % P

print(ans)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
max_int = 1000000007
a = [0] * m
for i in range(m):
    a[i] = int(input())
piv = 0
b = [1] * (n+1)
if a[0] == 1:
    piv += 1
    b[1] = 0
for i in range(2,n+1):
    if piv == m:
        b[i] = b[i-1] + b[i-2]
        b[i] %= max_int
    elif i == a[piv]:
        piv += 1
        b[i] = 0
    else:
        b[i] = b[i-1] + b[i-2]
        b[i] %= max_int

print(b[n]%max_int)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
max_int = 1000000007
a = [0] * m
for i in range(m):
    a[i] = int(input())
piv = 0
b = [1] * (n+1)
if a[0] == 1:
    piv += 1
    b[1] = 0
for i in range(2,n+1):
    if piv == m:
        b[i] = b[i-1] + b[i-2]
        #b[i] %= max_int
    elif i == a[piv]:
        piv += 1
        b[i] = 0
    else:
        b[i] = b[i-1] + b[i-2]
        #b[i] %= max_int

print(b[n]%max_int)

Submission status: Runtime Error

Solution code:



class MyClass:
    patternCount = 0

    def skip(self, maxNum, currentIndex):
        if currentIndex > maxNum or currentIndex in brokenIndexList:
            return
        
        if maxNum == currentIndex:
            self.patternCount += 1
            return

        self.skip(maxNum, currentIndex + 1)
        self.skip(maxNum, currentIndex + 2)

maxNum, brokenCount= map(int, input().split())

brokenIndexList = []
for i in range(brokenCount):
    brokenIndexList.append(int(input()))

if maxNum == 0:
    print(0)

c = MyClass()
c.skip(maxNum, 0)

result = c.patternCount % 1000000007
print(result)

Submission status: Runtime Error

Solution code:



class MyClass:
    patternCount = 0

    def skip(self, maxNum, currentIndex):
        if currentIndex > maxNum or currentIndex in brokenIndexList:
            return
        
        if maxNum == currentIndex:
            self.patternCount += 1
            return

        self.skip(maxNum, currentIndex + 1)
        self.skip(maxNum, currentIndex + 2)

maxNum, brokenCount= map(int, input().split())

brokenIndexList = []
for i in range(brokenCount):
    brokenIndexList.append(int(input()))

if maxNum == 0:
    print(0)

c = MyClass()
c.skip(maxNum, 0)

print(c.patternCount)

Submission status: Runtime Error

Solution code:
N, M = map(int,input().split(' '))
a = [int(input()) for i in range(M)]
for i in range(M-1):
  if a[i]+1 == a[i+1]:
    print(0)
    exit()
def step(n):
  if n == 0 :
    return 1
  elif n == 1 :
    return 2
  tmp = [0]*n
  tmp[0] = 1
  tmp[1] = 2
  for i in range(2,n):
    tmp[i] = tmp[i-2] + tmp[i-1]
  return tmp[n-1]
ans = step(a[0]-1)
for i in range(1,M):
  n = a[i] - a[i-1] - 2
  ans = ans*step(n)
n = N - a[M-1] -1
ans = ans*step(n)

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

Submission status: Runtime Error

Solution code:
N, M = map(int,input().split(' '))
a = [int(input()) for i in range(M)]
for i in range(M-1):
  if a[i]+1 == a[i+1]:
    print(0)
    exit()
def step(n):
  if n == 0 :
    return 1
  elif n == 1 :
    return 2
  tmp = [0]*n
  tmp[0] = 1
  tmp[1] = 2
  for i in range(2,n):
    tmp[i] = tmp[i-2] + tmp[i-1]
  return tmp[n-1]
ans = step(a[0]-1)
for i in range(1,M):
  n = a[i] - a[i-1] - 2
  ans = ans*step(n)
n = N - a[M-1] -1
ans = ans*step(n)

print(ans%(10**9+7))
print([step(i) for i in range(6)])

Submission status: Runtime Error

Solution code:
N, M = map(int,input().split(' '))
a = [int(input()) for i in range(M)]
for i in range(M-1):
  if a[i]+1 == a[i+1]:
    print(0)
    exit()
def step(n):
  if n <= 1 :
    return 1
  tmp = [0]*n
  tmp[0] = 1
  tmp[1] = 2
  for i in range(2,n):
    tmp[i] = tmp[i-2] + tmp[i-1]
  return tmp[n-1]
ans = step(a[0]-1)
for i in range(1,M):
  n = a[i] - a[i-1] - 2
  ans = ans*step(n)
n = N - a[M-1] -1
ans = ans*step(n)

print(ans%(10**9+7))
print([step(i) for i in range(6)])

Submission status: Runtime Error

Solution code:
class MyClass:
    patternCount = 0

    def skip(self, maxNum, currentIndex):
        if currentIndex >= maxNum or currentIndex in brokenIndexList:
            return
        
        if maxNum -1 == currentIndex:
            self.patternCount += 1
            return

        self.skip(maxNum, currentIndex + 1)
        self.skip(maxNum, currentIndex + 2)

maxNum, brokenCount= map(int, input().split())

brokenIndexList = []
for i in range(brokenCount):
    brokenIndexList.append(int(input()))

if maxNum == 0:
    print(0)

c = MyClass()
c.skip(maxNum, -1)

print(c.patternCount)

Submission status: Runtime Error

Solution code:
N, M = map(int,input().split(' '))
a = [int(input()) for i in range(M)]
for i in range(M-1):
  if a[i]+1 == a[i+1]:
    print(0)
    exit()
def step(n):
  if n == 0:
    return 1
  tmp = [0]*n
  tmp[0] = 1
  tmp[1] = 2
  if n == 1:
    return 2
  for i in range(2,n):
    tmp[i] = tmp[i-2] + tmp[i-1]
  return tmp[n-1]
ans = step(a[0]-1)
for i in range(1,M):
  n = a[i] - a[i-1] - 2
  ans = ans*step(n)
n = N - a[M-1] -1
ans = ans*step(n)

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import sys
from math import factorial
#nCi
def com(n, i):
    return int(factorial(n)/factorial(i)/factorial(n-i))
    
def cal1(num):
    total = 1
    if num < 1: return total
    if num == 1: return 2
    large_num = num
    for small_num in range(1, num):
        if small_num > large_num: break
        total += com(large_num, small_num)
        large_num -= 1
    return total

def main():
    N, M = map(int, input().split())
    len_list = []
    pre_a = -1
    for m in range(M):
        a = int(input())
        if (pre_a + 1) == a: sys.exit("0")
        len_list.append(a-(pre_a+3))
        pre_a = a
    len_list.append(N-(pre_a+2))
    ans = 1
    for num in len_list:
        ans *= cal1(num)
    print(ans%1000000007)
    
main()

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
out=[]
for i in range(m):
  out.append(int(input()))
def stairs(n):
  memo=["a"]*n
  def count(n):
    if n in out:
      return 0
    elif n<=2:
      return n
    else memo[n-1]!="a":
      return memo[n-1]%(10e9+7)
    return (memo[n-2]+memo[n-3])%(10e9+7)
  return count(n)
print(stairs(n)%(10e9+7))

Submission status: Runtime Error

Solution code:
def calc_Stairs_Patterns(num):
    if num >= 2:
        return calc_Stairs_Patterns(num - 1) + calc_Stairs_Patterns(num - 2)
    elif num == -1:
        print(0)
        exit()
    else:
        return 1
N, M = map(int,input().split())
data = []
for i in range(M):
    data.append(int(input()))
ans = 1
stair = 0
for i in data:
    ans *= calc_Stairs_Patterns(i  - 1 - stair)
    stair = i + 1
ans *= calc_Stairs_Patterns(N - stair)
print(ans % 1000000007)

Submission status: Runtime Error

Solution code:
def calc_Stairs_Patterns(num):
    if num >= 2:
        return calc_Stairs_Patterns(num - 1) + calc_Stairs_Patterns(num - 2)
    elif num == -1:
        print(0)
        exit()
    else:
        return 0
N, M = map(int,input().split())
data = []
for i in range(M):
    data.append(int(input()))
ans = 1
stair = 0
for i in data:
    ans *= calc_Stairs_Patterns(i  - 1 - stair)
    stair = i + 1
ans *= calc_Stairs_Patterns(N - stair)
print(ans % 1000000007)

Submission status: Runtime Error

Solution code:
def calc_Stairs_Patterns(num):
    if num >= 2:
        return calc_Stairs_Patterns(num - 1) + calc_Stairs_Patterns(num - 2)
    elif num == 1:
        return 1
    else :
        return 1
N, M = map(int,input().split())
data = []
for i in range(M):
    data.append(int(input()))
bef = 0
for i in data:
    if bef + 1 == i:
        print(0)
        exit()

ans = 1
stair = 0
for i in data:
    ans *= calc_Stairs_Patterns(i  - 1 - stair)
    stair = i + 1
ans *= calc_Stairs_Patterns(N - stair)
print(ans % 1000000007)

Submission status: Runtime Error

Solution code:
N, M = map(int,input().split())
data = []
for i in range(M):
    data.append(int(input()))
bef = 0
for i in data:
    if bef + 1 == i:
        print(0)
        exit()
    bef = i
print(int(2 ** ((N - M * 2) / 2)) % 1000000007)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
a=[]
for i in range(0,m):
    a.append(input())
    a[i]=int(a[i])
b=[a[0]-1]
for i in range(1,len(a)):
    b.append(a[i]-a[i-1]-1)
b.append(n-a[i]-1)
c,d=0,1
e=b
for i in range(0,max(b)):
    c,d=d,c+d
    for k in range(0,len(b)):
        if b[k]==i+1:
            e[k]=d
answer=1
for i in range(0,len(e)):
    answer=answer*e[i]
print(answer)

Submission status: Runtime Error

Solution code:
import sys

input = sys.stdin
N, W = input().split()
aArr = list()
ans = 0
tmp = int(N)
MOD = 10 ** 9 + 7
aArr = set(map(int, input()))

tmp = 0
tmpB = 0
ans = 1
for i in range(int(N)):
    if (i in aArr):
        tmp = 0
    elif i < 2:
        tmp = 1
    else:
        tmp = ans
    ans = (tmp + tmpB) % MOD
    tmpB = tmp
print(ans)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
a_list=[]
for i in range(0,m):
     a_list.append(int(input()))
a=0
b=1
k=0
for i in range(0,n):
    if a_list[k]!=i+1:
        (a,b)=(b,a+b)
    else:
        (a,b)=(b,0)
        if k<m-1:
            k=k+1
print(b)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
a_list=[]
for i in range(0,m):
  a_list.append(int(input()))
a=0
b=1
k=0
for i in range(0,n):
  if a_list[k]!=i+1:
  	(a,b)=(b,a+b)
  else:
    k=k+1
    (a,b)=(b,0)
print(b)

Submission status: Runtime Error

Solution code:
import sys

import numpy as np
MOD = 1000000007

def main():
  n, m = [int(x) for x in input().split()]
  pattern = [1]
  broken = -1
  brokencnc = 0
  if brokencnt < m:
    broken = int(input())
    brokencnt += 1

  for i in range(1, n + 1):
    if i == boken:
      pattern.append(0)
      if brokencnc < m:
        broken = int(input())
        brokencnt += 1
      continue
      
      if i == 1:
        pattern.append(pattern[i-1])
        
      if i > 1:
        pattern.append((pattern[i-1] + pattern[i-2])%MOD)
    print(pattern[n])
 main()

Submission status: Runtime Error

Solution code:
import sys
from math import factorial

def cal2(n, i):
    return int(factorial(n)/factorial(i)/factorial(n-i))
    
def cal1(num):
    total = 1
    if num < 1: return total
    if num == 1: return 2
    i = num
    for n in range(1, num):
        if n > i: return total
        total += cal2(i, n)
        i -= 1

def main():
    N, M = map(int, input().split())
    len_list = []
    pre_a = -1
    for m in range(M):
        a = int(input())
        if (pre_a + 1) == a: sys.exit("0")
        len_list.append(a-(pre_a+3))
        pre_a = a
    len_list.append(N-(pre_a+2))
    ans = 1
    for num in len_list:
        ans *= cal1(num)
    print(ans%1000000007)
    
main()

Submission status: Runtime Error

Solution code:
def dp(p, a, memo):
    if p in memo.keys():
        return memo[p]
    elif p == 0 or p == 1:
        return 1
    else:
        ans = 0
        if p in a:
            ans = 0
        else:
            ans = dp(p-1, a, memo) + dp(p-2, a, memo)
        memo[p] = ans
        return ans

# input
n, m = map(int, input().split())
a = [int(input()) for i in range(m)]
memo = {}
print(dp(n, a, memo) % (10**9+7))

Submission status: Runtime Error

Solution code:
def dp(p, a, memo):
    if p in memo.keys():
        return memo[p]
    else:
        ans = 0
        if p == 0:
            return 1
        else:
            if p in a:
                ans = 0
            else:
                ans = dp(p-1, a, memo) + dp(p-2, a, memo)
            memo[p] = ans
            return ans

# input
n, m = map(int, input().split())
a = [map(int, input().split()) for i in range(m)]
memo = {}

print(dp(n, a, memo) % (10**9+7))

Submission status: Runtime Error

Solution code:
# C - Typical Stairs
# import numpy as np

def dp(p, a, memo):
    if p in memo.keys():
        return memo[p]
    else:
        ans = 0
        if p == 0:
            return 1
        else:
            if p in a:
                ans = 0
            else:
                ans = dp(p-1, a, memo) + dp(p-2, a, memo)
            memo[p] = ans
            return ans

# input
n, m = map(int, input().split())
a = [int(input()) for i in range(m)]
memo = {}

print(dp(n, a, memo) % (10**9+7))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# c ABC129
# input


def endFib(n, a1=1, a2=0):
    if n < 1:
        return a1
    else:
        return endFib(n-1, a1 + a2, a1)


n, m = map(int, input().split())
mod = 10**9+7
o = 1
p = 0
if m == 0:
    if n < 3:
        o = n % mod
    else:
        o = endFib(n) % mod

elif m > 0:
    ft = int(input())
    if ft < 3:
        p = ft
    elif ft == 3:
        o = 2 % mod
        p = ft
    elif ft > 3:
        o = endFib(ft-1) % mod
        p = ft
    else:
        p = ft

    for i in range(m-1):
        t = int(input())
        if t-1-p == 0:
            print(0)
            exit()
        elif t-1-p == 1:
            p = t
        elif t-1-p == 2:
            p = t
        elif t-1-p == 3:
            o = (o * 2) % mod
            p = t
        elif t-1-p > 3:
            o = (o * endFib(t-2-p)) % mod
            p = t
        else:
            pass
    if n-p > 3:
        o = (o * endFib(n-p-1)) % mod
    elif n-p == 3:
        o = (o * 2) % mod
    else:
        pass

print(int(o))

Submission status: Runtime Error

Solution code:
# C - Typical Stairs
import numpy as np

n, m = map(int, input().split())
a = [int(input()) for i in range(m)]
memo = {}

def dp(p, a, memo):
    if p in memo.keys():
        return memo[p]
    else:
        ans = 0
        if p == 0:
            return 1
        elif p == 1:
            return 1
        else:
            if p-1 in a:
                ans = dp(p-2, a, memo)
            elif p-2 in a:
                ans = dp(p-1, a, memo)
            else:
                ans = dp(p-1, a, memo) + dp(p-2, a, memo)
        memo[p] = ans
        return ans

Zero = False
for i in range(m-1):
    if a[i+1] - a[i] == 1:
        Zero = True

if Zero:
    print(0)
else:    
    print(dp(n, a, memo) % (10**9+7))

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(500000)
N, M = map(int, input().rstrip().split())
a = [int(input())for _ in range(M)]
dp = [-1 for _ in range(N + 1)]
if N == 1:
    print(1)
    exit()
dp[0] = 0
dp[1] = 1
def loop(n):
    if n <= 0:
        return 1
    if dp[n] >= 0:
        return dp[n]
    ans = 0
    for i in range(1, 3):
        if n - i < 0:
            return 1
        if n - i in a:
            continue
        ans += loop(n - i)
        ans %= 1000000007

    dp[n] = ans
    return dp[n]

x = a[0]
for i in a:
    if i == x + 1:
        print(0)
        exit()

    x = i
loop(N)
print(dp[N])

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(500000)
N, M = map(int, input().rstrip().split())
a = [int(input())for _ in range(M)]
dp = [-1 for _ in range(N + 1)]
if N == 1:
    print(1)
    exit()
dp[0] = 0
dp[1] = 1
def loop(n):
    if n <= 0:
        return 1
    if dp[n] >= 0:
        return dp[n]
    ans = 0
    for i in range(1, 3):
        if n - i in a:
            continue
        ans += loop(n - i)
        ans %= 1000000007

    dp[n] = ans
    return dp[n]

x = a[0]
for i in a:
    if i == x + 1:
        print(0)
        exit()

    x = i
loop(N)
print(dp[N])

Submission status: Runtime Error

Solution code:
MOD = 10**9+7
N, M = [int(x) for x in input().split()]
if (M != 0):
    a_list = [int(input()) for _ in range(M)]
dp = [0] * (N+1)
dp[0] = 1
dp[1] = int(not (1 in a_list))
for i in range(2, N+1):
    if (i not in a_list):
        dp[i] = (dp[i-1] + dp[i-2]) % MOD
print(dp[N])

Submission status: Runtime Error

Solution code:
inf = input().split()
N = int(inf[0])
M = int(inf[1])
ls = []
for i in range(M):
  a = int(input())
  ls += [a]
step = [0 for i in range(N)]
if 1 not in ls:
  step[0] = 1
if 2 not in ls:
  step[1] = 1 + step[0]
for j in range(2, N):
  if j not in ls:
    step[j] = step[j-1]+step[j-2]
  else:
    step[j] = 0
ans = step[N-1]%(10^9+7)
print(ans)

Submission status: Runtime Error

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

sys.setrecursionlimit(10**5)

breakstep = []

for _ in range(m):
    breakstep.append(int(input()))

sl = [-1 for _ in range(n+1)]

def solve(i):
    if sl[i] == -1:
        if i in breakstep:
            sl[i] = 0
        elif i in [0, 1]:
            sl[i] = 1
        else:
            sl[i] = (solve(i-1) + solve(i-2)) % 1000000007
    return sl[i]

print(solve(n))

Submission status: Runtime Error

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

breakstep = []

for _ in range(m):
    breakstep.append(int(input()))

sl = [-1 for _ in range(n+1)]
def solve(i):
    if sl[i] == -1:
        if i in breakstep:
            sl[i] = 0
        elif i in [0, 1]:
            sl[i] = 1
        else:
            sl[i] = (solve(i-1) + solve(i-2)) % 1000000007
    return sl[i]

print(solve(n))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**6)
from functools import lru_cache

@lru_cache(maxsize=10000000)
n,m=map(int,input().split())
A = [int(input()) for i in range(m)]
mod = 10**9+7
memo={}
memo[1]=1
memo[0]=1

def fib(n):
  if n in A:
  	memo[n]=0
  	return memo[n]
  if n not in memo:
    memo[n] = fib(n-1) + fib(n-2)
  return memo[n]

print(fib(n)%mod)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
A = [int(input()) for i in range(m)]
mod = 10**9+7
memo={}
memo[1]=1
memo[0]=1

def fib(n):
  if n in A:
  	memo[n]=0
  	return memo[n]
  if n not in memo:
    memo[n] = fib(n-1) + fib(n-2)
  return memo[n]

print(fib(n)%mod)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
A = [int(input()) for i in range(m)]
mod = 1000000007
memo={}
memo[1]=1

def fib(n):
  if n < 1:
    return 1
  if n in A:
  	memo[n]=0
  	return memo[n]
  if n not in memo:
    memo[n] = fib(n-1) + fib(n-2)
  return memo[n]

print(fib(n)%mod)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
if M != 0:
    chk = int(input())
else :
    chk = 0
ans1 = 1
count = 0
if chk == 1:
    ans2 = 0
    chk = int(input())
    count += 1
else:
    ans2 = 1
for i in range(N-1):
    if chk == i+2:
        ans1 = ans2
        ans2 = 0
        count += 1
        if count != M:
            chk = int(input())
    else:
        tempo = ans2
        ans2 = ans1 + ans2
        ans1 = tempo
print(ans2%1000000007)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
chk = int(input())
ans1 = 1
count = 0
if chk == 1:
    ans2 = 0
    chk = int(input())
    count += 1
else:
    ans2 = 1
for i in range(N-1):
    if chk == i+2:
        ans1 = ans2
        ans2 = 0
        count += 1
        if count != M:
            chk = int(input())
    else:
        tempo = ans2
        ans2 = ans1 + ans2
        ans1 = tempo
print(ans2%1000000007)

Submission status: Runtime Error

Solution code:
import re  # 正規表現, findall('正規表現', 文字列), search('正規表現', 文字列)
import sys # プログラム終了: sys.exit()
# sys.setrecursionlimit(10**6) # 再帰呼び出しの上限を上げる
import math # 階乗: math.factorial()

def i_input(): return int(input())
def s_input(): return map(int,input().split())
def l_input(): return list(map(int, input().split()))
# 文字列のまま受け取りたいときはinput()

def main():
    N, M = s_input()
    A = []
    for _ in range(M):
        A.append(i_input())

    # 0段目を含む
    dp = [0] * (N + 1)

    # 初期化
    a_count = 0
    dp[0] = 1
    if M > 0:
        if A[0] == 1:
            dp[1] = 0
            a_count += 1
        else:
            dp[1] = 1
    else:
        A = [0]

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

    print(int(dp[-1] % 1000000007))

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import re  # 正規表現, findall('正規表現', 文字列), search('正規表現', 文字列)
import sys # プログラム終了: sys.exit()
# sys.setrecursionlimit(10**6) # 再帰呼び出しの上限を上げる
import math # 階乗: math.factorial()

def i_input(): return int(input())
def s_input(): return map(int,input().split())
def l_input(): return list(map(int, input().split()))
# 文字列のまま受け取りたいときはinput()

def main():
    N, M = s_input()
    A = []
    for _ in range(M):
        A.append(i_input())

    if M == 0:
        print(int(N % 1000000007))
        sys.exit()

    # 0段目を含む
    dp = [0] * (N + 1)

    # 初期化
    a_count = 0
    dp[0] = 1
    if A[0] == 1:
        dp[1] = 0
        a_count += 1
    else:
        dp[1] = 1

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

    print(int(dp[-1] % 1000000007))

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import re  # 正規表現, findall('正規表現', 文字列), search('正規表現', 文字列)
import sys # プログラム終了: sys.exit()
# sys.setrecursionlimit(10**6) # 再帰呼び出しの上限を上げる
import math # 階乗: math.factorial()

def i_input(): return int(input())
def s_input(): return map(int,input().split())
def l_input(): return list(map(int, input().split()))
# 文字列のまま受け取りたいときはinput()

def main():
    N, M = s_input()
    A = []
    for _ in range(M):
        A.append(i_input())

    # 0段目を含む
    dp = [0] * (N + 1)

    # 初期化
    a_count = 0
    dp[0] = 1
    if A[0] == 1:
        dp[1] = 0
        a_count += 1
    else:
        dp[1] = 1

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

    print(int(dp[-1] % 1000000007))

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import re  # 正規表現, findall('正規表現', 文字列), search('正規表現', 文字列)
import sys # プログラム終了: sys.exit()
# sys.setrecursionlimit(10**6) # 再帰呼び出しの上限を上げる
import math # 階乗: math.factorial()

def i_input(): return int(input())
def s_input(): return map(int,input().split())
def l_input(): return list(map(int, input().split()))
# 文字列のまま受け取りたいときはinput()

def main():
    N, M = s_input()
    A = []
    for _ in range(M):
        A.append(i_input())

    # 0段目を含む
    dp = [0] * (N + 1)

    # 初期化
    dp[0] = 1
    if A[0] == 1:
        dp[1] = 0
    else:
        dp[1] = 1

    for i in range(2, N + 1):
        # print(dp)
        if i in A:
            # print('a', i)
            dp[i] = 0
        else:
            dp[i] = dp[i - 1] + dp[i - 2]

    print(int(dp[-1] % 1000000007))

if __name__ == "__main__":
    main()