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:
import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''

N, M = map(int, input().split())
mod = 10 ** 9 + 7
a = [0] * M
dp = [0] * (N + 1)
dp[0] = 1
dp[1] = 1

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

for i in range(M):
	next = a[i]
	for j in range(now + 1, next + 1):
		if j == a[i]:
			dp[a[i]] = 0
		else:
			dp[j] = (dp[j - 1] + dp[j - 2]) % mod
	
	now = next

next = N
for j in range(now + 1, next + 1):
		dp[j] = (dp[j - 1] + dp[j - 2]) % mod
print(dp[N])

Submission status: Wrong Answer

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

dp = [1] * (n+1)
for j in range(n+1):
    if j in a:
        dp[j] = dp[j-1]
    elif j-1 in a or j-2 in a:
        dp[j] = dp[j-1]
    elif j > 1:
        dp[j] = dp[j-1] + dp[j-2]

print(dp[n])

Submission status: Wrong Answer

Solution code:
def fb(num):
    A, B = 1, 1
    for _ in range(num):
        A, B = A + B, A
    return B

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

p=0
ans=1
for i in range(M):
  ans*=fb(a[i]-p-1)
  p=a[i]
ans*=fb(N-p-1)
print(ans%1000000007)

Submission status: Wrong Answer

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

mod = 10 ** 9 + 7

dp = [0] * 100010

j = 0
dp[0] = 1
if M > 0:
    if a[0] == 1:
        dp[1] = 0
        j += 1
    else:
        dp[1] = 1

a += [-1]
for i in range(2, N+1):
    if M > 0:
        if i == a[j]:
            dp[i] = 0
            j += 1
            continue
    dp[i] = dp[i-1] + dp[i-2]
    dp[i] %= mod

print(dp[N] % mod)

Submission status: Wrong Answer

Solution code:
import math
import sys
import itertools

N, M = map(int, sys.stdin.readline().split())

mod_num = 1000000007

if M == 0:
    roop_time = math.floor(N/2)
    var_sum = 0
    for i in range(1, roop_time + 1):
        var_sum += len(list(itertools.combinations(range(N - i), i)))
    ans = var_sum + 1
    print(ans)
    sys.exit()

a = []
for i in range(M):
    a.append(int(sys.stdin.readline()))

for i in range(M):
    if i == 0:
        continue
    if (a[i] - a[i-1]) == 1:
        ans = 0
        print(ans)
        sys.exit()

section_N = []
temp = 0
for i in range(M):
    section_N.append(a[i] - temp - 1)
    temp = a[i]
section_N.append(N - temp - 1)


combinations = []
for i in range(len(section_N)):
    if section_N[i] == 1 or section_N[i] == 0:
        continue
    roop_time = math.floor(section_N[i]/2)
    var_sum = 0
    for j in range(1, roop_time + 1):
        var_sum += len(list(itertools.combinations(range(section_N[i] - j), j)))
    combinations.append(var_sum + 1)

ans = 1
for i in range(len(combinations)):
    ans = (ans * combinations[i])%mod_num
print(ans)

Submission status: Wrong Answer

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

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

    

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

print(dp[n])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
MOD = 1000000007
N, M = map(int, input().split())
a = []
for _ in range(M):
    a.append(int(input()))


def getPatternNum(num):
    pattern = [0] * (num + 2)
    pattern[0] = 0
    for i in range(1, num + 2):
        if i == 0 or i == 1:
            pattern[i] = 1
            continue
        pattern[i] = (pattern[i - 2] + pattern[i - 1]) % MOD
    return pattern

def solve():
    # 階段の連続してる数のリスト
    stepsList = [0] * (M + 1)
    maxSteps = 0
    if M > 0:
        stepsList[0] = a[0]
        for j in range(1, M):
            stepsList[j] = a[j] - a[j - 1] - 1
            if stepsList[j] == 0:
                return 0
        stepsList[M] = N - a[M - 1]
    else:
        stepsList = [N]
    pattern = getPatternNum(max(stepsList) + 1)
    # こわれてるところ以外のパターンを掛ける
    # print("#", pattern)
    for k in range(len(stepsList)):
        if k == 0:
            total = pattern[stepsList[k]]
        else:
            total = (total * pattern[stepsList[k]]) % MOD
        # print("##", k, stepsList[k], pattern[stepsList[k]], total)

    return total


ans = solve()
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
ana = []
for _ in range(M):
  ana.append(input())
ans = []
ans.append(1)#一段目まで登る方法は一通り
ans.append(2)#二段目まで登る方法は二通り
 
for i in range(2,N):
    tmp = i+1
    tmp2 = str(tmp)
    if tmp2 in ana:
        ans.append(0)
    else:
        ans.append((ans[i-1] + ans[i-2]) % 1000000007)
 
print(ans[N-1])

Submission status: Wrong Answer

Solution code:
import math

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

if M == 0:
    a = [-1 , N+1]
else :
    a = [-1] * (M+2)

    for i in range(1,M+1) :
        a[i] = int(input())

flag = True # 可能かどうか
for i in range(0,M+1) :
    if a[i] + 1 == a[i+1] :
        flag = False
        break

fib = [1] * (N+1) # フィボナッチ数列
for i in range(2,N) :
    fib[i] = fib[i-1] + fib[i-2]

if flag :
    a[M+1] = N + 1

    ans = 1

    for i in range(M+1) :
        length = a[i+1] - a[i] - 2 # 上がる長さ
        ans *= fib[length]

    print(ans % 1000000007)
else :
    print(0)

Submission status: Wrong Answer

Solution code:
def Fib(n):
    a, b = 0, 1
    if n == 1:
        return a
    elif n == 2:
        return b
    else:
        for i in range(n-2):
            a, b = b, a + b
        return b

a,b=[int(i) for i in input().split()]
ll=[]
y=-1
s=0
for i in range(b):
    x=int(input())
    ll.append(x)
    if x-y==1:
        s=1
        break
    y=x
ll.append(a+1)
l2=[]
if s==1:
    print(0)
elif b==0:
    print(Fib(a+2))
else:
    x=-1
    for i in ll:
        l2.append(Fib(i-x))
        x=i
    ans=1
    for i in l2:
        if i==0:
            i=1
        ans*=i
    print(ans%1000000007)

Submission status: Wrong Answer

Solution code:
def Fib(n):
    a, b = 1, 1
    if n == 1:
        return a
    elif n == 2:
        return b
    else:
        for i in range(n-2):
            a, b = b, a + b
        return b

a,b=[int(i) for i in input().split()]
ll=[]
y=-1
s=0
for i in range(b):
    x=int(input())
    ll.append(x)
    if x-y==1:
        s=1
        break
    y=x
ll.append(a+1)
l2=[]
if s==1:
    print(0)
elif b==0:
    print(Fib(a+1))
else:
    x=-1
    for i in ll:
        l2.append(Fib(i-x))
        x=i
    ans=1
    for i in l2:
        if i==0:
            i=1
        ans*=i
    print(ans%1000000007)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
o = [int(input()) for _ in range(m)]
print(o)
mod = (10**9)+7
dp = [1]+[0]*(n)

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

Submission status: Wrong Answer

Solution code:
def Fib(n):
    a, b = 0, 1
    if n == 1:
        return a
    elif n == 2:
        return b
    else:
        for i in range(n-2):
            a, b = b, a + b
        return b
a,b=input().split()
a=int(a)
b=int(b)
ll=[]
y=-1
s=0
for i in range(b):
    x=input()
    x=int(x)
    ll.append(x)
    if x-y==1:
        s=1
        break
    y=x
ll.append(a+1)
l2=[]
if s==1:
    print(0)
elif b==0:
    print(Fib(a+2))
else:
    x=-1
    for i in ll:
        l2.append(Fib(i-x))
        x=i
    ans=1
    for i in l2:
        if i==0:
            i=1
        ans*=i
    print(ans%1000000007)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
o = [int(input()) for _ in range(m)]
print(o)
mod = (10**9)+7
dp = [1]+[0]*(n)
flag1 = False

for i in range(n):
  if i+1 not in o:
    dp[i+1] = dp[i] + dp[i-1]
  else:
    dp[i+1] = 0
  #print(i,dp)
#print(dp)
print(dp[-1]%mod)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
a = set([int(input()) for _ in range(m)])
dp = [0]*(n+1)
dp[1] = int(1 not in a)
for i in range(2,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())

def get_fib(x):
    assert x>1
    fib = [1,1]
    for i in range(x-2):
        last2 = fib[-2:]
        fib.append(sum(last2))
    return fib

fib = get_fib(N+1)

a = 1
mod = 10 ** 9 + 7
result = 1

for m in range(M):
    b = int(input())
    if b == 1:
        a = b + 1
        continue
    elif b == a:
        result = 0
        break

    result *= fib[b-a]
    result = result % mod
    a = b + 1

result *= fib[(N)-a]
result = result % mod

print(result)

Submission status: Wrong Answer

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

mod = 10**9 + 7

li = [0]*(N+1)
li[0] = 1
li[1] = 1
for i in range(M):
    a = int(input())
    li[a] = -1

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

print(li[-1])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000)

def intinput(): return map(int,sys.stdin.readline().split())


n, m = intinput()
a = {int(sys.stdin.readline()) for _ in range(m)}
print(a)
memo = [0 for x in range(n + 4)]
memo[0] = 1
mod = 10 ** 9 + 7
for i in range(n):
    if i + 1 not in a:
        memo[i + 1] = (memo[i + 1] + memo[i]) % mod
    if i + 2 not in a:
        memo[i + 2] = (memo[i + 2] + memo[i]) % mod

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import os
import time
import re
import math


def main():
    N,M=map(int,input().split())
    A=[int(input()) for  a in range(M)] #a (1段~N-1段)
    start=time.time();#
    memo=[0]*(N+1)
    memo[0]=1
    ban=[False]*(N+1)
    for a in A:
        ban[a]=True
    mod=1000000007
    print(ban)
    for a in range(1,N+1):
        if ban[a]:
            memo[a]=0
        else:
            if a>1:
                memo[a]=(memo[a-1]+memo[a-2])%mod
            else:
                memo[a]=1



    print(memo[-1]%mod)
    #print("{}ms".format(math.floor(time.time()*1000-start*1000)))#


main()

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import os
import time
import re
import math


def main():
    N,M=map(int,input().split())
    A=[int(input()) for  a in range(M)] #a (1段~N-1段)
    start=time.time();#
    memo=[0]*(N+1)
    memo[0]=1
    ban=[False]*(N+1)
    for a in range(M):
        ban[a]=True
    mod=1000000007

    for a in range(1,N+1):
        if ban[a]:
            memo[a]=0
        else:
            if a>1:
                memo[a]=(memo[a-1]+memo[a-2])%mod
            else:
                memo[a]=1



    print(memo[-1]%mod)
    #print("{}ms".format(math.floor(time.time()*1000-start*1000)))#


main()

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import os
import time
import re
import math


def main():
    N,M=map(int,input().split())
    A=[int(input()) for  a in range(M)] #a (1段~N-1段)
    start=time.time();#
    memo=[0]*(N+1)
    memo[0]=1
    ban=[False]*(N+1)
    for a in range(M):
        ban[a]=A[a]
    mod=1000000007

    for a in range(1,N+1):
        if ban[a]:
            memo[a]=0
            continue
        if a>1:
            memo[a]=(memo[a-1]+memo[a-2])%mod
        else:
            memo[a]=1



    print(memo[-1]%mod)
    #print("{}ms".format(math.floor(time.time()*1000-start*1000)))#


main()

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import os
import time
import re
import math


def main():
    N,M=map(int,input().split())
    A=[int(input()) for  a in range(M)] #a (1段~N-1段)
    start=time.time();#
    memo=[0]*(N+1)
    memo[0]=1
    ban=[False]*(N+1)
    for a in range(M):
        ban[a]=A[a]
    mod=1000000007

    for a in range(1,N+1):
        if ban[a]:
            memo[a]=0
            continue
        if a>1:
            memo[a]=memo[a-1]+memo[a-2]
        else:
            memo[a]=1



    print(memo[-1]%mod)
    #print("{}ms".format(math.floor(time.time()*1000-start*1000)))#


main()

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import os
import time
import re
import math


def main():
    N,M=map(int,input().split())
    A=[int(input()) for  a in range(M)] #a (1段~N-1段)
    start=time.time();#
    memo=[0]*(N+1)
    memo[0]=1
    ban=[False]*(N+1)
    for a in range(M):
        ban[a]=A[a]
    mod=1000000007

    for a in range(1,N+1):
        if a>1:
            memo[a]=memo[a-1]+memo[a-2]
        else:
            memo[a]=1



    print(memo[-1]%mod)
    #print("{}ms".format(math.floor(time.time()*1000-start*1000)))#


main()

Submission status: Wrong Answer

Solution code:
def fib(n):
    if n == 0: 
        return 0

    if n == 1: 
        return 1

    def matmul(M1, M2):
        a11 = M1[0][0]*M2[0][0] + M1[0][1]*M2[1][0]
        a12 = M1[0][0]*M2[0][1] + M1[0][1]*M2[1][1]
        a21 = M1[1][0]*M2[0][0] + M1[1][1]*M2[1][0]
        a22 = M1[1][0]*M2[0][1] + M1[1][1]*M2[1][1]
        return [[a11, a12], [a21, a22]]

    def matPower(mat, p):
        if p == 1: 
            return mat

        m2 = matPower(mat, p//2)
        if p % 2 == 0:
            return matmul(m2, m2)
        else: 
            return matmul(matmul(m2, m2),mat)

    Q = [[1,1],[1,0]]

    q_final = matPower(Q, n-1)
    return q_final[0][0]

N, M = map(int, input().split())
if(M==0):
    print(fib(N)%1000000007)
else:
    V = []
    for x in range(M):
        V.append(int(input()))

    result = 1

    for i in range(1, M):
        if(V[i]-V[i-1]==1):
            result = 0

    result *= fib(V[0])

    for x in range(1, M):
        result *= fib(V[x]-V[x-1]-1)

    if(V[M-1]!=N):
        result *= fib(N-V[M-1])

    print(result%1000000007)

Submission status: Wrong Answer

Solution code:
mod = 1000000007
# inputs
N, M = map(int, input().split())
oks = [True] * (N + 1)
for _ in range(M):
    oks[int(input())] = False

dp = [1] * (N + 1)
for i in range(M):
    dp[i] = 0


for i in range(2, N + 1):
    if oks[i-1]:
        dp[i] = (dp[i-1] + dp[i-2]) % (10**9+7)

print(dp[N])

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
mod = 1000000007
dp = [0] * (N+2)
A = [int(input()) for _ in range(M)] 
dp[-1] = 1

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

print(dp[0])

Submission status: Wrong Answer

Solution code:
N,M = list(map(int, input().split()))
 
lst1 = [int(input()) for i in range(M)]
from functools import lru_cache
@lru_cache(maxsize=1024)
 
def fib(n):
  lst = []
  a = 1
  for i in range(1,n+1):  
    if (i == 1):
      if (i in lst1):
        a = 0
      lst.append(a)
    elif (i == 2):
      if (i in lst1):
        lst.append(lst[0])
      else:
        lst.append(lst[0] + 1)
    else:
      if (i in lst1):
        lst.append(0)
      else:
        lst.append(lst[i-3] + lst[i-2])
  return lst[-1]
print(fib(N) % 1000000007)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
# coding: utf-8
def main():
    N, M = map(int, input().split())

    a = [True] * (N+1)
    #s = [True for _ in range(N+1)]
    for _ in range(M):
        a[int(input())] = False
    
    #a = []
    #for i in range(M):
    #    a.append(int(input()))
    
    dp = [0] * (N+1)
    dp.append(1)
    mod = 1000000007
    
    for s in reversed(range(N)):
        if a[s] == False: # xだったら
            if a[s+1] == False:
                dp[s] = 0 # 2回連続で穴があったら0返して終了
                break
            else:
                dp[s] = 0 # 無を代入
        else: # oだったら
            dp[s] = (dp[s+1] + dp[s+2]) % mod # DP!! DP!!
            
    print(dp[0])

main()

Submission status: Wrong Answer

Solution code:
import math
 
N, M = map(int, input().split())
lista = [int(input()) for _ in range(M)]
 
sum = 1 # パターン総数
current = 0 # 現在の段数
 
# 連続で階段が壊れていたら上がるのは不可能
for i in range(M - 1):
  if lista[i + 1] - lista[i] == 1: 
    sum = 0
    break
 
# 連続では階段が壊れていない
if sum == 1:
  for a in lista:
    cnt = 0
    diff = a -current - 1
    for i in range(diff + 1):
      for j in range(diff // 2 + 1):
        if (i + 2 * j) == diff:
          cnt += math.factorial(i + j) // math.factorial(i) // math.factorial(j)
    current = a + 1
    sum *= cnt
    
    # 最後の段
    if a == lista[M - 1]:
      cnt = 0
      diff = N - current
      for i in range(diff + 1):
          for j in range(diff // 2 + 1):
            if (i + 2 * j) == diff:
              cnt += math.factorial(i + j) // math.factorial(i) // math.factorial(j)
      sum *= cnt
 
if M == 0:
  cnt = 0
  for i in range(N + 1):
    for j in range(N // 2 + 1):
      if (i + 2 * j) == N:
        cnt += math.factorial(i + j) // math.factorial(i) // math.factorial(j)
        sum *= cnt
 
print(sum % 1000000007)

Submission status: Wrong Answer

Solution code:
import math
 
N, M = map(int, input().split())
lista = [int(input()) for _ in range(M)]
 
sum = 1 # パターン総数
current = 0 # 現在の段数
 
# 連続で階段が壊れていたら上がるのは不可能
for i in range(M - 1):
  if lista[i + 1] - lista[i] == 1: 
    sum = 0
    break
 
# 連続では階段が壊れていない
if sum == 1:
  for a in lista:
    cnt = 0
    diff = a -current - 1
    for i in range(diff + 1):
      for j in range(diff // 2 + 1):
        if (i + 2 * j) == diff:
          cnt += math.factorial(i + j) // math.factorial(i) // math.factorial(j)
    current = a + 1
    sum *= cnt
    
    # 最後の段
    if a == lista[M - 1]:
      cnt = 0
      diff = N - current
      for i in range(diff + 1):
          for j in range(diff // 2 + 1):
            if (i + 2 * j) == diff:
              cnt += math.factorial(i + j) // math.factorial(i) // math.factorial(j)
      sum *= cnt
 
print(sum % 1000000007)

Submission status: Wrong Answer

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

r = [1, 2]
if 1 in a:
  r[0] = 0
  if not 2 in a:
    r[1] = 1
if 2 in a:
  r[1] = 0

for i in range(2, n):
  # print(r)
  r.append(r[-2] + r[-1] if not (i+1) in a else 0)

print(r[-1] % 1000000007)

Submission status: Wrong Answer

Solution code:
#ABC129C-TypicalStairs.py

#import list
import numpy as np
from sys import stdin, setrecursionlimit
from functools import lru_cache

input = stdin.readline
setrecursionlimit(1000)

#constant
#N = int(input())
N, M = list(map(int,input().split()))
A = {int(input()) for _ in range(M)}

#variable
rootList = np.array([1]+[0]*(N))

#function

#class

#main function
def main():
    for i in range(N):
        rootList[i+1] = rootList[i]+rootList[i-1]
        if i+1 in A:
            rootList[i+1] = 0
    print(rootList[N]%1000000007)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

r = [1, 2]
if 1 in a:
  r[0] = 0
  if not 2 in a:
    r[1] = 1
elif 2 in a:
  r[1] = 0

for i in range(2, n):
  # print(r)
  r.append(r[0] + r[1] if not (i+1) in a else 0)
  del r[0]

print(r[-1] % 1000000007)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
MOD = 1000000007 
D=[0] * n
for _ in range(m):
    D[int(input())] = -1
for i in range(n):
    if D[i] == -1:
        continue
    if i in (0, 1):
        D[i] = 1
        continue
    if D[i-1] != -1:
        D[i] += D[i-1]
    if D[i-2] != -1:
        D[i] += D[i-2]
    D[i]%=MOD
ans = 0
if D[n-1] != -1:
    ans += D[n-1]
if D[n-2] != -1:
    ans += D[n-2]
print(ans % MOD)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
MOD = 1000000007 
D=[0] * n
for _ in range(m):
    D[int(input())] = -1
for i in range(n):
    if D[i] == -1:
        continue
    if i == 0:
        D[i] = 1
        continue
    if D[i-1] != -1:
        D[i] += D[i-1]
    if D[i-2] != -1:
        D[i] += D[i-2]
    D[i]%=MOD
ans = 0
if D[n-1] != -1:
    ans += D[n-1]
if D[n-2] != -1:
    ans += D[n-2]
print(ans % MOD)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
ana = []
for _ in range(M):
  ana.append(input())
ans = []
ans.append(1)#一段目まで登る方法は一通り
ans.append(2)#二段目まで登る方法は二通り

for i in range(2,N):
    tmp = i+1
    tmp2 = str(tmp)
    if tmp2 in ana:
        ans.append(0)
    else:
        ans.append(ans[i-1] + ans[i-2])

print(ans[N-1] % 1000000007)

Submission status: Wrong Answer

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

ans = 0
dp=[[0 for i in range(N+1)] for j in range(N+1)]
#dp[何回目の移動か][今どこにいるか] = 何通りあるか
dp[0][0] = 1

for i in range(N):
  for j in range(N):
    if j+1 <= N:
      if A[j+1] == 1:
        dp[i+1][j+1] += dp[i][j]
    if j+2 <= N:
      if A[j+2] == 1:
        dp[i+1][j+2] += dp[i][j]

for i in range(N):
  ans += dp[i][N]

print(ans%1000000007)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

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

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

a.append(n)
s = 1
am = 0

for i in a:
    if i - am == 1 and i != a[0] and i != a[-1]:
        print(0)
        exit()

    elif i == a[0] or i == a[-1]:
        s *= fb(i - am)

    else:
        s *= (fb(i - am - 1))
    
    am = i

s = s % 1000000007
print(s)

Submission status: Wrong Answer

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

ans = 0
dp=[[0 for i in range(N+2)] for j in range(N+2)]
#dp[何回目の移動か][今どこにいるか] = 何通りあるか
dp[0][0] = 1

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

for i in range(N):
  ans += dp[i][N]

print(ans%1000000007)

Submission status: Wrong Answer

Solution code:
from itertools import combinations
import operator as op
from functools import reduce
from math import factorial as f

def nCr(n,r):
    return f(n) // f(r) // f(n-r)

def calcResult(n):
    if n == 1:
        return 1
    if n == 0:
        return 0
    n = n - 1
    possible2 = n // 2
    res = 0
    for r in range(possible2 + 1):
        _n = max(n-2*r+r, r)
        _r = min(n-2*r+r, r)
        res += nCr(_n, _r)
    return res

N, M = map(int, input().split())
prev_a = -1
B = 1
for i in range(M):
    a = int(input())
    B *= calcResult(a - prev_a)
    prev_a = a
B *= calcResult(N - prev_a)

print(int(B % 1000000007))

Submission status: Wrong Answer

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

def fib(n):
    if n == 0:
        return 0
    else:
        a0 = 0
        a1 = 1
        for i in range(n-1):
            b = a1
            a1 += a0
            a0 = b
        return a1

count = 1
b = 0
for i in range(m):
    a = int(input())
    if a == 1:
        b = 1
        continue
    num = a - b
    if num == 1:
        count *= 0
        break
    elif num == a:
        count *= fib(num)
        b = a 
    else:
        num -= 1
        count *= fib(num)
        b = a 
#     print(b, count, num)
    
count *= fib(n - b)

print(count%1000000007)

Submission status: Wrong Answer

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

def fib(n):
    if n == 0:
        return 0
    else:
        a0 = 0
        a1 = 1
        for i in range(n-1):
            b = a1
            a1 += a0
            a0 = b
        return a1

count = 1
b = 0
for i in range(m):
    a = int(input())
    if a == 1:
        b = 1
        continue
    num = a - b
    if num == a:
        count *= fib(num)
        b = a 
    elif num == 1:
        count *= 0
        break
    else:
        num -= 1
        count *= fib(num)
        b = a 
#     print(b, count, num)
    
count *= fib(n - b)

print(count%1000000007)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

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

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

a.append(n)
s = 1
am = 0

for i in a:
    if i - am == 1 and i != 1:
        print(0)
        exit()

    if i == a[0]:
        s *= fb(i)

    elif i == a[-1]:
        s *= fb(i - am)

    else:
        s *= (fb(i - am - 1))
    
    am = i

s = s % 1000000007
print(s)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

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

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

a.append(n)
s = 1
am = 0

for i in a:
    if i - am == 1 and i != 1:
        print(0)
        exit()

    if i == a[0]:
        s *= fb(i)

    elif i == a[-1]:
        s *= fb(i - am)

    else:
        s *= (fb(i - am - 1))
    
    am = i

print(s % 1000000007)

Submission status: Wrong Answer

Solution code:
import sys

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

if M == 0:
    alist = set()
else:
    alist = set(map(int, sys.stdin) for _ in range(M))

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

MOD = 10**9 + 7
for i in range(2, N + 1):
    if i in alist:
        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())

if M == 0:
    alist = set()
else:
    alist = set(map(int, input()) for _ in range(M))

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

MOD = 10**9 + 7
for i in range(2, N + 1):
    if i in alist:
        continue
    dp[i] = (dp[i - 1] + dp[i - 2]) % MOD

print(dp[N])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

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

n, m = map(int, input().split())
a=[]
while True:
    try:
        a.append(int(input()))
    except:
        break

a.append(n)
s = 1
am = 0
print(a)

for i in a:
    if i - am == 1 and i != 1:
        print(0)
        exit()

    print(i)
    if i == a[0]:
        s *= fb(i)

    elif i == a[-1]:
        s *= fb(i - am)

    else:
        s *= (fb(i - am - 1))
    
    am = i

print(s % 1000000007)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n,m=map(int,input().split())
a=[int(input()) for i in range(m)]
F = [1]*(n+3)
for i in range(2,n+1):
    if i in a:
        F[i]=0
        continue
    F[i]=(F[i-1]%(10**9+7)+F[i-2]%(10**9+7))%(10**9+7)
if n==1:
    print(1)
elif n==2:
    if m==1:
        print(1)
    elif m==0:
        print(2)
else:
    for i in range(m):
        if a[i]+1 in a or a[i]-1 in a:
            print(0)
            exit()
    print(F[n])

Submission status: Wrong Answer

Solution code:
N, M = list(map(int, input().split()))
a = []
b = []

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

inf = 1000000007

def judge(arr):
    for i in range(1,len(arr)):
        if arr[i-1]+1 == arr[i]:
            return 1
    return 0

if judge(a):
    print(0)
    exit()

S = []


for i in a:
    b.append([i-1,i])
    b.append([i,i+1])

for i in range(1,N):
    if not [i,i+1] in b:
        S.append([i,i+1])

print(2**(len(S)-1)%inf)

Submission status: Wrong Answer

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

def fib(n):
    dp_list = [0] * n
    dp_list[0] = 1
    if n == 1:
        return 1
    dp_list[1] = 2
    
    for i in range(2, n):
        dp_list[i] = dp_list[i - 1] + dp_list[i - 2]
    return dp_list[n - 1]

if N == 1:
    print(1)
    sys.exit()

if M == 0:
    print(fib(N))
    sys.exit()

a_list = [0] * M

for m in range(M):
    a_list[m] = int(input())

for m in range(M - 1):
    if a_list[m] + 1 == a_list[m + 1]:
        print(0)
        sys.exit()
    else:
        continue

range_list = [i for i in range(1, N + 1)]
new_list = [0] * (M + 1)


new_list[0] = [0] + range_list[0: a_list[0] - 1]
new_list[M] = range_list[a_list[M - 1]:]

if M - 1 >= 1:
    for m in range(1, M):
        new_list[m] = range_list[a_list[m - 1]: a_list[m] - 1]

MOD = 1000000007


count = 1
for item in new_list:
    if not item or len(item) == 1:
        continue
    else:
        count *= (fib(len(item) - 1) % MOD)
        count %= MOD
        #print(count)
print(count)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
oks = [True] * (N+1)
a = [int(input()) for _ in range(M)]
for i in a:
    oks[i] = False
dp = [0] * (N+1)
dp[0] = 1
for i in range(N+1):
    for j in range(i+1, min(i+2, N)+1):
        if oks[j]:
            dp[j] += int((dp[i]) % (1e9+7))


print(dp[N])

Submission status: Wrong Answer

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

def fib(n):
    dp_list = [0] * n
    dp_list[0] = 1
    if n == 1:
        return 1
    dp_list[1] = 2
    
    for i in range(2, n):
        dp_list[i] = dp_list[i - 1] + dp_list[i - 2]
    return dp_list[n - 1]

if M == 0:
    print(fib(N))
    sys.exit()

a_list = [0] * M

for m in range(M):
    a_list[m] = int(input())

for m in range(M - 1):
    if a_list[m] + 1 == a_list[m + 1]:
        print(0)
        sys.exit()
    else:
        continue

range_list = [i for i in range(1, N + 1)]
new_list = [0] * (M + 1)


new_list[0] = [0] + range_list[0: a_list[0] - 1]
new_list[M] = range_list[a_list[M - 1]:]

if M - 1 >= 1:
    for m in range(1, M):
        new_list[m] = range_list[a_list[m - 1]: a_list[m] - 1]

MOD = 1000000007


count = 1
for item in new_list:
    if not item or len(item) == 1:
        continue
    else:
        count *= (fib(len(item) - 1) % MOD)
        count %= MOD
        #print(count)
print(count)