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:
def rec(n):
  if n < 0:
    return 0
  if n in b:
    return 0
  if n == 0:
    return 1  
  if n in memo:
    return memo[n]
  
  tmp = rec(n-1) + rec(n-2)
  memo[n] = tmp
  return tmp
  

N, M = map(int, input().split())
memo = {}
b = {}
for i in range(M):
  val = int(input())
  b[val] = 1

ans = rec(N)
print(ans % 1000000007)

Submission status: Runtime Error

Solution code:
def main():
    mod = 1000000007
    N, M, *A = map(int, open(0).read().split())
    F = [0] * (N + 1)
    # A.sort() 制約で単調性は保証されている
    F[0] = 1
    if not A[0] == 1:
        F[1] = 1
    for i in range(2, N + 1):
        if i not in A:
            F[i] = (F[i-1] + F[i-2]) % mod
    print(F[-1])


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def main():
    mod = 1000000007
    N, M, *A = map(int, open(0).read().split())
    F = [0] * (N + 1)
    A.sort()
    F[0] = 1
    if not A[0] == 1:
        F[1] = 1
    for i in range(2, N + 1):
        if i not in A:
            F[i] = (F[i-1] + F[i-2]) % mod
    print(F[-1])


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def main():
    N, M = map(int, input().split(" "))
    mod = 1000000007
    A = []
    for _ in range(M):
        A.append(int(input()))
    F = [0] * (N + 1)
    A.sort()
    F[0] = 1
    if not A[0] == 1:
        F[1] = 1
    for i in range(2, N + 1):
        if i not in A:
            F[i] = (F[i-1] + F[i-2]) % mod
    print(F[-1])


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def main():
    N, M = map(int, input().split(" "))
    mod = 1000000007
    A = []
    for _ in range(M):
        A.append(int(input()))
    F = [0] * (N + 1)
    A.sort()
    last_broken = 0
    if not A[0] == 1:
        F[0] = 1
    if M > 1 and not A[1] == 2:
        F[1] = 1 + F[0]
    for i in range(2, N + 1):
        if last_broken < M and not i == A[last_broken]:
            F[i] = (F[i-1] + F[i-2]) % mod
        else:
            last_broken += 1
    print(F[-1])


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    N, M = map(int, input().split(" "))
    mod = 1000000007
    A = []
    for _ in range(M):
        A.append(int(input()))
    F = [0] * (N + 1)
    A.sort()
    last_broken = 0
    if not A[0] == 1:
        F[0] = 1
    if M > 1 and not A[1] == 2:
        F[1] = 1 + F[0]
    print(F)
    for i in range(2, N + 1):
        if last_broken < M and not i == A[last_broken]:
            F[i] = (F[i-1] + F[i-2]) % mod
        else:
            last_broken += 1
    print(F[-1])


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# DP
mod = 10 ** 9 + 7
N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]

safe = [True] * (N+1)
for i in range(M):
    safe[A[i]] = False 

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

for i in range(3, N+1):
    if safe[i]:
        dp[i] = dp[i-1] + dp[i-2]

##print(dp)
print((dp[N]+mod)%mod)

Submission status: Runtime Error

Solution code:
sys.setrecursionlimit(10 ** 5 + 10)
mod = 10 ** 9 + 7

# フィボナッチ数列
fib_memo = {}
def fib(N):
    if N < 2: return 1
    if N not in fib_memo:
        fib_memo[N] = fib(N-1) + fib(N-2)
    return fib_memo[N]

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

tmp_list = [0] * (M+1)
now_kaidan = 0
for i in range(M):
    tmp_list[i] = (A[i] - 1) - now_kaidan
    now_kaidan = A[i] + 1
tmp_list[-1] = N-now_kaidan
ans = 1

for v in tmp_list:
    if v == -1:     # 壊れた階段が連続している時は0移動方法がない
        print(0)
        exit()
    ans *= fib(v)
    ans %= mod

print(ans%mod)

Submission status: Runtime Error

Solution code:
mod = 10 ** 9 + 7

# フィボナッチ数列
fib_memo = {}
def fib(N):
    if N < 2: return 1
    if N not in fib_memo:
        fib_memo[N] = fib(N-1) + fib(N-2)
    return fib_memo[N]

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

tmp_list = [0] * (M+1)
now_kaidan = 0
for i in range(M):
    tmp_list[i] = (A[i] - 1) - now_kaidan
    now_kaidan = A[i] + 1
tmp_list[-1] = N-now_kaidan
ans = 1

for v in tmp_list:
    if v == -1:     # 壊れた階段が連続している時は0移動方法がない
        print(0)
        exit()
    ans *= fib(v)
    ans %= mod

print(ans%mod)

Submission status: Runtime Error

Solution code:
memo = [0]*10**6 #i番目の数列を格納するためのメモ
def fib(n):
    if n in a:
        return 0
    if n<=1:
        return 1 #0,1番目の数列はo,1
    if memo[n] != 0:
        return memo[n] #i番目の数列がmemoにある場合それを返す
    memo[n] = fib(n-1) + fib(n-2) #i番目の数列の計算
    return memo[n]

print(fib(i)%1000000007)

Submission status: Runtime Error

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

memo = [0]*10**5 #i番目の数列を格納するためのメモ
def fib(n):
    if n in a:
        return 0
    if n<=1:
        return 1 #0,1番目の数列はo,1
    if memo[n] != 0:
        return memo[n] #i番目の数列がmemoにある場合それを返す
    memo[n] = fib(n-1) + fib(n-2) #i番目の数列の計算
    return memo[n]

print(fib(i)%1000000007)

Submission status: Runtime Error

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

a = [int(input()) for i in range(M)]
dp = [0 for i in range(N + 1)]
flag = [False for i in range(N + 1)]
dp[0] = 1
if a[0] != 1:
    dp[1] = 1
for i in a:
    flag[i] = True
for i in range(2,N+1):
    if flag[i - 1] != True:
        dp[i] = dp[i - 1]
    if flag[i - 2] != True:
        dp[i] += dp[i - 2]
print(dp[N] % 1000000007 )

Submission status: Runtime Error

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

up = [0]*(m+1)
if m == 0:
  up[0] = n
else:
  up[0] = a[0]-1
  up[m] = n - a[m-1]-1
  for i in range(m-1):
    up[i+1] = a[i+1]-a[i]-2

ans = 1
if -1 in up:
  ans = 0
else:
  f = [0]*(max(up)+1)
  f[0] = 1
  f[1] = 1
  for i in range(2, max(up)+1):
    f[i] = f[i-1] + f[i-2]
  for i in range(m+1):
    ans *= f[up[i]]

print(ans % 1000000007)

Submission status: Runtime Error

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

up = [0]*(m+1)
up[0] = a[0]-1
up[m] = n - a[m-1]-1
ans = 1
for i in range(m-1):
  up[i+1] = a[i+1]-a[i]-2

if -1 in up:
  ans = 0
else:
  f = [0]*(max(up)+1)
  f[0] = 1
  f[1] = 1
  for i in range(2, max(up)+1):
    f[i] = f[i-1] + f[i-2]
  for i in range(m+1):
    ans *= f[up[i]]

print(ans % 1000000007)

Submission status: Runtime Error

Solution code:
import sys
from collections import deque

def main():
    N, M = map(int, input().split())
    a = deque([int(sys.stdin.readline().strip()) for _ in range(M)])
    atmp = a.popleft()

    dp=[0] * (N+1)
    for i in range(0, N+1):
        if i == atmp:
            if len(a) != 0:
                atmp = a.popleft()
            continue

        if i == 0 or i == 1:
            dp[i] = 1
            continue

        if dp[i-1] == 0 and dp[i-2] == 0:
            break


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

    print(dp[N] % 1000000007)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
from collections import deque

def main():
    N, M = map(int, input().split())
    a = deque([int(sys.stdin.readline().strip()) for _ in range(M)])

    if len(a) != 0:
        atmp = a.popleft()

    dp=[0] * (N+1)
    for i in range(0, N+1):
        if i == atmp:
            if len(a) != 0:
                atmp = a.popleft()
            continue

        if i == 0 or i == 1:
            dp[i] = 1
            continue

        if dp[i-1] == 0 and dp[i-2] == 0:
            break


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

    print(dp[N] % 1000000007)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    N, M = map(int, input().split(" "))
    A = [-1]
    maximum = 0
    way = [1, 2]
    mod = 1000000007
    result = 1
    for i in range(M):
        a = int(input())
        if A[-1] + 1 == a:
            return 0
        else:
            maximum = max(maximum, a - A[-1])
            A.append(a)
    for i in range(2, maximum):
        way.append(way[i - 2] + way[i - 1])
    for j in range(1, M):
        result = result * (way[j] - way[j - 1] + 1) % mod
    return result


if __name__ == '__main__':
    print(main())

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
a = set([int(input()) for _ in range(M)])
mod = 1000000007
dp = [0] * (n+1)
dp[0] = 1#0段目へ行く移動方法は1通りしかない
if 1 not in a:#もし階段がぶっ壊れてるリストに1段目が入っていないならば1段目へ行く移動方法は1通り、そうでないなら0通り
    dp[1] = 1
else:
    dp[1] = 0
for i in range(2,n+1):#2段目から調べていく
    if i in a:#現在のi段目がぶっ壊れリストに含まれてるなら何もせず飛ばす
        continue
    dp[i] = dp[i-1] + dp[i-2]#フィボナッチで処理
    dp[i] %= mod#modで割っていく
print(dp[n])#n+1番目を出力する

Submission status: Runtime Error

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

check = [1]*(n)
check.append(0)
check.append(0)
be = int(input())
check[be-1] = 0
check[be-2] = 2
for i in range(m-1):
    a = int(input())
    if a == be+1:
        print(0)
        exit()
    else:
        check[a-1] = 0
        check[a-2] = 2
        be = a
        

count = [0]*(n+2)

mod = 10**9+7
if check[0]==1:
    count[0] = 1
    count[1] = 2
elif count[0] == 0:
    count[1] = 1

for i in range(1,n-1):
    if check[i+1] == 0:
        count[i+2] = count[i]%mod
    else:
        if check[i+1] == 1 or check[i+1] == 2:
            count[i+1] += count[i]%mod
        if check[i+2] == 1 or check[i+2] == 2:
            count[i+2] += count[i]%mod
    
print(count[n-1]%mod)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
, M = map(int,input().split())
alist = list()
for _ in range(M):
    alist.append(int(input()))


li = {}
li[0] = 1

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

Submission status: Runtime Error

Solution code:
#n段の上り方のバリエーションはフィボナッチ数列になっている

def Fib(dan):
    
    if dan == 0:
        return 0
    elif dan == 1:
        return 1
    else:
        return Fib(dan-1)+Fib(dan-2)

N, M = map(int,input().split())
ans = 1
lasthole = 0
if M == 0:
    print(Fib(N+1)%1000000007)
else:
    alist = list()
    for i in range(M):
        alist.append( int(input()))
    for a in alist:
        dan = a - lasthole 
        lasthole = a +1
        ans *= Fib(dan)
        ans = ans % 1000000007
    ans *= Fib(N - alist[M-1])
    
print(ans%1000000007)

Submission status: Runtime Error

Solution code:
def Fib(dan):
    
    if dan == 0:
        return 0
    elif dan == 1:
        return 1
    else:
        return Fib(dan-1)+Fib(dan-2)

N, M = map(int,input().split())
ans = 1
lasthole = 0
if M == 0:
    print(Fib(N+1))
else:
    alist = list()
    for i in range(M):
        alist.append( int(input()))
    for a in alist:
        dan = a - lasthole 
        lasthole = a +1
        ans *= Fib(dan)
    ans *= Fib(N - alist[M-1])
print(ans%1000000007)

Submission status: Runtime Error

Solution code:
import sys
n,m = map(int,input().split())
broken = []
for i in range(m):
  broken.append(int(input()))
  if(len(broken) >= 2):
    if(broken[i+1] - broken[i] == 1):
      print("0")
      sys.exit()

Submission status: Runtime Error

Solution code:
import sys
n,m = int(input().split())
broken = []
for i in range(m):
  broken.append(int(input()))
  if(len(broken) >= 2):
    if(broken[i+1] - broken[i] == 1):
      print("0")
      sys.exit()

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
from itertools import accumulate
n,m=map(int,input().split())
dp=[0]*(n+1)
List=[int(input()) for i in range(m)]
List.sort()
step=0

dp[0]=1
dp[1]=1

if(List[0]==1):
    dp[1]=0
    step+=1
for i in range(2,n+1):
    # print(i,step)
    if(step<m and i==List[step]):
        step+=1
        dp[i]=0
    else:
        dp[i]=dp[i-2]+dp[i-1]
# print(List)
# print(dp)
print(dp[n]%((10**9)+7))

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

MOD = 1000000007


def main():
    n, m = [int(i) for i in input().split()]
    a = {int(input()) for _ in range(m)}
    steps = [0] * (n + 1)
    steps[0] = 1

    for now in range(n):
        for next_ in range(now + 1, min(now + 2, n) + 1):
            if next_ not in a:
                steps[next_] += steps[now] % MOD
                steps[next_ %= MOD]
    print(steps[-1])


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

ways=[]
nextbreak = a[0]
for i in range(N+1):
    if i==nextbreak:
        a = a[1:]
        try:
            nextbreak=a[0]
        except IndexError:
            nextbreak=0
        ways+=[0]
    elif i==0:
        ways +=[1]
    elif i==1:
        ways +=[1]
    else:
        ways+=[(ways[i-2]+ways[i-1])%1000000007]
print(ways[-1])

Submission status: Runtime Error

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

ways=[]

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

Submission status: Runtime Error

Solution code:
import math
N, M = map(int,input().split())
a = [int(input()) for i in range(M)]
b = [-1]+ a+ [N+1]
def combination(n, k):
    result = 1
    for i in range(n - k + 1, n + 1):
        result *= i
    for i in range(1, k + 1):
        result /= i
    return result

def fibonacci(k):
    k = k + 1
    result = 0
    for i in range(1, int(math.ceil(k / 2.0) + 1)):
        result += combination(k, 2 * i - 1) * pow(5, i - 1)
    return int(result / pow(2, k - 1))

def combi(d):
    if d < 0:
        return 0
    elif 0 <= d <= 1:
        return 1
    else:
        return fibonacci(d)
ans = 1
for i in range(len(b)-1):
    ans= (ans*combi(b[i+1]-b[i]-2))%1000000007
print(ans)

Submission status: Runtime Error

Solution code:
import math
N, M = map(int,input().split())
a = [int(input()) for i in range(M)]
b = [-1]+ a+ [N+1]
def combi(d):
    if d < 0:
        return 0
    elif 0 <= d <= 1:
        return 1
    else:
        combi = int((1/math.sqrt(5))*(((1+math.sqrt(5))/2)**(d+1) - ((1-math.sqrt(5))/2)**(d+1)) + 0.01)
        return combi
ans = 1
for i in range(len(b)-1):
    ans= (ans*combi(b[i+1]-b[i]-2))%1000000007
print(ans)

Submission status: Runtime Error

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

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

if 1 in a and 2 in a:
    print(0)
    exit()
elif 1 in a and 2 not in a:
    dp[1] = 0
    dp[2] = 1
elif 1 not in a and 2 in a:
    dp[1] = 1
    dp[2] = 0
else:
    dp[1] = 1
    dp[2] = 2

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

print(dp[n])

Submission status: Runtime Error

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

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

A.sort()
ida = 0
a = A[ida]
mod = 10**9 + 7

x = [1] + [0]*N
if a == 1:
  ida += 1
  if M >= 2:
    a = A[ida]
  else:
    x[1] = 1

for i in range(2, N+1):
  if i == a:
    ida += 1
    if ida >= M:
      a = N+1
    else:
      a = A[ida]
  
    x[i] = 0
  else:
    x[i] = (x[i-1] + x[i-2]) % mod

print(x[N])

Submission status: Runtime Error

Solution code:
N, M=map(int, input().split())
mod=10**9+7
dp=[0 for i in range(N+1)]
dp[N] = 1
is_broken =[False for i in range(N+1)]

for i in range(M):
    a=int(input())
    is_broken[a] = True

for i in reversed(range(N)):
    if is_broken[i]:
        dp[i] = 0
        continue
    dp[i] = (dp[i+1] + dp[i+2]) % mod

print(dp[0])

Submission status: Runtime Error

Solution code:
N, M=map(int, input().split())
items=[int(input()) for i in range(M)]
mod=10**9+7
dp=[0 for i in range(N+1)]
dp[0] = 1
is_broken =[1 for i in range(N+1)]

for i in range(M):
    is_broken[items[i]] = 0

for i in range(N).reverse:
    if is_broken[i]:
        dp[i] = 0
        continue
    dp[i] = (dp[i+1] + dp[i+1]) % mod

print(dp[0])

Submission status: Runtime Error

Solution code:
from collections import deque

def bfs(maze, visited, sy, sx, dead, goal):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    count = 0
    while queue:
        y, x = queue.popleft()
        if maze[y][x] == goal:
            count += 1
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y+j, x+k
            if not maze[new_y][new_x] in dead and \
                visited[new_y][new_x] == -1:
                visited[new_y][new_x] = visited[y][x] + 1
                queue.append([new_y, new_x])
    return count % 1000000007

n,m=map(int, input().split())
a=[int(input()) for i in range(m)]
maze=[[2*i+j for i in range(int(n/2+1))] for j in range(n+1)]
visited = [[[-1] for i in range(int(n/2+1))] for j in range(n+1)]
print(bfs(maze, visited, 0, 0, a, n))

Submission status: Runtime Error

Solution code:
from collections import deque

def bfs(maze, visited, sy, sx, dead, goal):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    count = 0
    while queue:
        y, x = queue.popleft()
        if maze[y][x] == goal:
            count += 1
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y+j, x+k
            if not maze[new_y][new_x] in dead and \
                visited[new_y][new_x] == -1:
                visited[new_y][new_x] = visited[y][x] + 1
                queue.append([new_y, new_x])
    return count % 1000000007
if __name__ == "__main__":
    n,m=map(int, input().split())
    a=[int(input()) for i in range(m)]
    maze=[[2*i+j for i in range(int(n/2+1))] for j in range(n+1)]
    visited = [[[-1] for i in range(int(n/2+1))] for j in range(n+1)]
    print(bfs(maze, visited, 0, 0, a, n))

Submission status: Runtime Error

Solution code:
#coding: utf-8
import math
import heapq
import bisect
#from scipy.misc import comb

MOD = 10**9+7

N = int(input())
X,Y = map(int, input().split())

# 複数個の数値を、intの配列として取得
L = list(map(int, input().split()))

# (x,y)みたいな構造体をN個まとめてリストにするとき
A = []
for i in range(N):
    a = tuple(map(int, input().split()))
    A.append(a)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
a = list(int(input())for i in range(m))
mod = 10**9+7
b = [0] * (n-1)
b[0] = 1
b[1] = 1
for i in a:
    b[i] = -1

for i in range(2,n+1):
    if b[i] == -1:
        continue
    if b[i-1] != -1:
        b[i] += b[i-1]
    if b[i-2] != -1:
        b[i] += b[i-2]

print(b[-1]%mod)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
a = list(int(input())for i in range(M))
mod = 10**9+7
b = [0] * (n-1)
b[0] = 1
b[1] = 1
for i in a:
    b[i] = -1

for i in range(2,n+1):
    if b[i] == -1:
        continue
    if b[i-1] != -1:
        b[i] += b[i-1]
    if b[i-2] != -1:
        b[i] += b[i-2]

print(b[-1]%mod)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
a = list(int(input())for i in range(M))
mod = 10**9+7
b = [0] * (n-1)
b[0] = 1
b[1] = 1
for i in a:
    b[i] = -1

for i in range(2,n+1):
    if b[i] == -1:
        continue
    if b[i-1] != -1:
        b[i] += b[i-1]
    if b[i-2] != -1:
        b[i] += b[i-2]

print(b[-1]%mod)

Submission status: Runtime Error

Solution code:
N, M = map(int,input().split())
a = [int(input()) for i in range(M)]
dp = [0 for i in range(N+1)]
dp[0] = 1
dp[1] = 1
for i in range(2,N+1)
  if (i-2 in a) and (i-1 in a):
    dp[-1] = 0
    break
  elif i-2 in a:
    dp[i] = dp[i-1]
  elif i-1 in a:
    dp[i] = dp[i-2]
  else:
    dp[i] = dp[i-1] + dp[i-2]

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

Submission status: Runtime Error

Solution code:
def examC():
    N, M = LI()
    A = [I() for _ in range(M)]
    A.append(N+1)
    fib = [1]*(N+1)
    for i in range(1,N-1):
        fib[i+2] = fib[i+1] + fib[i]
    fib[0] = 0
#    print(fib)
    ans = fib[A[0]]
    for i in range(M):
        ans *= fib[A[i+1]-A[i]-1]
        ans %=mod
    print(ans)
    return

def examD():
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,inf
mod = 10**9 + 7
inf = float('inf')

if __name__ == '__main__':
    examC()

Submission status: Runtime Error

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

for i in range(m):
    a = int(input())
    ans[a-1] = 0

if ans[0] != 0 and ans[1] != 0:
    ans[0] = 1
    ans[1] = 2

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

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
a=list(map(int,open(0).read().split()))

b=[0]*(N+2)
b[0]=1
b[1]=1

for j in range(M):
    b[a[j]]=-1

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

Submission status: Runtime Error

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

dp = [0] * 10100
dp[0] = 1
dp[1] = 0 if 1 in A else 1

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

print(dp[N])

Submission status: Runtime Error

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

dp = [-1] * 10100
dp[0] = 1
dp[1] = 1

for i in range(M):
    a = int(input())
    dp[a] = 0

for i in range(N):
    if dp[i+2] == 0: continue
    dp[i+2] = dp[i]+dp[i+1]

print(dp[N] % 1000000007)

Submission status: Runtime Error

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

dp = [0] * 20000
dp[0] = 1
dp[1] = 0 if 1 in A else 1
for i in range(N):
    if i+2 in A:
        continue
    dp[i+2] = dp[i] + dp[i+1]

print(dp[N] % 1000000007)

Submission status: Runtime Error

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

dp = [0] * 10010
dp[0] = 1
dp[1] = 0 if 1 in A else 1
for i in range(N):
    if i+2 in A:
        continue
    dp[i+2] = dp[i] + dp[i+1]

print(dp[N] % 1000000007)

Submission status: Runtime Error

Solution code:
import sys

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

A = int(input())
n = 1

dp = [0]*(N+1)
if N == 1:
    if 1 == A:
        print('0')
        sys.exit()
    else:
        print('1')
        sys.exit()
if 1 == A:
    dp[1] = 0
    if M != n:
        A = int(input())
        n += 1
else:
    dp[1] = 1
dp[0] = 1
for i in range(2, N+1):
    if i == A:
        dp[i] = 0
        if M != n:
            A = int(input())
            n += 1
    else:
        dp[i] = dp[i-1]%1000000007 + dp[i-2]%1000000007

print(dp[N]%1000000007)

Submission status: Runtime Error

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

dp = [0] * (N+1)
#どうやってもスタート地点から始まるから、0に行く方法は1通りのみ
dp[0] = 1

#1が壊れていなければ1に行く方法は0->1の1通りのみ
if a[0] != 1:
    dp[1] = 1
    not_broken_stairs = set(range(2, N+1)) - set(a)
else:
    not_broken_stairs = set(range(1, N+1)) - set(a)    

#i=2or3から始まる。
#１が壊れていなければ2に行く方法は(0->2の1通り)+(1->2の1通り)で2通り。
for i in not_broken_stairs:
    dp[i] = dp[i-2] + dp[i-1]
    
print(dp[-1] % (10 ** 9 + 7))

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
mod=10**9+7
t=[int(input()) for i in range(m)] 
dp=[-1]*(n+1)

dp[0]=0
dp[1]=1
dp[2]=2

for i in range(m):
    dp[t[i]]=0

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

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
mod=10**9+7
t=[int(input()) for i in range(m)] 
dp=[-1]*(n+1)

dp[0]=0
dp[1]=1
dp[2]=1

for i in range(m):
    dp[t[i]]=0

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

Submission status: Runtime Error

Solution code:
n, m = gets.chomp.split(' ').map(&:to_i)
arr = Array.new(n)
m.times do
  arr[gets.chomp.to_i] = 0
end

num = n-3
while(num>=0)
  arr[num] = (arr[num+1] + arr[num+2]) % 1_000_000_007
  num-=1
end
puts arr[0]

Submission status: Runtime Error

Solution code:
n.m = map(int,input().split())
l = [int(input()) for _ in[0]*m]
l=set(l)
dp=[0]*(n+1)#0〜n段目までのn+1通り。
#1段目までは手動。
dp[0]=1
dp[1]=0 if 1 in l else 1
MOD =10**9+7
#dp 貰うタイプ
for i in range(2,n+1):
  if i not in l:#床が壊れてなければ
    dp[i] = (dp[i-1] + dp[i-2])%MOD
print(dp[n])

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
def fib_memo(n):
    memo=["EMPTY"]*(n+1)
    def _fib(n):
        if n == 1:
            return 0
        elif n == 2:
            return 1
        elif memo[n] != "EMPTY":
            return memo[n]
        else:
            memo[n] = _fib(n-1)+_fib(n-2)
            return memo[n]
    return _fib(n)
def fib(n):
    f = ((1 + 5**0.5) / 2)**n / 5**0.5 + 0.5
    return int(f)
  
n,m=map(int,input().split())
a=[int(input()) for i in range(m)]
if a:
  cnt=fib(a[0]+1)*fib(n-a[m-1]+1)
  for i in range(1,m):
    cnt*=fib(a[i]-a[i-1])
  print(cnt%(10**9+7))
else:
  print(fib_memo(n+2)%(10**9+7))

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
mod = 10**9+7
def framod(n, mod, a=1):
    for i in range(1,n+1):
        a=a * i % mod
    return a

def power(n, r, mod):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod

def comb(n, k, mod):
    a=framod(n, mod)
    b=framod(k, mod)
    c=framod(n-k, mod)
    return (a * power(b, mod-2, mod) * power(c, mod-2, mod)) % mod

def cnt(n):
  s = sum([comb(n-i,i,mod)%mod for i in range(n//2+1)]):
  s = s%mod
  return s

A0 = 0
ans = 1
for i in range(M):
  A1 = int(input()) - 1
  ans = (ans * cnt(A1-A0))%mod
  A0 = A1+2
ans = (ans * cnt(N-A0))%mod
print(ans)

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
mod = 10**9+7
def framod(n, mod, a=1):
    for i in range(1,n+1):
        a=a * i % mod
    return a

def power(n, r, mod):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod

def comb(n, k, mod):
    a=framod(n, mod)
    b=framod(k, mod)
    c=framod(n-k, mod)
    return (a * power(b, mod-2, mod) * power(c, mod-2, mod)) % mod

def cnt(n):
  s = sum([comb(n-i,i,mod)%mod for i in range(n//2+1)]:
  s = s%mod
  return s

A0 = 0
ans = 1
for i in range(M):
  A1 = int(input()) - 1
  ans = (ans * cnt(A1-A0))%mod
  A0 = A1+2
ans = (ans * cnt(N-A0))%mod
print(ans)

Submission status: Runtime Error

Solution code:
def solve():
    N, M, *a = map(int, open(0).read().split())
    MOD = 1000000007

    dp = [0 for _ in range(N+1)]
    if 1 not in a:
        dp[1] = 1
        if 2 not in a:
            dp[2] = 2
    elif 2 not in a:
        dp[2] = 1

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


if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
from functools import lru_cache


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

mod = 10 ** 9 + 7

i = 0
b = []
for ai in a:
    b.append(ai - i)
    i = ai + 1
b.append(N + 1 - i)


@lru_cache(maxsize=None)
def f(n):
    if n < 2:
        return n
    else:
        return f(n - 2) + f(n - 1)


ans = 1
for bi in b:
    ans *= f(bi) % mod
print(ans % mod)

Submission status: Runtime Error

Solution code:
from functools import lru_cache


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

mod = 10 ** 9 + 7

i = 0
b = []
for ai in a:
    b.append(ai - i)
    i = ai + 1
b.append(N + 1 - i)


@lru_cache(maxsize=None)
def f(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return f(n - 2) + f(n - 1)


ans = 1
for bi in b:
    ans *= f(bi)
print(ans % mod)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
a = [int(input()) for _ in range(M)]
booli = [False]*(N)
for i in a:
    booli[i-1] = True
mod = 1000000007
INF = -1
dp = [INF]*(N+1)
dp[0] = 1
if booli[1]:
    dp[1] = 0
else:
    dp[1] = 1
def solve():
    for i in range(2,N+1):
        if booli[i-1]:
            dp[i] = 0
        else:
            dp[i] = dp[i-1]+dp[i-2]
    return dp[N]%mod
print(solve())

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
K=10**9+7
"""la=[]
for i in range(M):
    la.append(int(input()))"""
ldp=[0 for i in range(N)]
for i in range(M):
    a=int(input())
    ldp[a-1]=-1
if ldp[0]!=-1:
    ldp[0]=1
    #if ldp[1]!=-1:
    #    ldp[1]=1
if N>=1:
    if ldp[1]!=-1:
        ldp[1]+=1
        if ldp[0]!=-1:
            ldp[1]+=1

if N>=2:
    for i in range(2,N):
        if ldp[i]!=-1:
            if ldp[i-1]!=-1:
                ldp[i]=(ldp[i]+ldp[i-1])%K
            if ldp[i-2]!=-1:
                ldp[i]=(ldp[i]+ldp[i-2])%K
#print(ldp)
print(ldp[N-1])