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 Fib(n):    
    if n == 2 or n == 3:
        return 1
    else:
        return Fib(n - 1) + Fib(n - 2)
    
N, M = map(int, input().split())
S = [-1]
for i in range(M):
    S.append(int(input()))
S.append(N + 1)
S = [S[i + 1] - S[i] for i in range(M + 1)]
if any([x == 1 for x in S]):
    print(0)
    exit()
num = 1
for x in S:
    num *= Fib(x)
    num = num % 1000000007
print(num)

Submission status: Runtime Error

Solution code:
MOD = 10**9 + 7
N,M = map(int, input().split())
a = [int(input()) for _ in range(M)]

aa = [True] * (N+1)
for i in a:
    aa[i] = False

dp = [0] * (N+1)
dp[0] = 1
if aa[1]:
    dp[1] = 1

for i in range(2,N+1):
    if (aa[i] == False):
        dp[i] = 0
        continue
    dp[i] = dp[i-1] + dp[i-2]
    dp[i] =  dp[i] % MOD
print(dp[i])

Submission status: Runtime Error

Solution code:
MOD = 10**9 + 7
N,M = map(int, input().split())
a = [int(input()) for _ in range(M)]

aa = [True] * (N+1)
for i in a:
    aa[i] = False

dp = [0] * (N+1)
dp[0] = 1
dp[1] = 0
if aa[1]:
    dp[1] = 1

for i in range(2,N+1):
    if (aa[i] == False):
        dp[i] = 0
        continue
    dp[i] = dp[i-1] + dp[i-2]
    dp[i] %= MOD
print(dp[i])

Submission status: Runtime Error

Solution code:
MOD = 10**9 + 7
N,M = map(int, input().split())
a = [int(input()) for _ in range(M)]

aa = [True] * (N+1)
for i in a:
    aa[i] = False

dp = [0] * (N+1)
dp[0] = 1
if aa[1]:
    dp[1] = 1

for i in range(2,N+1):
    if (aa[i] == False):
        dp[i] = 0
        continue
    dp[i] = dp[i-1] + dp[i-2]
    dp[i] %= MOD
print(dp[i])

Submission status: Runtime Error

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

MOD = 10**9 + 7

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

dp = [0] * (N+1)
dp[0] = 1
dp[1] = 1
dp[2] = 2

aa = [True] * (N+1)
for i in a:
    aa[i] = False

for i in range(1,N+1):
    if (aa[i] == False):
        dp[i] = 0
        continue
    dp[i] = (dp[i-1]) + (dp[i-2])
print(dp[i]%MOD)

Submission status: Runtime Error

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

MOD = 10**9 + 7

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

dp = [0] * (N+1)
dp[0] = 1
dp[1] = 1
dp[2] = 2

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

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
a=[]
for i in range(m):
    A=int(input())
    a.append(A)
b=[0,1]
ans=1
for i in range(1,n+1):
    if i in a:
        b.append(0)
    else:
        b.append(b[i]+b[i-1])
    b[i]=b[i]%1000000007
    print(b)
print(b[len(b)-1]%1000000007)

Submission status: Runtime Error

Solution code:
def Fib(n):    
    if n == 2 or n == 3:
        return 1
    else:
        return Fib(n - 1) + Fib(n - 2)
    
N, M = map(int, input().split())
S = [-1]
for i in range(M):
    S.append(int(input()))
S.append(N + 1)
S = [S[i + 1] - S[i] for i in range(M + 1)]
if any([x == 1 for x in S]):
    print(0)
    exit()
num = 1
for x in S:
    num *= Fib(x)
print(num % 1000000007)

Submission status: Runtime Error

Solution code:
def fibona(x):
    import math
    return (((1/2+math.sqrt(5)/2)**(x+1))-((1/2-math.sqrt(5)/2)**(x+1))) // math.sqrt(5)

def main():
    n, m = map(int,input().split())
    mlis = []
    for _ in range(m):
        a = int(input())
        mlis.append(a)
    ans = 1
    mae = -1

    for i in range(m):
        broken = mlis[i]
        if mae == broken - 1:
            print(0)
            exit()
        nobori = (broken-1) - (mae+1)
        if nobori == 0:
            ans *= 1
            mae = broken
        else:
            ans *= fibona(nobori)
            ans = int(ans)
            ans %= (10 ** 9 + 7)
            mae = broken
    nobori = n - (mae+1)
    ans *= fibona(nobori) 
    ans = int(ans)
    ans %= (10 ** 9 + 7)
    print(ans)

        
        



if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def fibona(x):
    import math
    return (((1/2+math.sqrt(5)/2)**(x+1))-((1/2-math.sqrt(5)/2)**(x+1)))//math.sqrt(5)

def main():
    n, m = map(int,input().split())
    mlis = []
    for _ in range(m):
        a = int(input())
        mlis.append(a)
    ans = 1
    mae = -1

    for i in range(m):
        broken = mlis[i]
        if mae == broken - 1:
            print(0)
            exit()
        nobori = broken - 1 - (mae + 1)
        if nobori == 0:
            ans *= 1
            mae = broken
        else:
            ans *= fibona(nobori)
            ans %= (10 ** 9 + 7)
            #print(i, broken, nobori, ans) 
            mae = broken
    nobori = n - (mae+1)
    ans *= fibona(nobori) 
    ans %= (10 ** 9 + 7)
    print(int(ans))

        
        



if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def fibona(x):
    import math
    return (((1/2+math.sqrt(5)/2)**(x+1))-((1/2-math.sqrt(5)/2)**(x+1)))//math.sqrt(5)

def main():
    n, m = map(int,input().split())
    mlis = []
    for _ in range(m):
        a = int(input())
        mlis.append(a)
    ans = 1
    mae = -1

    for i in range(m):
        broken = mlis[i]
        if mae == broken - 1:
            print(0)
            exit()
        nobori = broken - 1 - (mae + 1)
        if nobori == 0:
            ans *= 1
            mae = broken
        else:
            ans *= fibona(nobori)
            ans %= (10 ** 9 + 7)
            #print(i, broken, nobori, ans) 
            mae = broken
    nobori = n - (mae+1)
    ans *= fibona(nobori) 
    ans %= (10 ** 9 + 7)
    print(ans)

        
        



if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
MOD = 10**9 + 7

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

a = list(set(range(2, N+2)) - set(a))
for i in a:
    dp[i] = (dp[i-1] + dp[i-2]) % MOD
print(dp[N] % MOD)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
MOD = 10**9 + 7

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

a = set(range(2, N+2)) - set(a)
for i in a:
    dp[i] = (dp[i-1] + dp[i-2]) % MOD
print(dp[N] % MOD)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
a.sort()
MOD = 10**9 + 7

dp = [0] * (N+1)
dp[0] = 1
dp[1] = 1 if a[0]!=1 else 0

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

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
dp = [0]*(n+1)
dp[0] = 1
m_list = [int(input()) for _ in range(m)]
for i in range(1,n+1):
  if i==1:
    if i==m_list[0]:
      m_list.pop(0)
      dp[i]=0
    else:
      dp[i]=1
  elif m_list and i == m_list[0]:
    m_list.pop(0)
    dp[i] = 0
  else:
    dp[i] = (dp[i-1]+dp[i-2])% 1000000007
print(dp[-1])

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
a.sort()
MOD = 10**9 + 7

dp = [0] * (N+1)
dp[0] = 1
dp[1] = 1 if a[0]!=1 else 0

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import sys
from operator import itemgetter

sys.setrecursionlimit(10**9)
input = sys.stdin.readline

def ii(): return int(input())
def mi(): return map(int, input().split())
def lmi(): return list(map(int, input().split()))
def iif(n): return [int(input()) for _ in range(n)]
def lmif(n): return [list(map(int, input().split())) for _ in range(n)]
def ss(): return input().split()

def main():
    mod = 1000000007

    N, M = mi()
    A = iif(M)
    DA = []
    left = 0
    for i in range(M):
        da = A[i] - left
        if da == 0 and left != 0:
            print(0)
            return
        else:
            DA.append(da-1)
        left = A[i] + 1
    if A[-1] != N:
        DA.append(N - A[-1] - 1)

    F = [1, 1]
    for i in range(100000):
        F.append(F[i] + F[i+1])

    ans = 1
    for i in DA:
        ans *= F[i]

    print(ans % mod)

    return

main()

Submission status: Runtime Error

Solution code:
import sys
from operator import itemgetter

sys.setrecursionlimit(10**9)
input = sys.stdin.readline

def ii(): return int(input())
def mi(): return map(int, input().split())
def lmi(): return list(map(int, input().split()))
def iif(n): return [int(input()) for _ in range(n)]
def lmif(n): return [list(map(int, input().split())) for _ in range(n)]
def ss(): return input().split()

def main():
    mod = 1000000007

    N, M = mi()
    A = iif(M)
    DA = []
    left = 0
    for i in range(M):
        da = A[i] - left
        if da == 1 and left != 0:
            print(0)
            return
        else:
            DA.append(da-1)
        left = A[i] + 1
    if A[-1] != N:
        DA.append(N - A[-1] - 1)

    F = [1, 1]
    for i in range(100000):
        F.append(F[i] + F[i+1])

    ans = 1
    for i in DA:
        ans *= F[i]

    print(ans % mod)

    return

main()

Submission status: Runtime Error

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

flag = 1
# 連続して床が壊れている場合はたどり着けない
for i in range(M-1):
  if a[i+1]-a[i] == 1:
    flag = 0
    break
    
if flag == 0:
  print(0)
else:
  pos = 0
  count = 0
  
  for i in range(M):
    diff = a[i] - pos - 1
    if diff > 0:	# 現在地の次の次の段以上が壊れている場合
      two_step = 1
      count += 1
      while 2*two_step <= diff:
        tmp = 1
        for j in range(diff-two_step, 0, -1):
          tmp *= j
        for j in range(two_step, 0, -1):
          tmp /= j
        count += tmp
        two_step += 1
      pos += (diff+2)
    else:		# 現在地の次の段が壊れている場合
      count += 1
      pos += 2

  diff = N - pos
  two_step = 1
  count += 1
  while 2*two_step <= diff:
    tmp = 1
    for j in range(diff-two_step, 0, -1):
      tmp *= j
    for j in range(two_step, 0, -1):
      tmp /= j
    count += tmp
    two_step += 1
  print(int(count%(10**9+7)))

Submission status: Runtime Error

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

flag = 1
for i in range(M-1):
  if a[i+1]-a[i] == 1:
    flag = 0
    break
    
if flag == 0:
  print(0)
else:
  pos = 0
  count = 0
  
  for i in range(M):
    diff = a[i] - pos - 1
    if diff > 0:
      two_step = 1
      count += 1
      while 2*two_step <= diff:
        tmp = 1
        for j in range(diff-two_step, 0, -1):
          tmp *= j
        for j in range(two_step, 0, -1):
          tmp /= j
        count += tmp
        two_step += 1
      pos += (diff+2)

  diff = N - pos
  two_step = 1
  count += 1
  while 2*two_step <= diff:
    tmp = 1
    for j in range(diff-two_step, 0, -1):
      tmp *= j
    for j in range(two_step, 0, -1):
      tmp /= j
    count += tmp
    two_step += 1
  print(int(count%(10**9+7)))

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

dp = [0] * n
dp[0] = 1
if issafe[1]:
    dp[1] = 1

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

Submission status: Runtime Error

Solution code:
, m = map(int, input().split())
issafe = [True] * 10000
for _ in range(m):
    a = int(input())
    issafe[a] = False

dp = [0] * 10000
dp[0] = 1
if issafe[1]:
    dp[1] = 1

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

Submission status: Runtime Error

Solution code:
, m = map(int, input().split())
issafe = [True] * 10000
for _ in range(m):
    a = int(input())
    issafe[a] = False

dp = [0] * 10000
dp[0] = 1
if issafe[1]:
    dp[1] = 1

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

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
issafe = [True] * 10001
for _ in range(m):
    a = int(input())
    issafe[a] = False

dp = [0] * 10001
dp[0] = 1
if issafe[1]:
    dp[1] = 1

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

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
issafe = [True] * 10000
for _ in range(m):
    a = int(input())
    issafe[a] = False

dp = [0] * 10000
dp[0] = 1
if issafe[1]:
    dp[1] = 1

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

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
a = {int(input()) for _ in range(m)}

dp = [0] * 10000
dp[0] = 1
if 1 not in a:
    dp[1] = 1

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

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

    dp[i] %= 1000000007    
print(dp[n])

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
#ABC129C 動的計画法

n, m = map(int, input().split())
a = int(input()) for _ in range(m)

dp = [0] * 10000
dp[0] = 1
if 1 not in a:
    dp[1] = 1

for i in range(2, n + 1):
    if  (i - 1) not in a:
        print("/", dp[i])
        dp[i] = dp[i] + dp[i - 1]
        print("●  dp[{0}]={2}  dp[{1}]={3}".format(i-1, i, dp[i - 1],  dp[i]))
    if (i - 2) not in a:
        print("//", dp[i])
        dp[i] = dp[i - 2] + dp[i] 
        print("■  dp[{0}]={2}  dp[{1}]={3}".format(i-2, i, dp[i - 1],  dp[i]))
    
    print("dp[{0}]={1}".format(i, dp[i]))
    
    dp[i] %= 1000000007
    
print(dp[n])

Submission status: Runtime Error

Solution code:
import sys

def resolve():
    read = sys.stdin.read
    readline = sys.stdin.readline

    N, M = map(int, readline().split())
    a = [int(x) for x in read().split()]
    
    dp = [0] * N * 2
    dp[0] = 1
    for i in range(N):
        one = i + 1
        two = i + 2
        now = dp[i]
        if one not in a:
            dp[one] += now
        if two not in a:
            dp[two] += now
    print(dp[N] % 1_000_000_007)


resolve()

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
bad = []
for i in range(m):
    bad.append(int(input()))
dp = [0 for x in range(n+1)]
dp[0] = 1
idx = 0
if bad[0] == 1:
    dp[1] = 0
    idx = 1
else:
    dp[1] = 1

for i in range(2, n+1):
    if idx < m and i == bad[idx]:
        dp[i] = 0
        idx+=1
    else:
        dp[i] = (dp[i-1] + dp[i-2]) % 1000000007

print(dp[n])

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
a = list(map(int,input().split()))
lis = [1] + [0]*n

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

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
a = list(map(int,input().split()))
lis = [1] + [0]*n

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

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
 
N,M = list(map(int,input().split()))
A = [int(input()) for _ in range(M)]
 
a2 = 1
a1 = 0 if 1 in A else 1
i = 1
def stair(stepb2,stepb1):
    global i
    i+=1
    step = stepb2 + stepb1
    
    if i in A:
        step = 0
    if i == N:
        print(step%1000000007)
        return step
    else:
        stair(stepb1,step)
if N == 1:
    print(a1)
else:
    _ = stair(a2,a1)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
 
N,M = list(map(int,input().split()))
A = [int(input()) for _ in range(M)]
 
a2 = 1
a1 = 0 if 1 in A else 1
i = 1
def stair(stepb2,stepb1):
    global i
    i+=1
    step = stepb2 + stepb1
    
    if i in A:
        step = 0
    if i == N:
        print(step%1000000007)
        return step
    else:
        stair(stepb1,step)
_ = stair(a2,a1)

Submission status: Runtime Error

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

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

a2 = 1
a1 = 0 if 1 in A else 1 
for i in range(2,N+1):
    a = 0 if a in A else (a2+a1)%1000000007
    a2 = a1
    a1 = a
print(1 if N == 1 else a%1000000007)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
a = [0]*(N+1)
pass_list = [0]*(N+1)
for i in range(M):
    b = int(input())
    a[b] = 1
if(a[1] !=1):
    pass_list[1]=1
if(a[2] !=1):
    pass_list[2]=1
for i in range(2,N+1):
    if(a[i] != 1):
        pass_list[i] += pass_list[i-1]+pass_list[i-2]
print(pass_list[N]%1000000007)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
check = False
a = []
pass_list = [0]*(N+1)
a.append(int(input()))
for i in range(1,M):
    a.append(int(input()))
    
if(1 not in a):
    pass_list[1]=1
if(2 not in a):
    pass_list[2]=1
for i in range(2,N+1):
    if(i not in a):
        pass_list[i] += pass_list[i-1]+pass_list[i-2]
print(pass_list[N]%1000000007)

Submission status: Runtime Error

Solution code:
import sys


def read():
    return sys.stdin.readline().rstrip()


def main():
    n, m = map(int, read().split())
    a = {int(read()) - 1 for _ in range(m)}
    mod = 10**9 + 7
    dp = [0] * n
    if 0 not in a:
        dp[0] = 1
    if 1 not in a:
        dp[1] = 1 + dp[0]
    for i in range(2, n):
        if i in a:
            continue
        dp[i] = (dp[i - 1] + dp[i - 2]) % mod
    print(dp[-1])


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
def gcd(*numbers): reduce(math.gcd, numbers)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
count = 0
ans = 0
inf = float("inf")

def dpp(n):
    for i in range(2,n+1):
        if a[i] = 0:
            dp[i] = 0
        else:
            dp[i] = dp[i-1]+dp[i-2]
    return dp[n]

N,M = I()
a = [1]*(N +1)
for i in range(M):
    x = k()
    a[x] = 0

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

print(dpp(N) % mod)

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 a[0] != 1:
    dp[1] = 1
    
for i in range(2,n+1):
    if i not in a:
        dp[i] = dp[i-1] + dp[i-2]
        dp[i] %= 1000000007
        
print(dp[n])

Submission status: Runtime Error

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

dp = [0 for _ in range(n+1)]
dp[0] = 1
mod = 10**9 + 7

if m == 0:
    dp[0] = 1
    dp[1] = 1
    for i in range(2, n+1):
        dp[i] = (dp[i-1] + dp[i-2]) % mod
    print(dp[n])
    exit()

if an[0] == 1:
    dp[1] = 0
    a = 1
else:
    dp[1] = 1
    a = 0

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

print(dp[n])

Submission status: Runtime Error

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

dp = [0 for _ in range(n+1)]
dp[0] = 1
mod = 10**9 + 7

if m == 0:
    dp[0] = 1
    dp[1] = 1
    for i in range(2, n+1):
        dp[i] = (dp[i-1] + dp[i-2]) % mod
    print(dp[n])
    exit()

if an[0] == 1:
    dp[1] = 0
    a = 1
else:
    dp[1] = 1
    a = 0

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

print(dp[n])

Submission status: Runtime Error

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

dp = [0 for _ in range(n+1)]
dp[0] = 1
mod = 10**9 + 7

if an[0] == 1:
    dp[1] = 0
    a = 1
else:
    dp[1] = 1
    a = 0

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

print(dp[n])

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
set_A = set()
dp = [0]*n
mod = pow(10, 9) + 7

for _ in range(m):
    set_A.add(int(input()))

if 1 not in set_A:
    dp[0] = 1
if 2 not in set_A:
    dp[1] = 1 + dp[0]

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

print(dp[n-1])

Submission status: Runtime Error

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

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

ans = 1
ls = [-1]
for _ in range(m):
    ls.append(int(input()))
ls.append(n+1)
ms = []
for i in range(m+1):
    t = ls[i+1]-ls[i]-2
    ms.append(t)
for j in ms:
    ans *= a(j)
ans = ans %1000000007
print(ans)

Submission status: Runtime Error

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

S=[]
s=0
for m in range(M):
    e = int(input())
    S.append(list(range(s,e)))
    s = e+1

e = int(N+1)
S.append(list(range(s,e)))

fibo=[0,1]
for n in range(2,N+1):
    fibo.append(fibo[n-2]+fibo[n-1])
    
ans=1
for s in S:
    ans=ans*fibo[len(s)]
print(ans%1000000007)

Submission status: Runtime Error

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

MOD = 10**9+7

dp = [0]*(n+1)
ng = [False]*(n+1)
for i in a:
    ng[a] = True
    
dp[0] = 1
if not ng[1]:
    dp[1] = 1
for i in range(2, n+1):
    if a[i]:
        continue
    else:
        dp[i] = (dp[i-1] + dp[i-2]) % MOD
print(dp[n])

Submission status: Runtime Error

Solution code:
n,m=map(int, input().split())
a=[]
for i in  range(m):
    a.append(int(input()))
dp=[[0]*(n+1)]
dp[0]=1
for i in range(1,n+1):
    if i in a:
        continue
        x=dp[i-1]
        if i>1:
            dp[i]+=dp[i-2]
ans=dp[n]
print(ans)

Submission status: Runtime Error

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

def main(n,a):
    nroute=[0]*(n+1)
    nroute[0]=0
    nroute[1]=1
    nroute[2]=1
    for i in range(3,n+1):
        nroute[i]=nroute[i-1]+nroute[i-2]
    #print(nroute)
    
    subn=[]
    i=0
    for j in a:
        subn.append((i,j-1))
        i=j+1
    subn.append((i,n))
    #print(subn)

    MOD=10**9+7
    nways=1
    for i,j in subn:
        l=j-i+1
        nways=nways*nroute[l]%MOD

    return nways

if __name__=='__main__':
    n,a=readinput()
    ans=main(n,a)
    print(ans)

Submission status: Runtime Error

Solution code:
def m():
    MOD = 10 ** 9 + 7
    N, M = map(int, input().split())
    A = [int(input()) for _ in range(M)]
    dp = [0] * (N + 1)
    for a in A: dp[a] = -1
    if dp[1] != -1 and dp[2] != -1:
        dp[1] = 1
        dp[2] = 2
    elif dp[1] != -1 and dp[2] == -1:
        dp[1] = 1
    elif dp[1] == -1 and dp[2] != -1:
        dp[2] = 1
    else:
        return 0

    for i in range(3, N + 1):
        if dp[i] == -1:
            continue
        l = dp[i - 2] if dp[i - 2] != -1 else 0
        r = dp[i - 1] if dp[i - 1] != -1 else 0
        dp[i] = (l + r) % MOD
    return dp[N] % MOD


print(m())

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
lis = [0]*n+1
a = []
for i in range(m):
    a.append(int(input()))
    
mod = 10**9+7
ans = 0
if n==1:
    print(1)
elif n==2:
    if m==1:
        print(1)
    else:
        print(2)
else:
    if 1 in a and 2 in a:
        print(0)
    elif 1 in a:
        lis[1] = 1
    elif 2 in a:
        lis[0] = 1
    else:
        lis[0] = 1
        lis[1] = 2
    
    for j in range(3,n+1):
        if j in a:
            lis[0] = lis[1]
            lis[1] = 0
        else:
            ans = lis[0]%mod + lis[1]%mod
            lis[0] = lis[1]
            lis[1] = ans
        
        if lis[0] == 0 and lis[1] == 0:
            ans = 0
            break
        

    print(ans%mod)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
breaks = []
for _ in range(m):
  breaks.append(int(input())-1)
stairs = [0 for _ in range(n)]

if n == 1:
  print(1)
else:
  if 0 not in breaks:
    stairs[0]=1

  if 1 not in breaks:
    stairs[1]=1  

  for i in range(n):
    if i+1 not in breaks:
      if i+1>=n:
        pass
      else:
        stairs[i+1]=stairs[i]+stairs[i+1]
    if i+2 not in breaks:
      if i+2>=n:
        pass
      else:
        stairs[i+2]=stairs[i]+stairs[i+2]
    if len(n)>3:
      if sum(stairs[-3:]) == 0:
        break

  print(stairs[-1]%1000000007)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
breaks = []
for _ in range(m):
  breaks.append(int(input())-1)
stairs = [0 for _ in range(n)]

if 0 not in breaks:
  stairs[0]=1

if 1 not in breaks:
  stairs[1]=1  

for i in range(n):
  if i+1 not in breaks:
    if i+1>=n:
      pass
    else:
      stairs[i+1]=stairs[i]+stairs[i+1]
  if i+2 not in breaks:
    if i+2>=n:
      pass
    else:
      stairs[i+2]=stairs[i]+stairs[i+2]
      
print(stairs[-1]%1000000007)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

B = ['.'] * (n + 1)
for a in A:
    B[a] = '#'
    
dp = [0] * (n + 1)
if B[1] == '.' and B[2] == '.':
    dp[1] = 1
    dp[2] = 2
elif B[1] == '#' and B[2] == '.':
    dp[2] = 1
elif B[1] == '.' and B[2] == '#':
    dp[1] = 1
    
for i in range(3, n + 1):
    if B[i] == '.':
        dp[i] = (dp[i - 2] + dp[i - 1]) % mod
    
print(1 if n == 1 else dp[-1])

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
a = [0]*m
for i in range(m):
  a[i] = int(input())
dp = [0]*(n+1)
dp[0] = 1
if 1 in a:
  dp[1] = 0
else:
  dp[1] = 1

for j in range(2,n+1):
  if j in a:
    dp[j] = 0
  else:
    dp[j] = dp[j-1]+dp[j-2]
  ans = dp[j]
  while ans >= 1000000007:
    ans -= 1000000007
print(ans)