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: Wrong Answer

Solution code:
# abc129_c.py
# https://atcoder.jp/contests/abc129/tasks/abc129_c

# C - Typical Stairs /
# 実行時間制限: 2 sec / メモリ制限: 1024 MB
# 配点 : 300点

# 問題文
# N段の階段があります。高橋君は現在、上り口(0 段目)にいます。 高橋君は一歩で 1 段か 2段上ることができます。
# ただし、a1,a2,a3,....aM段目の床は壊れており、その段に足を踏み入れることは危険です。
# 壊れている床を踏まないようにしながら、最上段(N段目)にたどりつくまでの移動方法は何通りあるでしょうか？ 
# 総数を 1,000,000,007で割った余りを求めてください。

# 制約
#     1≦N≦105
#     0≦M≦N−1
#     1≦a1<a2<
#     ... <aM≦N−1

# 入力
# 入力は以下の形式で標準入力から与えられます。
# N M
# a1
# a2
# .
# .
# .
# aM

# 出力
# 条件を満たすような移動方法の総数を、1,000,000,007で割った余りを出力してください。

# 入力例 1
# 6 1
# 3

# 出力例 1
# 4

# 移動方法は以下の 4通りです。
#     0→1→2→4→5→6
#     0→1→2→4→6
#     0→2→4→5→6
#     0→2→4→6

# 入力例 2
# 10 2
# 4
# 5

# 出力例 2
# 0

# 壊れている床を踏まないような移動方法がない場合もあります。

# 入力例 3
# 100 5
# 1
# 23
# 45
# 67
# 89

# 出力例 3
# 608200469

# 総数を 1,000,000,007で割った余りを出力することに注意して下さい。


global FLAG_LOG
FLAG_LOG = False


def log(value):
    # FLAG_LOG = True
    # FLAG_LOG = False
    if FLAG_LOG:
        print(str(value))


# 妥協しました・・・奇数だとダメです。Nが大きすぎても多分駄目です。
def calculation(lines):
    # S = lines[0]
    # N = int(lines[0])
    N, M = list(map(int, lines[0].split()))
    # values = list(map(int, lines[1].split()))
    # values = list(map(int, lines[2].split()))
    values = list()
    for i in range(M):
        values.append(int(lines[i+1]))
    # valueses = list()
    # for i in range(M):
    #     valueses.append(list(map(int, lines[i+1].split())))

    # 2つ連続して壊れていたらその場で0を返す
    for i in range(len(values)-1):
        if values[i+1] - values[i] == 1:
            return [0]

    # 最低1パターンあるのでこれを積算してゆく
    result = 1

    safe_steps = get_safe_steps(M, N, values)
    log(f'safe_steps=[{safe_steps}]')

    for safe_step in safe_steps:
        result = int((result * def_n_pattern(safe_step)) % 1000000007)

    return [result]


# 壊れた階段をよけた数に分割する
def get_safe_steps(N, M, values):
    # 最小値から順に追加
    ret = list()
    # 到着済みのステップ(=スタート地点)
    prev = 0
    for value in values:
        # 到着済みのステップから次の手前までのステップ数を追加
        ret.append(value - prev - 1)
        # 到着済みのステップを記録
        prev = value + 1
    # 最後の1段を追加
    ret.append(M - prev)
    return ret


# 進む数ごとのパターン数を返す
def def_n_pattern(n):
    if n == 0:
        result = 1
    # if n == 2:
    #     result = 2
    # if n == 10:
    #     result = 89
    # if n == 20:
    #     result = 0
    #     result += 1
    #     result += 19
    #     result += 18*17/2
    #     result += 17*16*15/6
    #     result += 16*15*14*13/24
    #     result += 15*14*13*12*11/120
    #     result += 14*13*12*11*10*9/720
    #     result += 13*12*11*10*9*8*7/5040
    #     result += 12*11*10*9*8*7*6*5/40320
    #     result += 11*10*9*8*7*6*5*4*3/362880
    #     result += 10*9*8*7*6*5*4*3*2*1/3628800

    result = 1
    for i in range(int(n/2)):
        tmp = 1
        for j in range(i):
            tmp *= (n-i-j)
            tmp /= (j+1)
        result += tmp
    return result


# 引数を取得
def get_input_lines():
    line = input()
    N, M = list(map(int, line.split()))
    lines = list()
    lines.append(line)
    for _ in range(M):
        lines.append(input())
    return lines


# テストデータ
def get_testdata(pattern):
    if pattern == 1:
        lines_input = ['6 1', '3']
        lines_export = [4]
    if pattern == 2:
        lines_input = ['10 2', '4', '5']
        lines_export = [0]
    if pattern == 3:
        lines_input = ['100 5', '1', '23', '45', '67', '89']
        lines_export = [608200469]
    return lines_input, lines_export


# 動作モード判別
def get_mode():
    import sys
    args = sys.argv
    global FLAG_LOG
    if len(args) == 1:
        mode = 0
        FLAG_LOG = False
    else:
        mode = int(args[1])
        FLAG_LOG = True
    return mode


# 主処理
def main():
    import time
    started = time.time()
    mode = get_mode()
    if mode == 0:
        lines_input = get_input_lines()
    else:
        lines_input, lines_export = get_testdata(mode)

    lines_result = calculation(lines_input)

    for line_result in lines_result:
        print(line_result)

    # if mode > 0:
    #     print(f'lines_input=[{lines_input}]')
    #     print(f'lines_export=[{lines_export}]')
    #     print(f'lines_result=[{lines_result}]')
    #     if lines_result == lines_export:
    #         print('OK')
    #     else:
    #         print('NG')
    # finished = time.time()
    # duration = finished - started
    # print(f'duration=[{duration}]')


# 起動処理
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#https://atcoder.jp/contests/abc129/tasks/abc129_c
N,M = map(int,input().split())
Danger_List = []
Route_List = [[] for i in range(N+1)]
for i in range(M):
    Route_List[int(input())] = 0
        
Route_List[0] = 1

for i in range(1,N+1):
    if Route_List[i] != 0:
        if i == 1:
            Route_List[i] = 1
        else:
            Route_List[i] = Route_List[i-1] + Route_List[i-2]

    
    
        
print(Route_List[-1])

Submission status: Wrong Answer

Solution code:
from itertools import product

def mat2_mul(X, Y):
    Z = [ [0, 0], 
          [0, 0] ]
    for (i,j,k) in product(range(2),range(2),range(2)):
        Z[i][j] += X[i][k] * Y[k][j]
    return Z

def mat2_pow(X, n):
    if n == 0:
        return [ [1, 0],
                 [0, 1] ]
    elif n % 2:
        return mat2_mul(X, mat2_pow(X, n-1))  
    else:
        half_pow = mat2_pow(X, n/2)
        return mat2_mul(half_pow, half_pow)

def fibona(n):
    if n == 0:
        return 0
    else:
        F = [ [0, 1],
              [1, 1] ]
        return mat2_pow(F, n)[1][1]
def main():
    n, m = map(int,input().split())
    mlis = []
    for _ in range(m):
        a = int(input())
        mlis.append(a)
    ans = 1
    mae = -1


    for i in range(m):

        broken = mlis[i]
        if mae == broken - 1:
            print(0)
            exit()

        nobori = (broken-1) - (mae+1)
        if nobori == 0:
            ans *= 1
            mae = broken
        else:
            ans *= fibona(nobori)
            ans %= (10 ** 9 + 7)
            mae = broken

    nobori = n - (mae+1)
    ans *= fibona(nobori) 
    ans %= (10 ** 9 + 7)
    print(int(ans))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
a=[int(input()) for i in range(M)]
b=0
c=0
while b<N:
  if b+2 in a:
    b+=1
    c+=1
  else:
    b+=2
    c+=1
print(c)

Submission status: Wrong Answer

Solution code:
def fib(n):
    if n <= 1:
        return n
    result = [1, 0, 0, 1]
    matrix = [1, 1, 1, 0]
    while n > 0:
        if n % 2:
            result = mul(matrix, result)
        matrix = mul(matrix, matrix)
        n //= 2
    return result[2]

def mul(a, b):
    return [a[0]*b[0] + a[1]*b[2],
            a[0]*b[1] + a[1]*b[3],
            a[2]*b[0] + a[3]*b[2],
            a[2]*b[1] + a[3]*b[3]]
    
N, M = map(int, input().split())
if N == 1:
    print(1)
S = [-1]
for i in range(M):
    S.append(int(input()))
S.append(N + 1)
S = [S[i + 1] - S[i] for i in range(M + 1)]
if any([x == 1 for x in S]):
    print(0)
    exit()
num = 1
for x in S:
    num *=  fib(x - 1)
    num = num % 1000000007
print(num)

Submission status: Wrong Answer

Solution code:
def fib(n):
    if n <= 1:
        return n
    result = [1, 0, 0, 1]
    matrix = [1, 1, 1, 0]
    while n > 0:
        if n % 2:
            result = mul(matrix, result)
        matrix = mul(matrix, matrix)
        n //= 2
    return result[2]

def mul(a, b):
    return [a[0]*b[0] + a[1]*b[2],
            a[0]*b[1] + a[1]*b[3],
            a[2]*b[0] + a[3]*b[2],
            a[2]*b[1] + a[3]*b[3]]
    
N, M = map(int, input().split())
if N == 1:
    print(1)
S = [-1]
for i in range(M):
    S.append(int(input()))
S.append(N + 1)
S = [S[i + 1] - S[i] for i in range(M + 1)]
if any([x == 1 for x in S]):
    print(0)
    exit()
num = 1
for x in S:
    num *= fib(x)
    num = num % 1000000007
print(num)

Submission status: Wrong Answer

Solution code:
import numpy as np
n,m=map(int, input().split())
a=set(int(input())  for i in  range(m))
x=(10**9)+7

dp=np.array([0]*(n+1))
dp[0]=1
if 1 not in a:
  dp[1]=1

for i in range(2,n+1):
  if i in a:
    continue
  dp[i]+=dp[i-1]+dp[i-2]
  #print(dp)
  
print(dp[-1]%x)

Submission status: Wrong Answer

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

MOD = 10**9 + 7

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

dp = [0] * (N+1)
dp[0] = 1
if safe[1]:
    dp[1] = 1

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

print(dp)

Submission status: Wrong Answer

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

MOD = 10**9 + 7

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

print(safe)

dp = [0] * (N+1)
dp[0] = 1
if safe[1]:
    dp[1] = 1

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

print(dp)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
#
# Created: Jul, 12, 2020 18:27:48 by Nobody
# $Author$
# $Date$
# $URL$
__giturl__ = "$URL$"


from sys import stdin
input = stdin.readline


def main():
  N, M = list(map(int, input().split()))
  A = set([int(input()) for _ in range(M)])

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

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

  print(dp[N] % 1000000007)


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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
#
# Created: Jul, 12, 2020 18:27:48 by Nobody
# $Author$
# $Date$
# $URL$
__giturl__ = "$URL$"


from sys import stdin
input = stdin.readline


def main():
  N, M = list(map(int, input().split()))
  A = set([int(input()) for _ in range(M)])

  dp = [0]*(N+1)
  dp[0] = 1
  dp[1] = 1

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

  print(dp[N] % 1000000007)


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

Submission status: Wrong Answer

Solution code:
import sys
from operator import itemgetter

sys.setrecursionlimit(10**9)
input = sys.stdin.readline

def ii(): return int(input())
def mi(): return map(int, input().split())
def lmi(): return list(map(int, input().split()))
def iif(n): return [int(input()) for _ in range(n)]
def lmif(n): return [list(map(int, input().split())) for _ in range(n)]
def ss(): return input().split()

def main():
    mod = 1000000007

    F = [1, 1]
    for i in range(100000):
        F.append(F[i] + F[i+1])

    N, M = mi()

    if M == 0:
        print(F[N])
        return

    A = iif(M)
    DA = []
    left = 0
    for i in range(M):
        da = A[i] - left
        if da == 0 and left != 0:
            print(0)
            return
        else:
            DA.append(da-1)
        left = A[i] + 1
    if A[-1] != N:
        DA.append(N - A[-1] - 1)


    ans = 1
    for i in DA:
        ans *= F[i]

    print(ans % mod)

    return

main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
 
N,M = list(map(int,input().split()))
lis = [-1]*(N+1)
for i in range(M):
    lis[int(input())] = 0
lis[0] = 1
if lis[1]==-1:
    lis[1] = 1 
for i in range(2,N+1):
    if lis[i] == -1:
        
        lis[i] = lis[i-1] + lis[i-2]

        
    if lis[i] ==0 and lis[i-1] == 0:
        break
print(1 if N == 1 else lis[-1]%1000000007)

Submission status: Wrong Answer

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
def gcd(*numbers): reduce(math.gcd, numbers)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
count = 0
ans = 0
inf = float("inf")

def dpp(n):
    
    dp = [0]*(N+1)
    dp[0] = 1

    if n == 0:
        return 0
    if n == 1:
        if 1 in a:
            dp[1] = 0
            return 0
        else:
            dp[1] = 1
            return 1

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

N,M = I()
a = []
for i in range(M):
    x = k()
    a.append(x)

print(dpp(N) % mod)

Submission status: Wrong Answer

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

dp = [0] * (N + 1)

dp[0] = 1
for i in range(N):
    for j in range(i + 1, min(N, i + 2) + 1):
        if A[j] is True:
            dp[j] += dp[i]
            dp[j] %= 10 ** 9 + 7

print(dp[N])

Submission status: Wrong Answer

Solution code:
import math

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

def count_combinations(min_val, max_val):
    path_len = max_val - min_val - 2
    if path_len < 2:
        return 1
    twos = path_len // 2
    min_amount = twos + (path_len % 2)
    count = 0
    for i in range(min_amount, path_len + 1):
        count += comb(i, twos)
        twos -= 1
    return count

def conut_paths(a):
    paths = 1
    for i in range(len(a) - 1):
        paths *= count_combinations(a[i], a[i + 1])
    return paths % 1000000007

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

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

A.insert(0, -1)
A.append(N + 1)
print(A)
print(conut_paths(A))

Submission status: Wrong Answer

Solution code:
def main():
    N, M = map(int, input().split())
    A = set()
    for _ in range(M):
        a = int(input())
        A.add(a)
    mod = 10**9 + 7
    dp = [0] * (N+1)
    dp[0] = 1
    if 1 not in A:
        dp[1] = 1
    for i in range(1, N+1):
        if i not in A:
            dp[i] = dp[i-1] + dp[i-2]
            dp[i] %= mod
    return dp[-1]
print(main())

Submission status: Wrong Answer

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

Flag = [True for _ in range(N+1)]
for a in A:
    Flag[a] = False

Dp = [0 for _ in range(N+1)]

Dp[0] = 1
Dp[1] = 1
for i in range(N-1):
    if Flag[i+2]:
        Dp[i+2] = (Dp[i] + Dp[i+1])%(10**9+7)
print(Dp[-1])

Submission status: Wrong Answer

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

Flag = [True for _ in range(N+1)]
for a in A:
    Flag[a] = False

Dp = [0 for _ in range(N+1)]

Dp[0] = 1
Dp[1] = 1
for i in range(N-1):
    if Flag[i+2]:
        Dp[i+2] = (Dp[i] + Dp[i+1])%(10**9+7)
Dp[N]

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
lis = [0]*(n+1)
a = []
for i in range(m):
    a.append(int(input()))
    
mod = 10**9+7
ans = 0
if n==1:
    print(1)
elif n==2:
    if m==1:
        print(1)
    else:
        print(2)
else:
    if 1 in a and 2 in a:
        print(0)
    elif 1 in a:
        lis[1] = 1
    elif 2 in a:
        lis[0] = 1
    else:
        lis[0] = 1
        lis[1] = 2
    
    for j in range(3,n+1):
        if j in a:
            lis[0] = lis[1]
            lis[1] = 0
        else:
            ans = lis[0]%mod + lis[1]%mod
            lis[0] = lis[1]
            lis[1] = ans
        
        if lis[0] == 0 and lis[1] == 0:
            ans = 0
            break
        

    print(ans%mod)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
lis = [0]*2
a = []
for i in range(m):
    a.append(int(input()))
ans = 0
if n==1:
    print(1)
elif n==2:
    if m==1:
        print(1)
    else:
        print(2)
else:
    if 1 in a and 2 in a:
        print(0)
    elif 1 in a:
        lis[1] = 1
    elif 2 in a:
        lis[0] = 1
    else:
        lis[0] = 1
        lis[1] = 2
    
    for j in range(3,n+1):
        if j in a:
            lis[0] = lis[1]
            lis[1] = 0
        else:
            ans = lis[0] + lis[1]
            lis[0] = lis[1]
            lis[1] = ans
        
        if lis[0] == 0 and lis[1] == 0:
            ans = 0
            break
        

    print(ans%1000000007)

Submission status: Wrong Answer

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

if n==1:
    print(1)
elif n==2:
    if m==1:
        print(1)
    else:
        print(2)
else:##n>=3
    if 1 in a and 2 in a:
        print(0)
    elif 1 in a:
        lis[2] = 1
    elif 2 in a:
        lis[1] = 1
    else:
        lis[1] = 1
        lis[2] = 2
    
    for j in range(3,n+1):
        if j in a:
            pass
        else:
            lis[j] = lis[j-1] + lis[j-2]
        
        if lis[j] == 0 and lis[j-1] == 0:
            break
    print(lis[n]%1000000007)

Submission status: Wrong Answer

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

for i in range(m):
    a = int(input())
    broken[a] = 1

dp = [0] * (n + 1)
mod = 1000000007

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

print(dp[n])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
a = [0]*m
for i in range(m):
  a[i] = int(input())
dp = [0]*(n+1)
dp[0] = 1
dp[1] = 1

for j in range(1,n+1):
  if j in a:
    dp[j] = 0
  else:
    dp[j] = dp[j-1]+dp[j-2]
#print(dp)
print(dp[n]%1000000007)

Submission status: Wrong Answer

Solution code:
N, M = [int(_) for _ in input().split()]
A = [int(input()) for i in range(M)]
isBroken = [False] * (N + 1)
for i in A:
    isBroken[i] = True


def solve():

    # It's impossible
    if M >= 1:
        temp = A[0]
        for a in A[1:]:
            if a - 1 == temp:
                return 0
            temp = a

    # We can
    memo = [0] * (N + 1)

    def rec(i):
        if i == 0:
            return 1
        if i < 0:
            return 0
        if isBroken[i]:
            return 0

        return 0
        if memo[i] == 0:
            count1 = rec(i - 1) % 1000000007
            count2 = rec(i - 2) % 1000000007
            memo[i] = (count1 + count2) % 1000000007
            # print(f"memo[{i}] = {count1} + {count2} -> {memo[i]}")
        return memo[i]
    return rec(N)


print(solve())

Submission status: Wrong Answer

Solution code:
N, M = [int(_) for _ in input().split()]
A = [int(input()) for i in range(M)]
isBroken = [False] * (N + 1)
for i in A:
    isBroken[i] = True


def solve():

    # It's impossible
    if M >= 1:
        temp = A[0]
        for a in A[1:]:
            if a - 1 == temp:
                return 0
            temp = a
    return 0

    # We can
    memo = [0] * (N + 1)

    def rec(i):
        if i == 0:
            return 1
        if i < 0:
            return 0
        if isBroken[i]:
            return 0
        if memo[i] == 0:
            count1 = rec(i - 1) % 1000000007
            count2 = rec(i - 2) % 1000000007
            memo[i] = (count1 + count2) % 1000000007
            # print(f"memo[{i}] = {count1} + {count2} -> {memo[i]}")
        return memo[i]
    return rec(N)


print(solve())

Submission status: Wrong Answer

Solution code:
import sys

N, M = [int(_) for _ in input().split()]
A = [int(input()) for i in range(M)]
isBroken = [False] * (N + 1)
for i in A:
    isBroken[i] = True

print("")
sys.exit()

def solve():

    # It's impossible
    temp = A[0]
    for a in A[1:]:
        if a - 1 == temp:
            return 0
        temp = a

    return 1

    # We can
    memo = [0] * (N + 1)

    def rec(i):
        if i == 0:
            return 1
        if i < 0:
            return 0
        if isBroken[i]:
            return 0
        if memo[i] == 0:
            count1 = rec(i - 1) % 1000000007
            count2 = rec(i - 2) % 1000000007
            memo[i] = (count1 + count2) % 1000000007
            # print(f"memo[{i}] = {count1} + {count2} -> {memo[i]}")
        return memo[i]
    return rec(N)


print(solve())

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
A = [int(input()) for i in range(m)]
if m == 0:
  Fib = [1,2]
  for i in range(2,n+1):
    Fib.append(Fib[i-2]+Fib[i-1])
  print(Fib)
  print(Fib[n]%1000000007)
  exit()

B = [A[i+1]- A[i] for i in range(m-1)]
B.insert(0,A[0]+1)
B.append(n+1-A[m-1])

M = max(A)

Fib = [0,1]
for i in range(2,M+10):
  Fib.append(Fib[i-2]+Fib[i-1])

ans = 1
for i in range(len(B)):
  ans = (ans * Fib[B[i]-1])%1000000007
  
print(ans)

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
A = [int(input()) for i in range(m)]
if m == 0:
  Fib = [1,2]
  for i in range(2,n):
    Fib.append(Fib[i-2]+Fib[i-1])
  print(Fib)
  print(Fib[n-1]%1000000007)
  exit()

B = [A[i+1]- A[i] for i in range(m-1)]
B.insert(0,A[0]+1)
B.append(n+1-A[m-1])

M = max(A)

Fib = [0,1]
for i in range(2,M+10):
  Fib.append(Fib[i-2]+Fib[i-1])

ans = 1
for i in range(len(B)):
  ans = (ans * Fib[B[i]-1])%1000000007
  
print(ans)

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
A = [int(input()) for i in range(m)]
if m == 0:
  Fib = [1,2]
  for i in range(2,n):
    Fib.append(Fib[i-2]+Fib[i-1])
  print(Fib)
  print(Fib[n-1])
  exit()

B = [A[i+1]- A[i] for i in range(m-1)]
B.insert(0,A[0]+1)
B.append(n+1-A[m-1])

M = max(A)

Fib = [0,1]
for i in range(2,M+10):
  Fib.append(Fib[i-2]+Fib[i-1])

ans = 1
for i in range(len(B)):
  ans = (ans * Fib[B[i]-1])%1000000007
  
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = (int(x) for x in input().split())
A = [-1]*(N+1)
for i in range(M):
  a = int(input())
  A[a] = 0
A[N] = 1
A[N-1] = 1
for i in reversed(range(N-1)):
#  print("i",i)
  if A[i] == -1:
  	A[i] = A[i+1] + A[i+2]
#  print("A[i]",A[i])
print(A[0]%(1000000007))

Submission status: Wrong Answer

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

MOD = 10**9+7

dp = [0] * (10**5 + 3)
dp[1] = 0
dp[2] = 1
dp[3] = 2
for i in range(3, len(dp)):
    dp[i] = dp[i-1] + dp[i-2] 

res = 1
if M > 0:
    bef = -1
    for a in a_list:
        res *= dp[a-bef]
        res %= MOD
        bef = a
else:
    bef = 0
res *= dp[N-bef+1]
res %= MOD

print(res)

Submission status: Wrong Answer

Solution code:
import math

# N段の階段 M数の壊れてた床
N, M = map(int, input().split())
bar = 1000000007

bf_arr = []
for _ in range(M):
    l = int(input())
    bf_arr.append(l)

bf_arr.append(N + 1)

bf_cnt_arr = []

for i in range(M+1):
    if i == 0:
        bf = bf_arr[i]-1
    else:
        bf = bf_arr[i] - bf_arr[i-1] - 2

    if bf < 0:
        bf_cnt_arr.append(0)
        break
    n1 = bf
    n2 = 0
    bf_cnt = 0
    while n1 >= 0:
        cnt = int(math.factorial(n1 + n2) /
                  (math.factorial(n1) * math.factorial(n2)))
        bf_cnt += cnt
        n1 -= 2
        n2 += 1
    bf_cnt_arr.append(bf_cnt % bar)

final = 1

for i in bf_cnt_arr:
    final *= i

print(final % bar)

Submission status: Wrong Answer

Solution code:
import math

# N段の階段 M数の壊れてた床
N, M = map(int, input().split())
bar = 1000000007

bf_arr = []
for _ in range(M):
    l = int(input())
    bf_arr.append(l)

bf_arr.append(N + 1)

bf_cnt_arr = []

for i in range(M+1):
    if i == 0:
        bf = bf_arr[i]-1
    else:
        bf = bf_arr[i] - bf_arr[i-1] - 2

    if bf < 0:
        bf_cnt_arr.append(0)
        break
    n1 = bf
    n2 = 0
    denominator = math.factorial(bf)
    bf_cnt = 0
    while n1 >= 0:
        cnt = int(math.factorial(n1 + n2) /
                  (math.factorial(n1) * math.factorial(n2)))
        bf_cnt += cnt
        n1 -= 2
        n2 += 1
    bf_cnt_arr.append(bf_cnt)

final = 1

for i in bf_cnt_arr:
    final *= i

print(final % bar)

Submission status: Wrong Answer

Solution code:
import math

# N段の階段 M数の壊れてた床
N, M = map(int, input().split())
bar = 1000000007

bf_arr = []
for _ in range(M):
    l = int(input())
    bf_arr.append(l)

bf_arr.append(N + 1)

print("bf_arr", bf_arr)
bf_cnt_arr = []

for i in range(M+1):
    if i == 0:
        bf = bf_arr[i]-1
    else:
        bf = bf_arr[i] - bf_arr[i-1] - 2

    if bf < 0:
        bf_cnt_arr.append(0)
        break
    n1 = bf
    n2 = 0
    denominator = math.factorial(bf)
    bf_cnt = 0
    while n1 >= 0:
        cnt = int(math.factorial(n1 + n2) /
                  (math.factorial(n1) * math.factorial(n2)))
        bf_cnt += cnt
        n1 -= 2
        n2 += 1
    bf_cnt_arr.append(bf_cnt)

print(bf_cnt_arr)

final = 1

for i in bf_cnt_arr:
    final *= i

print(final % bar)

Submission status: Wrong Answer

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

def basic_step_ptn_nums(x): # 'x'段までのパターン総数
    if x == 1:
        print(1)
    else:
        dp = [0] * (x+1) # DP枠_including step'0'
        dp[:2] = 1, 1 # 固定部分
        for i in range(2, x+1):
            dp[i] = dp[i-1] + dp[i-2] # -1段目と-2段目の合計
        print(dp[-1])

basic_step_ptn_nums(8)

Submission status: Wrong Answer

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

def main():
    #print(arg)
    #input = arg.split("\n")
    N,M = list(map(int, input().split(" ")))
    #print(input)
    #return
    A = [int(input()) for i in range(M)]
    #print(N)
    #print(M)

    #return

    if len(A) > 1:
        for i in range(1,M):
            if A[i] - A[i-1] == 1:
                print(0)
                return


    dp = [0] * (N-M+1)
    dp[0] = 1

    for i in range(1,N-M+1):
        dp1 = dp[i-1]
        dp2 = 0
        if i >= 2:
            dp2 = (dp[i-2]*2)
        
        #print("i={0}: dp1={1}, dp2={2}".format(i, dp1, dp2))
        dp[i] = max(dp1, dp2)
        
    print(dp[N-M])

#main("6 1\n3")
main()

Submission status: Wrong Answer

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

def main():
    #print(arg)
    #input = arg.split("\n")
    N,M = list(map(int, input().split(" ")))
    #print(input)
    #return
    A = [int(input()) for i in range(M)]
    #print(N)
    #print(M)
    print(A)

    #return

    if len(A) > 1:
        for i in range(1,M):
            if A[i] - A[i-1] == 1:
                print(0)
                return


    dp = [0] * (N-M+1)
    dp[0] = 1

    for i in range(1,N-M+1):
        dp1 = dp[i-1]
        dp2 = 0
        if i >= 2:
            dp2 = (dp[i-2]*2)
        
        print("i={0}: dp1={1}, dp2={2}".format(i, dp1, dp2))
        dp[i] = max(dp1, dp2)
        
    print(dp[N-M])

#main("6 1\n3")
main()

Submission status: Wrong Answer

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

def main():
    #print(arg)
    #input = arg.split("\n")
    N,M = list(map(int, input().split(" ")))
    #print(input)
    #return
    A = [int(input()) for i in range(M)]
    #print(N)
    #print(M)
    print(A)

    #return

    if len(A) > 1:
        for i in range(1,M):
            if A[i] - A[i-1] == 1:
                print(0)
                return


    dp = [0] * (N-M+1)
    dp[0] = 1

    for i in range(1,N-M+1):
        dp1 = dp[i-1]%1000000007
        dp2 = 0
        if i >= 2:
            dp2 = (dp[i-2]*2)%1000000007
        
        print("i={0}: dp1={1}, dp2={2}".format(i, dp1, dp2))
        dp[i] = max(dp1, dp2)
        
    print(dp[N-M])

#main("6 1\n3")
main()

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
MOD = 10**9+7
dp = [0] * (N+1)
dp[1] = 1
for _ in range(M):
  dp[int(input())] = -1
if N < 2: 
  print(dp[N])
  exit()
dp[2] = 1
for i in range(N+1):
  if dp[i] == -1: continue
  if i-1>=0 and dp[i-1] != -1:
    dp[i] += dp[i-1]
  if i-2>=0 and dp[i-2] != -1:
    dp[i] += dp[i-2]
  dp[i] %= MOD

print(dp[N])

Submission status: Wrong Answer

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