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 = [int(nm) for nm in input().split()]
A = [-1]
for m in range(M):
  A.append(int(input()))
A.append(N+1)

import math
total_case = 1
for m in range(M+1):
  a1 = A[m]
  a2 = A[m+1]
  safe_stairs = a2 - a1 - 1
  if safe_stairs == 0:
    print(0)
    break
  howmany_jump1 = safe_stairs - 1
  mx_jump2 = howmany_jump1 // 2
  #２のジャンプは０回～（mx_jump2）回
  case = 0
  for j2 in range(mx_jump2 + 1):
    jump2 = j2
    jump1 = howmany_jump1 - (j2 * 2)
    c = math.factorial(jump1 + jump2) / (math.factorial(jump1) * math.factorial(jump2))
    case += c
  total_case *= case
else:
  ans = int(total_case % (10**9 + 7))
  print(ans)

Submission status: Runtime Error

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

import math
total_case = 1
for m in range(M+1):
  a1 = A[m]
  a2 = A[m+1]
  safe_stairs = a2 - a1 - 1
  howmany_jump1 = safe_stairs - 1
  mx_jump2 = howmany_jump1 // 2
  #２のジャンプは０回～（mx_jump2）回
  case = 0
  for j2 in range(mx_jump2 + 1):
    jump2 = j2
    jump1 = howmany_jump1 - (j2 * 2)
    c = math.factorial(jump1 + jump2) / (math.factorial(jump1) * math.factorial(jump2))
    case += c
  total_case *= case

ans = int(total_case % (10**9 + 7))
print(ans)

Submission status: Runtime Error

Solution code:
N, M = (int(_) for _ in input().split())
a = [0 for i in range(M)]
MOD = 10 ** 9 + 7
for i in range(M):
    a[i] = int(input())
a.append(0)
dp = [0 for i in range(N + 1)]
j = 0
for i in range(N + 1):
    if i == a[j]:
        j += 1
    elif i == 0:
        dp[i] = 1
    elif i == 1:
        dp[i] = 1
    else:
        dp[i] = dp[i - 1] + dp[i - 2]
print(dp[N] % MOD)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
j = 0
dp = [0] * 100100
dp[0] = 1
for i in range(1,N+1):
    if i == A[j]:
        j += 1
        dp[i] = 0
    else:
        dp[i] = dp[i-1] + dp[i-2]
        dp[i] %= 10**9+7
print(dp[N])

Submission status: Runtime Error

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

a = [-1]
for i in range(m):
    a.append(int(input()))
a.append(n+1)

m += 1
ans = 1
dp = []
for i in range(m):
    if a[i-1]-a[i]-1 == 0:
        ans = 0
        break
    elif a[i-1]-a[i]-1 == 1:
        continue
    else:
        dp.clear()
        dp = [1] + [0]*(a[i+1]-a[i]-2)
    for j in range(1, a[i+1]-a[i]-1):
        dp[j] = dp[j-1] + dp[j-2]
    ans *= dp[-1]

print(ans%1000000007)

Submission status: Runtime Error

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

broken = [False] * (n + 1)
for x in xs:
    broken[x] = True

cache = [-1] * (n + 1)

def solve(pos, n, broken, cache):
    if pos > n or broken[pos]:
        return 0
    if pos == n:
        return 1
    res = cache[pos]
    if res >= 0:
        return res
    res = solve(pos+1, n, broken, cache) + solve(pos+2, n, broken, cache)
    cache[pos] = res = res % 1000000007
    return res

print(solve(0,n,broken,cache))

Submission status: Runtime Error

Solution code:
import sys


def fb(num):
    a, b = 1, 0
    for _ in range(num):
        a, b = a + b, a
    return a


N, M = map(int,input().split())
a = [int(input()) for i in range(M)]
for i in range(len(a)-1):
    if a[i]+1 == a[i+1]:
        print(0)
        sys.exit()

k =[a[0]-1]
for i in range(len(a)-1):
    k.append(a[i+1]-a[i]-2)
k.append(N-a[-1]-1)
ans = 1
# print(k)
for g in k:
    ans *= int(fb(g))
    ans = ans%1000000007
print(int(ans))

Submission status: Runtime Error

Solution code:
import sys
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under


def getcase(y):
    total = 0
    for j in range(y//2+1):
        total +=cmb(j+y-2*j,j)
    return total


N, M = map(int,input().split())
a = [int(input()) for i in range(M)]
for i in range(len(a)-1):
    if a[i]+1 == a[i+1]:
        print(0)
        sys.exit()

k =[a[0]-1]
for i in range(len(a)-1):
    k.append(a[i+1]-a[i]-2)
k.append(N-a[-1]-1)
ans = 1
# print(k)
for g in k:
    ans *= getcase(g)
    ans = ans%1000000007
print(int(ans))

Submission status: Runtime Error

Solution code:
import sys
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under


def getcase(y):
    total = 0
    for j in range(y//2+1):
        total +=cmb(j+y-2*j,j)
    return total


N, M = map(int,input().split())
a = [int(input()) for i in range(M)]
for i in range(len(a)-1):
    if a[i]+1 == a[i+1]:
        print(0)
        sys.exit()

k =[a[0]-1]
for i in range(len(a)-1):
    k.append(a[i+1]-a[i]-2)
k.append(N-a[-1]-1)
ans = 1
# print(k)
for g in k:
    ans *= getcase(g)
    ans = ans%1000000007
print(int(ans%1000000007))

Submission status: Runtime Error

Solution code:
import sys
from scipy.special import comb


def getcase(y):
    total = 0
    for j in range(y//2+1):
        total +=comb(j+y-2*j,j)
    return total


N, M = map(int,input().split())
a = [int(input()) for i in range(M)]
for i in range(len(a)-1):
    if a[i]+1 == a[i+1]:
        print(0)
        sys.exit()

k =[a[0]-1]
for i in range(len(a)-1):
    k.append(a[i+1]-a[i]-2)
k.append(N-a[-1]-1)
ans = 1
# print(k)
for g in k:
    ans *= getcase(g)
    ans = ans%1000000007
print(int(ans%1000000007))

Submission status: Runtime Error

Solution code:


def down(current_step):
    global memo
    if current_step < 0 or current_step in dangerous_step:
        return 0
    if current_step == 0:
        return 1
    if current_step == 1 and (current_step-1) in memo:
        return memo[current_step-1]
    if current_step in memo:
        return memo[current_step]
    memo[current_step] = (down(current_step - 1) +
                          down(current_step - 2)) % ((1e+9) + 7)
    return memo[current_step]

n, m = [int(x) for x in input().split()]
memo = dict()
dangerous_step = {int(input()): 0 for x in range(m)}
print(int(down(n)))

Submission status: Runtime Error

Solution code:


def down(current_step):
    if current_step < 0 or current_step in dangerous_step:
        return 0
    if current_step == 0:
        return 1
    if current_step == 1:
        return memo[current_step-1]
    if current_step in memo:
        return memo[current_step]
    memo[current_step] = (down(current_step - 1) +
                          down(current_step - 2)) % ((1e+9) + 7)
    return memo[current_step]

n, m = [int(x) for x in input().split()]
memo = dict({0:1})
dangerous_step = {int(input()): 0 for x in range(m)}
print(int(down(n)))

Submission status: Runtime Error

Solution code:
def down(current_step):
    if current_step < 0:
        return 0
    if current_step == 0:
        return 1
    if current_step in memo:
        return memo[current_step]
    memo[current_step] = (down(current_step - 1) +
                          down(current_step - 2)) % ((1e+9) + 7)
    return memo[current_step]

n, m = [int(x) for x in input().split()]
memo = dict()
memo = {int(input()): 0 for x in range(m)}
print(int(down(n)))

Submission status: Runtime Error

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)

f = open('C_input_29.txt')
lines = f.readlines()
f.close()
N, M = map(int, lines[0].split())
A = []
for line in lines[1:]:
    A.append(int(line))

#  N, M = LI()
#  A = []
#  for i in range(M):
#      A.append(_I())

if M != 0:
    # 連続した壊れた段がある場合は0
    B = [i for i in A]
    B.remove(B[0])
    B.append(10**15+100)
    diffs = [b - a for a, b in zip(A,B)]
    #  print(diffs)

    if any(i == 1 for i in diffs):
        # 隣同士なので0
        print(0)
        exit()
#  print('hoge')
"""
考え方
xにたどり着く通りは、x-1とx-2段目にたどり着く通りの合計
dp
3が障害のとき
1へは1通り
2へは0からと1からの2通り
3へは0通り
4へは2からの2通りと、3からの0通りで2通り
5へは3からの0通りと4からの2通りで2通り
6へは4からの2通りと5からの2通りで4通り
"""
dp = {}
#  print('fua')
dp[0] = 1
dp[1] = 1 if 1 not in A else 0
[dp.update({i: (dp[i-1] + dp[i-2] )%mod}) if i not in A else dp.update({i: 0}) for i in range(2, N+1)]
#  for i in range(2, N+1):
#      print(i)
#      # i段目までの通りを計算する
#      if i in A:
#          # i段目が障害のときは0になっているので飛ばす
#          dp[i] = 0
#          continue
    
#      dp[i] = dp[i-1] + dp[i-2]

print(dp[N] % mod)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
def cbn(l):
    if l<3:
        return(max(1,l))
    else:
        return(cbn(l-1)+cbn(l-2))
ans=1
a=-1
for i in range(m):
    now=a+1
    a=int(input())
    if now==a:
        print(0)
        exit()
    else:
        ans*=cbn(a-now-1)
ans*=cbn(n-a-1)
mod=10**9+7
print(ans%mod)

Submission status: Runtime Error

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)

N, M = LI()
A = []
for i in range(M):
    A.append(_I())

"""
飛び越える前までの道筋の通りを調べてかけていく
"""

# 連続した壊れた段がある場合は0
B = [i for i in A]
B.remove(B[0])
B.append(10**15)
diffs = [b - a for a, b in zip(A,B)]
#  print(diffs)

if any(i == 1 for i in diffs):
    # 隣同士なので0
    print(0)
    exit()

# 隣り合うものがないので、各区間の通りを出していく
res = [0 for _ in range(N)]
for aidx in range(len(A)+1):
    if aidx == 0:
        start = 0
    else:
        start = A[aidx-1] + 1

    if aidx == len(A):
        # last item
        end = N
    else:
        end = A[aidx] - 1
    #ぐうきで分ける、一箇所を2とびにした場合、2箇所を2とびにした場合などで変える
    r = end - start
    max_2_steps = r // 2
    #  print('ma', max_2_steps)
    for i in range(max_2_steps + 1):
        tmp = r
        tmp -= 2 * i
        #  print('i,r,tmp', i, r, tmp)
        # tmpが1段ずつになる
        res[aidx] += int(math.factorial(i + tmp) / (math.factorial(tmp) * math.factorial(i)))

#  print(res)
ans = 0
for r in res:
    if r == 0:
        continue
    if ans == 0:
        ans = r
    else:
        ans *= r
print(ans % mod)

Submission status: Runtime Error

Solution code:
from copy import *
from sys import *
import math
import queue
from collections import defaultdict,Counter,deque
from fractions import Fraction as frac

setrecursionlimit(1000000)


def main():
	fib = [0,1,1,2]
	for i in range(3,10**5):
		fib.append(fib[i-1]+fib[i])
	n,m = map(int,input().split())
	last=0
	ans = 1
	for i in range(m):
		t = int(input())
		ans *= fib[t-last]
		last =  t+1
	ans *= fib[n-last+1]
	print(ans%(10**9+7))


def zip(a):
	mae = a[0]
	ziparray = [mae]
	for i in range(1,len(a)):
		if(mae != a[i]):
			ziparray.append(a[i])
			mae = a[i]
	return ziparray

def is_prime(n):
	if n < 2: return False

	for k in range(2, int(math.sqrt(n)) + 1):
		if n % k == 0:
			return False

	return True

def list_replace(n,f,t):
	return [t if i==f else i for i in n]

def base_10_to_n(X, n):
	X_dumy = X
	out = ''
	while X_dumy>0:
		out = str(X_dumy%n)+out
		X_dumy = int(X_dumy/n)
	if(out == ''): return '0'
	return out

def gcd(m,n):
	x = max(m,n)
	y = min(m,n)
	while(x%y!=0):
		z = x%y
		x = y
		y = z
	return y

class Queue():
	def __init__(self):
		self.q = deque([])
	def push(self,i):
		self.q.append(i)
	def pop(self):
		return self.q.popleft()
	def size(self):
		return len(self.q)
	def debug(self):
		return self.q

class Stack():
	def __init__(self):
		self.q = []
	def push(self,i):
		self.q.append(i)
	def pop(self):
		return self.q.pop()
	def size(self):
		return len(self.q)
	def debug(self):
		return self.q

class graph():
	def __init__(self):
		self.graph = defaultdict(list)
	def addnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].append(t)
		self.graph[t].append(f)
	def rmnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].remove(t)
		self.graph[t].remove(f)
	def linked(self,f):
		return self.graph[f]

class dgraph():
	def __init__(self):
		self.graph = defaultdict(set)
	def addnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].append(t)
	def rmnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].remove(t)
	def linked(self,f):
		return self.graph[f]

main()

Submission status: Runtime Error

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

sta = []
for i in range(N):
    if i == 0:
        sta.append(1)
    elif i == 1:
        sta.append(1)
    elif i == 2:
        sta.append(2)
    else:
        sta.append(sta[i-1]+sta[i-2])

row = []
now = 1
flag = 0
for i in range(N):
    I = i+1
    if i == 0:
        if I in A:
            now = 0
            flag = 1
        else:
            now+=1
    else:
        if I in A:
            if flag == 1:
                flag = 2
                break
            else:
                row.append(now)
                now = 0
                flag = 1
        else:
            flag = 0
            now+=1

if flag == 2:
    print(0)
else:
    row.append(now)
    ans = 1
    for r in row:
        ans = (ans*sta[r-1])%mod
    print(ans)

Submission status: Runtime Error

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

sta = []
for i in range(N):
    if i == 0:
        sta.append(1)
    elif i == 1:
        sta.append(1)
    elif i == 2:
        sta.append(2)
    else:
        sta.append(sta[i-1]+sta[i-2])

row = []
now = 1
flag = 0
for i in range(N):
    I = i+1
    if i == 0:
        if I in A:
            now = 0
            flag = 1
        else:
            now+=1
    else:
        if I in A:
            if flag == 1:
                flag = 2
                break
            else:
                row.append(now)
                now = 0
                flag = 1
        else:
            flag = 0
            now+=1
row.append(now)
ans = 1
for r in row:
    ans*=sta[r-1]
if flag == 2:
    print(0)
else:
    print(ans%mod)

Submission status: Runtime Error

Solution code:
n, m = map(int,input().split())
a = []
for i in range(m):
    a.append(int(input()))
dp = []
dp.append(1)
j = 0
k = len(a)-1
if 1 == a[j]:
    dp.append(0)
    j = min(k,j+1)
else:
    dp.append(1)

for i in range(2,n+1):
    if i == a[j]:
        dp.append(0)
        j = min(k,j+1)
    else:
        dp.append(dp[i-1] + dp[i-2])

print(dp[n]%(1000000007))

Submission status: Runtime Error

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

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

print(dp[n]%(1000000007))

Submission status: Runtime Error

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

mod = 1000000007
b = [0]*(m + 1)
if m != 0:
    b[0] = a[0] - 1
    b[m] = n - a[m - 1] - 1
else:
    b[0] = n

for i in range(1,m):
    b[i] = a[i] - a[i-1] - 2

b.sort()
ans = 1
if b[0] == -1:
    ans = 0
else:
    pattern = [0]*(b[m]+1)
    pattern[0] = 1
    pattern[1] = 1
    for i in range(2,b[m]+1):
        pattern[i] = pattern[i-1] + pattern[i-2]
    for i in range(m + 1):
        ans *= pattern[b[i]]

print(ans % mod)

Submission status: Runtime Error

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

mod = 1000000007
b = [0]*(m + 1)
if m != 0:
    b[0] = a[0] - 1
    b[m] = n - a[m - 1] - 1
else:
    b[0] = n

for i in range(1,m):
    b[i] = a[i] - a[i-1] - 2

b.sort()
ans = 1
if b[0] == -1:
    ans = 0
else:
    pattern = [0]*(b[m]+1)
    pattern[0] = 1
    pattern[1] = 1
    for i in range(2,b[m]+1):
        pattern[i] = pattern[i-1] + pattern[i-2]
    for i in range(m + 1):
        ans *= pattern[b[i]]

print(ans % mod)

Submission status: Runtime Error

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

mod = 1000000007
b = [0]*(m + 1)

b[0] = a[0] - 1
b[m] = n - a[m - 1] - 1

for i in range(1,m):
    b[i] = a[i] - a[i-1] - 2

b.sort()
ans = 1
if b[0] == -1:
    ans = 0
else:
    pattern = [0]*(b[m]+1)
    pattern[0] = 1
    pattern[1] = 1
    for i in range(2,b[m]+1):
        pattern[i] = pattern[i-1] + pattern[i-2]
    for i in range(m + 1):
        ans *= pattern[b[i]]

print(ans % mod)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3

import sys

P_NUM = 1000000007


def solv(n, m, a):
    comb_m2 = 1
    if 1 in a:
        comb_m1 = 0
    else:
        comb_m1 = 1

    for i in range(2, n+1):
        if i in a:
            comb = 0
        else:
            comb = (comb_m1 + comb_m2) % P_NUM
        
        comb_m1, comb_m2 = comb, comb_m1

    return comb


if __name__ == '__main__':

    n, m = map(int, input().split())
    if m:
        a = set(map(int, sys.stdin))
    else:
        a = set()

    ans = solv(n, m, a)

    print(ans)

Submission status: Runtime Error

Solution code:
n, m = map(int,input().split())
a = []
import sys
sys.setrecursionlimit(10000)
for i in range(m):
    a.append(int(input()))
memo = [0 for i in range(n)]
done = [0 for i in range(n)]
def p(i):
    if done[i-1] == 1:
        return memo[i-1]
    if i in a:
        return 0
    elif i == 1:
        return 1
    elif i == 2:
        return p(1) + 1
    else:
        done[i-1] = 1
        memo[i-1] = p(i-1) + p(i-2)
        return memo[i-1]
print(p(n) % (10**9 + 7))

Submission status: Runtime Error

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

Submission status: Runtime Error

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

dp = [-1 for _ in range(N+1)]
dp[0] = 1
dp[1] = 1
for i in range(2, N+1):
  if B[i-2] == 0 and B[i-1] == 1:
    dp[i] = dp[i-2]
  elif B[i-2] == 1 and B[i-1] == 0:
    dp[i] = dp[i-1]
  elif:
    dp[i] = dp[i-1] + dp[i-2]
  else:
    dp[i] = 0

print(dp[-1])

Submission status: Runtime Error

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

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

memo = [0 for i in range(N + 10)]
memo[1] = 1
memo[2] = 2
for i in range(3, N + 10):
    memo[i] = memo[i - 1] + memo[i - 2]

ans = 1
for i in range(M):
    if i == 0:
        tmp = A[i] - 1
        if tmp == 0:
            tmp = 1
    else:
        tmp = A[i] - A[i - 1] - 2
    ans *= memo[tmp]
    ans %= int(1e9 + 7)

if N - A[-1] - 1 != 0:
    ans *= memo[(N - A[-1] - 1)]
    ans %= int(1e9 + 7)
print(ans)

Submission status: Runtime Error

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

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

memo = [0 for i in range(N + 10)]
memo[1] = 1
memo[2] = 2
for i in range(3, N + 10):
    memo[i] = memo[i - 1] + memo[i - 2]

ans = 1
for i in range(M):
    if i == 0:
        tmp = A[i] - 1
        if tmp == 0:
            tmp = 1
    else:
        tmp = A[i] - A[i - 1] - 2
    ans *= memo[tmp]
    ans %= int(1e9 + 7)

ans *= memo[(N - A[-1] - 1)]
ans %= int(1e9 + 7)
print(ans)

Submission status: Runtime Error

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

step = [0] * (N+1)
if 1 in A:
  step[1] = 0
else:
  step[1] = 1
if 2 in A:
  step[2] = 0
else:
  step[2] = step[1] + 1

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

Submission status: Runtime Error

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

step = [0] * (N+1)
if 1 in A:
  step[1] = 0
else:
  step[1] = 1
if 2 in A:
  step[2] = 0
else:
  step[2] = step[1] + 1

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

Submission status: Runtime Error

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

step = [0] * (N+1)
if 1 in A:
  step[1] = 0
else:
  step[1] = 1
if 2 in A:
  step[2] = 0
else:
  step[2] = step[1] + 1

for i in range(3, N+1):
  if i in A:
    step[i] = 0
  else:
    step[i] = step[i-1] + step[i-2]
print(step[N])

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(5000)

def step(n, A):
    memo = A
    def _step(n):
        if memo[n] != -1:
            return memo[n]
        elif n == 1:
            return 1
        elif n == 2:
            if memo[1] == 0:
                return 1
            else:
                return 2
        memo[n] = (_step(n-1) + _step(n-2))%(10**9+7)
        return memo[n]
    return _step(n)

N, M = map(int, input().split())
A = [-1] * (N+1)
for _ in range(M):
    idx = int(input())
    A[idx] = 0
print(step(N, A))

Submission status: Runtime Error

Solution code:
def C_TypicalStairs():
    N, M = map(int, input().split())
    am = [int(input()) for i in range(M)]
    n_list = [i for i in range(N+1)]
    can_move = True
    num_move = 0
    # 到達不可を除く
    for i in range(M-1):
        if ((am[i] + 1) == am[i+1]):
            can_move = False
    if (can_move):
        num_move = fib(len(n_list[:am[0]]))
        if (M <= 1):
            pass
        else:
            for i in range(M-1):
                num_move *= fib(len(n_list[am[i]+1:am[i+1]]))
        num_move *= fib(len(n_list[am[M-1]+1:]))
    print(num_move % 1000000007)

def fib(n):
    if (n <= 1):
        a0 = n
    else:
        a0, a1 = 0, 1
        for _ in range(n):
            a0, a1 = a1, a0 + a1
    return a0
if __name__ == "__main__":
    C_TypicalStairs()

Submission status: Runtime Error

Solution code:
#coding:utf-8
#DPの練習

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

#壊れている階段とそうでない階段を判別するリスト
broken = [0] * (n+1)

#段ごとに何通りかを集計するためのリスト
dp = [0] * (n+1)
#0段目は必ず1通りしかない
dp[0] = 1


#壊れている階段をマークする
for i in range(m):
    broken[a[i]] = 1

#1段目から壊れている可能性があるので場合分け
if broken[1] == 1:
    dp[2] = 0
else:
    #1段目が無事な場合は1通り
    dp[2] = 1

#3段目以降
for i in range(2, n+1):
    if broken[i] == 1:
        #壊れていた場合次の段を確認する
        continue
    dp[i] = dp[i-1] + dp[i-2]
    dp[i] = dp[i] % 1000000007

print(dp[n])

Submission status: Runtime Error

Solution code:
def main():
  n, m = map(int,input().split())
  if m != 0:
    BStep = [int(input()) for _ in range(m)]
    sumstep = culc(0,BStep[0]-1)
    for i in range(1,m):
      sumstep*=culc(BStep[i-1]+1,BStep[i]-1)
    sumstep*=culc(BStep[m-1]+1,n)
  else:
    sumstep=culc(0,n)
  print(sumstep%1000000007)

def culc(fromstep,tostep):
  if tostep-fromstep==0:
    ans = 1
  elif tostep<=fromstep:
    ans = 0
  else:
    stepsum = 0
    up = tostep - fromstep
    tsmax = up//2
    for i in range(tsmax+1):
      one = up - 2*i
      stepsum += per(one + i)//(per(one)*per(i))
      # print(" ",stepsum)
    ans = stepsum
  # print(ans)
  return ans
def per(n):
  if n == 0:
    return 1
  else:
    return n*per(n-1)

main()

Submission status: Runtime Error

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

  sumstep = culc(0,BStep[0]-1)
  for i in range(1,m):
    sumstep*=culc(BStep[i-1]+1,BStep[i]-1)
  sumstep*=culc(BStep[m-1]+1,n)
  print(sumstep%1000000007)

def culc(fromstep,tostep):
  if tostep-fromstep==0:
    ans = 1
  elif tostep<=fromstep:
    ans = 0
  else:
    stepsum = 0
    up = tostep - fromstep
    tsmax = up//2
    for i in range(tsmax+1):
      one = up - 2*i
      stepsum += per(one + i)//(per(one)*per(i))
      # print(" ",stepsum)
    ans = stepsum
  # print(ans)
  return ans
def per(n):
  if n == 0:
    return 1
  else:
    return n*per(n-1)

main()

Submission status: Runtime Error

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

  sumstep = culc(0,BStep[0]-1)
  for i in range(1,m):
    sumstep*=culc(BStep[i-1]+1,BStep[i]-1)
  sumstep*=culc(BStep[m-1]+1,n)
  print(sumstep%1000000007)

def culc(fromstep,tostep):
  if tostep-fromstep==0:
    ans = 1
  elif tostep<=fromstep:
    ans = 0
  else:
    stepsum = 0
    up = tostep - fromstep
    tsmax = up//2
    for i in range(tsmax+1):
      one = up - 2*i
      stepsum += per(one + i)//(per(one)*per(i))
      print(" ",stepsum)
    ans = stepsum
  print(ans)
  return ans
def per(n):
  if n == 0:
    return 1
  else:
    return n*per(n-1)

main()

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
bro = [int(input()) for i in range(M)]
mod = 10**9 + 7
dp = [0]*(N+1)
dp[0] = 1
if bro[0] != 1:
    dp[1] = 1
else:
    del bro[0]
for i in range(2,N+1):
    if len(bro) == 0:
        dp[i]= (dp[i-1] + dp[i-2]) % mod
    elif bro[0] == i:
        del bro[0]
        continue
    else:
        dp[i]= (dp[i-1] + dp[i-2]) % mod
print(dp[-1] % mod)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
am = [int(input()) for i in range(M)]
dp = [0]*(N+1)
if not 1 in am:
	dp[1]=1
if not 2 in am:
	dp[2]=1
for i in range(1,N):
    if not (i+1) in am:
        dp[i+1] += dp[i]
    if not (i+2) in am:
        if i+2<=N:
            dp[i+2] += dp[i]
print(dp[N]%(10**9+7))

Submission status: Runtime Error

Solution code:
def f(i):

    if(dp[i] != -1):
        return dp[i]
    if e[i] != 1:
        return 0
    else:
        dp[i] = f(i+1) + f(i+2)
        return dp[i]


n,m = list(map(int,input().split()))
e = [1] * n
dp = [-1] * n
dp.append(1)
dp[n-1] = 1
for i in range(m):
    e[int(input())] = 0
print(f(0) % 1000000007)

Submission status: Runtime Error

Solution code:


def f(i):

    if(dp[i] != -1):
        return dp[i]
    if(i==n or i==n-1):
        return 1
    if e[i] != 1:
        return 0
    else:
        dp[i] = f(i+1) + f(i+2)
        return dp[i]


n,m = list(map(int,input().split()))
e = [1] * n
dp = [-1] * n
dp.append(-1)

for i in range(m):
    e[int(input())] = 0
print(f(0) % 1000000007)

Submission status: Runtime Error

Solution code:
import math
n, m = map(int,input().split())
a = []
pam = -1

def fib(k):
    if k<0:
        return 0
    r=(((1+math.sqrt(5))/2)**(k+1)-((1-math.sqrt(5))/2)**(k+1))/math.sqrt(5)
    return round(r)


for i in range(0,m):
    am = int(input())
    a.append(am-pam)
    pam = am
a.append(n+1-pam)
count = 1
for aa in a:
    count = count * (fib(aa-2))%(1000000007)
print(count%(1000000007))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)
n, m = map(int,input().split())
a = []
pam = -1

fibk={}
def fib(k):
    if k in fibk:
        return fibk[k]
    if k<0:
        return 0
    elif k==0 or k==1:
        return 1
    elif k-2 in fibk and not(k-1 in fibk):
        return fib(k-1)+fibk[k-2]
    elif k-2 in fibk and k-1 in fibk:
        return fibk[k-1]+fibk[k-2]
    else:
        return fib(k-1)+fib(k-2)


for i in range(0,m):
    am = int(input())
    a.append(am-pam)
    pam = am
a.append(n+1-pam)
count = 1
for aa in a:
    count = count * (fib(aa-2))%(1000000007)
print(count%(1000000007))

Submission status: Runtime Error

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

fibk={}
def fib(k):
    if k in fibk:
        return fibk[k]
    if k<0:
        return 0
    elif k==0 or k==1:
        return 1
    elif k-2 in fibk and not(k-1 in fibk):
        return fib(k-1)+fibk[k-2]
    elif k-2 in fibk and k-1 in fibk:
        return fibk[k-1]+fibk[k-2]
    else:
        return fib(k-1)+fib(k-2)


for i in range(0,m):
    am = int(input())
    a.append(am-pam)
    pam = am
a.append(n+1-pam)
count = 1
for aa in a:
    count = count * fib(aa-2)
print(count%(1000000007))

Submission status: Runtime Error

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


def fib(k):
    if k<0:
        return 0
    elif k==0 or k==1:
        return 1
    else:
        return fib(k-1)+fib(k-2)


for i in range(0,m):
    am = int(input())
    a.append(am-pam)
    pam = am
a.append(n+1-pam)
count = 1
for aa in a:
    count = count * fib(aa-2)
print(a)
print(count%(1000000007))