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:
N, M = map(int, input().split())
a = [int(input()) for i in range(M)]

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]
        
print((f[N-1]+f[N-2])%1000000007)

Submission status: Runtime Error

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

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]
        
print((f[N-1]+f[N-2])%1000000007)

Submission status: Runtime Error

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

f = [0 for i in range(N)]
f[0] = 1
f[1] = 1

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

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
lia = [int(input()) for _ in range(m)]
cnt = 0
li = [0] * (n+1)
mod = 1000000007

for i in range(n+1):
    if i == 0 or i == 1:
        if lia[cnt] == i:
            li[i] = 0
            if cnt < m-1:
                cnt += 1
        else:
            li[i] = 1
    else:
        if lia[cnt] == i:
            li[i] = 0
            if cnt < m-1:
                cnt += 1
        else:
            li[i] = li[i-1] + li[i-2]
    li[i] %= mod

print(li[n])

Submission status: Runtime Error

Solution code:
import numpy as np
import math

N, M = map(int, input().split())
a = np.zeros(M)
for i in range(M):
  a[i] = np.array(int(input()))

count_even = 0
count_odd = 0
count_all = 0
dcount_all = 1

if N % 2 == 0:
  for s2 in range(0, int(N/2) + 1):
    s1 = int(N - 2*s2)
    count_even += (math.factorial(s1+ s2)) / ((math.factorial(s1)) * (math.factorial(s2)))
else:
  for s2 in range(0, int((N-1)/2) + 1):
    s1 = int((N-1) - 2*s2)
    count_odd += (math.factorial(s1+ s2)) / ((math.factorial(s1)) * (math.factorial(s2)))
count_all += count_even + count_odd 

a = np.append(a, np.array([0, N]))
a = np.sort(a)

for j in range(0, M+1):
  dcount_even = 0
  dcount_odd = 0
  if a[j] != 0 and a[j] != N-1 and a[j+1] - a[j] == 1:
    dcount_all = count_all
    break
  elif (a[j+1] - a[j]) % 2 == 0:
    for ds2 in range(0, int((a[j+1] - a[j])/2) + 1):
      ds1 = int(a[j+1] - a[j] - 2*ds2 +1)
      dcount_even += (math.factorial(ds1 + ds2)) / ((math.factorial(ds1)) * (math.factorial(ds2)))
  else:
    for ds2 in range(0, int((a[j+1] - a[j] - 1)/2) + 1):
      ds1 = int(a[j+1] - a[j] -1 - 2*ds2 +1)
      dcount_odd += (math.factorial(ds1 + ds2)) / ((math.factorial(ds1)) * (math.factorial(ds2)))
  dcount_all *= dcount_even + dcount_odd
count = int((count_all - dcount_all) % 1000000007)
print(count)

Submission status: Runtime Error

Solution code:
def resolve():
    n, m = map(int, input().split())
    li_broken = [int(input()) for _ in range(m)]
    dp = [0] * (n + 2)

    for i in reversed(range(n + 1)):

        if i == n:
            dp[i] = 1
            continue

        if i in li_broken:
            dp[i] = 0
            continue

        dp[i] = dp[i+1] + dp[i+2]

    print(dp[0] % 1000000007)（）
    
resolve()

Submission status: Runtime Error

Solution code:
import math

# 組み合わせ
def ncr(n, r):
	return int(math.factorial(n) / (math.factorial(r) * math.factorial(n-r)))


n, m = map(int, input().split(' '))
# n, m = map(int, "100 5".split(' '))
# brokens = [int(input()) for _ in range(m)]
# brokens = [1, 23, 45, 67, 89]
brokens = [0 for _ in range(m)]
for i in range(m):
	brokens[i] = int(input())

steps = [0 for _ in range(m+1)]

# 移動する段数
steps[0] = brokens[0] - 1
for i in range(1, m):
	steps[i] = (brokens[i] - 1) - (brokens[i-1] + 1)
steps[m] = n - (brokens[m-1] + 1)

ans = 1
for i in range(m+1):
	stepComb = 1

	if(steps[i] < 0):
		ans = 0
		break
	
	twos = steps[i]//2

	for t in range(1, twos+1):
		stepComb += ncr((steps[i]-t), t)
	
	ans *= stepComb

print(ans % 1000000007)

Submission status: Runtime Error

Solution code:
# 組み合わせ
def ncr(n, r):
	return int(math.factorial(n) / (math.factorial(r) * math.factorial(n-r)))


n, m = map(int, input().split(' '))
# n, m = map(int, "100 5".split(' '))
# brokens = [int(input()) for _ in range(m)]
# brokens = [1, 23, 45, 67, 89]
brokens = [0 for _ in range(m)]
for i in range(m):
	brokens[i] = int(input())

steps = [0 for _ in range(m+1)]

# 移動する段数
steps[0] = brokens[0] - 1
for i in range(1, m):
	steps[i] = (brokens[i] - 1) - (brokens[i-1] + 1)
steps[m] = n - (brokens[m-1] + 1)

ans = 1
for i in range(m+1):
	stepComb = 1

	if(steps[i] < 0):
		ans = 0
		break
	
	twos = steps[i]//2

	for t in range(1, twos+1):
		stepComb += ncr((steps[i]-t), t)
	
	ans *= stepComb

print(ans % 1000000007)

Submission status: Runtime Error

Solution code:
# 組み合わせ
def ncr(n, r):
	return int(math.factorial(n) / (math.factorial(r) * math.factorial(n-r)))


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

steps = [0 for _ in range(m+1)]

# 移動する段数
steps[0] = brokens[0] - 1
for i in range(1, m):
	steps[i] = (brokens[i] - 1) - (brokens[i-1] + 1)
steps[m] = n - (brokens[m-1] + 1)

ans = 1
for i in range(m+1):
	stepComb = 1

	if(steps[i] < 0):
		ans = 0
		break
	
	twos = steps[i]//2

	for t in range(1, twos+1):
		stepComb += ncr((steps[i]-t), t)
	
	ans *= stepComb

print(ans % 1000000007)

Submission status: Runtime Error

Solution code:
# 組み合わせ
def ncr(n, r):
	return int(math.factorial(n) / (math.factorial(r) * math.factorial(n-r)))


n, m = map(int, "100 5".split(' '))
brokens = [int(input()) for _ in range(m)]

steps = [0 for _ in range(m+1)]

# 移動する段数
steps[0] = brokens[0] - 1
for i in range(1, m):
	steps[i] = (brokens[i] - 1) - (brokens[i-1] + 1)
steps[m] = n - (brokens[m-1] + 1)

ans = 1
for i in range(m+1):
	stepComb = 1

	if(steps[i] < 0):
		ans = 0
		break
	
	twos = steps[i]//2

	for t in range(1, twos+1):
		stepComb += ncr((steps[i]-t), t)
	
	ans *= stepComb

print(ans % 1000000007)

Submission status: Runtime Error

Solution code:
# 組み合わせ
def ncr(n, r):
	return int(math.factorial(n) / (math.factorial(r) * math.factorial(n-r)))

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

steps = [0 for _ in range(m+1)]

# 移動する段数
steps[0] = brokens[0] - 1
for i in range(1, m):
	steps[i] = (brokens[i] - 1) - (brokens[i-1] + 1)
steps[m] = n - (brokens[m-1] + 1)

ans = 1
for i in range(m+1):
	stepComb = 1

	if(steps[i] < 0):
		ans = 0
		break
	
	twos = steps[i]//2

	for t in range(1, twos+1):
		stepComb += ncr((steps[i]-t), t)
	
	ans *= stepComb

print(ans % 1000000007)

Submission status: Runtime Error

Solution code:
import sympy as sym

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)

pipi = 1

n,m = map(int,input().split())
a = []
b = []
flag = 0

#危ない階段
for i in range(m):
    a.append(int(input()))

#配列がいくつあるか
for i in range(m):
    if i == 0:
        if a[0] > 1:
            #穴が1以上であれば、すきまがある
            b.append(a[0]-1)
            #空いている場所を追加

    if m != 1 and i!=0:
        if a[i]-a[i-1]-2 <= -1:
            flag = 1
            break
        else:
            b.append(a[i]-a[i-1]-2)

    if i == m-1:
        #穴がn未満であれば、すきまがある
        if a[i] < n:
            b.append(n-a[i]-1)

if flag == 0:
    #n列の階段を求める　→ フィボナッチn+1番目＝nの配列
    for i,value in enumerate(b):
        if value >= 0:
            pipi *= fib(value+2)

if flag == 0:
    print(pipi % 1000000007)
else:
    print(0)

Submission status: Runtime Error

Solution code:
import sympy as sym

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)

pipi = 1

n,m = map(int,input().split())
a = []
b = []
flag = 0

#危ない階段
for i in range(m):
    a.append(int(input()))

#配列がいくつあるか
for i in range(m):
    if i == 0:
        if a[0] > 1:
            #穴が1以上であれば、すきまがある
            b.append(a[0]-1)
            #空いている場所を追加

    if m != 1 and i!=0:
        if a[i]-a[i-1]-2 <= -1:
            flag = 1
            break
        else:
            b.append(a[i]-a[i-1]-2)

    if i == m-1:
        #穴がn未満であれば、すきまがある
        if a[i] < n:
            b.append(n-a[i]-1)

if flag == 0:
    #n列の階段を求める　→ フィボナッチn+1番目＝nの配列
    for i,value in enumerate(b):
        if value >= 0:
            pipi *= fib(value+2)

if flag == 0:
    print(pipi % 1000000007)
else:
    print(0)

Submission status: Runtime Error

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

for _ in range(n):
    b.append(b[-1] + b[-2])

c.append(a[0])
for i in range(m - 1):
    c.append(a[i + 1] - a[i] - 1)
c.append(n - a[m - 1])

for i in c:
    ans *= b[i]

print(ans % 1000000007)

Submission status: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
# PROXY

import math
N, M = [int(i) for i in input().split()]
list = i = [int(input()) for i in range(M)]
Nlist = []
counter = 1
while counter < M:
    Diff_id = list[counter] - list[counter - 1]
    Nlist.append(Diff_id - 2 if Diff_id != 1 else -1)
    counter += 1
Nlist.insert(0,list[0] -1 if list[0] - 1 != 0 else 1)
Nlist.insert(M,N - list[M - 1] - 1 if N - list[M - 1] - 1 != 0 else 1)
counter = 0
ANSER = 1
while counter <= M:
    SQ5 = math.sqrt(5)
    P = ((1 + SQ5) / 2)**(Nlist[counter] + 1)
    Q = ((1 - SQ5) / 2)**(Nlist[counter] + 1)
    HowMany = math.floor((P - Q ) / SQ5)
    ANSER *= HowMany
    counter += 1
print(ANSER % (10**9 + 7))

Submission status: Runtime Error

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

out_list = []
for x in range(m):
    out_list.append(int(input()))

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

print(fib(n) % 1000000007)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
A = set()
for i in range(M):
    A.append(int(input()))
count = [0] * (N+1)
count[0] = 1
mod = 10 ** 9 + 7
if 1 in A:
    if 2 in A:
        print(0)
        exit()
    count[2] = 1
    start = 3
else:
    count[1] = 1
    start = 2
for i in range(start, N+1):
    if i in A:
        continue
    count[i] = count[i-1] + count[i-2]
    count[i] %= mod
print(count[N])

Submission status: Runtime Error

Solution code:
[n,m] = [int(i) for i in input().split()]
ls = []
tmp1 = -1
tmp2 = 0
checker = 0
ans = []
for i in range(m):
    tmp2 = int(input())
    ls.append(tmp2)
    if tmp2 - tmp1 == 1:
        checker = 1
        print(0)
        break
    tmp1 = tmp2
#i番目までの道の数
if n == 1:
    if 1 in ls:
        print(0)
    else:
        print(1)
else:
    for i in range(1,n+1):
        if i == 1:
            #1段目が使える時
            if 1 not in ls:
                ans.append(1)
            else:
                ans.append(0)
        elif i == 2:
            #2段目が使える時
            if 1 not in ls and 2 not in ls:
                ans.append(2)
            else:
                ans.append(1)
        else:
            if i in ls:
                ans.append(0)
            else:
                ans.append((ans[i-3]+ans[i-2])%(10**9+7))
if checker == 0:
    print(ans[n-1])

Submission status: Runtime Error

Solution code:
from functools import reduce

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

N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
B = [0]*(M + 1)
for i in range(M+1):
  if i == 0:
    diff = A[i] - 1
    B[0] = fib_memo(diff + 1)
  elif i == M:
    diff = N - A[M - 1] - 1
    B[M] = fib_memo(diff + 1)
  else:
    diff = A[i] - A[i-1] - 2
    if diff < 0:
      B[i] = 0
      break
    B[i] = fib_memo(diff + 1)
Ans = reduce(lambda a, b: a*b, B)
print(Ans % 1000000007)

Submission status: Runtime Error

Solution code:
from functools import reduce

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

N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
B = [0]*(M + 1)
for i in range(M+1):
  if i == 0:
    diff = A[i] - 1
    B[0] = fib_memo(diff + 1)
  elif i == M:
    diff = N - A[M - 1] - 1
    B[M] = fib_memo(diff + 1)
  else:
    diff = A[i] - A[i-1] - 2
    if diff == 1:
      B[i] = 0
      break
    B[i] = fib_memo(diff + 1)
Ans = reduce(lambda a, b: a*b, B)
print(Ans % 1000000007)

Submission status: Runtime Error

Solution code:
from functools import reduce

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

N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
B = [0]*(M + 1)
for i in range(M+1):
  if i == 0:
    diff = A[i] - 1
    B[0] = fib_memo(diff + 1)
  elif i == M:
    diff = N - A[M - 1] -1
    B[M] = fib_memo(diff + 1)
  else:
    diff = A[i] - A[i-1]
    if diff == 1:
      B[i] = 0
      break
    B[i] = fib_memo(diff + 1)
Ans = reduce(lambda a, b: a*b, B)
print(Ans % 1000000007)

Submission status: Runtime Error

Solution code:
import math

def cal(x):
    if x == 0:
        return 0
    elif x == 1 or x == 2:
        return 1
    else:
        x-=2
        return (2**math.ceil(x/2) + 2**math.floor(x/2) -1)
"""input n,m """
n, m = map(int,input().split())
t = int(input())
arr = [t]
for i in range(m-1):
    r = int(input())
    arr.append(r-t-1)
    t = r
arr.append(n-t)
dem = cal(arr[0])
for i in range(1,len(arr)):
    dem*=cal(arr[i])
    dem%=1000000007
print(dem%1000000007)

Submission status: Runtime Error

Solution code:
def pattern(N): # N段の階段を上る上り方、例えば1段目から5段目はN = 4 = 5-1
    if N == 0 or N == 1:
        return 1
    elif N == 2:
        return 2
    else:
        return pattern(N-1) + pattern(N-2)
n, m = map(int, input().split())
# ai番目に穴が空いているとき
# 自分がx番目にいると、ai-1番目まで上るやり方はpattern(ai-1-x)
# 穴を飛び越えたら自分はai+1番目に到着
# 初めは0段目なので、a1番目の穴の直前まで行くのにpattern(a1-1),これはx=0とすればいい
# 最後に、n段目まで上るのにはpattern(n-x)
x = 0
ans = 1
for i in range(m):
    a = int(input())
    if i == 0:
        ans = ans * pattern(a - x - 1)
        x = a + 1
    elif a == x:
        ans = 0
        break
    else:
        ans = ans * pattern (a - x - 1)
        x = a + 1
ans = ans * pattern (n - x)
print(ans % 1000000007)

Submission status: Runtime Error

Solution code:
def pattern(N): # N段の階段を上る上り方、例えば1段目から5段目はN = 4 = 5-1
    if N == 0 or N == 1:
        return 1
    elif N == 2:
        return 2
    else:
        return pattern(N-1) + pattern(N-2)
n, m = map(int, input().split())
# ai番目に穴が空いているとき
# 自分がx番目にいると、ai-1番目まで上るやり方はpattern(ai-1-x)
# 穴を飛び越えたら自分はai+1番目に到着
# 初めは0段目なので、a1番目の穴の直前まで行くのにpattern(a1-1),これはx=0とすればいい
# 最後に、n段目まで上るのにはpattern(n-x)
x = 0
ans = 1
for i in range(m):
    a = int(input())
    if i == 0:
        ans = ans * pattern(a - x - 1)
        x = a + 1
    elif a == x + 1:
        ans = 0
        break
    else:
        ans = ans * pattern (a - x - 1)
        x = a + 1
ans = ans * pattern (n - x)
print(ans % 1000000007)

Submission status: Runtime Error

Solution code:
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

n,m = map(int,input().split())
a = [int(input()) for i in range(m)]
ans = fib(a[0])
if m != 0:
  for j in range(1,m):
    if m == 1:
        continue
    elif a[j] == a[j-1]+1:
        ans = 0
    else:
        ans *= fib(a[j]-a[j-1]-1)
  ans *= fib(n-a[m-1])
else:
  ans = fib(n+1)
print(ans%1000000007)

Submission status: Runtime Error

Solution code:
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

n,m = map(int,input().split())
a = [int(input()) for i in range(m)]
ans = fib(a[0])
try:
  for j in range(1,m):
    if m == 1:
        continue
    elif a[j] == a[j-1]+1:
        ans = 0
    else:
        ans *= fib(a[j]-a[j-1]-1)
  ans *= fib(n-a[m-1])
except:
  ans = 0
print(ans%1000000007)

Submission status: Runtime Error

Solution code:
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

n,m = map(int,input().split())
a = [int(input()) for i in range(m)]
ans = fib(a[0])
for j in range(1,m):
    if m != 1:
        continue
    elif a[j] == a[j-1]+1:
        ans = 0
    else:
        ans *= fib(a[j]-a[j-1]-1)
ans *= fib(n-a[m-1])
print(ans%1000000007)

Submission status: Runtime Error

Solution code:
def pattern(N): # N段の階段を上る上り方
    if N == 1 or N == 2:
        return 1
    elif N == 3:
        return 2
    else:
        return pattern(N-1) + pattern(N-2)
n, m = map(int, input().split())
ans = 1
x = -1
for i in range(m):
    a = int(input())
    if a == x + 1:
        ans = 0
        break
    elif i == 0:
        ans = ans * pattern(a)
        x = a
    elif a == x + 2:
        x = a
    else:
        ans = ans * pattern(a - x - 1)
        x = a
ans = ans * pattern(n - x)
print(ans % 1000000007)

Submission status: Runtime Error

Solution code:
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

n,m = map(int,input().split())
a = [int(input()) for i in range(m)]
ans = fib(a[0])
for j in range(1,m):
    if m == 1:
        continue
    elif a[j] == a[j-1]+1:
        ans = 0
    else:
        ans *= fib(a[j]-a[j-1]-1)
ans *= fib(n-a[m-1])
print(ans%1000000007)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)
n,m = [int(i) for i in input().split()]
a = {int(input()) for i in range(m)}
dp = {}
def stairs(step):
  if step in a:
    return 0
  if step == 1:
    return 1
  if step == 2:
    return stairs(step-1) + 1
  if step in dp.keys():
    return dp[step]
  else:
    dp[step] = stairs(step-1) + stairs(step-2)
    return dp[step]
print(int(stairs(n)%1000000007))

Submission status: Runtime Error

Solution code:
def pattern(N): # N段の階段を上る上り方
    if N == 1 or N == 2:
        return 1
    elif N == 3:
        return 2
    else:
        return pattern(N-1) + pattern(N-2)
n, m = map(int, input().split())
ans = 1
x = -1
for i in range(m):
    a = int(input())
    if a == x + 1:
        ans = 0
        break
    elif i == 0:
        ans = ans * pattern(a)
        x = a
    else:
        ans = ans * pattern(a - x - 1)
        x = a
ans = ans * pattern(n - x)
print(ans % 1000000007)

Submission status: Runtime Error

Solution code:
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

n,m = map(int,input().split())
a = [int(input()) for i in range(m)]
ans = fib(a[0])
for j in range(1,m):
    if m == 1:
        continue
    elif a[j] == a[j-1]:
        ans = 0
    else:
        ans *= fib(a[j]-a[j-1]-1)
ans *= fib(n-a[m-1])
print(ans%1000000007)

Submission status: Runtime Error

Solution code:
import sys

N,M = list(map(int, input().split()))
a = [int(input()) - 1 for i in range(M)]
memo = [-1 for i in range(N)]

def process(n): #n段目まで何通りでいけるか？
    if memo[n] != -1:
        return memo[n]
    if n == -1: # nが-1
        return 1
    if n < -1:
        return 0
    if n in a:
        memo[n] = 0
        return 0
    if n == 0:
        memo[0] = 1
        return 1
    cnt = process(n-1) + process(n-2)
    memo[n] = cnt
    return cnt

print(process(N-1) % 1000000007)

Submission status: Runtime Error

Solution code:
import sys

N,M = list(map(int, input().split()))
a = [int(input()) - 1 for i in range(M)]
memo = [-1 for i in range(N)]

def process(n): #n段目まで何通りでいけるか？
    if memo[n] != -1:
        return memo[n]
    if n == -1: # nが-1
        return 1
    if n in a:
        memo[n] = 0
        return 0
    if n == 0:
        memo[0] = 1
        return 1
    cnt = process(n-1) + process(n-2)
    memo[n] = cnt
    return cnt

print(process(N-1) % 1000000007)

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
a=[]
for i in range(M):
    a.append(int(input()))
def story(n):
    if n in a:
        ans=0
    elif n==1:
        ans=1
    elif n==2:
        ans=2
    else:
        ans=(story(n-1)+story(n-2))%1000000007
    return ans
print(story(N))

Submission status: Runtime Error

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

P = 1000000007

dp = [0]*(N+1)

if 1 in List:
    dp[1] = 0
    if 2 in List:
        dp[2] = 0
    else:
        dp[2] = 1
else:
    dp[1] = 1
    if 2 in List:
        dp[2] = 0
    else:
        dp[2] = 2

for i in range(2, N):
    if i+1 in List:
        dp[i+1]=0
    else:
        if i in List:
            dp[i+1] = dp[i-1]%P
        else:
            dp[i+1] = (dp[i]+dp[i-1])%P
        
print(dp[N])

Submission status: Runtime Error

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

dp = {i:0 for i in A}

dp[0]=1 # 0段目
if A[0]==1:
  dp[1]=0
  A.remove(1)
else:
  dp[1]=1

safe_stairs = list(range(2,N+1))
[safe_stairs.remove(int(a)) for a in A]
  
for i in safe_stairs:  
  dp[i]= int(dp[i-1]+dp[i-2])
print(dp[N]%1000000007)

Submission status: Runtime Error

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

dp = {i:0 for i in A}

dp[0]=1 # 0段目

safe_stairs = list(range(1,N+1))
[safe_stairs.remove(a) for a in A]
  
for i in safe_stairs:  
  dp[i]=dp[i-1]+dp[i-2]
print(dp[N]%1000000007)

Submission status: Runtime Error

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

dp = []
dp.append(1) # 0段目
if 1 in A: # 1段目
  dp.append(0) 
else :
  dp.append(1) 

for i in range(2,N+1):  
  if i in A:
    dp.append(0)
  else :
    dp.append(dp[i-1]+dp[i-2])
print(dp[N])

Submission status: Runtime Error

Solution code:
N,M = (map(int,input1.split()))
A = list(map(int,input2.split()))

dp = []
dp.append(1) # 0段目
if 1 in A: # 1段目
  dp.append(0) 
else :
  dp.append(1) 

for i in range(2,N+1): # N段目
  if i in A:
    dp.append(0)
  else :
    dp.append(dp[i-1]+dp[i-2])
print(dp[N])

Submission status: Runtime Error

Solution code:
def main():
    n, m = [int(x) for x in input().split()]
    pattern = [1]
    broken = -1
    brokencnt = 0
    if brokencnt < m:
        broken = int(input())
        brokencnt += 1
    for i in range(1, n + 1):
        if i == broken:
            pattern.append(0)
            if brokencnt < m:
                broken = int(input())
                brokencnt += 1
            continue
        if i == 1:
            pattern.append(pattern[i - 1])
        if i > 1:
            pattern.append((pattern[i - 1] + pattern[i - 2]) % MOD)
    print(pattern[n])
main()

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
mod = 1e+9+7
flags = [True  for i in range(N)]
for i in range(M):
    tmp = int(input())
    flags[tmp-1] = False
dp = [0 for i in range(N)]
dp[0] = 1
dp[1] = 2

if not flags[0]:
    dp[0] = 0
    dp[1] = 1
if not flags[1]:
    dp[1] = 0
for i in range(2, N):
    if flags[i]:
        dp[i] = int((dp[i-1] + dp[i-2]) % mod)
print(dp[N-1])

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
mod = 1e+9+7
flags = [True  for i in range(N)]
for i in range(M):
    tmp = int(input())
    flags[tmp-1] = False
dp = [0 for i in range(N)]
dp[0] = 1
dp[1] = 2

if not flags[0]:
    dp[0] = 0
    dp[1] = 1
if not flags[1]:
    dp[1] = 0
for i in range(2, N):
    if flags[i]:
        dp[i] = int((dp[i-1] + dp[i-2]) % mod)
print(dp)

Submission status: Runtime Error

Solution code:
import sys
mod = 10 ** 9 + 7

n,m = map(int,input().split())
if n in [0,1]:
    print(1)
    sys.exit()
    
if not m == 0: lis = [int(input()) for x in range(m)]
else: lis = []
val1 = 1
if 1 in lis: val2 = 0
else: val2 = 1

if lis[0] == 1 and len(lis) >= 2:
    flg = lis[1]
    nex = 1
else:
    flg = lis[0]
    nex = 0
#print(lis)
for x in range(2,n):
    if x == flg: #x in lis
        #print(flg)
        nex += 1
        try: flg = lis[nex]
        except:flg = 0
        now = 0
    else:
        now = (val1 + val2) % mod
    val1,val2 = val2,now
    
print((val1 + val2) % mod)

Submission status: Runtime Error

Solution code:
import sys
mod = 10 ** 9 + 7

n,m = map(int,input().split())
if n in [0,1]:
    print(1)
    sys.exit()
    
if not m == 0:
    lis = [int(input()) for x in range(m)]
else:
    lis = []
val1 = 1
if 1 in lis:
    val2 = 0
else:
    val2 = 1

if lis[0] == 1:
    flg = lis[1]
    nex = 1
else:
    flg = lis[0]
    nex = 0
#print(lis)
for x in range(2,n):
    if x == flg: #x in lis
        #print(flg)
        nex += 1
        try: flg = lis[nex]
        except:flg = 0
        now = 0
    else:
        now = (val1 + val2) % mod
    val1,val2 = val2,now
    
print((val1 + val2) % mod)

Submission status: Runtime Error

Solution code:
import sys
mod = 10 ** 9 + 7

n,m = map(int,input().split())
if n in [0,1]:
    print(1)
    sys.exit()
    
if not m == 0:
    lis = [int(input()) for x in range(m)]
else:
    lis = []
val1 = 1
if 1 in lis:
    val2 = 0
else:
    val2 = 1

if lis[0] == 1:
    flg = lis[1]
    nex = 1
else:
    flg = lis[0]
    nex = 0
print(lis)
for x in range(2,n):
    if x == flg: #x in lis
        #print(flg)
        nex += 1
        try: flg = lis[nex]
        except:flg = 0
        now = 0
    else:
        now = (val1 + val2) % mod
    val1,val2 = val2,now
    
print((val1 + val2) % mod)

Submission status: Runtime Error

Solution code:
import sys
mod = 10 ** 9 + 7

n,m = map(int,input().split())
if n in [0,1]:
    print(1)
    sys.exit()
    
if not m == 0:
    lis = [int(input()) for x in range(m)]
else:
    lis = []
val1 = 1
if 1 in lis:
    val2 = 0
else:
    val2 = 1
nex = 0
flg = lis[0]
f = 0
for x in range(2,n):
    if x == flg:
        nex += 1
        try: flg = lis[nex]
        except:flg = 0
        now = 0
    else:
        now = (val1 + val2) % mod
    val1,val2 = val2,now
    
print((val1 + val2) % mod)

Submission status: Runtime Error

Solution code:
import sys
mod = 10 ** 9 + 7

n,m = map(int,input().split())
if n in [0,1]:
    print(1)
    sys.exit()
    
if not m == 0:
    lis = [int(input()) for x in range(m)]
else:
    lis = []
val1 = 1
if 1 in lis:
    val2 = 0
else:
    val2 = 1
nex = 0
flg = lis[0]
f = 0
for x in range(2,n):
    if x == flg:
        nex += 1
        flg = lis[nex]
        now = 0
    else:
        now = (val1 + val2) % mod
    val1,val2 = val2,now
    
print((val1 + val2) % mod)

Submission status: Runtime Error

Solution code:
mod = 10 ** 9 + 7

n,m = map(int,input().split())
if not m == 0:
    lis = [int(input()) for x in range(m)]
else:
    lis = []
stairs = [0 for x in range(n)]
stairs[0] = 1
if 1 in lis:
    stairs[1] = 0
else:
    stairs[1] = 1
#print(stairs)
f = 0
for x in range(2,n):
    if x in lis:
        stairs[x] = 0
    else:
        stairs[x] = (stairs[x-1] + stairs[x-2]) % mod
    
#print(stairs)
print((stairs[n-1] + stairs[n-2]) % mod)

Submission status: Runtime Error

Solution code:
mod = 10 ** 9 + 7

n,m = map(int,input().split())
if not m == 0:
    lis = [int(input()) for x in range(m)]
stairs = [0 for x in range(n)]
stairs[0] = 1
if 1 in lis:
    stairs[1] = 0
else:
    stairs[1] = 1
#print(stairs)
f = 0
for x in range(2,n):
    if x in lis:
        stairs[x] = 0
    else:
        stairs[x] = (stairs[x-1] + stairs[x-2]) % mod
    
#print(stairs)
print((stairs[n-1] + stairs[n-2]) % mod)

Submission status: Runtime Error

Solution code:
mod = 10 ** 9 + 7

n,m = map(int,input().split())
lis = [int(input()) for x in range(m)]
if n == 1:
    print(1)
elif n == 2:
    print(2)
stairs = [0 for x in range(n)]
stairs[0] = 1
if 1 in lis:
    stairs[1] = 0
else:
    stairs[1] = 1
#print(stairs)
f = 0
for x in range(2,n):
    if x in lis:
        stairs[x] = 0
    else:
        stairs[x] = (stairs[x-1] + stairs[x-2]) % mod
    
#print(stairs)
print((stairs[n-1] + stairs[n-2]) % mod)

Submission status: Runtime Error

Solution code:
mod = 10 ** 9 + 7

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

stairs = [0 for x in range(n)]
stairs[0] = 1
if 1 in lis:
    stairs[1] = 0
else:
    stairs[1] = 1
#print(stairs)
f = 0
for x in range(2,n):
    if x in lis:
        stairs[x] = 0
    else:
        stairs[x] = (stairs[x-1] + stairs[x-2]) % mod
    
#print(stairs)
print((stairs[n-1] + stairs[n-2]) % mod)

Submission status: Runtime Error

Solution code:
mod = 10 ** 9 + 7

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

stairs = [0 for x in range(n)]
stairs[0] = 1
if 1 in lis:
    stairs[1] = 0
else:
    stairs[1] = 1
#print(stairs)
f = 0
for x in range(2,n):
    if x in lis:
        stairs[x] = 0
    else:
        stairs[x] = (stairs[x-1] + stairs[x-2]) % mod
    
#print(stairs)
print((stairs[n-1] + stairs[n-2]) % mod)

Submission status: Runtime Error

Solution code:
    import sys
    n = [int(i) for i in input().split()]
    a = []
    for i in range(n[1]):
        a.append(int(input()))
     
    a.append(n[0]+1)
    a = sorted(list(set(a)))
     
     
    def k(i):
        ans = 1
        pri = 0
        for idx in range(i):
            tmp = ans
            ans += pri
            pri = tmp
        return ans
     
     
    for i in range(1, len(a)):
        if a[i]-a[i-1] == 1:
            print(0)
            sys.exit()
    j = -1
    ans = 1
    for i in a:
        ii = i-j-2
        ans = ans*k(ii)
        j = i
    if len(a) == 1:
        ans = k(n[0])
    print(ans % 1000000007)