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:
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
arr=[1,2]
arr=arr+[0]*(n-2)
danger=[int(input()) for _ in range(m)]
if danger[0]==1:
  arr[0]=0
  arr[1]=1
for i in range(m):
  arr[danger[i]-1]=-1
for i in range(n):
  if arr[i]==-1:
    arr[i]=0
  elif i==0 or i==1:
    continue 
  else:
    arr[i]=(arr[i-1]+arr[i-2])%(10**9+7)
print(arr[n-1]%(10**9+7))

Submission status: Runtime Error

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

ans = int(1)

A = [0]*(M+1)
A[0]=N
if M!=0:
    A[0] = a[0] - 1
    A[M] = N - a[M-1]-1
    for i in range(M-1):
        A[i+1] = a[i+1] - a[i]- 2
        if A[i+1]==-1:
            ans = 0


SA =[0]*N
SA[0] = int(1)
SA[1] = int(1)
if N>2:
    for i in range(N - 1):
        SA[i + 2] = SA[i + 1] + SA[i]
        SA[i + 2] = SA[i + 2] % 1000000007

for i in range(M+1):
    if A[i]>=0:
        ans *= SA[A[i]]
        ans = ans%1000000007


print(ans)

Submission status: Runtime Error

Solution code:


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

ans = int(1)

A = [0]*(M+1)
A[0]=N
if M!=0:
    A[0] = a[0] - 1
    A[M] = N - a[M-1]-1
    for i in range(M-1):
        A[i+1] = a[i+1] - a[i]- 2
        if A[i+1]==-1:
            ans = 0


SA =[0]*N
SA[0] = int(1)
SA[1] = int(1)
if N>2:
    for i in range(N - 2):
        SA[i + 2] = SA[i + 1] + SA[i]
        SA[i + 2] = SA[i + 2] % 1000000007

for i in range(M+1):
    if A[i]>=0:
        ans *= SA[A[i]]
        ans = ans%1000000007


print(ans)

Submission status: Runtime Error

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

ans = int(1)

A = [0]*(M+1)
if M!=0:
    A[0] = a[0] - 1
    A[M] = N - a[M-1]-1
    for i in range(M-1):
        A[i+1] = a[i+1] - a[i]- 2
        if A[i+1]==-1:
            ans = 0


SA =[0]*N
SA[0] = int(1)
SA[1] = int(1)
if N>2:
    for i in range(N - 2):
        SA[i + 2] = SA[i + 1] + SA[i]
        SA[i + 2] = SA[i + 2] % 1000000007

for i in range(M+1):
    if A[i]>=0:
        ans *= SA[A[i]]
        ans = ans%1000000007


print(ans)

Submission status: Runtime Error

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

ans = int(1)

A = [0]*(M+1)
A[0] = a[0]-1
if M!=0:
    A[M] = N - a[M-1]-1
for i in range(M-1):
    A[i+1] = a[i+1] - a[i]- 2
    if A[i+1]==-1:
        ans = 0


SA =[0]*N
SA[0] = int(1)
SA[1] = int(1)
if N>2:
    for i in range(N - 2):
        SA[i + 2] = SA[i + 1] + SA[i]
        SA[i + 2] = SA[i + 2] % 1000000007

for i in range(M+1):
    if A[i]>=0:
        ans *= SA[A[i]]
        ans = ans%1000000007


print(ans)

Submission status: Runtime Error

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

ans = int(1)

A = [0]*(M+1)
A[0] = a[0]-1
if M!=0:
    A[M] = N - a[M-1]-1
for i in range(M-1):
    A[i+1] = a[i+1] - a[i]- 2
    if A[i+1]==-1:
        ans = 0


SA =[0]*N
SA[0] = int(1)
SA[1] = int(1)
for i in range(N-2):
    SA[i+2] = SA[i+1] + SA[i]
    SA[i+2] = SA[i+2]%1000000007

for i in range(M+1):
    if A[i]>=0:
        ans *= SA[A[i]]
        ans = ans%1000000007


print(ans)

Submission status: Runtime Error

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

ans = int(1)

A = [0]*(M+1)
A[0] = a[0]-1
A[M] = N - a[M-1]-1
for i in range(M-1):
    A[i+1] = a[i+1] - a[i]- 2
    if A[i+1]==-1:
        ans = 0


SA =[0]*N
SA[0] = int(1)
SA[1] = int(1)
for i in range(N-2):
    SA[i+2] = SA[i+1] + SA[i]
    SA[i+2] = SA[i+2]%1000000007

for i in range(M+1):
    if A[i]>=0:
        ans *= SA[A[i]]
        ans = ans%1000000007


print(ans)

Submission status: Runtime Error

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

ans = int(1)

A = [0]*(M+1)
A[0] = a[0]-1
A[M] = N - a[M-1]-1
for i in range(M-1):
    A[i+1] = a[i+1] - a[i]- 2
    if A[i+1]==-1:
        ans = 0

SA =[0]*N
SA[0] = int(1)
SA[1] = int(1)
for i in range(N-2):
    SA[i+2] = SA[i+1] + SA[i]
    SA[i+2] = SA[i+2]%1000000007

for i in range(M+1):
    ans *= SA[A[i]]
    ans = ans%1000000007


print(ans)

Submission status: Runtime Error

Solution code:
import sys
n,m=map(int,input().split())
arr=[1,2]
arr=arr+[0]*(n-2)
danger=tuple(map(int,sys.stdin))
m=0
if 1 == danger[0]:
  arr[0]=0
  arr[1]=1
  m=1
for i in range(n):
  if i+1 == danger[m]:
    arr[i]=0
    m+=1
  elif i==0 or i==1:
    continue 
  else:
    arr[i]=(arr[i-1]+arr[i-2])%(10**9+7)
print(arr[n-1]%(10**9+7))

Submission status: Runtime Error

Solution code:
import sys
n,m=map(int,input().split())
arr=[1,2]
arr=arr+[0]*(n-2)
danger=tuple(map(int,sys.stdin))
m=0
if 1 == danger[0]:
  arr[0]=0
  arr[1]=1
  m=1
for i in range(n):
  if i+1 in danger[m]:
    arr[i]=0
    m+=1
  elif i==0 or i==1:
    continue 
  else:
    arr[i]=(arr[i-1]+arr[i-2])%(10**9+7)
print(arr[n-1]%(10**9+7))

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
s=[]
for i in range(m):
    s.append(int(input()))
l=[1]
if s[0]!= 1:l.append(1)
else:l.append(0)
for i in range(2,n+1):
    if i in s:num=0
    else:num = (l[i-2]+l[i-1])%1000000007
    l.append(num)
print(l[-1])

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
s=[]
for i in range(m):
    s.append(int(input()))
l=[1]
if s[0]!= 1:l.append(1)
else:l.append(0)
for i in range(2,n+1):
    if i in s:num=0
    else:num = (l[i-2]+l[i-1])%1000000007
    l.append(num)
print(l)

Submission status: Runtime Error

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

x=[0]*(N+1)
j=0
if N!=0:
    x[0]=1
if N>1 and M!= 0 and a[0]==1:
        j+=1
    else:
        x[1]=1

for i in range(2,N+1): 
    print(j)
    if j==M or i!=a[j]:
        x[i]=x[i-1]+x[i-2]
    else:
        x[i]=0
        j+=1
print(int(x[N]%(1000000007)))

Submission status: Runtime Error

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

x=[0]*(N+1)
j=0
if len(x)!=0:
    x[0]=1
if len(x) >0:
    if a[0]==1:
        j+=1
    else:
        x[1]=1


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

print(int(x[N]%(1000000007)))

Submission status: Runtime Error

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

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

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

print(int(x[N]%((1e+9)+7)))

Submission status: Runtime Error

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

x=[0 if i in a else 1 for i in range(N+1)]
for i in range(2,N+1):
    if x[i]!=0:
        x[i]=x[i-1]+x[i-2] 

print(x[N]%((1e+9)+7))

Submission status: Runtime Error

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

x=[0 if i in a else 1 for i in range(N+1)]
for i in range(2,N+1):
    if x[i]!=0:
        x[i]=x[i-1]+x[i-2] 

print(x[N]%((10e+9)+7))

Submission status: Runtime Error

Solution code:
def fib(x):
  if x==0:
    return 0
  elif x==1 or x==2:
  	return 1
  else:
  	return fib(x-2)+fib(x-1)

N,M=(int(x) for xin input().split())
a=[int(input()) for i in range(M)]
x=1
for i in range(1,M):
  x*=fib(a[i]-a[i-1])

print (a%((10e+9)+7))

Submission status: Runtime Error

Solution code:
def fib(x):
  if x==0:
    return 0
  elif x==1 or x==2
  	return 1
  else
  	return fib(x-2)+fib(x-1)

N,M=(int(x) for xin input().split())
a=[int(input()) for i in range(M)]
x=1
for i in range(1,M):
  x*=fib(a[i]-a[i-1])

print (a%((10e+9)+7))

Submission status: Runtime Error

Solution code:
def fib(x):
  if x=0:
    return 0
  elif x=1 or x=2
  	return 1
  else
  	return fib(x-2)+fib(x-1)

N,M=(int(x) for xin input().split())
a=[int(input()) for i in range(M)]
x=1
for i in range(1,M):
  x*=fib(a[i]-a[i-1])

print (a%((10e+9)+7))

Submission status: Runtime Error

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

else:
    ls = []
    
dp = [0 for _ in range(n+1)]
dp[1] = 1
dp[2] = 2

for i in range(3,n+1):
    if i in ls :
        dp[i] = 0
    else:
        dp[i] = (dp[i-1]+dp[i-2])%(10**9+7)

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

Submission status: Runtime Error

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

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

for i in range(3,n+1):
    if i in ls :
        dp[i] = 0
    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())
ls = [int(input()) for _ in range(m)]

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

for i in range(3,n+1):
    if i in ls :
        dp[i] = 0
    else:
        dp[i] = dp[i-1]+dp[i-2]

print(dp)

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

Submission status: Runtime Error

Solution code:
def fib(n):
    if n <= 1:
        return n
    result = [1, 0, 0, 1]
    matrix = [1, 1, 1, 0]
    while n > 0:
        if n % 2:
            result = mul(matrix, result)
        matrix = mul(matrix, matrix)
        n //= 2
    return result[2]

def mul(a, b):
    return [a[0]*b[0] + a[1]*b[2],
            a[0]*b[1] + a[1]*b[3],
            a[2]*b[0] + a[3]*b[2],
            a[2]*b[1] + a[3]*b[3]]

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

flag = False
for i in range(M-1):
  if (A[i]+1 == A[i+1]):
    flag = True

if flag:
  print(0)
else:
  parts = []  
  for i in range(M):
    if i == 0:
      a_list = [x for x in range(0, A[i])]
      parts.append(a_list)
    else:
      a_list = [x for x in range(A[i-1]+1, A[i])]
      parts.append(a_list)
  a_list = [x for x in range(A[M-1]+1, N+1)]
  parts.append(a_list)
  ans = 1
  for part in parts:
    part_ans = fib(len(part))
    ans *= part_ans
  print(ans % 1000000007)

Submission status: Runtime Error

Solution code:
import scipy.misc as sm

def fib(N):
  N = N-1
  a = N // 2
  ans = 0
  for i in range(a+1):
      sum = sm.factorial(N-i)/(sm.factorial(N-2*i)*sm.factorial(i))
      ans += int(sum)
  return ans

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

flag = False
for i in range(M-1):
  if (A[i]+1 == A[i+1]):
    flag = True

if flag:
  print(0)
else:
  parts = []  
  for i in range(M):
    if i == 0:
      a_list = [x for x in range(0, A[i])]
      parts.append(a_list)
    else:
      a_list = [x for x in range(A[i-1]+1, A[i])]
      parts.append(a_list)
  a_list = [x for x in range(A[M-1]+1, N+1)]
  parts.append(a_list)
  ans = 1
  for part in parts:
    part_ans = fib(len(part))
    ans *= part_ans
  print(ans % 1000000007)

Submission status: Runtime Error

Solution code:
import sympy as sym #sympyのインポート
def Fib(n):
    x = sym.symbols('x',nonnegative=True,integer=True) #変数xの宣言(非負の整数)
    Fib=1/sym.sqrt(5)*(((1+sym.sqrt(5))/2)**(n-1)-((1-sym.sqrt(5))/2)**(n-1)) #一般項の式
    result=Fib.subs(x,n) #xにnを代入
    result=result.evalf() #式を浮動小数点数として評価
    return int(result)
def main():
    sum = 1
    b = -1
    N,M = map(int,input().split())
    for i in range(M):
        a = int(input())
        if a == b+1:
            print(0)
            exit()
        sum *= Fib(a-b)
        b = a 
    sum *= Fib(N-b)
    
    print(sum%1000000007)
#if __name__ == '__main__':
main()

Submission status: Runtime Error

Solution code:
import sys
from fractions import gcd
from functools import reduce
from itertools import combinations

import numpy as np

sys.setrecursionlimit(200000)


def input():
    return sys.stdin.readline()[:-1]


def ii(t: type = int):
    return t(input())


def il(t: type = int):
    return list(map(t, input().split()))


def imi(N: int, t: type = int):
    return [ii(t) for _ in range(N)]


def iml(N: int, t: type = int):
    return [il(t) for _ in range(N)]


def solve():
    mod = 100_000_000_7
    N, M = il()
    a = [True] * (N+1)
    for b in imi(M):
        a[b] = False
    dp = [0] * (N + 1)
    dp[0] = 1
    for now in range(N):
        for next in range(now + 1, min(N, now + 2)+1):
            if a[next]:
                dp[next] += dp[now]
                dp[next] %= mod
    return dp[N]


if __name__ == "__main__":
    print(solve())

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
a=[int(input()) for _ in range(M)]
 
def count_step(n):
    num=n//2
    count=0
    for i in range(num+1):
        N=n-i
        if i==0:
            count+=1
        elif i==1:
            count+=N
        else:
            nume=1
            denom=1
            for j in range(i):
                nume*=(N-j)
                denom*=(j+1)
            count+=int(nume/denom)
    return count
 
if M!=0:
    a2=[a[0]-1]
    
    for i in range(M-1):
        p=a[i+1]-a[i]-2
        
        a2.append(p)
    
    a2.append(N-a[M-1]-1)
 
p=1
for i in range(M-1):
    if a[i]+1==a[i+1]:
        p=0
        break
 
if p==0:
    pattern=0
else:
    if M==0:
        pattern=count_step(N)
    else:
        pattern=1
        for i in range(len(a2)):
            pattern*=count_step(a2[i])
 
print(int(pattern%1000000007))

Submission status: Runtime Error

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

def count_step(n):
    num=n//2
    count=0
    for i in range(num+1):
        N=n-i
        if i==0:
            count+=1
        elif i==1:
            count+=N
        else:
            nume=1
            denom=1
            for j in range(i):
                nume*=(N-j)
                denom*=(j+1)
            count+=nume/denom
    return count

if M!=0:
    a2=[a[0]-1]
    
    for i in range(M-1):
        p=a[i+1]-a[i]-2
        
        a2.append(p)
    
    a2.append(N-a[M-1]-1)

p=1
for i in range(M-1):
    if a[i]+1==a[i+1]:
        p=0
        break

if p==0:
    pattern=0
else:
    if M==0:
        pattern=count_step(N)
    else:
        pattern=1
        for i in range(len(a2)):
            pattern*=count_step(a2[i])

print(int(pattern%1000000007))

Submission status: Runtime Error

Solution code:
import math

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

def count_step(n):
    num=n//2
    count=0
    for i in range(num+1):
        N=n-i
        if i==0:
            count+=1
        elif i==1:
            count+=N
        else:
            nume=1
            denom=1
            for j in range(i):
                nume*=(N-j)
                denom*=(j+1)
            count+=int(nume/denom)
    return count

if M!=0:
    a2=[a[0]-1]
    
    for i in range(M-1):
        p=a[i+1]-a[i]-2
        
        a2.append(p)
    
    a2.append(N-a[M-1]-1)

p=1
for i in range(M-1):
    if a[i]+1==a[i+1]:
        p=0
        break

if p==0:
    pattern=0
else:
    pattern=1
    if M==0:
        pattern=count_step(N)
    else:
        for i in range(len(a2)):
            pattern*=count_step(a2[i])

print(pattern%1000000007)

Submission status: Runtime Error

Solution code:
import itertools

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

def count_step(n):
    num=n//2
    count=0
    for i in range(num+1):
        step=[]
        for _ in range(n-2*i):
            step.append(1)
        for _ in range(i):
            step.append(2)
        count+=len(list(itertools.combinations(step,i)))
    return count

a2=[a[0]-1]

for i in range(M-1):
    p=a[i+1]-a[i]-2
    
    a2.append(p)

a2.append(N-a[M-1]-1)

p=1
for i in range(M-1):
    if a[i]+1==a[i+1]:
        p=0
        break

if p==0:
    pattern=0
else:
    pattern=1
    for i in range(len(a2)):
        pattern*=count_step(a2[i])

print(pattern%1000000007)

Submission status: Runtime Error

Solution code:
def fib(x):
    if x == 1:
        return 1
    a0 = 1
    a1 = 1
    for i in range(x-1):
        tmp = a1
        a1 = a0 + a1
        a0 = tmp
    return a1

n, m = map(int, input().split())
*a_list, = map(int, input().split())
a_list = a_list + [n]

count = 1
_a = 0
for a in a_list:
    num = a - _a - 1
    count = count * fib(num) % 1000000007
    _a = a
print(count)

Submission status: Runtime Error

Solution code:
def fib(x):
   if x == 1:
    return 1
  a0 = 1
  a1 = 1
  for i in range(x-1):
    tmp = a1
    a1 = a0 + a1
    a0 = tmp
  return a1

n, m = map(int, input().split())
*a_list, = map(int, input().split())
a_list = a_list + [n]

count = 1
_a = 0
for a in a_list:
  num = a - _a
  count = count * fib(num) % 1000000007
  _a = a
print(count)

Submission status: Runtime Error

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

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

print(dp[N-1] % 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
dp = [0] * (N + 1)

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

print(dp[N] % MOD)

Submission status: Runtime Error

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

arr=[0]*N

if 1 in a:
    arr[0]=0
else:
    arr[0]=1

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

print(arr[-1]%(10**9+7))

Submission status: Runtime Error

Solution code:
def step(n, A):
    if n == 1:
        return 1
    elif n == 2:
        return 2
    elif n in A:
        return 0
    else:
        return step(n-1, A) + step(n-2, A)

N, M = map(int, input().split())
A = [int(input()) for i in range(M)]
print(step(N, A))

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
# A = set()
# for i in range(m):
#     a = int(input())
#     A.add(a)
a = []
for i in range(m):
    a.append(int(input()))
    A = a
dp = [0] * (n + 1)
for i in range(n + 1):
    if i in A:
        dp[i] = 0
    else:
        if i == 0:
            dp[i] = 1
        elif i == 1:
            dp[i] = 1
        else:
            dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007
print(dp[n])

"""
100 5
1
23
45
67
89
"""

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
# A = set()
# for i in range(m):
#     a = int(input())
#     A.add(a)
a = set()
for i in range(m):
    a.append(int(input()))
    A = a
dp = [0] * (n + 1)
for i in range(n + 1):
    if i in A:
        dp[i] = 0
    else:
        if i == 0:
            dp[i] = 1
        elif i == 1:
            dp[i] = 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 = set()
for i in range(m):
    a = int(input())
    A.add(a)
dp = [0] * (n + 1)
for i in range(n + 1):
    if i in a:
        dp[i] = 0
    else:
        if i == 0:
            dp[i] = 1
        elif i == 1:
            dp[i] = 1
        else:
            dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007
print(dp[n])

"""
100 5
1
23
45
67
89
"""

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
A = set()
for i in range(m):
    a.append(int(input()))
    A.add(a)
dp = [0] * (n + 1)
for i in range(n + 1):
    if i in a:
        dp[i] = 0
    else:
        if i == 0:
            dp[i] = 1
        elif i == 1:
            dp[i] = 1
        else:
            dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007
print(dp[n])

"""
100 5
1
23
45
67
89
"""

Submission status: Runtime Error

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

dp = [0] * (n + 1)

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

print(int(dp[n]))

"""
100 5
1
23
45
67
89
"""

Submission status: Runtime Error

Solution code:
import numpy as np

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

dp = np.zeros(n + 1)
dp[0] = 1
if a[0] == 1:
    dp[1] = 0
else:
    dp[1] = 1

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

print(int(dp[n]))

"""
100 5
1
23
45
67
89
"""

Submission status: Runtime Error

Solution code:
import numpy as np


def chmin(a1, a2):
    if a1 <= a2:
        return a1
    elif a1 > a2:
        return a2


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

dp = np.full(n + 1, np.inf)
dp[0] = 1
if a[0] == 1:
    dp[1] = 0
else:
    dp[1] = 1

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

print(int(dp[n]))

"""
100 5
1
23
45
67
89
"""

Submission status: Runtime Error

Solution code:


N, M = map(int, input().split())
a=[]
step=[0]*200000
total=1
count=0
num=0

for i in range(M):
    a.append(int(input()))

for x in range(M):
    num=a[x]-a[x-1]
    if(num==1):
        print(0)
        exit(0)
    else:
        num=0

step[0]=1
for k in range(1,N+1):
    if M!=0:
        if k==a[count]:
            step[k]=0
            if count<M-1:
                    count +=1
        else:
            if k>0:
                step[k]+=step[k-1]
            if k>1:
                step[k]+=step[k-2]
    else:
        if k > 0:
            step[k] += step[k - 1]
        if k > 1:
            step[k] += step[k - 2]



print(step[N]%1000000007

Submission status: Runtime Error

Solution code:


N, M = map(int, input().split())
a=[]
step=[0]*200000
total=1
count=0
num=0

for i in range(M):
    a.append(int(input()))

for x in range(M):
    num=a[x]-a[x-1]
    if(num==1):
        print(0)
        exit(0)
    else:
        num=0

step[0]=1
for k in range(1,N+1):
    if k==a[count]:
        step[k]=0
        if count<M-1:
            count +=1
    else:
        if k>0:
            step[k]+=step[k-1]
        if k>1:
            step[k]+=step[k-2]


print(step[N]%1000000007)

Submission status: Runtime Error

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

a_s = []

for _ in range(M):
    a_m = int(input())
    a_s.append(a_m)

def count(n):
    if n == 0:
        return 1
    elif n == 1:
        return 1
    elif n in a_s:
        return 0
    else:
        return count(n-1) + count(n-2)

ans = count(N) % 1000000007;

print(ans)

Submission status: Runtime Error

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

n,m = map(int, input().split())
a = [0] + [int(input()) for _ in range(m)] + [n]
dif = [0]*(m+1)
for i in range(m+1):
  dif[i] = a[i+1] - a[i] - 1
if 0 in dif:
  print(0)
else:
  dif[-1] += 1
  print(np.mod(np.prod(list(map(F,dif))),MOD))

Submission status: Runtime Error

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

for i in range(M):
  d[a[i]] = 1

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

Submission status: Runtime Error

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

stairs = [1] * (N+1)
for i in reversed(range(N+1)):
    if i in A:
        stairs[i] = 0
        continue

    one_step, two_step = 1, 0
    if stairs[i+1:i+2]:
        one_step = stairs[i+1]
    if stairs[i+2:i+3]:
        two_step = stairs[i+2]

    stairs[i] = one_step + two_step
print(stairs[0] % 1_000_000_007)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
import bisect
from collections import defaultdict

def main():
    N, M = map(int, input().split())
    As = set([int(input()) for i in range(M)])
    BIG_NUM = 1000000007

    prev_prev_step = 1
    if 1 in As:
        prev_step = 0
    else:
        prev_step = 1

    for i in range(2, N+1):
        if i in As:
            current_step = 0
        else:
            current_step = (prev_step + prev_prev_step) % BIG_NUM
        prev_prev_step = prev_step
        prev_step = current_step

    print(current_step)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#coding:utf-8
#dp[i]:i段目に登るまでの組み合わせ総数
#dp[i] = dp[i-1] + dp[i-2] if dp[i] != B[i] else 0
N,M = list(map(int,input().split()))
B = [True] * N
try:
    for _ in range(M):
        B[int(input())-1] = False
except:
    print(0)
    import sys
    sys.exit(1)
dp = [0] * N
if B[0]:
    dp[0] = 1
dp[1] = dp[0] + 1 if B[1] else 0
mod = 10**9 + 7
for i in range(2,N):
    if B[i] :
        dp[i] = dp[i-1] + dp[i-2]
        dp[i] %= mod
print(dp[-1])

Submission status: Runtime Error

Solution code:
#coding:utf-8
#dp[i]:i段目に登るまでの組み合わせ総数
#dp[i] = dp[i-1] + dp[i-2] if dp[i] != B[i] else 0
N,M = list(map(int,input().split()))
B = [True] * N
for _ in range(M):
    B[int(input())-1] = False
dp = [0] * N
dp[0] = 1 if B[0] else 0
dp[1] = dp[0] + 1 if B[1] else 0
mod = 10**9 + 7
for i in range(2,N):
    if B[i] :
        dp[i] = dp[i-1] + dp[i-2]
        dp[i] %= mod
print(dp[-1])

Submission status: Runtime Error

Solution code:
W,H,x,y = [int(i) for i in input().split()]
flag=0
if W==x+x and H==y+y:
    flag=1



print(W*H/2,flag)

Submission status: Runtime Error

Solution code:
W,H,x,y = [int(i) for i in input().split()]
flag=0
if W==x*2 and H==y*2:
    flag=1



print(W*H/2,flag)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
from math import floor  
stairs_num, broken_num = tuple(int(i) for i in input().split(" "))
broken_list = []
for i in range(broken_num):
    broken_list.append(int(input()))
trance_num_list = []
if len(broken_list) >= 1 and broken_list[0] == 1:
    trance_num_list.append(0)
else:
    trance_num_list.append(1)
if (len(broken_list) >= 1 and broken_list[0] == 2) or \
 (len(broken_list) >= 2 and broken_list[1] == 2):
    trance_num_list.append(0)
else:
    if trance_num_list[0] == 0:
        trance_num_list.append(1)
    else:
        trance_num_list.append(2)
if stairs_num > 2:
    a = len(broken_list)
    for i in range(stairs_num - 2):
        key = 0
        left = 0
        right = a
        while left < right:
            midle = floor(left + right)
            if broken_list[midle] < i + 3:
                left = midle + 1
            elif broken_list[midle] == i + 3:
                key = 1
                break
            else:
                right = midle - 1
        if key:
            trance_num_list.append(0)
        else:
            trance_num_list.\
             append((trance_num_list[-1] + trance_num_list[-2]) % 1000000007)
print(trance_num_list[stairs_num - 1])

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
a = [0] * m
dp = [1, 1]
x = 0
for i in range(m):
    a[i] = int(input())
if a[0] == 1:
    dp[1] = 0
    x = 1

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


for i in range(2, n+1):
    if i != a[x]:
        dp.append((dp[-1] + dp[-2]) % 1000000007)
    else:
        dp.append(0)
        if x < len(a)-1:
            x += 1
# print(dp)
print(dp[-1])

Submission status: Runtime Error

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

for i in range(m):
    a[i] = int(input())

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

x = 0
for i in range(1, n+1):
    if i != a[x]:
        dp.append((dp[-1] + dp[-2]) % 1000000007)
    else:
        dp.append(0)
        if x < len(a)-1:
            x += 1
# print(dp)
print(dp[-1])

Submission status: Runtime Error

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

for i in range(m):
    a[i] = int(input())

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

x = 0
for i in range(1, n+1):
    if i != a[x]:
        dp.append((dp[-1] + dp[-2]) % 1000000007)
    else:
        dp.append(0)
        if x < len(a)-1:
            x += 1
# print(dp)
print(dp[-1])

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Wed Jun 19 17:29:01 2019

@author: makigon
"""
mod = 10 ** 9 + 7
N, M = map(int, input().split())
a = [int(input()) for i in range(M)]

aset = set(a)
f = [0 for i in range(N)]
f[0] = 1
if 1 in a:
    f[1] = 0
else:
    f[1] = 1

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

if N == 1:
    print(f[i-1])
else:       
    print((f[N-1]+f[N-2]) % mod)