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
sys.setrecursionlimit(10000)

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


def forward(steps):
    global cnt
    if steps > n:
        return
    if steps == n:
        cnt += 1
        return
    elif steps in A:
        return

    forward(steps + 1)
    forward(steps + 2)


forward(0)
print(cnt % 1000000007)

Submission status: Runtime Error

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


def forward(steps):
    global cnt
    if steps > n:
        return
    if steps == n:
        cnt += 1
        return
    elif steps in A:
        return

    forward(steps + 1)
    forward(steps + 2)


forward(0)
print(cnt % 1000000007)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100001)

CONST = 1000000007

def noboru(i, a2, a1):
    if (i == 0 or i == 1):
        return a1
    elif (i == 2):
        return a2
    else:
        return noboru(i-1, a2+a1, a2)


def func(N, M, a):
    ans = 1
    pos = 0
    for i in range(M):
        if (pos == a[i]):
            return 0
        else:
            ans = (ans * noboru(a[i] - pos - 1, 2, 1)) % CONST
            pos = a[i] + 1
    ans = (ans * noboru(N - pos, 2, 1)) % CONST
    return ans

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

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100001)

CONST = 1000000007

def noboru(i, a2, a1):
    if (i == 0 or i == 1):
        return a1 % CONST
    elif (i == 2):
        return a2 % CONST
    else:
        return noboru(i-1, (a2+a1) % CONST, a2 % CONST)


def func(N, M, a):
    ans = 1
    pos = 0
    for i in range(M):
        if (pos == a[i]):
            return 0
        else:
            ans = (ans * noboru(a[i] - pos - 1, 2, 1)) % CONST
            pos = a[i] + 1
    ans = (ans * noboru(N - pos, 2, 1)) % CONST
    return ans

N, M = map(int, input().split(" "))
a = [int(input()) for _ in range(M)]
print(func(N, M, a))
# print(noboru(10000, 2, 1))
# print(sys.getrecursionlimit())

Submission status: Runtime Error

Solution code:
def noboru(i, a2, a1):
    if (i == 0 or i == 1):
        return a1
    elif (i == 2):
        return a2
    else:
        return noboru(i-1, a2+a1, a2)


def func(N, M, a):
    ans = 1
    pos = 0
    for i in range(M):
        if (pos == a[i]):
            return 0
        else:
            ans = (ans * noboru(a[i] - pos - 1, 2, 1)) % 1000000007
            pos = a[i] + 1
    ans = (ans * noboru(N - pos, 2, 1)) % 1000000007
    return ans

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

Submission status: Runtime Error

Solution code:
def noboru(i, a2, a1):
    if (i == 0 or i == 1):
        return a1
    elif (i == 2):
        return a2
    else:
        return noboru(i-1, a2+a1, a2)


def func(N, M, a):
    ans = 1
    pos = 0
    for i in range(M):
        if (pos == a[i]):
            return 0
        else:
            ans *= noboru(a[i] - pos - 1, 2, 1)
            pos = a[i] + 1
    ans *= noboru(N - pos, 2, 1)
    return ans

N, M = map(int, input().split(" "))
a = [int(input()) for _ in range(M)]
print(func(N, M, a) % 1000000007)

Submission status: Runtime Error

Solution code:
def noboru(i, a2, a1):
    if (i == 1):
        return a1
    elif (i == 2):
        return a2
    else:
        return noboru(i-1, a2+a1, a2)


def func(N, M, a):
    ans = 1
    for i in range(M):
        if (i==0):
            if (a[i] == 1):
                ans *= 1
            else:
                ans *= noboru(a[i] -1, 2, 1)
        elif(a[i] == a[i-1] + 1):
            return 0
        elif(a[i] == a[i-1] + 2):
            ans *= 1
        else:    
            ans *= noboru(a[i] - a[i-1] -2, 2, 1)
    ans *= noboru(N - a[M-1] -1, 2, 1)
    return ans

N, M = map(int, input().split(" "))
a = [int(input()) for _ in range(M)]
print(func(N, M, a) % 1000000007)

Submission status: Runtime Error

Solution code:
def noboru(i, a2, a1):
    if (i == 1):
        return a1
    elif (i == 2):
        return a2
    else:
        return noboru(i-1, a2+a1, a2)


def func(N, M, a):
    ans = 1
    if (a[0] == 1):
        ans *=1
    else:
        ans *= noboru(a[0]-1, 2, 1)
    if (M > 1):
        for i in range(1, M):
            if (a[i] == a[i-1]+1):
                return 0
            else:
                ans *= noboru(a[i] - a[i-1] -2, 2, 1)
    ans *= noboru(N - a[M-1] -1, 2, 1)
    return ans

N, M = map(int, input().split(" "))
a = [int(input()) for _ in range(M)]
#A_i = list(map(int, input().split(" ")))
#B_i = list(map(int, input().split(" ")))
print(func(N, M, a) % 1000000007)
#print(noboru(100, 2, 1))

Submission status: Runtime Error

Solution code:
def noboru(i, a2, a1):
    if (i == 1):
        return a1
    elif (i == 2):
        return a2
    else:
        return noboru(i-1, a2+a1, a2)


def func(N, M, a):
    ans = 1
    i = 0
    if (a[0] == 1):
        ans *=1
    else:
        ans *= noboru(a[0]-1,2,1)
    if (M > 1):
        for i in range(1, M):
            if (a[i] == a[i-1]+1):
                return 0
            else:
                ans *= noboru(a[i] - a[i-1] -2,2,1)
    ans *= noboru(N - a[i] -1,2,1)
    return ans

N, M = map(int, input().split(" "))
a = [int(input()) for _ in range(M)]
print(func(N, M, a) % 1000000007)

Submission status: Runtime Error

Solution code:
def noboru(m):
    if (m == 1):
        return 1
    elif (m == 2):
        return 2
    else:
        return noboru(m-1)+noboru(m-2)

def func(N, M, a):
    ans = 1
    i = 0
    if (a[0] == 1):
        ans *=1
    else:
        ans *= noboru(a[0]-1)
    if (M > 1):
        for i in range(1, M):
            if (a[i] == a[i-1]+1):
                return 0
            else:
                ans *= noboru(a[i] - a[i-1] -2)
    ans *= noboru(N - a[i] -1)
    return ans

N, M = map(int, input().split(" "))
a = [int(input()) for _ in range(M)]
#A_i = list(map(int, input().split(" ")))
#B_i = list(map(int, input().split(" ")))
print(func(N, M, a) % 1000000007)
#print(noboru(6))

Submission status: Runtime Error

Solution code:
def noboru(m):
    if (m == 1):
        return 1
    elif (m == 2):
        return 2
    else:
        return noboru(m-1)+noboru(m-2)

def func(N, M, a):
    ans = 1
    i = 0
    if (a[0] == 1):
        ans *=1
    else:
        ans *= noboru(a[0]-1)
    if (M > 1):
        for i in range(1, M):
            if (a[i] == a[i-1]+1):
                return 0
            else:
                ans *= noboru(a[i] - 2 - a[i-1])
    ans *= noboru(N - 1 - a[i])
    return ans % 1000000007

N, M = map(int, input().split(" "))
a = [int(input()) for _ in range(M)]
#A_i = list(map(int, input().split(" ")))
#B_i = list(map(int, input().split(" ")))
print(func(N, M, a))
#print(noboru(6))

Submission status: Runtime Error

Solution code:
def noboru(m):
    if (m == 1):
        return 1
    elif (m == 2):
        return 2
    else:
        return noboru(m-1)+noboru(m-2)

def func(N, M, a):
    ans = 1
    if (a[0] == 1):
        ans *=1
    else:
        ans *= noboru(a[0]-1)
    for i in range(1, M):
        if (a[i] == a[i-1]+1):
            return 0
        else:
            ans *= noboru(a[i] - 2 - a[i-1])
    ans *= noboru(a[M] - 1 - a[i])
    return ans % 1000000007

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

Submission status: Runtime Error

Solution code:
#129c
import sys
sys.setrecursionlimit(10000)

N,M = map(int, input().split())

now_step = 0
ans = 1
calculated_jump = {}
mod_number = 1000000007 

#開いている段数の移動パターンを算出する関数
def jump(now_step):
    
    if now_step in calculated_jump:
        return calculated_jump[now_step]
    else:
        if now_step == 2:
            return 2
        elif now_step == 1:
            return 1
        else:
            if now_step not in calculated_jump:
                calculated_jump[now_step] = jump(now_step-1) + jump(now_step-2)
                return jump(now_step-1) + jump(now_step-2)

for _ in range(M):
    a = int(input())
    
    if a == now_step:
        print("0")
        break
    elif a - 1 - now_step != 0: #左記成立時は1通りしかない。
        target_step_count = a - 1 - now_step #aは踏んではいけない段なので、その前がターゲット
        ans = ans * jump(target_step_count)
            
    now_step = a + 1

else:
    if now_step != N:
        target_step_count = N - now_step
        ans = ans * jump(target_step_count)
    
    print(ans % mod_number)

Submission status: Runtime Error

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

now_step = 0
ans = 1
calculated_jump = {}
mod_number = 1000000007 

#開いている段数の移動パターンを算出する関数
def jump(now_step):
    
    if now_step in calculated_jump:
        return calculated_jump[now_step]
    else:
        if now_step == 2:
            return 2
        elif now_step == 1:
            return 1
        else:
            if now_step not in calculated_jump:
                calculated_jump[now_step] = jump(now_step-1) + jump(now_step-2)
                return jump(now_step-1) + jump(now_step-2)

for _ in range(M):
    a = int(input())
    
    if a == now_step:
        print("0")
        break
    elif a - 1 - now_step != 0: #左記成立時は1通りしかない。
        target_step_count = a - 1 - now_step #aは踏んではいけない段なので、その前がターゲット
        ans = ans * jump(target_step_count)
            
    now_step = a + 1

else:
    if now_step != N:
        target_step_count = N - now_step
        ans = ans * jump(target_step_count)
    
    print(ans % mod_number)

Submission status: Runtime Error

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

now_step = 0
ans = 1
calculated_jump = {}
mod_number = 1000000007 

#開いている段数の移動パターンを算出する関数
def jump(now_step):
    
    if now_step in calculated_jump:
        return calculated_jump[now_step]
    else:
        if now_step == 2:
            return 2
        elif now_step == 1:
            return 1
        else:
            if now_step not in calculated_jump:
                calculated_jump[now_step] = jump(now_step-1) + jump(now_step-2)
                return jump(now_step-1) + jump(now_step-2)

for _ in range(M):
    a = int(input())
    
    if a == now_step:
        print("0")
        break
    elif a - 1 - now_step != 0: #左記成立時は1通りしかない。
        target_step_count = a - 1 - now_step #aは踏んではいけない段なので、その前がターゲット
        ans = ans * jump(target_step_count) % mod_number
            
    now_step = a + 1

else:
    if now_step != N:
        target_step_count = N - now_step
        ans = ans * jump(target_step_count) % mod_number
    
    print(ans)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
dp = [0] * (10**5)
jud = [True]*(n+1)
for k in range(m):
    a = int(input())
    jud[a] = False

dp[0] = 1
if jud[1]:
    dp[1] = 1
else:
    dp[1] = 0

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
from collections import deque
n, m = map(int, input().split())
a = set(int(input()) for _ in range(m))
M = 1000000007
dp = {}
dp[0] = 1
dp[1] = 1
for i in range(2, n+1):
    if i in a:
        dp[2] = 0
    else:
        dp[2] = dp[0] + dp[1]
    dp[0] = dp[1]
    dp[1] = dp[2]

print(dp[2] % M)

Submission status: Runtime Error

Solution code:
from collections import deque
n, m = map(int, input().split())
a = set(int(input()) for _ in range(m))
M = 1_000_000_007
dp = {}
dp[0] = 1
for i in range(1, n+1):
    if i in a:
        dp[i] = 0
        continue
    if i - 2 < 0:
        dp[i] = dp[i-1]
    else:
        dp[i] = dp[i-1] + dp[i-2]

print(dp[n] % M)

Submission status: Runtime Error

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

def fib(n,b):
  b = np.zeros(n+1,dtype="int64")
  if n <= 1:
    return 1
  elif b[n]!=0:
    return b[n]
  b[n] = fib(n-1,b) +fib(n-2,b)
  return b[n]

  
s = 0
x = 1
for i in range (0,M):
  if s == a[i]:
    print("0")
    sys.exit()
  g = a[i]-1
  b = np.zeros(g-s+1,dtype="int64")
  x = x * fib(g-s,b)
  s = g + 2

x = x * fib(N-s,b)
print(x % 1000000007)

Submission status: Runtime Error

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

def fib(n):
  if n <= 1:
    return 1
  return fib(n-1) +fib(n-2)
  
s = 0
x = 1
for i in range (0,M):
  if s == a[i]:
    print("0")
    sys.exit()
  g = a[i]-1
  x = x * fib(g-s)
  s = g + 2

x = x * fib(N-s)
print(x % 1000000007)

Submission status: Runtime Error

Solution code:
import sys
n,m = map(int,input().split())
a = []
for i in range(m):
    a.append(int(input()))
fib = [1,1]
for i in range(n):
    fib.append((fib[i]+fib[i+1])%1000000007)
if m == 0:
	print(fib[n])
    sys.exit()
answer = fib[a[0]-1]
for i in range(m-1):
    if a[i] + 1 == a[i+1]:
        answer = 0
    else:
        answer = answer * fib[a[i+1]-a[i]-2] % 1000000007
answer = answer * fib[n-a[m-1]-1] % 1000000007
print(answer)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
a = []
for i in range(m):
    a.append(int(input()))
fib = [1,1]
#n段登る場合の数がfib[n]になるようにする
for i in range(n):
    fib.append((fib[i]+fib[i+1])%1000000007)
answer = 1
answer *= fib[a[0]-1]
if m > 1:
    if a[0]+1 == a[1]:
        answer = 0
for i in range(m-1):
    if a[i] + 1 == a[i+1]:
        answer = 0
    answer = answer * fib[a[i+1]-a[i]-2] % 1000000007
answer = answer * fib[n - a[m-1] -1] % 1000000007
print(answer)

Submission status: Runtime Error

Solution code:
import sys
n,m = map(int,input().split())
a = []
for i in range(m):
    a.append(int(input()))
fib = [1,1]
#n段登る場合の数がfib[n]になるようにする
for i in range(n):
    fib.append((fib[i]+fib[i+1])%1000000007)
answer = 1
answer *= fib[a[0]-1]
if m > 1:
    if a[0]+1 == a[1]:
        print(0)
        sys.exit()
for i in range(m-1):
    if a[i] + 1 == a[i+1]:
        print(0)
        sys.exit()
    answer = answer * fib[a[i+1]-a[i]-2] % 1000000007
answer = answer * fib[n - a[m-1] -1] % 1000000007
print(answer)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
N , M = map(int ,input().split())
mod = 10 ** 9 + 7
A = []
for i in range(M):
    A.append(int(input()))
    if A[i] - 1 == A[i - 1] and i > 0:
        print("0")
        exit()
dp = [0] * (N + 1)
dp[0] = 1
idx = 0
crash = A[idx]
for i in range(1 , N + 1):
    if i == crash:
        idx += 1
        if idx < M:
            crash = A[idx]
        continue
    else:
        if i == 1:
            dp[1] = 1
        else:
            dp[i] = dp[i - 1] + dp[i - 2]
            dp[i] %= mod
print(dp[-1])

Submission status: Runtime Error

Solution code:
N , M = map(int ,input().split())
mod = 10 ** 9 + 7
A = []
for i in range(M):
    A.append(int(input()))
    if A[i] - 1 == A[i - 1] and i > 0:
        print("0")
        exit()
dp = [0] * (N + 1)
dp[0] = 1
idx = 0
crash = A[idx]
for i in range(1 , N + 1):
    if i == crash:
        idx += 1
        crash = A[idx]
        continue
    else:
        if i == 1:
            dp[1] = 1
        else:
            dp[i] = dp[i - 1] + dp[i - 2]
            dp[i] %= mod
print(dp[-1])

Submission status: Runtime Error

Solution code:
from functools import lru_cache
import sys
sys.setrecursionlimit(10**5)
N , M = map(int ,input().split())
mod = 10 ** 9 + 7
A = []
for i in range(M):
    A.append(int(input()))
    if A[i] - 1 == A[i - 1] and i > 0:
        print("0")
        exit()

@lru_cache(maxsize=None)
def fib(n):
    if n == 0 or n == 1:
        return 1
    else:
        return fib(n - 1)+fib(n - 2)
ans = 1
now = 0
for a in A:
    next = a - 1
    ans *= fib(next - now)
    now = a + 1
if now == 0:
    ans = fib(N)
else:
    ans *= fib(N - now)
print(ans % mod)

Submission status: Runtime Error

Solution code:
from functools import lru_cache
N , M = map(int ,input().split())
mod = 10 ** 9 + 7
A = []
for i in range(M):
    A.append(int(input()))
    if A[i] - 1 == A[i - 1] and i > 0:
        print("0")
        exit()

@lru_cache(maxsize=None)
def fib(n):
    if n == 0 or n == 1:
        return 1
    else:
        return fib(n - 1)+fib(n - 2)
ans = 1
now = 0
for a in A:
    next = a - 1
    ans *= fib(next - now)
    now = a + 1
if now == 0:
    ans = fib(N)
else:
    ans *= fib(N - now)
print(ans % mod)

Submission status: Runtime Error

Solution code:
from functools import lru_cache
N , M = map(int ,input().split())
mod = 10 ** 9 + 7
A = []
for i in range(M):
    A.append(int(input()))
    if A[i] - 1 == A[i - 1] and i > 0:
        print("0")
        exit()

@lru_cache(maxsize=None)
def fib(n):
    if n == 0 or n == 1:
        return 1
    else:
        return fib(n - 1)+fib(n - 2)
ans = 1
now = 0
for a in A:
    next = a - 1
    ans *= fib(next - now)
    now = a + 1
if now == 0:
    ans = fib(N)
else:
    ans *= fib(N - now)
    print(ans % mod)

Submission status: Runtime Error

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

ans=1


def fb(num):
    """num番目のフィボナッチ数を返す
    """
    a, b = 1, 1
    for i in range(num):
        a, b = a + b, a
    return b
    
#print(fb(3))

if m==0:
	ans=ans*fb(n)
	
else:
	for i in range(m-1):
		if (lista[i]+1==lista[i+1])&(m>=2):
			ans=0
  	
  	
		else:
			lista.append(n)
			if lista[0]!=1:
					ans=ans*(fb(lista[0]-1))
					for i in range(1,m):
							ans=ans*(fb(lista[i]-lista[i-1]-2))
					
		 
					
			if lista[0]==1:
					for i in range(1,m):
							ans=ans*(fb(lista[i]-lista[i-1]-2))
					
		
	ans= ans*(fb(lista[m]-lista[m-1]-1))
		
print(ans%1000000007)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
def fibo(i):
    c, b = 1, 0
    while i > 0:
        c, b = c + b, c
        i -= 1
    return c
m = a[0] + 1
num = fibo(m - 2)
if M > 1 :
    for i in range(M - 1):
    m = a[i + 1] - a[i]
    if m > 1:
        num = num * fibo(m - 2)
    else:
        num = 0
        break
    num = num * fibo(N - a[M - 1] - 1)
elif M == 1:
    num = num * fibo(N - a[M - 1] - 1)
else :
    num = fibo(N)
print(num % 1000000007)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
def fibo(i):
    c, b = 1, 0
    while i > 0:
        c, b = c + b, c
        i -= 1
    return c
m = a[0] + 1
num = fibo(m - 2)
for i in range(M - 1):
    m = a[i + 1] - a[i]
    if m > 1:
        num = num * fibo(m - 2)
    else:
        num = 0
        break
num = num * fibo(N - a[M - 1] - 1)
print(num % 1000000007)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
def fibo(i):
    c, b = 1, 0
    while i > 0:
        c, b = c + b, c
        i -= 1
    return c
m = a[0] + 1
num = fibo(m - 2)
for i in range(M - 1):
    m = a[i + 1] - a[i]
    if m > 1:
        num = num * fibo(m - 2)
    elif m == 1:
        num = 0
        break
num = num * fibo(N - a[M - 1] - 1)
print(num % 1000000007)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
def fibo(i):
    c, b = 1, 0
    while i > 0:
        c, b = c + b, c
        i -= 1
    return c
m = a[0] + 1
num = fibo(m - 2)
for i in range(M - 1):
    m = a[i + 1] - a[i]
    num = num * fibo(m - 2)
    if m == 1:
        num = 0
        break
num = num * fibo(N - a[M - 1] - 1)
print(num % 1000000007)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
def fibo(i):
    a, b = 1, 0
    while i > 0:
        a, b = a + b, a
        i -= 1
    return a
m = a[0] + 1
num = fibo(m - 2)
for i in range(M - 1):
    m = a[i + 1] - a[i]
    num = num * fibo(m - 2)
    if m == 1:
        num = 0
        break
num = num * fibo(N - a[M - 1] - 1)
print(num % 1000000007)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
def fibo(i, memo={}):
    if i == 0:
        return 1
    elif i == 1:
        return 1
    else:
        if i in memo:
            return memo[i]
        else:
            memo[i] = fibo(i-1, memo) + fibo(i-2, memo)
            return memo[i]
m = a[0] + 1
num = fibo(m - 2, memo)
for i in range(M - 1):
    m = a[i + 1] - a[i]
    num = num * fibo(m - 2, memo)
    if m == 1:
        num = 0
        break
num = num * fibo(N - a[M - 1] - 1, memo)
print(num % 1000000007)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
def fibo(i, memo={}):
    if i == 0:
        return 1
    elif i == 1:
        return 1
    else:
        if i in memo:
            return memo[i]
        else:
            memo[i] = fibo(i-1, memo) + fibo(i-2, memo)
            return memo[i]
m = a[0] + 1
num = fibo(m - 2)
for i in range(M - 1):
    m = a[i + 1] - a[i]
    num = num * fibo(m - 2)
    if m == 1:
        num = 0
        break
num = num * fibo(N - a[M - 1] - 1)
print(num % 1000000007)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
def fibo(i, memo={}):
    if i == 0, 1:
        memo[i] = 1
        return memo[i]
    else:
        if i in memo:
            return memo[i]
        else:
            memo[i] = fibo(i-1, memo) + fibo(i-2, memo)
            return memo[i]
m = a[0] + 1
num = fibo(m - 2)
for i in range(M - 1):
    m = a[i + 1] - a[i]
    num = num * fibo(m - 2)
    if m == 1:
        num = 0
        break
num = num * fibo(N - a[M - 1] - 1)
print(num % 1000000007)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
def fibo(i, memo={}):
    if i == 0, 1:
        memo[i]=1
        return memo[i]
    else:
        if i in memo.keys():
            return memo[i]
        else:
            memo[i] = fibo(i-1, memo) + fibo(i-2, memo)
            return memo[i]
m = a[0] + 1
num = fibo(m - 2)
for i in range(M - 1):
    m = a[i + 1] - a[i]
    num = num * fibo(m - 2)
    if m == 1:
        num = 0
        break
num = num * fibo(N - a[M - 1] - 1)
print(num % 1000000007)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
def fibo(i):
    if i == 0 :
        return 1
    elif i == 1:
        return 1
    else :
        return fibo(i - 1) + fibo(i - 2)
m = a[0] + 1
num = fibo(m - 2)
for i in range(M - 1):
    m = a[i + 1] - a[i]
    num = num * fibo(m - 2)
    if m == 1:
        num = 0
        break
num = num * fibo(N - a[M - 1] - 1)
print(num % 1000000007)

Submission status: Runtime Error

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

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

fiblist=[1,1]
for j in range(10**5):
    nums=(fiblist[-1]+fiblist[-2])%(10**9+7)
    fiblist.append(nums)
lists.insert(0,0)
lists.append(n)
ans=1
if m>=2:
    for i in range(m+1):
        if i==0:
            ans=ans*fiblist[lists[1]-lists[0]-1]
            ans=ans%(10**9+7)
        elif i==m:
            ans=ans*fiblist[lists[m+1]-lists[m]-1]
            ans=ans%(10**9+7)
        elif i!=0 and i!=m:
            if lists[i+1]-lists[i]==1:
                ans=0
                break
            else:
                ans=ans*fiblist[lists[i+1]-lists[i]-2]
                ans=ans%(10**9+7)
    print(ans) 
if m==0:
    print(fib(n))
if m==1:
    print(fib(lists[1]-1)*fib(n-lists[1]-1)%(10**9+7))

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
if m>=2:
    lists=[]
    for i in range(m):
        a=int(input())
        lists.append(a)

    fiblist=[1,1]
    for j in range(10**5):
        nums=(fiblist[-1]+fiblist[-2])%(10**9+7)
        fiblist.append(nums)
    lists.insert(0,0)
    lists.append(n)
    ans=1
    for i in range(m+1):
        if i==0:
            ans=ans*fiblist[lists[1]-lists[0]-1]
            ans=ans%(10**9+7)
        elif i==m:
            ans=ans*fiblist[lists[m+1]-lists[m]-1]
            ans=ans%(10**9+7)
        elif i!=0 and i!=m:
            if lists[i+1]-lists[i]==1:
                ans=0
                break
            else:
                ans=ans*fiblist[lists[i+1]-lists[i]-2]
                ans=ans%(10**9+7)
    print(ans) 
if m==0:
    print(fib(n))
if m==1:
    print(fib(lists[0]-1)*fib(n-lists[0]-1)%(10**9+7))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
def fibo(i):
    if i == 0 :
        return 1
    elif i == 1:
        return 1
    else :
        return fibo(i - 1) + fibo(i - 2)
num = 1
m = a[0] + 1
for i in range(M - 1):
    num = num * fibo(m - 2)
    m = a[i + 1] - a[i]
    if m == 1:
        num = 0
        break
num = num* fibo(N - a[M] - 1)
print(num % 1000000007)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
def fibo(i):
    if i = 0, 1 :
        return 1, 1
    else :
        return fibo(i - 1) + fibo(i - 2)
num = 1
m = a[0] + 1
for i in range(M - 1):
    num = num * fibo(m - 2)
    m = a[i + 1] - a[i]
    if m == 1:
        num = 0
        break
num = num* fibo(N - a[M] - 1)
print(num % 1000000007)

Submission status: Runtime Error

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

def combination(n, r):
        return math.factorial(n)//(math.factorial(n - r) * math.factorial(r))

def keisan(a,b):
    count = 0
    n = b - a - 2
    r = 0

    while n >= r:

        count += combination(n,r)
        n -= 1
        r += 1

    return count

result = 1

if M == 0:
    keisan(-1,N+1)
    print(int(result)%1000000007)
    sys.exit()

for item in a:

    if i == 0:
        result *= keisan(-1,item)
        continue

    #階段の段が連続して壊れている場合は登れない
    if item - prev_item == 1:
        result = 0
        break
    else:
        result *= keisan(prev_item,item)

    prev_item = item

else:
    result *= keisan(prev_item,N+1)

print(int(result)%1000000007)

Submission status: Runtime Error

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

def combination(n, r):
        return math.factorial(n)//(math.factorial(n - r) * math.factorial(r))

def keisan(a,b):
    count = 0
    n = b - a - 2
    r = 0

    while n >= r:

        count += combination(n,r)
        n -= 1
        r += 1

    return count

result = 1

for i in range(M):


    if i == 0:
        result *= keisan(-1,a[i])
        continue

    #階段の段が連続して壊れている場合は登れない
    if a[i] - a[i-1] == 1:
        result = 0
        break
    else:
        result *= keisan(a[i-1],a[i])

else:
    result *= keisan(a[M-1],N+1)

print(int(result)%1000000007)

Submission status: Runtime Error

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

def combination(n, r):
        return math.factorial(n)//(math.factorial(n - r) * math.factorial(r))

def keisan(a,b):
    count = 0
    n = b - a - 1
    r = 0

    while n >= r:

        count += combination(n,r)
        n -= 1
        r += 1

    return count

result = 1

for i in range(M):


    if i == 0:
        result *= keisan(0,a[i])
        continue

    #階段の段が連続して壊れている場合は登れない
    if a[i] - a[i-1] == 1:
        result = 0
        break
    else:
        result *= keisan(a[i-1],a[i])

else:
    result *= keisan(a[M-1],N)

print(int(result)%1000000007)

Submission status: Runtime Error

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

def combination(n, r):
        return math.factorial(n)//(math.factorial(n - r) * math.factorial(r))

def keisan(a,b):
    count = 0
    n = b - a - 1
    r = 0

    while n >= r:

        count += combination(n,r)
        n -= 1
        r += 1

    return count

result = 1

for i in range(M):


    if i == 0:
        result *= keisan(0,a[i])
        continue

    #階段の段が連続して壊れている場合は登れない
    if a[i] - a[i-1] == 1:
        result = 0
        break
    else:
        result *= keisan(a[i-1],a[i])

else:
    result *= keisan(a[M-1],N)