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 numpy as np
N, M = map(int, input().split())
A = np.array([int(input()) for _ in range(M)], dtype = int)

MOD= 1000000007
dp = np.zeros(N, dtype = int)
if M != 0:
    dp[A - 1] = -1

if dp[0] == -1 and dp[1] == -1:
    pass
elif dp[0] == -1:
    dp[1] = 1
# elif dp[1] == -1:
#     dp[0] = 1
else:
    dp[0] = 1
    dp[1] = 2


if N >= 3:
    for n in range(2, N):
        if dp[n] != -1:
            dp[n] = (max(dp[n-1], 0) + max(dp[n-2], 0)) % MOD

print (dp[-1])

Submission status: Runtime Error

Solution code:
import numpy as np
N, M = map(int, input().split())
A = np.array([int(input()) for _ in range(M)], dtype = int)

MOD= 1000000007
dp = np.zeros(N, dtype = int)
if M != 0:
    dp[A - 1] = -1

if dp[0] == -1 and dp[1] == -1:
    pass
elif dp[0] == -1:
    dp[1] = 1
elif dp[1] == -1:
    dp[0] = 1
else:
    dp[0] = 1
    dp[1] = 2


# if N >= 3:
#     for n in range(2, N):
#         if dp[n] != -1:
#             dp[n] = (max(dp[n-1], 0) + max(dp[n-2], 0)) % MOD

print (dp[-1])

Submission status: Runtime Error

Solution code:
import numpy as np
N, M = map(int, input().split())
if M == 1:
    A = int(input())
else:
    A = np.array([int(input()) for _ in range(M)], dtype = int)

MOD= 1000000007
dp = np.zeros(N, dtype = int)
dp[A - 1] = -1
if dp[0] == -1 and dp[1] == -1:
    pass
elif dp[0] == -1:
    dp[1] = 1
elif dp[1] == -1:
    dp[0] = 1
# else:
#     dp[0] = 1
#     dp[1] = 2


# if N >= 3:
#     for n in range(2, N):
#         if dp[n] != -1:
#             dp[n] = (max(dp[n-1], 0) + max(dp[n-2], 0)) % MOD

print (dp[-1])

Submission status: Runtime Error

Solution code:
import numpy as np
N, M = map(int, input().split())
if M == 1:
    A = int(input())
else:
    A = np.array([int(input()) for _ in range(M)], dtype = int)

MOD= 1000000007
dp = np.zeros(N, dtype = int)
dp[A - 1] = -1
if dp[0] == -1 and dp[1] == -1:
    pass
elif dp[0] == -1:
    dp[1] = 1
elif dp[1] == -1:
    dp[0] = 1
else:
    dp[0] = 1; dp[1] = 2;


# if N >= 3:
#     for n in range(2, N):
#         if dp[n] != -1:
#             dp[n] = (max(dp[n-1], 0) + max(dp[n-2], 0)) % MOD

print (dp[-1])

Submission status: Runtime Error

Solution code:
import numpy as np
N, M = map(int, input().split())
if M == 1:
    A = int(input())
else:
    A = np.array([int(input()) for _ in range(M)], dtype = int)

MOD= 1000000007
dp = np.zeros(N, dtype = int)
dp[A - 1] = - 1
if dp[0] == -1 and dp[1] == -1:
    pass
elif dp[0] == -1:
    dp[1] = 1
elif dp[1] == -1:
    dp[0] = 1
else:
    dp[0] = 1; dp[1] = 2;


# if N >= 3:
#     for n in range(2, N):
#         if dp[n] != -1:
#             dp[n] = (max(dp[n-1], 0) + max(dp[n-2], 0)) % MOD

print (dp[-1])

Submission status: Runtime Error

Solution code:
import numpy as np
N, M = map(int, input().split())
if M == 1:
    A = int(input())
else:
    A = np.array([int(input()) for _ in range(M)], dtype = int)

MOD= 1000000007
dp = np.zeros(N, dtype = int)
dp[A - 1] = - 1
if dp[0] == -1 and dp[1] == -1:
    pass
elif dp[0] == -1:
    dp[1] = 1
elif dp[1] == -1:
    dp[0] = 1
else:
    dp[0] = 1; dp[1] = 2;


if N >= 3:
    for n in range(2, N):
        if dp[n] != -1:
            dp[n] = (max(dp[n-1], 0) + max(dp[n-2], 0)) % MOD

print (dp[-1])

Submission status: Runtime Error

Solution code:
import numpy as np
N, M = map(int, input().split())
if M == 1:
    A = int(input())
else:
    A = np.array([int(input()) for _ in range(M)], dtype = int)
l_a = len(A)

MOD= 1000000007
dp = np.zeros(N, dtype = int)
dp[A - 1] = - 1
if dp[0] == -1 and dp[1] == -1:
    pass
elif dp[0] == -1:
    dp[1] = 1
elif dp[1] == -1:
    dp[0] = 1
else:
    dp[0] = 1; dp[1] = 2;


if N >= 3:
    for n in range(2, N):
        if dp[n] != -1:
            dp[n] = (max(dp[n-1], 0) + max(dp[n-2], 0)) % MOD

print (dp[-1])

Submission status: Runtime Error

Solution code:
import numpy as np
N, M = map(int, input().split())
A = np.array([int(input()) for _ in range(M)], dtype = int)
l_a = len(A)

MOD= 1000000007
dp = np.zeros(N, dtype = int)
dp[A - 1] = - 1
if dp[0] == -1 and dp[1] == -1:
    pass
elif dp[0] == -1:
    dp[1] = 1
elif dp[1] == -1:
    dp[0] = 1
else:
    dp[0] = 1; dp[1] = 2;


if N >= 3:
    for n in range(2, N):
        if dp[n] != -1:
            dp[n] = (max(dp[n-1], 0) + max(dp[n-2], 0)) % MOD

print (dp[-1])

Submission status: Runtime Error

Solution code:
import numpy as np
N, M = map(int, input().split())
A = np.array([int(input()) for _ in range(M)], dtype = int)
l_a = len(A)

MOD= 1000000007
dp = np.zeros(N, dtype = int)
dp[A - 1] = - 1
if dp[0] == -1 and dp[1] == -1:
    pass
elif dp[0] == -1:
    dp[1] = 1
elif dp[1] == -1:
    dp[0] = 1
else:
    dp[0] = 1; dp[1] = 2;


for n in range(2, N):
    # print (dp)
    if dp[n] != -1:
        dp[n] = (max(dp[n-1], 0) + max(dp[n-2], 0)) % MOD

print (dp[-1])

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
ss = [1]*n
for i in range(0,m):
    ss[int(input())-1] = 0
if ss[n-3] != 0:
    ss[n-3] = ss[n-2]+ ss[n-1]
for i in range(n-4,-1,-1):
    if ss[i] == 0:
        continue
    ss[i] = ss[i+1] + ss[i+2]
print((ss[0]+ss[1])%(10**9+7))

Submission status: Runtime Error

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

traps = {}
for i in range(m):
    t = int(input())
    traps[t] = 1

mem = {}

def f(k):
    if k in mem:
        return mem[k]

    if k >= n:
        return 0
    if k == n - 1:
        return 1
    if k == n - 2:
        if n - 1 in traps:
            return 1
        else:
            return 2

    res = 0
    if k + 1 not in traps:
        res += f(k + 1)
    if k + 2 not in traps:
        res += f(k + 2)
    mem[k] = res
    return res % MOD

print(f(0))

Submission status: Runtime Error

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

sum = 0
start = 0
for i in range(M):
  sum += (a[i] - start - 1)**2
  start = a[i] + 1
  
sum += (N - a[M-1] - 1)**2
print(sum % 1000000007)

Submission status: Runtime Error

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

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

if m >= 2:
    for i in range(1, m):
        if steps[i] - steps[i-1] == 1:
            print(0)
            exit()

res = 1
nowstep = 0
for i in range(m):
    res *= stepcmb(steps[i]-nowstep-1) % (10**9+7)
    nowstep = steps[i] + 1
res = (res * stepcmb(n-nowstep)) % (10**9+7)

print(res)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
a = [-1]
flag = True

if m>0:
  for i in range(m):
    a.append(int(input()))
    if i>0 and a[i+1]==a[i]+1:
      flag = False
    break
  if not flag:
    print(0)
  
  a.append(n+1)
  step = [a[i+1]-a[i]-1 for i in range(m+1)]
  onestep = [1,1]
  if max(step)>=3:
    for i in range(3,max(step)+1):
      onestep.append(onestep[-2]+onestep[-1])
  
  ans = 1
  for i in range(m+1):
    ans *= onestep[step[i]-1]
  if flag:
    print(ans%1000000007)
else:
  onestep=[1,1]
  for i in range(2,n+1):
    onestep.append(onestep[-2]+onestep[-1])
  print(onestep[-1])

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
a = [-1]
flag = True
for i in range(m):
  a.append(int(input()))
  if i>0 and a[i+1]==a[i]+1:
    flag = False
    break
if not flag:
  print(0)
a.append(n+1)

step = [a[i+1]-a[i]-1 for i in range(m+1)]

onestep = [1,1]
if max(step)>=3:
  for i in range(3,max(step)+1):
    onestep.append(onestep[-2]+onestep[-1])

ans = 1
for i in range(m+1):
  ans *= onestep[step[i]-1]
if flag:
  print(ans%1000000007)

Submission status: Runtime Error

Solution code:
def Fib(n, memo={}):
    if n == 1:
        return 1
    elif n == 2:
        return 1
    elif n in memo:
        return memo[n]
    else:
        memo[n] = Fib(n-1,memo)+Fib(n-2,memo)
        return memo[n]
n,m=map(int,input().split())
if m==0:
	print(Fib(n+1)%(10**9+7))
	exit()
a=[]
for i in range(m):
	a.append(int(input()))
if a[0]!=1:
	a.insert(0,-1)
if a[-1]!=n-1:
	a.append(n+1)
b=[]
for i in range(len(a)-1):
	b.append(a[i+1]-a[i]-1)
	if a[i+1]-a[i]==1:
		print(0)
		exit()
ans=1
for i in range(len(b)):
	ans*=Fib(b[i])
	ans%=10**9+7
print(ans)

Submission status: Runtime Error

Solution code:
def Fib(n, memo={}):
    if n == 1:
        return 1
    elif n == 2:
        return 1
    elif n in memo:
        return memo[n]
    else:
        memo[n] = Fib(n-1,memo)+Fib(n-2,memo)
        return memo[n]
n,m=map(int,input().split())
if m==0:
	print(Fib(n+1))
	exit()
a=[]
for i in range(m):
	a.append(int(input()))
if a[0]!=1:
	a.insert(0,-1)
if a[-1]!=n-1:
	a.append(n+1)
b=[]
for i in range(len(a)-1):
	b.append(a[i+1]-a[i]-1)
	if a[i+1]-a[i]==1:
		print(0)
		exit()
ans=1
for i in range(len(b)):
	ans*=Fib(b[i])
	ans%=10**9+7
print(ans)

Submission status: Runtime Error

Solution code:
def Fib(n, memo={}):
    if n == 1:
        return 1
    elif n == 2:
        return 1
    elif n in memo:
        return memo[n]
    else:
        memo[n] = Fib(n-1,memo)+Fib(n-2,memo)
        return memo[n]
n,m=map(int,input().split())
if m==0:
	print(Fib(n))
	exit()
a=[]
for i in range(m):
	a.append(int(input()))
if a[0]!=1:
	a.insert(0,-1)
if a[-1]!=n-1:
	a.append(n+1)
b=[]
for i in range(len(a)-1):
	b.append(a[i+1]-a[i]-1)
	if a[i+1]-a[i]==1:
		print(0)
		exit()

ans=1
for i in range(len(b)):
	ans*=Fib(b[i])
	ans%=10**9+7
print(ans)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
a=[]
for i in range(m):
	a.append(int(input()))
if a[0]!=1:
	a.insert(0,-1)
if a[-1]!=n-1:
	a.append(n+1)
b=[]
for i in range(len(a)-1):
	b.append(a[i+1]-a[i]-1)
	if a[i+1]-a[i]==1:
		print(0)
		exit()
def Fib(n, memo={}):
    if n == 1:
        return 1
    elif n == 2:
        return 1
    elif n in memo:
        return memo[n]
    else:
        memo[n] = Fib(n-1,memo)+Fib(n-2,memo)
        return memo[n]
ans=1
for i in range(len(b)):
	ans*=Fib(b[i])
	ans%=10**9+7
print(ans)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
a=[]
for i in range(m):
	a.append(int(input()))
if a[0]!=1:
	a.insert(0,-1)
if a[-1]!=n-1:
	a.append(n+1)
b=[]
for i in range(len(a)-1):
	b.append(a[i+1]-a[i]-1)
	if a[i+1]-a[i]==1:
		print(0)
		exit()
def Fib(n, memo={}):
    if n == 1:
        return 1
    elif n == 2:
        return 1
    elif n in memo:
        return memo[n]
    else:
        memo[n] = Fib(n-1,memo)+Fib(n-2,memo)
        return memo[n]
ans=1
for i in range(len(b)):
	ans*=Fib(b[i])
	ans%=10**9+7
print(ans)
print(b)

Submission status: Runtime Error

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

memo = [-1]*(N+1)
memo[0] = 1

def dodp(x):
    if memo[x] != -1:
        pass
    elif x in a:
        memo[x] = 0
    elif x == 1:
        memo[x] = dodp(x-1)
    else:
        memo[x] = dodp(x-1)+dodp(x-2)
    memo[x] %= MOD
    return memo[x]
    
dodp(N)
print(memo[N])

Submission status: Runtime Error

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

def fib(n):
    if (n==1) or (n==2):
        return 1
    else:
        return fib(n-1)+fib(n-2)

start = 0
ans = 1

for k in a:
    tmp = k-start
    if tmp==0:
        print(0)
        exit(0)
    ans *= fib(tmp)
    ans%=mod
    start = k+1

ans*=fib(n-start+1)
ans%=mod

print(ans)

Submission status: Runtime Error

Solution code:
import sys


"""
# 標準入力取得
## 文字列
    = sys.stdin.readline().rstrip()
    = list(sys.stdin.readline().rstrip())

## 数値
    = int(sys.stdin.readline())
    = map(int, sys.stdin.readline().split())
    = list(map(int, sys.stdin.readline().split()))
    = [list(map(int,list(sys.stdin.readline().split()))) for i in range(N)]
"""

if __name__ == "__main__":
    N , M = map(int, sys.stdin.readline().split())
    A = [int(sys.stdin.readline()) for _ in range(M)]
    broken = [True if i in A else False for i in range(N + 1)]
    L = [0] * (N + 1)
    L[0] = 1
    if not broken[1]:
        L[1] = 1
    for i in range(2, N + 1):
        if not broken[i]:
            L[i] = L[i - 1] + L[i - 2]
    print(L[N] % mod)

Submission status: Runtime Error

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

#listの中をinで探すのはくっそ遅い
if N == 1:
    print(1)
    exit()
if 1 in a and 2 in a:
    print(0)
    exit()
if 1 in a:
    n[0] = 0
    n[1] = 1
if 2 in a:
    n[1] = 0

for i in range(N - 2):
    if i + 3 in a:
        pass
    else:
        n[i + 2] = (n[i + 1] + n[i]) % 1000000007

print(n[N - 1])

Submission status: Runtime Error

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

#listの中をinで探すのはくっそ遅い
if N == 1:
    print(1)
    exit()
if 1 in a and 2 in a:
    print(0)
    exit()
if 1 in a:
    n[0] = 0
    n[1] = 1

for i in range(N - 2):
    if i + 3 in a:
        pass
    else:
        n[i + 2] = (n[i + 1] + n[i]) % 1000000007

print(n[N - 1])

Submission status: Runtime Error

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

#listの中をinで探すのはくっそ遅い
if 1 in a and N == 1:
    print(0)
    exit()
if 1 in a and 2 in a:
    print(0)
    exit()
if 1 in a:
    n[0] = 0
    n[1] = 1

for i in range(N - 2):
    if i + 3 in a:
        pass
    else:
        n[i + 2] = (n[i + 1] + n[i]) % 1000000007

print(n[N - 1])

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
a = set(map(int, input().split()))
n = [0] * N
n[0] = 1
n[1] = 2

if 1 in a and N == 1:
    print(0)
    exit()
if 1 in a and 2 in a:
    print(0)
    exit()
if 1 in a:
    n[0] = 0
    n[1] = 1

for i in range(N - 2):
    if i + 3 in a:
        pass
    else:
        n[i + 2] = (n[i + 1] + n[i]) % 1000000007

print(n[N - 1])

Submission status: Runtime Error

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

if 1 in a and N == 1:
    print(0)
    exit()
if 1 in a and 2 in a:
    print(0)
if 1 in a:
    n[0] = 0
    n[1] = 1

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

print(n[N - 1])

Submission status: Runtime Error

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

if 1 in a and N == 1: print(0), exit()

for i in range(N - 2):
    if i + 3 not in a:
        n[i + 2] = n[i + 1] + n[i]
print(n[N - 1])

Submission status: Runtime Error

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

nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]

def v(x):
    if x == -1:
        return 1
    else:
        q = x // 2
        r = x % 2
        ans = 0
        for i in range(x // 2 + 1):
            ans += cmb(q + r, r)
            r = r + 2
            q = q - 1
        return ans
for i in range(M + 1):
    if a[i + 1] - a[i] == 1:
        print(0)
        exit()

for i in range(M + 1):
    n = n * v((a[i + 1] - 1) - (a[i] + 1)) % 1000000007

print(n)

Submission status: Runtime Error

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

nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]

def v(x):
    if x == -1:
        return 1
    else:
        q = x // 2
        r = x % 2
        ans = 0
        for i in range(x // 2 + 1):
            ans += cmb(q + r, r)
            r = r + 2
            q = q - 1
        return ans
for i in range(M + 1):
    if a[i + 1] - a[i] == 1:
        print(0)
        exit()

for i in range(M + 1):
    n *= v((a[i + 1] - 1) - (a[i] + 1))  % 1000000007

print(n)

Submission status: Runtime Error

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

  if a[0]==1:
    way=[1, 0]
    a.remove(1)
  else:
    way=[1, 1]
else:
  way=[1, 1]
  
for i in range(2, N+1):
  if len(a)>0:
    if i==a[0]:
      a.remove(i)
      way=[way[1], 0]
    else:
      way=[way[1], sum(way)]
  else:
    way=[way[1], sum(way)]
    
print(way[1]%1000000007)

Submission status: Runtime Error

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

if a[0]==1:
  way=[1, 0]
  a.remove(1)
else:
  way=[1, 1]
  
for i in range(2, N+1):
  if len(a)>0:
    if i==a[0]:
      a.remove(i)
      way=[way[1], 0]
    else:
      way=[way[1], sum(way)]
  else:
    way=[way[1], sum(way)]
    
print(way[1]%1000000007)

Submission status: Runtime Error

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

nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]

def v(x):
    if x == -1:
        return 1
    else:
        q = x // 2
        r = x % 2
        ans = 0
        for i in range(x // 2 + 1):
            ans += cmb(q + r, r)
            r = r + 2
            q = q - 1
        return ans
for i in range(M + 1):
    if a[i + 1] - a[i] == 1:
        print(0)
        exit()

for i in range(M + 1):
    n *= v((a[i + 1] - 1) - (a[i] + 1))

print(n % 1000000007)

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
A=[int(input()) for i in range(M)]
dp=[0]*(N+1)
idx=0
dp[0]=1
if A[idx]==1:
    dp[1]=0
    if M>1:idx+=1
else:
    dp[1]=1

for i in range(2,N+1):
    if A[idx]==i:
        dp[i]=0
        if idx+1<M:idx+=1
    else:
        dp[i]=(dp[i-1]+dp[i-2])%(10**9+7)
print(dp[-1])

Submission status: Runtime Error

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

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

f = [0 for i in range(n+1)]
f[-2:] = [1, 1]
for i in range(m):
  f[int(input())-1] = -1

div_num = 1000000007

for index in range(n-1)[::-1]:
  i = index + 1
  if f[i] == -1:
    continue
  if f[i+1] == -1 and f[i+2] == -1:
    print(0)
    exit()
  elif f[i+1] == -1 and f[i+2] != -1:
    f[i] = f[i+2]
  elif f[i+1] != -1 and f[i+2] == -1:
    f[i] = f[i+1]
  else:
    f[i] = f[i+1]+f[i+2]

print(int(f[0]%div_num))

Submission status: Runtime Error

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

f = [1, 1]
for i in range(n-1)[::-1]:
  flag1 = True if i+1 not in alist else False
  flag2 = True if i+2 not in alist else False
  if flag1 is False and flag2 is False:
    print(0)
    exit()
  elif falg1 is False and flag2 is True:
    f = [f[1]] + [f[0]]
  elif flag1 is True and flag2 is False:
    f = [f[0]] + [f[0]]
  else:
    f = [f[0]+f[1]] + [f[0]]
     
print(int(f[0]%div_num))

Submission status: Runtime Error

Solution code:
n, m = [int(x) for x in input().split(' ')]
a = set(int(input()) for x in range(m))

m = [0] * n
m[0] = 1 if 1 not in a else 0
m[1] = 2 if 2 not in a else 0

if m[0] == 0 and m[1] == 2:
    m[1] = 1

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

print(m[-1] % 1000000007)

Submission status: Runtime Error

Solution code:
from math import factorial

def cases(idx_start, idx_end):
  cases = 0
  for r in range((idx_end - idx_start)//2+1):
    n = idx_end - idx_start - r
    cases += factorial(n) / factorial(r) / factorial(n - r)
  return cases

n, m  = map(int, input().split())
alist = [int(input()) for i in range(m)]
div_num = 1000000007

if m == 0:
  print(cases(1,n+1)%div_num)
  exit()

ans = cases(1,alist[0])
for i in range(1,m):
  if alist[i] - alist[i-1] <= 1:
    print(0)
    exit()
  ans *= cases(alist[i-1]+1, alist[i])
ans *= cases(alist[-1]+1, n+1)
print(int(ans%div_num))

Submission status: Runtime Error

Solution code:
from math import factorial

def cases(idx_start, idx_end):
  cases = 0
  for r in range((idx_end - idx_start)//2+1):
    n = idx_end - idx_start - r
    cases += factorial(n) / factorial(r) / factorial(n - r)
  return cases

n, m  = map(int, input().split())
alist = [int(input()) for i in range(m)]
div_num = 1000000007

ans = cases(1,alist[0])
for i in range(1,m):
  if alist[i] - alist[i-1] <= 1:
    print(0)
    exit()
  ans *= cases(alist[i-1]+1, alist[i])
ans *= cases(alist[-1]+1, n+1)
print(int(ans%div_num))

Submission status: Runtime Error

Solution code:
big = 10**9 + 7

def typical_stairs(n,m,a):

    flag = [True]*(n+1)
    for i in range(m):
        tmp = a[i]
        flag[tmp] = False

    route = [0]*(n+1)
    route[0] = 1
    if flag[1]:
        route[1] = 1
    else:
        route[1] = 0

    for i in range(2,n+1):
        if flag[i]:
            route[i] = route[i-1] + route[i-2]

        ans = route[i]

    return ans%big
if __name__ == '__main__':
    n,m = map(int,raw_input().split())
    a = [int(raw_input()) for _ in range(m)]

    print typical_stairs(n,m,a)

Submission status: Runtime Error

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

dp = [0] * N
if 1 in a:
    dp[0] = 0
    if 2 in a:
        dp[0] = 0
    else:
        dp[1] = 1
else:
    dp[0] = 1
    if 2 in a:
        dp[1] = 0
    else:
        dp[1] = 2

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

Submission status: Runtime Error

Solution code:
MOD = 10**9 + 7
N, M = map(int,input().split())
a = set(int(input()) for _ in range(M))
dp = [0] * N
if 1 in a:
    dp[0] = 0
    if 2 in a:
        dp[0] = 0
else:
    dp[0] = 1
    if 2 in a:
        dp[1] = 0
    else:
        dp[1] = 2

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

Submission status: Runtime Error

Solution code:
MOD = 10**9 + 7
N, M = map(int,input().split())
a = set(int(input()) for _ in range(M))
dp = [0] * N
if 1 not in a:
    dp[0] = 1
    if 2 not in a:
        dp[1] = 2
else:
    if 2 not in a:
        dp[1] = 1

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

Submission status: Runtime Error

Solution code:
MOD = 1000000007
N, M = map(int,input().split())
a = [int(input()) for _ in range(M)]
dp = [0] * N
if 1 not in a:
    dp[0] = 1
    if 2 not in a:
        dp[1] = 2
else:
    if 2 not in a:
        dp[1] = 1

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

Submission status: Runtime Error

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

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

Submission status: Runtime Error

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

if a[0] = 0:
  print(0)
  exit()
#パターン数はフィボナッチ数列で通り数が増える
def Fib(n):
    a, b = 1, 1
    if n == 1:
        return a
    elif n == 2:
        return b
    else:
        for i in range(n-2):
            a, b = b, a + b
        return b
#aとa+1の間の距離nに対して、フィボナッチ数列n+1番目数のパターンが有る
ans = 1
if M > 1:
    for i in range(len(a)-1):
        n = a[i+1]-a[i]-1 #間の距離n
        if n == 0:
            print(0)
            exit()
        ans = ans*Fib(n+1)%1000000007
        i += 1
    print(ans)
elif M == 1:
    print(Fib(a[0])%1000000007 * Fib(N-a[0])%1000000007)
elif M == 0:
    print(Fib(N)%1000000007)

Submission status: Runtime Error

Solution code:
from functools import lru_cache

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

mod = 10**9+7

@lru_cache(maxsize=n)
def stairway(i) :
    if i in a :
        return 0
    elif i == 0 :
        return 1
    elif i == 1 :
        return stairway(0)
    else :
        return (stairway(i-1)+stairway(i-2))%mod
    
print(stairway(n))

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

n,m = map(int,input().split())
A = [int(input()) for _ in range(m)] #壊れた階段

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

for i in range(N+1):
    if (i+1) in A and (i+2) in A:
        print(0)
        exit()
    if (i+1) not in A:
        dp[i+1] += dp[i]
    if (i+2) not in A:
        dp[i+2] += dp[i]

print(dp[n])

Submission status: Runtime Error

Solution code:
import numpy as np
n,m=map(int,input().split())
lis=[]
ans=np.zeros(n+1)
ans[0]=1
for i in range(m):
    lis.append(int(input()))

if 1 not in lis:
    ans[1]=1

for i in range(n-1):
    if i+2 not in lis:
        ans[i+2]=ans[i]+ans[i+1]

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

Submission status: Runtime Error

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

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

num=max(b)

mod=1000000007

def fib(n,num):
    fib=[0 for i in range(num+10)]
    fib[0]=1
    fib[1]=1
    for i in range(2,num+1):
        fib[i]=fib[i-1]+fib[i-2]
    return fib[n]
p=1
for j in range(M+1):
    p*=fib(b[j],num)

if 0 in b[1:]:
    print(0)
else:
    print(p%mod)

Submission status: Runtime Error

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

DENOMINATOR = 1000000007

pos = 0
route = 1
before = 0

for i in range(1, N+1):
    route, before = route+before, route
    if A[pos] == i:
        route = 0
        if pos < M-1:
            pos+=1

print(route%DENOMINATOR)

Submission status: Runtime Error

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

b=[]
b.append(a[1]-a[0]-1)
for i in range(1,M):
    if i==0:
        b.append(1)
    elif a[i+1]-a[i]==1 and i!=0:
        b.append(0)
    else:
        b.append(a[i+1]-a[i]-2)
b.append(N-a[M]-1)

num=max(b)

mod=1000000007

def fib(n,num):
    fib=[0 for i in range(num+1)]
    fib[0]=1
    fib[1]=1
    for i in range(2,num+1):
        fib[i]=fib[i-1]+fib[i-2]
    return fib[n]
p=1
for j in range(M+1):
    p*=fib(b[j],num)

if 0 in b[1:]:
    print(0)
else:
    print(p%mod)

Submission status: Runtime Error

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

    if 1 not in lis:
        ans[1]=1

    for i in range(n-1):
        if i+2 not in lis:
            ans[i+2]=ans[i]+ans[i+1]

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

Submission status: Runtime Error

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

    if 1 not in lis:
        ans[1]=1

    for i in range(n-1):
        if i+2 not in lis:
            ans[i+2]=ans[i]+ans[i+1]

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
hole = []*(n+1)
for i in range(m):
  hole[int(input())] = 1
dp = [0]*(n+1)
MOD = 10**9+7
   
for i in range(1,n+1):
  if hole[i]==1:
    dp[i] = 0
  dp[i] = dp[i-1]+dp[i-2]
  dp[i] %= MOD

print(dp[-1])

Submission status: Runtime Error

Solution code:
d = {}


def calc_step_combination(num):
    if num == 0:
        return 0
    if num == 1 or num == 2:
        return 1
    if num in d:
        return d[num]
    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)
        batch_start = a + 1
    step_batch.append(n - batch_start + 1)

    result = 1
    for i, steps in enumerate(step_batch):
        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 or num == 2:
        return 1
    if num in d:
        return d[num]
    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)
        batch_start = a + 1
    step_batch.append(n - batch_start + 1)

    result = 1
    for i, steps in enumerate(step_batch):
        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 or num == 2:
        return 1
    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)
        batch_start = a + 1
    step_batch.append(n - batch_start + 1)

    result = 1
    for i, steps in enumerate(step_batch):
        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()