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:
n,m=map(int,input().split())

if n==1:
  print(1)
  exit()
if n==2:
  if m==0:
    print(2)
  else:
    print(1)

fib=[0 for i in range(n+2)]
fib[1]=1
for i in range(2,n+2):
  fib[i] = (fib[i-1]+fib[i-2]) % 1000000007

com=1
anow=-1
for i in range(m):
  a=int(input())
  if a-anow==1:
    print(0)
    exit()
  com = (com * fib[a-anow-1]) % 1000000007
  anow=a

com = (com * fib[n-anow]) % 1000000007
print(com)

Submission status: Wrong Answer

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

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

for i in range(2,N+1):
    #n-1段目が安全なら
    if a[i-1]==0:
        dp[i]+=dp[i-1]
    #n-2段目が安全なら
    if a[i-2]==0:
        dp[i]+=dp[i-2]
    dp[i] = dp[i]%MOD
print(dp[N])

Submission status: Wrong Answer

Solution code:
import sys
n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
d = {i: 0 for i in range(n + 1)}
if n == 1:
    print(1)
    sys.exit()
elif n == 2:
    print(2)
    sys.exit()
d[0] = 1
d[1] = 1
for i in range(2, n + 1):
    if i  in a:
        d[i] = 0
    elif i - 1 in a:
        if i - 2 in a:
            print(0)
            sys.exit()
        else:
            d[i] = d[i - 2]
    elif i - 2 in a:
        d[i] = d[i - 1]
    else:
        d[i] = d[i - 1] + d[i - 2]
d[n] %= 1000000007
print(d[n])

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
flag=list(1 for _ in range(n+1))
count=list(0 for _ in range(n+1))
ans=0
for i in range(m):
    x=int(input())
    flag[x]=0
print(flag)

if n==1:
    ans=1
else:
    if flag[1]==1:
        count[1]=1
    if flag[2]==1:
        count[2]=count[1]+1
    for i in range(3,n+1):
        if flag[i]==1:
            count[i]=count[i-1]+count[i-2]
            
    ans=count[n]
print(ans%(10**9+7))

Submission status: Wrong Answer

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

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

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

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

print(dp)

Submission status: Wrong Answer

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

MOD   = 10**9+7 
dp    = [0]*(n+1)
dp[0] = 1

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

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

  if i==1:
    dp[1] == dp[0]
    continue
  
  dp[i] = (dp[i-2] + dp[i-1]) % MOD

print(dp[n])

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
p = 1000000007
aaa = [0] * (n + 1)
f = [0] * (n + 1)
for _ in range(m):
    x = int(input())
    aaa[x] = 1
f[0] = 1
f[1] = 1
for i in range(1, n + 1):
    f[i] = (f[i - 1] + f[i - 2]) % p
    if aaa[i] == 1:
        f[i] = 0
print(f[n])

Submission status: Wrong Answer

Solution code:
import sys
N, M = map(int, input().split())
ok = [True] * (N + 1)
for _ in range(M):
    a = int(sys.stdin.readline())
    ok[a] = False
ans = 0
if N == 1:
    ans = 1
elif N == 2:
    ans = 2 if ok[1] else 1
else:
    counts = [0] * (N + 1)
    if ok[1]:
        counts[1] = 1
    if ok[2]:
        counts[2] = 2
    for s in range(3, N + 1):
        if ok[s]:
            count = counts[s-1] + counts[s-2]
            count %= 1000000007
            counts[s] = count
        else:
            counts[s] = 0
    ans = counts[N]
print(ans)

Submission status: Wrong Answer

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

fact=[0,1]
fact_inv=[0]*(n+1)
for i in range(2,n+1):
  fact.append(fact[-1]*i % MOD)

fact_inv[n] = pow(fact[n],MOD-2,MOD)
for i in range(n-1,-1,-1):
  fact_inv[i] = fact_inv[i+1]*(i+1)%MOD

def comb(n,r):
  return fact[n]*fact_inv[r]*fact_inv[n-r]%MOD

def sigmaComb(dis):
  ans=0
  if dis == 1 or dis == 0:
    return 1
  end=dis//2 if dis%2 != 0 else dis//2+1
  for i in range(end):
    t=comb(dis-i,i)
    ans+=t
  return ans

hole=[0]
ans=1
for i in range(m):
  t = int(input())
  availLeft=hole[-1]
  availRight=t-1
  dis=availRight-availLeft
  if dis <0:
    ans=0
    break

  ans=ans*sigmaComb(dis)%MOD
  # print("dis=",dis,t,ans)
  hole.append(t+1)
else:
  availLeft=hole[-1]
  availRight=n
  dis=availRight-availLeft
  #print("dis=",dis,hole[-1],ans)
  ans=ans*sigmaComb(dis)%MOD

print(ans%MOD)

Submission status: Wrong Answer

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

fact=[0,1]
fact_inv=[0]*(n+1)
for i in range(2,n+1):
  fact.append(fact[-1]*i % MOD)

fact_inv[n] = pow(fact[n],MOD-2,MOD)
for i in range(n-1,-1,-1):
  fact_inv[i] = fact_inv[i+1]*(i+1)%MOD

def comb(n,r):
  return fact[n]*fact_inv[r]*fact_inv[n-r]%MOD

def sigmaComb(dis):
  ans=0
  if dis == 1:
    return 1
  end=dis//2 if dis%2 != 0 else dis//2+1
  for i in range(end):
    t=comb(dis-i,i)
    ans+=t
  return ans

hole=[0]
ans=1
for i in range(m):
  t = int(input())
  if t == hole[-1]+1:
    if hole[-1] == 0:
      hole.append(t)
      continue
    else:
      ans=0
      break
  if hole[-1] == 0:
    dis=t-hole[-1]-1
  else:
    dis=t-hole[-1]-2

  ans=ans*sigmaComb(dis)%MOD
  #print("dis=",dis,t,ans)
  hole.append(t)
else:
  dis=n-hole[-1]-2+1
  #print("dis=",dis,hole[-1],ans)
  ans=ans*sigmaComb(dis)%MOD

print(ans%MOD)

Submission status: Wrong Answer

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

fact=[0,1]
fact_inv=[0]*(n+1)
for i in range(2,n+1):
  fact.append(fact[-1]*i % MOD)

fact_inv[n] = pow(fact[n],MOD-2,MOD)
for i in range(n-1,-1,-1):
  fact_inv[i] = fact_inv[i+1]*(i+1)%MOD

def comb(n,r):
  return fact[n]*fact_inv[r]*fact_inv[n-r]%MOD

def sigmaComb(dis):
  ans=0
  end=dis//2 if dis%2 != 0 else dis//2+1
  for i in range(end):
    t=comb(dis-i,i)
    ans+=t
  return ans

#print(fact)
#print(fact_inv)
hole=[0]
ans=1
for i in range(m):
  t = int(input())
  if t == hole[-1]+1:
    if hole[-1] == 0:
      hole.append(t)
      continue
    else:
      ans=0
      break
  dis=t-hole[-1]-2
  ans=ans*sigmaComb(dis)%MOD
  hole.append(t)
else:
  dis=n-hole[-1]-2+1
  ans=ans*sigmaComb(dis)%MOD

print(ans%MOD)

Submission status: Wrong Answer

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

mod = pow(10, 9)+7
point = [0]*(n+1)
point[0] = 1
j = 0
if 1 in a:
    point[1] = 0
    if m > 2:
        j += 1
else:
    point[1] = 1

if m == 0:
    a = [0]

for i in range(2, n+1):
    print(i)
    if i == a[j]:
        if j < m-1:
            j += 1
    else:
        point[i] = point[i-1]+point[i-2]
        point[i] %= mod

print(point[-1] % mod)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

##### 割り算の切り上げ #####
# tmp = -(-4 // 3)

##### dict の for文 #####
# for k, v in d.items():
#     print(k, v)

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N,M = inputMap()
	ans = [0 for i in range(N+1)]
	ans[0] = 1
	a = []
	for i in range(M):
		tmp = inputInt()
		a.append(tmp)

	for i in range(N+1):
		if i+1 <= N:
			ans[i+1] = (ans[i+1] + ans[i]) % mod
		if i+2 <= N:
			ans[i+2] = (ans[i+2] + ans[i]) % mod

	print(ans[N])


#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)


class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# dfs のサンプル
def dfs(graph,parent,counter,edge):
    stk = []
    stk.append(edge)
    while len(stk) > 0:
        p = stk.pop()
        for e in graph[p]:
            if parent[p] == e:
                continue
            else:
                parent[e] = p
                counter[e] += counter[p]
                stk.append(e)

if __name__ == "__main__":
	main()

Submission status: Wrong Answer

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

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

print(dp[n]%1000000007)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]

mod = 10**9+7

dp = [0] * -~n
dp[0] = 1
dp[1] = 1 not in a

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

print(dp[n])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
f = lambda j: j not in a

mod = 10**9+7

dp = [0] * -~n
dp[0] = 1
dp[1] = f(1)

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

print(dp[n])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
f = lambda j: j not in a

mod = 10**9+7

dp = [0] * -~n
dp[0] = 1
dp[1] = f(1)

for i in range(2, -~n):
    dp[i] += (dp[i - 1] + dp[i - 2]) * f(i) % mod

print(dp[n])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
n, m, *a = map(int, open(0).read().split())
f = lambda j: j not in a

mod = 10**9+7

dp = [0] * -~n
dp[0] = 1
dp[1] = f(1)

for i in range(2, -~n):
    dp[i] += (dp[i - 1] + dp[i - 2]) * f(i) % mod

print(dp[n])

Submission status: Wrong Answer

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

stair = [0]*n
s = 1
s_tmp = 2
for i in range(n):
    stair[i] = s
    s_tmp_tmp = s_tmp
    s_tmp = s_tmp+s
    s= s_tmp_tmp
    
#print(stair)

ans = 1
muri = 0
tmp = -1
for i in range(m):
    
    a = int(input())
    
    # 前の欠陥から連続の場合fail
    if a-1 == tmp:
        muri = 1
        break
    
    # 1段目スキップ
    elif a == 1:
        tmp = a
        continue
    # そうでないとき、まえの欠陥から正常な段数だけパターンがある
    else:
        ans *= stair[a-tmp-3]
        ans %= (10**9)+7
        #else:
        #    ans *= stair[a-tmp-3]
        #    ans %= (10**9)+7

    #print(ans)
    # 1段前を記録
    tmp = a

# 最後の階段
if n-tmp >= 2:
    ans *= stair[n-tmp-2]
    ans %= (10**9)+7

#print('last')
#print(ans)

if muri == 1:
    print(0)
else:
    if m == 0:
        print(stair[n-1]%(10**9+7))
    else:
        print(ans)

Submission status: Wrong Answer

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

stair = [0]*n
s = 1
s_tmp = 2
for i in range(n):
    stair[i] = s
    s_tmp_tmp = s_tmp
    s_tmp = s_tmp+s
    s= s_tmp_tmp
    
#print(stair)

ans = 1
muri = 0
tmp = -1
for i in range(m):
    
    a = int(input())
    
    # 前の欠陥から連続の場合fail
    if a-1 == tmp:
        muri = 1
        break
    
    # 1段目スキップ
    elif a == 1:
        tmp = a
        continue
    # そうでないとき、まえの欠陥から正常な段数だけパターンがある
    else:
        ans *= stair[a-tmp-3]
        ans %= (10**9)+7

    # 1段前を記録
    tmp = a

# 最後の階段
ans *= stair[n-tmp-2]

if muri == 1:
    print(0)
else:
    if m == 0:
        print(stair[n-1]%(10**9+7))
    else:
        print(ans%(10**9+7))

Submission status: Wrong Answer

Solution code:
from collections import deque

n,m=map(int,input().split())
step=list(range(2,n+1))
broken=[]
for i in range(m):
    broken+=[int(input())]
mod=10**9+7
dp=[0]*(n+1)
dp[0]=1
if m==0:
    dp[1]=1
elif not broken[0]==1:
    dp[1]=1
b=deque(broken)
if len(broken) != 0:
    bad_one = b.popleft()
    if bad_one==1 and len(b) == 1:
        bad_one=b.popleft()
else:
    bad_one = -1
for i in step:
    if i != bad_one:
        dp[i]=(dp[i-1]+dp[i-2])%mod
    elif i == bad_one and len(b) != 0:
        bad_one = b.popleft()
print(dp[n])

Submission status: Wrong Answer

Solution code:
from collections import deque

n,m = map(int,input().split())
step = list(range(2,n+1))
broken = []
for i in range(m):
    broken += [int(input())]

mod = 10**9+7
dp = [0]*(n+1)
dp[0] = 1

if m == 0:
    dp[1] = 1
    for i in step:
        dp[i] = dp[i-1] + dp[i-2]
else:
    if not broken[0] == 1:
        dp[1] = 1
    b = deque(broken)
    if len(broken) != 0:
        bad_one = b.popleft()
    for i in step:
        if i != bad_one:
            dp[i] = (dp[i-1]+dp[i-2]) % mod
        elif i == bad_one and len(b) != 0:
            bad_one = b.popleft()
print(dp[n] % mod)

Submission status: Wrong Answer

Solution code:
from collections import deque

n,m=map(int,input().split())
step=list(range(2,n+1))
broken=[]
for i in range(m):
    broken+=[int(input())]
mod=10**9+7
dp=[0]*(n+1)
dp[0]=1
if m==0:
    dp[1]=1
elif not broken[0]==1:
    dp[1]=1
b=deque(broken)
if len(broken) != 0:
    bad_one = b.popleft()
else:
    bad_one = -1
for i in step:
    if i != bad_one:
        dp[i]=(dp[i-1]+dp[i-2])%mod
    elif i == bad_one and len(b) != 0:
        bad_one = b.popleft()
print(dp[n])

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
step=list(range(2,n+1))
broken=[]
for i in range(m):
    broken+=[int(input())]
mod=10**9+7
dp=[0]*(n+1)
dp[0]=1
if len(broken)>0 and not broken[0]==1:
    dp[1]=1
for i in step:
    if not i in broken:
        dp[i]=(dp[i-1]+dp[i-2])%mod
print(dp[n])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

# 0段目
dp=[1] * (n +1)
broken=[0] * (n +1)

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

# 最後の２段は１個定
for i in range(n-2,-1,-1):
    if broken[i]:
        dp[i]=0
        continue

    dp[i] = (dp[i+1] + dp[i+2]) %p

print(dp[0])

Submission status: Wrong Answer

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

import sys
# import math
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product                # product(iter, repeat=n)
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4


def main():
    mod = 1000000007                  # 10^9+7
    inf = float('inf')
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():  return int(input())
    def mi():  return map(int, input().split())
    def mi_0(): return map(lambda x: int(x)-1, input().split())
    def lmi(): return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():  return list(input())
    
    
    n, m = mi()
    L = [ii() for _ in range(m)]

    FIBO = [0] * (n+1)    # FIBO[i] = k 段目から k+i 段目に行く場合の数
    for i in range(n+1):
        if i == 0 or i == 1:
            FIBO[i] = 1
        else:
            FIBO[i] = FIBO[i-1] + FIBO[i-2]

    prev = 0
    ans = 1
    for broken_step in L:
        if prev == broken_step:
            print(0)
            exit()
        ans *= FIBO[broken_step - 1 - prev]
        prev = broken_step + 1
    ans *= FIBO[n - prev]
    print(ans)





if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n,m=list(map(int,input().split(" ")))
a=[]
dp=[float("inf") for i in range(n+1)]
for i in range(m):
  a=int(input())
  dp[a]=0
dp[0]=1
if dp[1] != 0:
  dp[1]=1
for i in range(2,n+1):
  if dp[i]!=0:
    dp[i]=dp[i-1]+dp[i-2]
print(dp[n])

Submission status: Wrong Answer

Solution code:
n,m=list(map(int,input().split(" ")))
a=[]
for i in range(m):
  a.append(int(input()))
dp=[float("inf") for i in range(n+1)]
dp[0]=1
if 1 in a:
  dp[1]=0
else:
  dp[1]=1
for i in range(2,n+1):
  if i in a:
    dp[i]=0
  else:
    dp[i]=dp[i-1]+dp[i-2]
print(dp[n])

Submission status: Wrong Answer

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

arr = [-1]+arr+[N+1]
#from math import factorial
from functools import reduce
def combinations_count(n, r):
    mul = lambda a,b: a*b
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

count = 0
for i in range(0,len(arr)-1):
    start,end = arr[i],arr[i+1]
    span = end - start - 2 # the first step is taken by a certain step (with no choice)
    if span < 0:
        count = 0 # impossible
        break 
    nptn = int(span/2)
    regional_count = 0

    for k in range(0,nptn+1):
        #regional_count += factorial(span-k) // factorial(k) // factorial(span-2*k)
        mul = lambda a,b: a*b
        regional_count += combinations_count(span,k) // reduce(mul, range(1,span-2*k+1),1)
    
    if count == 0:
        count += regional_count
    else:
        count *= regional_count
print(count % 1000000007)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
a = [0]
lim = int((1e+9)+7)
fibo = [1,1]
def f(num):
    if len(fibo) < num+1:
        while(len(fibo) <= num):
            fibo.append((fibo[-1]+fibo[-2])%lim)
    return fibo[num]

for _ in range(m):
    a.append(int(input()))
for i in range(1,len(a)-1):
    if a[i+1]-a[i] == 1:
        print(0)
        exit()

a.append(n)

d = []
for i in range(len(a)-1):
    d.append((a[i+1]-a[i])-1)
ansf = 1
for i in range(len(d)):
    if i == 0:
        ansf = (ansf * f(d[i]))%lim
    elif i == len(d)-1:
        ansf = (ansf * f(d[i]))%lim
    else:
        ansf = (ansf * f(d[i]-1))%lim
print(ansf)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
a = [0]
lim = int((1e+9)+7)
def combination(n,k):
    ans = 1
    for i in range(k):
        ans = (ans*(n-i))
        ans = (ans/(i+1))
    return int(ans)

def stair(num):
    ans = 0
    for i in range(num):
        ans = (ans+combination(num-i,i))%lim
    return int(ans)

for _ in range(m):
    a.append(int(input()))
a.append(n+1)
d = []
for i in range(m+1):
    d.append(a[i+1]-a[i])
d[0] += 1
for i in range(len(d)):
    if not(i == 0 or i == len(d)-1):
        if d[i] == 1:
            print(0)
            exit()
ansf = 1
for i in range(1,len(d)):
    if d[i] != 1:
        ansf = (ansf * stair(d[i]-2))%lim
print(ansf%lim)

Submission status: Wrong Answer

Solution code:
def main():
    n,m=map(int,input().split())
    res=[1,1]
    flg=0
    mod=10**9+7
    a=n+1
    gap=[]
    if m!=0:
        a=int(input())
        gap.append(a-1)
        for i in range(m-1):
            b=int(input())
            dif=b-a-1
            if dif==0:
                flg=1
                break
            else:
                gap.append(dif-1)
                a=b
        gap.append(n-a-1)
    else:
        gap.append(n+1)
    if flg==1:
        print(0)
    else:
        for i in range(2,max(gap)+1):
            res.append((res[i-1]+res[i-2])%mod)
        ans=1
        for i in gap:
            ans=(ans*res[i])%mod
        print(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)]
check=[0 for i in range(n+1)]
for i in range(m):
    check[a[i]]=1
MOD= 1000000007

c=[0]*(n+1)
c[0]=1
if 1 in a:
    c[1]=0
else:
    c[1]=1

for i in range(2,n+1):
    if check[i]!=0:
        print(i)
        continue
    else:
        c[i] = (c[i - 1] + c[i - 2]) % MOD

print(c[n])

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()

def Fibo(n):
	S = [1, 1]
	if n == 1:
		return 1
	for i in range(1, n):
		S.append(S[i] + S[i-1])

	return S[n]

if M == 0:
	print(Fibo(N))
	exit()

a = [INT()]
for i in range(1, M):
	a.append(INT())
	if a[i] == a[i-1]+1:
		print(0)
		exit()
m = [a[0]-1]
for i in range(1, M):
	m.append(a[i]-a[i-1]-2)
m.append(N-a[M-1]-1)



ans = 1
for n in m:
	ans *= Fibo(n)

print(ans%mod)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
if N==1:
  print(N)
  exit()
dp=[-1]*N
dp[-1]=1
dp+=[1]
mod=10**9+7
for i in range(M):
  a=int(input())
  dp[a]=0
i=N-2
while i>=0:
  if dp[i]==-1:
    dp[i]=dp[i+1]+dp[i+2]
  i-=1
print(dp[0])

Submission status: Wrong Answer

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

a = -2
for _ in range(M):
    new = int(input())
    if a+1 == new:
        print(0)
        exit()
    else:
        damaged.add(new-2)
        a = new
# これで連続ダメージの場合は以下の処理で存在しなくなった

a = 1
b = 2
i = 3
while i <= N-2:
    if i in damaged:
        i += 2
        a = 0
    else:
        tmp = b
        b = a + b
        a = tmp
        i += 1

print(b % 1000000007)

Submission status: Wrong Answer

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

a = -2
for _ in range(M):
    new = int(input())
    if a+1 == new:
        print(0)
        exit()
    else:
        damaged.add(new)
        a = new
# これで連続ダメージの場合は以下の処理で存在しなくなった

a = 1
b = 2
i = 3
while i <= N-2:
    if i in damaged:
        i += 2
        a = 0
    else:
        tmp = b
        b = a + b
        a = tmp
        i += 1

print(b % (1000000007))

Submission status: Wrong Answer

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

a = -2
for _ in range(M):
    new = int(input())
    if a+1 == new:
        print(0)
        exit()
    else:
        damaged.add(new)
        a = new
# これで連続ダメージの場合は以下の処理で存在しなくなった

a = 1
b = 2
i = 3
while i <= N-1:
    if i in damaged:
        i += 2
        a = 0
    else:
        tmp = b
        b = a + b
        a = tmp
        i += 1

print(b % (1000000007))

Submission status: Wrong Answer

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

ans=0
MOD= 1000000007

c=[0]*(n+1)
c[0]=1
if 1 in a:
    c[1]=0
else:
    c[1]=1

for i in range(2,n+1):
    c[i]+=(c[i-1]+c[i-2])%MOD
    if i in a:
        continue

print(c[n]%MOD)

Submission status: Wrong Answer

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

mod=10e9+7

inf=float('inf')

dp=[inf]*(n+1)
dp[0]=1
dp[1]=1

for i in a:
    dp[i]=0

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

print(int(dp[-1]))

Submission status: Wrong Answer

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

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

if 1 in l:
    dp[1] = 0

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

Submission status: Wrong Answer

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

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

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

print(dp[N])

Submission status: Wrong Answer

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

n, m, *broken = map(int, sys.stdin.read().split())
broken = set(broken)

def main():
    ways = [0] * (n + 1)
    ways[0] = 1
    ways[1] = not 1 in broken
    for i in range(2, n + 1):
        ways[i] = (not i in broken) * (ways[i-1] + ways[i-2]) % MOD
    print(ways[n])

if __name__ ==  '__main__':
    main()

Submission status: Wrong Answer

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

a = [int(input())-1 for _ in range(M)]
T = 1
for i in range(M-1):
    if a[i]+1==a[i+1]:
        T = 0
        break
if T == 0:
    print(0)
else:
    if N==1:
        print(0)
    else:
        L = [0 for _ in range(N)]
        for i in range(M):
            L[a[i]] = -1
        if L[0] == -1:
            L[1] = 1 
        else:
            L[0] = 1
            if L[1] != -1:
                L[1] = 2
        for i in range(2,N):
            if L[i] != -1:
                if L[i-2] == -1:
                    L[i] = L[i-1]%1000000007
                elif L[i-1] == -1:
                    L[i] = L[i-2]%1000000007
                else:
                    L[i] = (L[i-1]+L[i-2])%1000000007
        print(L)

Submission status: Wrong Answer

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

large = 10**9 +7
count = [0]*(n+1)
itr = 0
count[0] = 1

if m >0 and a[0] != 1 :
    count[1] = 1
else:
    count[1] = 0
    itr = 1
if n >=2:
    for i in range(2,n+1):
        if m > 0 and itr<len(a) and a[itr] == i:
            itr +=1
            continue
        else:
            count[i] = (count[i-1] + count[i-2])%large

print(count[n])

Submission status: Wrong Answer

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

large = 10**9 +7
count = [0]*(n+1)
itr = 0
count[0] = 1

if m >0 and a[0] != 1 :
    count[1] = 1
else:
    count[1] = 0
    itr = 1

for i in range(2,n+1):
    if m > 0 and itr<len(a) and a[itr] == i:
        itr +=1
        continue
    else:
        count[i] = (count[i-1] + count[i-2])%large

print(count[n])

Submission status: Wrong Answer

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

  

dp=[0]*(N+3)
dp[1]=1
dp[2]=1
for i in range(3,N+3):
  dp[i]=(dp[i-1]+dp[i-2])%mod
if len(hole)==1:
  print(dp[N+1])
  
#print(dp)
#print(hole)
ans=1
for h in hole:
  ans*=dp[h]
  ans%=mod
  
print(ans)