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:
d = {}


def calc_step_combination(num):
    if num <= 0:
        return 0
    if num == 1:
        return 1
    if num == 2:
        return 2
    res = calc_step_combination(num - 1) + calc_step_combination(num - 2)
    d[num] = res
    return res


def sol(n, a_list):
    step_batch = []
    batch_start = 0
    for a in a_list:
        step_batch.append(a - batch_start - 1)
        batch_start = a + 1
    step_batch.append(n - batch_start)

    result = 1
    for i, steps in enumerate(step_batch):
        if i == 0 and steps == 0:
            continue
        result *= calc_step_combination(steps)

    print(result % 1000000007)


def main():
    n, m = map(int, input().split())
    a_list = []
    for i in range(0, m):
        a_list.append(int(input()))
    sol(n, a_list)


main()

Submission status: Runtime Error

Solution code:
d = {}


def calc_step_combination(num):
    if num <= 0:
        return 0
    if num == 1:
        return 1
    if num == 2:
        return 2
    res = calc_step_combination(num - 1) + calc_step_combination(num - 2)
    d[num] = res
    return res


def sol(n, a_list):
    step_batch = []
    batch_start = 0
    for a in a_list:
        step_batch.append(a - batch_start - 1)
        batch_start = a + 1
    step_batch.append(n - batch_start)

    result = 1
    for i, steps in enumerate(step_batch):
        if i == 0 and steps == 0:
            continue
        result *= calc_step_combination(steps)

    print(result % 1_000_000_007)


def main():
    n, m = map(int, input().split())
    a_list = []
    for i in range(0, m):
        a_list.append(int(input()))
    sol(n, a_list)


main()

Submission status: Runtime Error

Solution code:
def calc_step_combination(num):
    if num == 0:
        return 0
    if num == 1:
        return 1
    if num == 2:
        return 2
    return calc_step_combination(num - 1) + calc_step_combination(num - 2)


def sol(n, a_list):
    step_batch = []
    batch_start = 0
    for a in a_list:
        step_batch.append(a - batch_start - 1)
        batch_start = a + 1
    step_batch.append(n - batch_start)

    result = 1
    for i, steps in enumerate(step_batch):
        if i == 0 and steps == 0:
            continue
        result *= calc_step_combination(steps)

    print(result % 1_000_000_007)


def main():
    n, m = map(int, input().split())
    a_list = []
    for i in range(0, m):
        a_list = int(input())
    sol(n, a_list)


main()

Submission status: Runtime Error

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

import math
def fibonacci(n):
    a = 1/math.sqrt(5) * (((1+math.sqrt(5))/2)**n - ((1-math.sqrt(5))/2)**n)
    return(int(a))

ans = 1
t1 = 0
a_ind = 0
for i in range(N+1):
    if i == A[a_ind] or i == N:
        t2 = A[a_ind]
        ans *= fibonacci(t2-t1)
        t1 = A[a_ind]+1
        a_ind =min(a_ind+1, len(A)-1)
print(ans%1000000007)

Submission status: Runtime Error

Solution code:

# 壊れている床を無視すればフィボナッチ数になってる

from collections import defaultdict

def Fib(n, dd, broken):
    if n in broken:
        return 0

    if dd[n] != 0:
        return dd[n]

    if n <= 1:
        return 1

    x = Fib(n-1, dd, broken) + Fib(n-2, dd, broken)
    dd[n] = x
    return x

dd = defaultdict(int)

n, m = map(int, input().split())
A = [int(input()) for _ in range(m)]

ans = Fib(n, dd, A)
print(ans % 1000000007)

Submission status: Runtime Error

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

d = [0] * (n+1)
d[1] = (1 if len(a) == 0 or a[0] != 1 else 0)
d[2] = (d[1] + 1 if len(a) == 0 or 2 not in a else 0)

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

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
a = [int(input()) for i in range(m)]
b = [a[0]-1] + [a[i+1]-a[i]-2 for i in range(m-1)] + [n-a[m-1]-1]
c = [1,1]+[0]*(n-1)
for i in range(2,n+1):
  c[i] = c[i-1] + c[i-2]
ans = 1
for j in b:
  if j == -1:
    ans = 0
    break
  ans = ans * c[j] %1000000007
print(ans)

Submission status: Runtime Error

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

#フィボナッチ数列の初期値を調節
dp = [0] * (n+1)
dp[0] = 1
if 1 in a:
  dp[1] = 0
else:
  dp[1] = 1
  
for i in range(2, n+1):
  if dp[i-2] == 0 and dp[i-1] == 0:
    ans = 0
    flag = 1
    break
  elif i in a:
    continue
  else:
    dp[i] = dp[i-1] + dp[i-2]
if flag == 0:
  ans = dp[n]
print(ans%(10**9+7))

Submission status: Runtime Error

Solution code:
def p(boundary):
    step=[0]*(boundary+1)
    step[0]=0
    step[1]=1
    step[2]=2
    for i in range(2,boundary-1):
        step[i+1]=step[i]+step[i-1]
    d=step[boundary]
    return d


N,M = (int(i) for i in input().split())
a = [int(input()) for i in range(M)] 
b=[]
for i in range(0,M-2):
    b.append(a[i+1]-a[i]-2)
b.append(N-a[M-1]-1)
ans=p(a[0]-1)
for i in range(M):
    c=b[i]
    ans=p(c)*ans
print(ans)

Submission status: Runtime Error

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

n,m = map(int, input().split())
a = []
for i in range(m):
    a.append(int(input()))
if len(a) >= 2:
    for i in range(m-1):
        if a[i]+1 == a[i+1]:
            print(0)
            exit()

def fib(n):
    if n <= 1:
        return 1
    return fib(n-1) + fib(n-2)
tmp = 0
ans = 1
for i in range(len(a)):
    ans *= fib(a[i]-tmp-1)
    tmp = a[i]+1
if tmp < n:
    ans *= fib(n-tmp)
print(ans%(10**9+7))

Submission status: Runtime Error

Solution code:
def fibonacci(x, y):
  return x + y

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

for i in range(m-1):
  if a[i+1] - a[i] == 1:
    ans = 0
    flag = 1
    break

dp = [0] * 3
dp[0] = 1
dp[1] = 2
if flag == 0:
  if a[0] == 1:
    dp[0] = 1
    dp[1] = 1
for i in range(n):
  dp[2] 
	
      
print(ans%(10**9+7))

Submission status: Runtime Error

Solution code:
n,m=[int(i) for i in input().split()]
badone=[int(input()) for i in range(m)]
badstares=[1 for i in range(n)]
for i in badone:
    badstares[i-1]=0


stares=[-1 for i in range(n)]
for i in range(n):
    
    i=n-1-i
    if i==n-1:
        stares[i]=1
    elif i==n-2:
        if badstares[i]==0:
            stares[i]=-1
        else:
            stares[i]=1
    else:
        if badstares[i]==0:
            stares[i]=-1
        else:
            if stares[i+1]==-1 and stares[i+2]==-1:
                    stares[i]=-1
            elif stares[i+1]==-1 and stares[i+2]!=-1:
                    stares[i]=stares[i+2]
            elif stares[i+2]==-1:
                stares[i]=stares[i+1]
            else:
                stares[i]=stares[i+1]+stares[i+2]
    
if stares[0]==-1 and stares[1]==-1:
    print(0)
elif stares[0]==-1:
    print(stares[1]%1000000007)
elif stares[1]==-1:
    print(stares[0]%1000000007)
else:
    print((stares[0]+stares[1])%1000000007)

Submission status: Runtime Error

Solution code:
n,m=[int(i) for i in input().split()]
badone=[int(input()) for i in range(m)]
badstares=[1 for i in range(n)]
for i in badone:
    badstares[i-1]=0


stares=[-1 for i in range(n)]
for i in range(n):
    
    i=n-1-i
    if i==n-1:
        stares[i]=1
    elif i==n-2:
        if badstares[i]==0:
            stares[i]=-1
        else:
            stares[i]=1
    else:
        if badstares[i]==0:
            stares[i]=-1
        else:
            if stares[i+1]==-1:
                if stares[i+2]==-1:
                    stares[i]=-1
                else:
                    stares[i]=stares[i+2]
            elif stares[i+2]==-1:
                stares[i]=stares[i+1]
            else:
                stares[i]=stares[i+1]+stares[i+2]
    
print(max(stares[0]+stares[1],0)%1000000007)

Submission status: Runtime Error

Solution code:
import math
def conbination(x,y):
  return math.factorial(x) // (math.factorial(x-y) * math.factorial(y))
 
n, m = map(int, input().split())
a = []
for i in range(m):
  a.append(int(input()))

flag = 0
ans = 0
 
for i in range(m-1):
  if a[i+1] - a[i] == 1:
    ans = 0
    flag = 1
    break
    
if flag == 0:
  for i in range(n-2*m): #i:２段のぼる回数
    if i>=m
    ans += conbination(n-2*m-1, i-m) * (conbination(n-m, m) 
      
print(ans%(10**9+7))

Submission status: Runtime Error

Solution code:
import math
def conbination(x,y):
  return math.factrial(x) // (math.factrial(x-y) * math.factrial(y))

n, m = map(int, input().split())
a = [int(i) for i in input().split()]
flag = 0
ans = 0

for i in range(n-1):
  if a[i+1] - a[i] == 1:
    ans = 0
    flag = 1
    break
    
if flag == 0:
  for i in range(n-2*m-1): #i:２段のぼる回数
    ans += conbination(n-2*m-2, i)
      
print(ans%(10**9+7))

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
mod=10**9+7
n1=0
n2=0
A=[]
for i in range(M):
  n1=n2
  n2=int(input())
  #print(n2-n1+1)
  A.append(n2-n1-2)
A.append(N-n2-1)
if A[0]==-1:
  A.pop(0)
else:
  A[0]=A[0]+1
#print(A)
mx=max(A)
dp=[0 for i in range(mx+1)]
dp[0]=1
dp[1]=1
for i in range(mx-1):
  dp[i+2]=(dp[i]+dp[i+1])%mod
dp[0]=0
dp.append(0)
#print(dp)
ans=1
for i in range(len(A)):
  ans=(ans*dp[A[i]])%mod
print(ans)

Submission status: Runtime Error

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

dp = [0] * (N+1)
dp[0] = 1
if 1 in A:
  dp[1] = 0
else:
  dp[1] = 1
div = 1000000007

for i in range(2,N+1):
  if (dp[i-1] == 0) & (dp[i-2]==0):
    print(dp)
    print(0)
    sys.exit()
  elif i in A:
    continue
  else:
    dp[i] = dp[i-1]+dp[i-2]

print(dp[N])

Submission status: Runtime Error

Solution code:
N, M = [int(i) for i in input().split()]

dp = [0] * (N + 1)
dp[0] = 1
b = 1
f = FalseN, M = [int(i) for i in input().split()]

dp = [0] * (N + 1)
dp[0] = 1
b = 1
f = False
for _ in range(M):
    a = int(input())
    if a - b == 1:
        f = True
        break
    dp[a] = -1
    b = a

if f:
    ans = 0
elif len(dp) == 2:
    if dp[1] == -1:
        ans = 0
    else:
        ans = 1
else:
    MOD = 10**9 + 7
    
    if dp[1] != -1:
        dp[1] = 1
    for i in range(2, N + 1):
        if dp[i] != -1:
            s = 0 if dp[i-2] == -1 else (dp[i-2] % MOD)
            p = 0 if dp[i-1] == -1 else (dp[i-1] % MOD)
            dp[i] = s + p
            ans = dp[-1] % MOD
print(ans)

Submission status: Runtime Error

Solution code:
N, M = [int(i) for i in input().split()]

dp = [0] * (N + 1)
dp[0] = 1
b = 1
f = False
for _ in range(M):
    a = int(input())
    if a - b == 1:
        f = True
        break
    dp[a] = -1
    b = a

if f:
    ans = 0
else:
    MOD = 10**9 + 7
    
    if dp[1] != -1:
        dp[1] = 1
    for i in range(2, N + 1):
        if dp[i] != -1:
            s = 0 if dp[i-2] == -1 else (dp[i-2] % MOD)

            p = 0 if dp[i-1] == -1 else (dp[i-1] % MOD)

            dp[i] = s + p
            ans = dp[-1] % MOD
print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

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

if step[0] == -1:
    step[0] = 1

if step[1] == -1:
    step[1] = step[0]+1

for i in range(2,N):
    if step[i] == -1:
        step[i] = step[i-1]+step[i-2]

print(step[N-1] % 1000000007)

Submission status: Runtime Error

Solution code:
# ABC 129, c
n, m = map(int, input().split())
dp = [int(el) for el in input().split(' ')]
dp[0] = 1
dp[1] = 1
for j in [int(input()) for j in range(m)]:
    dp[j] = -1
for i in range(n + 1):
    if i < 2:
        if dp[i] == -1:
            dp[i] = 0
    else:
        if dp[i] == -1:
            dp[i] = 0
        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 = [int(input()) for _ in range(m)]
ans = 0

for i in range(m):
    if i == 0:
        j = (a[0]-1)*2 + (n-(a[0]+1)*2
        ans += j
    elif i >= 1 :
        if a[i] - a[i-1] == 1:
            print(0)
            break
        else:
            k = (a[i]-1)*2 + (n-(a[i]+1)*2 
            ans += k
else:
    print(ans % 1000000007)

Submission status: Runtime Error

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

ans = [a[0]]

for i in range(M-1):
    ans.append(a[i+1]-a[i]-1)
        
def fibonacci(n):
    listf = [0]+[1]*n
    a, b = 1, 0
    for i in range(n-1):
        a, b = (a+b)%1000000007 , a
        listf[i+2] = a
    return listf

fib = fibonacci(N)

result = 1
for j in range(len(ans)):
    result = result * fib[ans[j]] % 1000000007

result = result * fib[(N - a[-1])] % 1000000007
    
print(result)

Submission status: Runtime Error

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

print(dp[0]%mod)

Submission status: Runtime Error

Solution code:
import numpy as np
N,M=map(int,input().split())
a=[int(input()) for i in range(M)]
a_a=np.ones( N+1 )
for i in range(M):
    a_a[a[i]]=0
c=np.zeros(N+1)
c[0]=1
for i in range(1,N+1):
    if i==1:
        c[i]=c[i-1]*a_a[i-1]
    else:
        c[i]=c[i-1]*a_a[i-1]+c[i-2]*a_a[i-2]
print(int(c[N])%(7+10**9))

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)

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

dp = [0] * N
dp[1] = 1
dp[2] = 2


def fib(n):
    if n == 0:
        return 0
    elif dp[n] == 0:
        dp[n] = fib(n - 1) + fib(n - 2)
    return dp[n]


if a[0] == 1:
    ans = 1
else:
    ans = fib(a[0] - 1)
if M > 1:
    for i in range(1, M):
        if a[i] - a[i - 1] <= 1:
            ans = 0
        else:
            ans = ans * fib(a[i] - a[i - 1] - 2) % 1000000007
ans = ans * fib(N - a[-1] - 1) % 1000000007
print(ans)

Submission status: Runtime Error

Solution code:
import sys
N, M = map(int, input().split())
A = [int(input()) for i in range(M)]
d = [0]*N
d[0] = 1
d[1] = 1
def func(N):
    if d[N] > 0:
        return d[N]
    d[N] = func(N-1) + func(N-2)
    return d[N]
if M == 0:
    print(func(N)%1000000007)
    sys.exit()

for i in range(M-1):
    if A[i+1] == A[i]+1:
        print(0)
        sys.exit()
        

A = [-1] + A + [N+1]

B = [A[i+1]-A[i]-2 for i in range(M+1)]
ans = 1
for i in range(M+1):
    ans = ans * func(B[i])
ans = ans%1000000007
print(ans)

Submission status: Runtime Error

Solution code:
import sys
N, M = map(int, input().split())
A = [int(input()) for i in range(M)]
d = [0]*N
d[0] = 1
d[1] = 1
def func(N):
    if d[N] > 0:
        return d[N]
    d[N] = func(N-1) + func(N-2)
    return d[N]
if M == 0:
    print(func(N)/%1000000007)
    sys.exit()

for i in range(M-1):
    if A[i+1] == A[i]+1:
        print(0)
        sys.exit()
        

A = [-1] + A + [N+1]

B = [A[i+1]-A[i]-2 for i in range(M+1)]
ans = 1
for i in range(M+1):
    ans = ans * func(B[i])
ans = ans%1000000007
print(ans)

Submission status: Runtime Error

Solution code:
import sys
N, M = map(int, input().split())
A = [int(input()) for i in range(M)]
d = [0]*N
d[0] = 1
d[1] = 1
def func(N):
    if d[N] > 0:
        return d[N]
    d[N] = func(N-1) + func(N-2)
    return d[N]
if M == 0:
    print(func(N))
    sys.exit()

for i in range(M-1):
    if A[i+1] == A[i]+1:
        print(0)
        sys.exit()
        

A = [-1] + A + [N+1]

B = [A[i+1]-A[i]-2 for i in range(M+1)]
ans = 1
for i in range(M+1):
    ans = ans * func(B[i])
ans = ans%1000000007
print(ans)

Submission status: Runtime Error

Solution code:
import sys
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)
        sys.exit()
        
d = [0]*N
d[0] = 1
d[1] = 1
A = [-1] + A + [N+1]
def func(N):
    if d[N] > 0:
        return d[N]
    d[N] = func(N-1) + func(N-2)
    return d[N]
B = [A[i+1]-A[i]-2 for i in range(M+1)]
ans = 1
for i in range(M+1):
    ans = ans * func(B[i])
ans = ans%1000000007
print(ans)

Submission status: Runtime Error

Solution code:
import sys
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]:
        print(0)
        sys.exit()
        
d = [0]*N
d[0] = 1
d[1] = 1
A = [-1] + A + [N+1]
def func(N):
    if d[N] > 0:
        return d[N]
    d[N] = func(N-1) + func(N-2)
    return d[N]
B = [A[i+1]-A[i]-2 for i in range(M+1)]
ans = 1
for i in range(M+1):
    ans = ans * func(B[i])
ans = ans%1000000007
print(ans)

Submission status: Runtime Error

Solution code:
#階数Nの階段の上り方の総数を求める関数
N , M= map(int, input().split())
A = [int(input()) for i in range(M)]
d = [0]*N
d = [0]*N
d[0] = 1
d[1] = 1
A = [-1] + A + [N+1]
def func(N):
    if d[N] > 0:
        return d[N]
    d[N] = func(N-1) + func(N-2)
    return d[N]
B = [A[i+1]-A[i]-2 for i in range(M+1)]
ans = 1
for i in range(M+1):
    ans = ans * func(B[i])
ans = ans%1000000007
print(ans)

Submission status: Runtime Error

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

MOD = 1000000007

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

if 1 not in a:
    dp[1] = 1
else:
    dp[1] = 0

for i in range(2, N + 1):
    print(f"i: {i}, dp: {dp}")

    if i in a:
        continue
    dp[i] = dp[i - 1] + dp[i - 2]
    dp[i] %= MOD
print(f"i: {i}, dp: {dp}")

print(dp[N])

Submission status: Runtime Error

Solution code:
s,n=map(int,input().split())
x=list(int(input()) for _ in range(n))

w0=int(1)
b0=int(0)
cnt=0

for i in range(1,s):
	if i==x[cnt]:
		w1=int(0)
		b1=w0
		w0=w1
		b0=b1
		if cnt<n-1: 
			cnt+=1
	else:
		w1=b0+w0
		b1=w0
		w0=w1
		b0=b1

print((w0+b0)%1000000007) 
#print(w0+b0)

Submission status: Runtime Error

Solution code:
s,n=map(int,input().split())
x=list(int(input()) for _ in range(n))

w0=1
b0=0
cnt=0

for i in range(1,s):
	if i==x[cnt]:
		w1=0
		b1=w0
		w0=w1
		b0=b1
		if cnt<len(x)-1: 
			cnt+=1
	else:
		w1=b0+w0
		b1=w0
		w0=w1
		b0=b1

print((w0+b0)%1000000007)

Submission status: Runtime Error

Solution code:
import sys,math
N,M = map(int,input().split())
a = []
cnt = 0
ans = 1
fi = []
fi.append(1)
fi.append(1)
fi.append(1)
for i in range(3,10*5+2):
    tmp = fi[i-1]+fi[i-2]
    fi.append(tmp)
for i in range(M):
    a.append(int(input()))
for i in range(N+1):
    if i in a:
        if cnt == 0:
            print(0)
            sys.exit()
        else:
            ans *= fi[cnt]
            cnt = 0
    else:
        cnt += 1
ans *= fi[cnt]

print(ans % 1000000007)

Submission status: Runtime Error

Solution code:
import sys,math
N,M = map(int,input().split())
a = []
cnt = 0
ans = 1
fi = []
fi.append(1)
fi.append(1)
fi.append(1)
for i in range(3,10*5+1):
    tmp = fi[i-1]+fi[i-2]
    fi.append(tmp)
for i in range(M):
    a.append(int(input()))
for i in range(N+1):
    if i in a:
        if cnt == 0:
            print(0)
            sys.exit()
        else:
            ans *= fi[cnt]
            cnt = 0
    else:
        cnt += 1
ans *= fi[cnt]

print(ans % 1000000007)

Submission status: Runtime Error

Solution code:
import sys

N,M=map(int,input().split())
a=[int(input()) for i in range(M)]
c=[0]*(N+1)
c[0]=1
MOD=7+10**9
if M==0:
    c[1]=1
    for i in range(1,N):
        c[i+1]=c[i]+c[i-1]
    print(c[N])
else:
    j=0
    for i in range(1,N+1):
        if i==a[j]:
            if j+1<=M:
                if i+1==a[j+1]:
                    print(0)
                    sys.exit(0)
                else:
                    j+=1
        elif i==1:
            c[i]=1
        else:
            c[i]=(c[i-1]+c[i-2])%MOD
    print(c[-1]%MOD)

Submission status: Runtime Error

Solution code:
#129
N,M=map(int,input().split())
a=[int(input()) for i in range(M)]
f=[1,2,3,5,8]
def cu(x):
    global f
    if len(f)<x:
        for i in range(len(f),x):
            f.append( f[i-1]+f[i-2] )
    return f[x-1]

a_d=[a[0]-1]
for i in range(M-1):
    a_d.append( a[i+1]-a[i]-1 )
a_d.append(N-a[-1]-1)
if 0 in a_d[1:]:
    print(0)
    exit(0)
else:
    count=1
    for i in range(M+1):
        if i==0 and a_d[0]!=0:
            count=cu(a_d[0])
        elif i==M:
            count=count*cu(a_d[-1])
        else:
            if a_d[i]>=3:
                count=count*cu(a_d[i]-1)
print(count%(10**9+7))

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
j=0

for i in range(1,n+1):
    if i==a[j]:
        if j<m-1:
            j+=1
    else:
        if i==1:
            dp[i]=1
        else:
            dp[i]=dp[i-1]+dp[i-2]

print(dp[n]%(10**9+7))

Submission status: Runtime Error

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

def fib(x):
    if x==-1:
        count=0
    elif x==0:
        count=1
    else:
        count=fib(x-1)+fib(x-2)
    return count
    
for i in range(m+1):
    ans=ans*fib(a[i+1]-a[i]-2)
    
print(ans%1000000007)

Submission status: Runtime Error

Solution code:
from functools import lru_cache
n,m=map(int,input().split())
a=[int(input()) for _ in range(m)]
@lru_cache(maxsize=None)
def f(x):
    if x<2:return x
    elif x-1 in a:return 0
    else:return (f(x-1)+f(x-2))%1000000007
print(f(n+1))

Submission status: Runtime Error

Solution code:
from functools import lru_cache
n,m=map(int,input().split())
a=[int(input()) for _ in range(m)]
@lru_cache(maxsize = None)
def f(x):
    if x<2:return x
    elif x-1 in a: return 0
    else:return (f(x - 1) + f(x - 2))%1000000007
print(f(n+1))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)
n,m = map(int,input().split())
a = [int(input()) for i in range(m)]
def toori(n):
    if n == 1:
        return 1
    elif n ==2:
        return 2
    else:
        return toori(n-1) + toori(n-2)
    
res =toori(a[0]-1)

for i in range(m):
    p= a[i+1] - a[i]-1
    res = res * toori(p)
print(res%1000000007)

Submission status: Runtime Error

Solution code:
import numpy as np

a,b=map(int,input().split())
c=[]
for i in range(b):
    c.append(int(input()))
c.append(a+1)    
def Fib(n):
    fib=1/np.sqrt(5)*(((1+np.sqrt(5))/2)**(n)-((1-np.sqrt(5))/2)**(n))
    return(int(fib))

d=[]
z=-1
for j in c:
    di=j-z-1
    if j-z==1:
        print(0)
        exit()
    else:
        d.append(Fib(di))
        z=j
ans=1
for k in d:
    ans=ans*k
print(ans%1000000007)

Submission status: Runtime Error

Solution code:
import numpy as np

a,b=map(int,input().split())
c=[]
for i in range(b):
    c.append(int(input()))
c.append(a+1)    
def Fib(n):
    fib=1/np.sqrt(5)*(((1+np.sqrt(5))/2)**(n-1)-((1-np.sqrt(5))/2)**(n-1))
    return(int(fib))

d=[]
z=-1
for j in c:
    di=j-z
    if j-z==1:
        print(0)
        exit()
    else:
        d.append(Fib(di))
        z=j
ans=1
for k in d:
    ans=ans*k
print(ans%1000000007)

Submission status: Runtime Error

Solution code:
import numpy as np

a,b=map(int,input().split())
c=[]
for i in range(b):
    c.append(int(input()))
c.append(a+1)    
def Fib(n):
    fib=1/np.sqrt(5)*(((1+np.sqrt(5))/2)**(n-1)-((1-np.sqrt(5))/2)**(n-1))
    return(int(fib))

d=[]
z=-1
for j in c:
    d.append(Fib(j-z))
    z=j
ans=1
for k in d:
    ans=ans*k
print(ans%1000000007)

Submission status: Runtime Error

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



  for i in range(2,n):
    if A[i]!=0:
      A[i]=(A[i-1]+A[i-2])
      A[i]%=MOD

    
  print(A[n-1])

Submission status: Runtime Error

Solution code:
MOD=10**9+7
n,m=map(int,input().split())
A=[1 for i in range(n)]
A[1]=2
for i in range(m):
  A[int(input())-1]=0
if A[0]==0:
  A[1]=1


for i in range(2,n):
  if A[i]!=0:
    A[i]=(A[i-1]+A[i-2])
    A[i]%=MOD
    
    
print(A[n-1])

Submission status: Runtime Error

Solution code:
MOD=10**9+7
n,m=map(int,input().split())
A=[1 for i in range(n)]
A[1]=2
for i in range(m):
  A[int(input())-1]=0
if A[0]==0:
  A[1]=1


for i in range(2,n):
  if A[i]!=0:
    A[i]=(A[i-1]+A[i-2])
    A[i]%=MOD
    
    
print(A)

Submission status: Runtime Error

Solution code:
ans = int(0)

k = [i for i in range(n+1)]

for i in l:
  k.remove(i)

for i in range(n-m-1):
  if k[i]+1 == k[i+1] and  k[i+1] + 1 == k[i+2]:
    ans += 2

answer = ans%1000000007
print(answer)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
a = [int(input()) for i in range(M)]
dp = [0]*(N+1)
div = 10**9 + 7
#dp[x] = dp[x-1] + dp[x-2]になる
dp[0] = 1
dp[1] = 1 if a[0] != 1 else 0

for x in range(2, N+1):
  if (x-1 in a and x-2 in a) or (x in a):
    dp[x] = 0
  elif x-1 in a:
    dp[x] = dp[x-2]
  elif x-2 in a:
    dp[x] = dp[x-1]
  else:
    dp[x] = dp[x-1]+dp[x-2]
  dp[x] = dp[x] % div
print(dp[-1]%div)

Submission status: Runtime Error

Solution code:
MOD=1000000007
n,m=map(int,input().split())
A=[1 for i in range(n)]
A[1]=2
for i in range(m):
  A[int(input())-1]=0
  


for i in range(2,n):
  if A[i]!=0:
    A[i]=(A[i-1]+A[i-2])%MOD
    
    
print(A[n-1])

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
a = [int(input()) for i in range(M)]
dp = [0]*(N+1)
div = 10**9 + 7
#dp[x] = dp[x-1] + dp[x-2]になる
dp[0] = 1
dp[1] = 1 if a[0] != 1 else 0

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

print(dp[-1]%div)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

resolve()

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
a = [int(input()) for _ in range(M)]
dp = [0]*(N+1)
j = 0
dp[0] = 1
mod = 10**9+7
for i in range(1, N+1):
    if i == a[j]:
        j += 1
        j = min(M-1, j)
    elif i == 1:
        dp[i] = 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())
a = [int(input()) for _ in range(m)]
d = [0]*(n+1)
if not 1 in a : d[1] = 1
if not 2 in a : d[2] = d[1] + 1
for i in range(3,n+1):
    if not i in a :
        d[i] += d[i-1] + d[i-2]
print(d[i]%1000000007)

Submission status: Runtime Error

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

resolve()

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
li = [int(input()) for _ in range(m)]
li.append(n+1)
ans_li=[1 for i in range(m+1)]
global count

def counter( start, end):
    global count
    if start == end:
        count+=1
    elif start > end:
        return
    else:
        counter(start+1, end)
        counter(start+2, end)

start_pos = 0
for i in range(0, m+1):
    count = 0
    if start_pos == li[i]-1:
        start_pos = li[i]+1
        continue
    counter(start_pos, li[i]-1)
    start_pos = li[i]+1
    ans_li[i] = count

ans = 1

for i in ans_li:
    ans *=i
print(ans)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
li = [int(input()) for _ in range(m)]
li.append(n+1)
ans_li=[0 for i in range(m+1)]
global count

def counter( start, end):
    global count
    if start == end:
        count+=1
    elif start > end:
        return
    else:
        counter(start+1, end)
        counter(start+2, end)

start_pos = 0
for i in range(0, m+1):
    count = 0
    if start_pos == li[i]-1:
        start_pos = li[i]+1
        continue
    counter(start_pos, li[i]-1)
    start_pos = li[i]+1
    ans_li[i] = count

ans = 1
for i in ans_li:
    ans *=i
print(ans)

Submission status: Runtime Error

Solution code:
N, M = [int(nm) for nm in input().split()]
A = []
for m in range(M):
  A.append(int(input()))

for n in range(N+1):
  if n == 0:
    i1 = 1
  elif n == 1:
    i2 = 1
    if n in A:
      i2 = 0
  else:
    i3 = i1 + i2
    if n in A:
      i3 = 0
    i1, i2 = i2, i3

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

Submission status: Runtime Error

Solution code:
N, M = [int(nm) for nm in input().split()]
A = []
for m in range(M):
  A.append(int(input()))

for n in range(N, -1, -1):
  if n == N:
    i2 = 1
  elif n == N-1:
    i1 = 1
    if n in A:
      i1 = 0
  else:
    i = i1 + i2
    if n in A:
      i = 0
    i1, i2 = i, i1

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