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:
def fib(n):
    if n == 1 or n == 2:
        return 1
    return fib(n - 1) + fib(n - 2)

pipi = 1

n,m = map(int,input().split())
a = []
b = []
flag = 0

#危ない階段
for i in range(m):
    a.append(int(input()))

#配列がいくつあるか
for i in range(m):
    if i == 0:
        if a[0] > 1:
            #穴が1以上であれば、すきまがある
            b.append(a[0]-1)
            #空いている場所を追加

    if m != 1 and i!=0:
        if a[i]-a[i-1]-2 <= -1:
            flag = 1
            break
        else:
            b.append(a[i]-a[i-1]-2)

    if i == m-1:
        #穴がn未満であれば、すきまがある
        if a[i] < n:
            b.append(n-a[i]-1)

if flag == 0:
    #n列の階段を求める　→ フィボナッチn+1番目＝nの配列
    for i,value in enumerate(b):
        if value >= 0:
            pipi *= fib(value+1)

if flag == 0:
    print(pipi % 1000000007)
else:
    print(0)

Submission status: Wrong Answer

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

breakstep = []

for _ in range(m):
    breakstep.append(int(input()))

sl = [1]
def solve(i):
    global sl
    l = len(sl)
    if l < i+1:
        while l < i+1:
            if l in breakstep: 
                sl.append(0)
                l += 1
                continue
            elif l == 1:
                l += 1
                sl.append(1)
            sl.append(sl[l-1] + sl[l-2])
            l += 1
    return sl[i]
print(solve(n)%1000000007)

Submission status: Wrong Answer

Solution code:
def fib(n):
    if n == 1 or n == 2:
        return 1
    return fib(n - 1) + fib(n - 2)

pipi = 1

n,m = map(int,input().split())
a = []
b = []
flag = 0

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

for i in range(m):
    if i == 0:
        if a[0] > 1:
            b.append(a[0]-1)

    if m != 1 and i!=0:
        if a[i]-a[i-1]-2 <= -1:
            flag = 1
            break
        else:
            b.append(a[i]-a[i-1]-2)

    if i == m-1:
        if a[i] < n:
            b.append(n-a[i]-1)

if flag == 0:
    for i,value in enumerate(b):
        if value >= 0:
            pipi *= fib(value+1)
if flag == 0:
    print(pipi % 1000000007)
else:
    print("0")

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
mod = 1000000007
falls = []

for j in range(m):
    falls.append(int(input())) 

results =[]

if 1 in falls:
    result = 0
else:
    result = 1

results.append(result)

if 1 in falls:
    result = 0
else:
    if results[0] == 0:
        result = 1
    else:
        result = 2

results.append(result)

for i in range(3,n+1):
    number = i

    if number in falls:
        result = 0

    else:
        result = (results[i-3] + results[i-2]) % mod

    results.append(result)

print(results[n-1])

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
sys.setrecursionlimit(10**7)

NM = input()
N, M = NM.split(" ")
del NM
N, M = int(N), int(M)
broken_steps = [int(input()) for num in range(M)]

all_steps = np.ones(N+1, dtype=np.float128)
all_steps[broken_steps] = 0
ok_steps = all_steps
del all_steps

for num in reversed(range(0,len(ok_steps)-2)):
  if ok_steps[num]==0:
    pass
  else:
    ok_steps[num] = ok_steps[num+1] + ok_steps[num+2]

#print(ok_steps[-20:].astype(int))
print(ok_steps[0].astype(int)%1000000007)

Submission status: Wrong Answer

Solution code:
import numpy as np
NM = input()
N, M = NM.split(" ")
del NM
N, M = int(N), int(M)
broken_steps = [int(input()) for num in range(M)]

all_steps = np.ones(N+1, dtype=np.float128)
all_steps[broken_steps] = 0
ok_steps = all_steps
del all_steps

for num in reversed(range(0,len(ok_steps)-2)):
  if ok_steps[num]==0:
    pass
  else:
    ok_steps[num] = ok_steps[num+1] + ok_steps[num+2]

#print(ok_steps[-20:].astype(int))
print(ok_steps[0].astype(int)%1000000007)

Submission status: Wrong Answer

Solution code:
N,M = [int(i) for i in input().split()]
A = []
for _ in range(M):
    A.append(int(input()))
steps = [0]*N
for a in A:
    steps[a-1] = 1
cnt = []
for n in range(N):
    if n == 0:
        if steps[n]==0:
            cnt.append(1)
        elif steps[n]==1:
            cnt.append(0)
    elif n == 1:
        if steps[n]==0:
            cnt.append(cnt[n-1]+1)
        elif steps[n]==1:
            cnt.append(0)
    elif steps[n] == 0:
        cnt.append(cnt[n-2]+cnt[n-1])
    elif steps[n] == 1:
        cnt.append(0)
print(cnt[-1])

Submission status: Wrong Answer

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

li_m = list()

for _ in range(m):
    li_m.append(int(input()))


if set(li_m).intersection([l + 1 for l in li_m]):
    print(0)
    exit(0)


answer = 1

def pt(length):

    if length == 0:
        return 1

    li_test = [0] * length
    for i in range(length):
        if i == 0:
            li_test[i] = 1
        elif i == 1:
            li_test[i] = li_test[i - 1] + 1
        elif i == len(li_test):
            li_test[i] = li_test[i - 1] + 1
        else:
            li_test[i] = li_test[i - 1] + li_test[i - 2]

    return li_test[-1]


idx_start = 0
idx_end = 0

for idx, v in enumerate(li_m):
    if idx == 0:
        idx_end = v - 1
    else:
        idx_start = idx_end + 2
        idx_end = v - 1

    subkaidan = idx_end - idx_start

    answer = answer * pt(subkaidan)

    if idx == len(li_m) - 1:
        idx_start = idx_end + 2
        idx_end = n
        subkaidan = idx_end - idx_start

        answer = answer * pt(subkaidan)


print(answer % 1000000007)

Submission status: Wrong Answer

Solution code:
import sys
n, m = map(int, input().split())
bf = -1
way = [-1] * (n+1)
way[0] = 1
way[1] = 1
for i in range(m):
    tmp = int(input())
    if bf + 1 == tmp:
        print(0)
        sys.exit()
    bf = tmp
    way[tmp] = 0
for i in range(2, n+1):
    if way[i] == -1:
        way[i] = way[i-2] + way[i-1]
print(way[n])

Submission status: Wrong Answer

Solution code:
import numpy as np
NM = input()
N, M = NM.split(" ")
del NM
N, M = int(N), int(M)
broken_steps = [int(input()) for num in range(M)]
all_steps = np.ones(N+1, dtype=int)
all_steps[broken_steps] = 0
ok_steps = list(all_steps)
del all_steps

for num in range(0, len(ok_steps)):
  i = - (num + 1)
  
  if (i==-1 or i==-2):
    pass
  else:
    if ok_steps[i]==0:
      pass
    else:
      ok_steps[i] = ok_steps[i+1] + ok_steps[i+2]

print(ok_steps[0]%1000000007)

Submission status: Wrong Answer

Solution code:
import numpy as np
NM = input()
N, M = NM.split(" ")
del NM
N, M = int(N), int(M)
broken_steps = [int(input()) for num in range(M)]
#all_steps = [num for num in range(N+1)]
all_steps = np.ones(N+1)  ##np.int32だと足りない  ##64もあかんかも
all_steps[broken_steps] = 0
ok_steps = list(all_steps)
#ok_steps = [0 if num in broken_steps else 1 for num in range(len(all_steps))]
#for num in range(len(all_steps)):
#  if num in broken_steps:
#    ok_steps.append(0)
#  else:
#  	ok_steps.append(1)
#del all_steps, broken_steps
#print(ok_steps)
for num in range(0, len(ok_steps)):
  i = - (num + 1)
  
  if (i==-1 or i==-2):
    pass
  else:
    if ok_steps[i]==0:
      pass
    else:
      ok_steps[i] = ok_steps[i+1] + ok_steps[i+2]
      

#for num in range(0, len(ok_steps)):
#  i = - (num + 1)
#  
#  if (i==-1 or i==-2):
#    pass
#  else:
#    if ok_steps[i]==0:
#      pass
#    else:
#      print(i)
#      ok_steps[i] = ok_steps[i+1] + ok_steps[i+2]
#print(ok_steps[-3])        
print(ok_steps[0]%1000000007)

Submission status: Wrong Answer

Solution code:
import numpy as np
NM = input()
N, M = NM.split(" ")
del NM
N, M = int(N), int(M)
broken_steps = [int(input()) for num in range(M)]
#all_steps = [num for num in range(N+1)]
all_steps = np.ones(N+1, dtype=int)  ##np.int32だと足りない
all_steps[broken_steps] = 0
ok_steps = list(all_steps)
#ok_steps = [0 if num in broken_steps else 1 for num in range(len(all_steps))]
#for num in range(len(all_steps)):
#  if num in broken_steps:
#    ok_steps.append(0)
#  else:
#  	ok_steps.append(1)
#del all_steps, broken_steps
#print(ok_steps)
for num in range(0, len(ok_steps)):
  i = - (num + 1)
  
  if (i==-1 or i==-2):
    pass
  else:
    if ok_steps[i]==0:
      pass
    else:
      ok_steps[i] = ok_steps[i+1] + ok_steps[i+2]
      

#for num in range(0, len(ok_steps)):
#  i = - (num + 1)
#  
#  if (i==-1 or i==-2):
#    pass
#  else:
#    if ok_steps[i]==0:
#      pass
#    else:
#      print(i)
#      ok_steps[i] = ok_steps[i+1] + ok_steps[i+2]
#print(ok_steps[-3])        
print(ok_steps[0]%1000000007)

Submission status: Wrong Answer

Solution code:
import numpy as np
NM = input()
N, M = NM.split(" ")
del NM
N, M = int(N), int(M)
broken_steps = [int(input()) for num in range(M)]
#all_steps = [num for num in range(N+1)]
all_steps = np.ones(N+1, dtype=np.int64)  ##np.int32だと足りない
all_steps[broken_steps] = 0
ok_steps = list(all_steps)
#ok_steps = [0 if num in broken_steps else 1 for num in range(len(all_steps))]
#for num in range(len(all_steps)):
#  if num in broken_steps:
#    ok_steps.append(0)
#  else:
#  	ok_steps.append(1)
#del all_steps, broken_steps
#print(ok_steps)
for num in range(0, len(ok_steps)):
  i = - (num + 1)
  
  if (i==-1 or i==-2):
    pass
  else:
    if ok_steps[i]==0:
      pass
    else:
      ok_steps[i] = ok_steps[i+1] + ok_steps[i+2]
      

#for num in range(0, len(ok_steps)):
#  i = - (num + 1)
#  
#  if (i==-1 or i==-2):
#    pass
#  else:
#    if ok_steps[i]==0:
#      pass
#    else:
#      print(i)
#      ok_steps[i] = ok_steps[i+1] + ok_steps[i+2]
#print(ok_steps[-3])        
print(ok_steps[0]%1000000007)

Submission status: Wrong Answer

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


def fib(dan):
    if dan == 1:
        return 1
    elif dan == 2:
        return 1
    elif dan == 0:
        return 0
    else:
        a1 = 1
        a2 = 1
        a3 = 0
        for _ in range(dan-2):
            a3 = (a1 + a2) % 1000000007
            a1 = a2 % 1000000007
            a2 = a3 % 1000000007

        return a3



if m != 0:
    ans = fib(li[0]) % 1000000007
    for i in range(m-1):
        ans = ans * fib(li[i+1] - li[i] - 1 ) % 1000000007

    ans = ans * fib(n - li[m-1]) % 1000000007
    print(ans)

else:
    print(fib(n))

Submission status: Wrong Answer

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


def fib(dan):
    if dan == 1:
        return 1
    elif dan == 2:
        return 1
    elif dan == 0:
        return 0
    else:
        a1 = 1
        a2 = 1
        a3 = 0
        for _ in range(dan-2):
            a3 = a1 + a2 
            a1 = a2 % 1000000007
            a2 = a3 % 1000000007

        return a3



if m != 0:
    ans = fib(li[0]) % 1000000007
    for i in range(m-1):
        ans = ans * fib(li[i+1] - li[i] - 1 ) % 1000000007

    ans = ans * fib(n - li[m-1]) % 1000000007
    print(ans)

else:
    print(fib(n))

Submission status: Wrong Answer

Solution code:
# 2019 6/12
# ABC129 C Typical Stairs
# fn: ways from 0 to n
# f(n) = f(n-1) + f(n-2)
# DP

import sys

N, M = list(map(int, input().split()))
if M > 0:
    broken = set(map(int, sys.stdin))
else:
    broken = set()

dp = [0] * (N + 1)

dp[0] = 1
dp[1] = 1 if 1 not in broken else 0

MOD = 10 ** 9 + 7

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

print(dp[N-5:])

print(dp[N])

Submission status: Wrong Answer

Solution code:
# 2019 6/12
# ABC129 C Typical Stairs
# fn: ways from 0 to n
# f(n) = f(n-1) + f(n-2)
# DP

import sys

N, M = list(map(int, input().split()))
if M > 0:
    broken = set(map(int, sys.stdin))
else:
    broken = set()

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

dp[0] = 1
dp[1] = 1 if 1 not in broken else 0

MOD = 10 ** 9 + 7

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

print(dp[N] % MOD)

Submission status: Wrong Answer

Solution code:
def fib(num_steps):
    xb = 1
    xa = 1
    if num_steps in [0, 1]:
        return xa
    elif num_steps == 2:
        return xa + xb
    else:
        for i in range(num_steps-2):
            tmp = xa
            xa = xa + xb
            xb = tmp
    
    return xa

N, M = map(int, input().split())
ways = 1
now = 0

for i in range(M):
    hole = int(input())
    diff = (hole - 1) - now

    if diff < 0:
        ways *= 0
    else:
        ways *= fib(diff)

    now = hole + 1

if now < N:
    ways *= fib(N - now)

print(ways % 1000000007)

Submission status: Wrong Answer

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

if N==1:
  print(0)
  exit()

A = []
a_prev = None
for i in range(M):
  a_i = int(input())
  if a_prev == a_i:
    print(0)
    exit()
  A.append(a_i)
  a_prev = a_i

N_2 = 1
N_1 = 1  
ans = 0
for i in range(1, N):
  if i in A:
    N_1 = 0
  ans = N_1 + N_2
  N_2 = N_1
  N_1 = ans
print(ans%1000000007)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
A=[-1]+[int(input()) for i in range(M)]+[N+1]
res=1
for i in range(1,len(A)):
  steps=A[i]-A[i-1]-2
  if steps<0:
    patern_nmu=0
  else:
    p,q=1,0
    for j in range(steps):
      p,q=p+q,p
    patern_nmu=p
    res*=patern_nmu
    res%=1000000007
print(res)

Submission status: Wrong Answer

Solution code:
path = 1
a_num = 0
now = 0
N,M = map(int,input().split(' '))
flag = 1
if a_num < M:
  next_a = int(input())
  a_num += 1
else:
  next_a = -1
if a_num < M:
  next_a2 = int(input())
  a_num += 1
else:
  next_a2 = next_a
while(now<N-1):
  if now+1 == next_a and now+2 == next_a2:
    path = 0
    break
  elif now+1 == next_a:
    next_a = next_a2
    if a_num < M:
      next_a2 = int(input())
      a_num += 1
    now += 2
  elif now+2 == next_a:
    now += 1
  elif now+1 != next_a and now+2 != next_a:
    path *= 2
    now += 2

if path != 0 and now+1 == next_a:
  print(path % 1000000007)
elif path != 0 and now+1 !=next_a:
  print(path*2 % 1000000007)
elif path == 0:
  print(path % 1000000007)

Submission status: Wrong Answer

Solution code:
print('test')

Submission status: Wrong Answer

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns()) #int
na = lambda: list(map(int, stdin.readline().split())) #int,list
ns = lambda: stdin.readline().rstrip()  # str


def dp(n):
	v=[1,1,2]
	for i in range(n):
		v.append(v[i+1]+v[i+2])
	return v

n,m=na()
dp = dp(n)
#print(dp[0:10])
ans=1
flag=0
a=[-1]
for i in range(m):
	a.append(ni())

for i in range(m):
	
	#print(a)
	if (a[i+1]-a[i]==1):
		flag=1
		break
	ans*=dp[a[i+1]-a[i]-2]
if flag==1:
	print(0)
else:
	print((ans*(n-a[-1]-1))%1000000007)

Submission status: Wrong Answer

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns()) #int
na = lambda: list(map(int, stdin.readline().split())) #int,list
ns = lambda: stdin.readline().rstrip()  # str


def dp(n):
	v=[1,1,2]
	for i in range(n):
		v.append(v[i+1]+v[i+2])
	return v

n,m=na()
dp = dp(n)
#print(dp[0:10])
ans=1
flag=0
a=[-1]
for i in range(m):
	a.append(ni())

for i in range(m):
	
	#print(a)
	if (a[i+1]-a[i]==1):
		flag=1
		break
	ans*=dp[a[i+1]-a[i]-2]

print((ans*(n-a[-1]-1))%1000000007)

Submission status: Wrong Answer

Solution code:
mod=10**9+7
def f(a,r):
    s=[[0,0],[0,0]]
    s[0][0]=(a[0][0]*r[0][0]+a[0][1]*r[1][0])%mod
    s[0][1]=(a[0][0]*r[0][1]+a[0][1]*r[1][1])%mod
    s[1][0]=(a[1][0]*r[0][0]+a[1][1]*r[1][0])%mod
    s[1][1]=(a[1][0]*r[0][1]+a[1][1]*r[1][1])%mod
    return s
b=[[1,1],[1,0]]
k=[b]
for i in range(20):
    k.append(f(k[-1],k[-1]))
n,m=map(int,input().split())
t=0
ans=1
for i in range(m):
    a=int(input())
    if t==a:
        print(0)
        break
    else:
        s=bin(a-1-t)[2:]
        s="0"*(21-len(s))+s
        s=s[::-1]
        p=[[1,0],[0,1]]
        for j in range(21):
            if s[j]=="1":
                p=f(p,k[j])
        ans=(ans*p[0][0])%mod
        t=a+1
        if i==m-1:
            s=bin(n-t)[2:]
            s="0"*(21-len(s))+s
            s=s[::-1]
            p=[[1,0],[0,1]]
            for j in range(21):
                if s[j]=="1":
                    p=f(p,k[j])
            ans=(ans*p[0][0])%mod
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
mod=10**9+7
def f(a,r):
    s=[[0,0],[0,0]]
    s[0][0]=(a[0][0]*r[0][0]+a[0][1]*r[1][0])%mod
    s[0][1]=(a[0][0]*r[0][1]+a[0][1]*r[1][1])%mod
    s[1][0]=(a[1][0]*r[0][0]+a[1][1]*r[1][0])%mod
    s[1][1]=(a[1][0]*r[0][1]+a[1][1]*r[1][1])%mod
    return s
b=[[1,1],[1,0]]
k=[b]
for i in range(20):
    k.append(f(k[-1],k[-1]))
n,m=map(int,input().split())
t=0
ans=1
for i in range(m):
    a=int(input())
    if t==a:
        print(0)
        break
    else:
        s=bin(a-1-t)[2:]
        s="0"*(21-len(s))+s
        s=s[::-1]
        p=[[1,0],[0,1]]
        for j in range(21):
            if s[j]=="1":
                p=f(p,k[j])
        ans=(ans*p[0][0])%mod
        t=a+1
        if i==m-1:
            s=bin(n-t)[2:]
            s="0"*(21-len(s))+s
            s=s[::-1]
            p=[[1,0],[0,1]]
            for j in range(21):
                if s[j]=="1":
                    p=f(p,k[j])
            ans=(ans*p[0][0])%mod
else:
    print(ans)

Submission status: Wrong Answer

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

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

for i in range(2, N + 1):
  if i in broken:
    continue
  else:
    stair[i] = stair[i - 2] + stair[i - 1]

print (stair[N] % 1000000007)

Submission status: Wrong Answer

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

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

for i in range(2, N + 1):
  if stair[i] in broken:
    continue
  else:
    stair[i] = stair[i - 2] + stair[i - 1]

print (stair[N] % 1000000007)

Submission status: Wrong Answer

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

cnt = [1, 2]

for i in range(1, n - 1):
    cnt.append(cnt[i] + cnt[i - 1])

if m == 0:
    print(cnt[n - 1] % 1000000007)
    exit()

l = [int(input()) for _ in range(m)]

l_diff = [l[0] - 1]
for i in range(1, m):
    l_diff.append(l[i] - l[i - 1] - 2)
l_diff.append(n - l[m - 1] - 1)

print(l_diff)
for k in range(1, m):
    if l[k] - l[k - 1] == 1:
        print(0)
        exit()


total = 1
for j in l_diff:
    if j == 0:
        pass
    else:
        total *= cnt[j - 1]

print(total % 1000000007)

Submission status: Wrong Answer

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

cnt = [1, 2]

for i in range(1, n - 1):
    cnt.append(cnt[i] + cnt[i - 1])

if m == 0:
    print(cnt[n - 1])
    exit()

l = [int(input()) for _ in range(m)]

l_diff = [l[0] - 1]
for i in range(1, m):
    l_diff.append(l[i] - l[i - 1] - 2)
l_diff.append(n - l[m - 1] - 1)

for k in range(1, m):
    if l[k] - l[k - 1] == 1:
        print(0)
        exit()


total = 1
for j in l_diff:
    if j == 0:
        pass
    else:
        total *= cnt[j - 1]

print(total % 1000000007)

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
a = [0]*(n+1)
a[1] = 1
if n >= 2:
    a[2] = 2
for i in range(m):
    a[int(input())] = "*"
if a[1] == "*":
    a[2] = 1
#階段が壊れていないならば a(n+2)=a(n+1)+a(n), a(0)=0, a(1)=1
#というフィボナッチ数列の問題になる
#ここでは、壊れている階段かどうかを逐次判定していくのが良いだろう
for i in range(1,n-1):
    if a[i+2] != "*":
        if a[i+1] != "*":
            if a[i] != "*":
                a[i+2] = a[i+1]+a[i]
            else:
                a[i+2] = a[i+1]
        else:
            if a[i] != "*":
                a[i+2] = a[i]
ans = a[-1]%1000000007
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10000)

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

def fib(n):
        a, b = 0, 1
        for i in range(n):
            a, b = b, a + b
        return b if n >= 0 else 0

if M == 0:
    ans = fib(N)


elif M == 1:
    ans = fib(a[0]-1) * fib(N-a[0]-1)

else:
    ans = fib(a[0]-1)
    for i in range(M-1):
        ans = (ans * fib(a[i+1]-a[i]-2))%(10**9+7)

    ans = (ans * fib(N-a[-1]-1))%(10**9+7)

print(ans)

Submission status: Wrong Answer

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

res = 1
for i in range(1, len(a)):
    steps = a[i] - a[i-1] - 2
    if steps < 0:
        patern_nmu = 0
    elif steps <= 1:
        patern_nmu = 1
    else:
        p, q = 1, 0
        for j in range(steps-1):
            p, q = p+q, p
        patern_nmu = p
    res *= patern_nmu
    res %= 1000000007

print(res)

Submission status: Wrong Answer

Solution code:
N,M = (int(i) for i in input().split())
a = [int(input()) for i in range(M)]
hoge = [0] * N
if 1 not in a:
    hoge[0] = 1
if 2 not in a and N >= 2:
    hoge[1] = hoge[0] + 1

for i in range(2,N):
    if i + 1  not in a:
        if i not in a:
            hoge[i] += hoge[i - 1]
        elif (i-1) not in a:
            hoge[i] += hoge[i - 2]

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

Submission status: Wrong Answer

Solution code:
N,M = (int(i) for i in input().split())
a = [int(input()) for i in range(M)]
hoge = [0] * N
if 1 not in a:
    hoge[0] = 1
if 2 not in a and N >= 2:
    hoge[1] = hoge[0] + 1

for i in range(2,N):
    if i + 1  in a:
        hoge[i] = 0
        if i not in a:
            hoge[i] += hoge[i - 1]
        elif (i-1) not in a:
            hoge[i] += hoge[i - 2]

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

Submission status: Wrong Answer

Solution code:
N,M = (int(i) for i in input().split())
a = [int(input()) for i in range(M)]
hoge = [0] * N
if 1 not in a:
    hoge[0] = 1
if 2 not in a and N >= 2:
    hoge[1] = hoge[0] + 1

for i in range(2,N):
    if i + 1 not in a:
        hoge[i] = 0
        if i not in a:
            hoge[i] += hoge[i - 1]
        elif (i-1) not in a:
            hoge[i] += hoge[i - 2]

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

Submission status: Wrong Answer

Solution code:
N,M = (int(i) for i in input().split())
a = [int(input()) for i in range(M)]
hoge = [0] * N
if 1 not in a:
    hoge[0] = 1
if 2 not in a and N >= 2:
    hoge[1] = hoge[0] + 1

for i in range(2,N):
    if i + 1 not in a:
        hoge[i] = 0
        if i in a:
            hoge[i] += hoge[i - 2]
        elif (i-1) in a:
            hoge[i] += hoge[i - 1]
      
print(hoge[N-1] % (10**9 + 7))

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
mod = 1000000007
a = [True] * (n + 1)
for i in range(m):
    a[int(input())] = False
dp = [0] * (n + 1)
dp[0] = 1

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

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

print(dp)

Submission status: Wrong Answer

Solution code:
from functools import lru_cache
import sys

sys.setrecursionlimit(1000000)

mod = 10 ** 9 + 7

@lru_cache(maxsize=1000000)
def saiki(i):
    if i == 0:
        return 1
    if i == 1:
        return 1
    if ok[i]:
        return saiki(i - 1) % mod + saiki(i - 2) % mod
    else:
        return 0


n, m = map(int, input().split())
a = [int(input()) for i in range(m)]
ok = [True] * (n + 1)
for i in a:
    ok[i] = False
print(saiki(n) % mod)

Submission status: Wrong Answer

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

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

wa = (10**9) + 7

#dpを使う

dp = [0]*(N+1)
dp[0]=1
now_a = 0
if len(a)!=0:
    a.reverse()
    now_a = a.pop()
if len(a)==0:
    now_a = -1
for i in range(1,N+1):
    if i==1:
        dp[i]=dp[i-1]
    else:
        dp[i]=dp[i-1] + dp[i-2]
    if i == now_a:
        dp[i]=0
        if len(a)!=0:
            now_a = a.pop()
        else:
            now_a = -1

print(dp[N]%wa)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
a = []
if M >= 1:
    for i in range(M):
        a.append(int(input()))

def fibo(n):
    a, b = 1, 1
    if (n == 0) or (n == 1) or (n == 2):
        return 1
    else:
        for _ in range(n-2):
            a, b = b, a + b
        return b

aa = [] #aの差を取ったもののリスト
if M >= 2:
    for k in range(M-1):
        aa.append(a[k+1] - a[k] - 1)
#print(aa)
#aa.append(N - a(M))

    if 0 in aa:
        ans = 0

    else:
        ans = 1
        ans_list = []
        for i in range(M-1):
            ans_list.append(fibo(aa[i]))

        ans_list.append(fibo(a[0]))
        ans_list.append(fibo(N - a[M-1]))
    #print(ans_list)
    
        for i in range (len(ans_list)):
            ans = (ans * ans_list[i]) % (10**9 + 7)

elif M == 1:
    ans_list = []
    ans_list.append(fibo(a[0]))
    ans_list.append(fibo(N - a[0]))
    ans = (ans_list[0] * ans_list[1]) % (10**9 + 7)

elif M == 0:
    ans = fibo(N+1)

print(ans)

Submission status: Wrong Answer

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



num=[1,1,2]


mod=1000000007

list=[]
count=0
jud=1
ans=1
for i in range(n+1):
	
	if i>2:
		num.append(1)
		num[i]=(num[i-1]+num[i-2])%mod

	if(jud==0 and i in a):
		print("0")
		
		break
	elif i in a:

		#list.append(count-1)
		ans*=num[count-1]%mod
		count=1
		jud=0
	elif(i==n):
		
		ans*=num[count-1]%mod
		#list.append(count-1)
		print(ans%mod)
	else:
		jud=1
		count+=1

Submission status: Wrong Answer

Solution code:
import math

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

ng = 0
INF = pow(10, 9) + 7
ans = 1
now = 0
if M == 0:
    last = N
    if last % 2 == 0:
        tmp = 1
        i = int(last / 2)
        for j in range(1, i + 1):
            tmp += int(math.factorial(i + j) / (math.factorial(2 * j) * math.factorial(i - j)))
        ans *= tmp
        ans %= INF
    else:
        i = int(last / 2)
        tmp = i + 1
        for j in range(1, i + 1):
            tmp += int(math.factorial(i + j + 1) / (math.factorial((2 * j) + 1) * math.factorial(i - j)))
        ans *= tmp
        ans %= INF
else:
    for ind in range(M):
        nex = int(input())
        if ind == 0:
            broken = nex - now - 1
        else:
            broken = nex - now - 2
        if nex != 1 and nex - now == 1:
            ng = 1
            break
        if broken % 2 == 0:
            tmp = 1
            i = int(broken / 2)
            for j in range(1, i+1):
                tmp += int(math.factorial(i+j) / (math.factorial(2*j) * math.factorial(i-j)))
            ans *= tmp
            ans %= INF
        else:
            i = int(broken / 2)
            tmp = i + 1
            for j in range(1, i+1):
                tmp += int(math.factorial(i+j+1) / (math.factorial((2*j)+1) * math.factorial(i-j)))
            ans *= tmp
            ans %= INF
        now = nex
    else:
        last = N
        broken = last - now - 1
        if last - now == 1:
            ng = 1
        if broken % 2 == 0:
            tmp = 1
            i = int(broken / 2)
            for j in range(1, i+1):
                tmp += int(math.factorial(i+j) / (math.factorial(2*j) * math.factorial(i-j)))
            ans *= tmp
            ans %= INF
        else:
            i = int(broken / 2)
            tmp = i + 1
            for j in range(1, i+1):
                tmp += int(math.factorial(i+j+1) / (math.factorial((2*j)+1) * math.factorial(i-j)))
            ans *= tmp
            ans %= INF

if ng:
    print(0)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
# python template for atcoder1
from functools import reduce
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


MOD = 10**9+7
N, M = map(int, input().split())
grid = [True]*(N+1)
broken = [int(input()) for _ in range(M)]
for b in broken:
    grid[b] = False

steps = []
dp = [0]*(N+1)
dp[0] = 1
for i in range(N-1):
    dp[i+1] += dp[i]
    dp[i+2] += dp[i]
    dp[i+1] %= MOD
    dp[i+2] %= MOD

seq = 0
ans = 1
for v in grid:
    if v:
        seq += 1
    else:
        if seq == 0:
            ans = 0
            break
        ans *= dp[seq - 1]
        ans %= MOD
        seq = 0
else:
    ans *= dp[seq-1]
    ans %= MOD
print(ans)

Submission status: Wrong Answer

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

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

if s[n] < 0:
    print(0)
else:
    print(s[n])