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:
from math import floor  
stairs_num, broken_num = tuple(int(i) for i in input().split(" "))
broken_list = []
for i in range(broken_num):
    broken_list.append(int(input()))
trance_num_list = []
if len(broken_list) >= 1 and broken_list[0] == 1:
    trance_num_list.append(0)
else:
    trance_num_list.append(1)
if (len(broken_list) >= 1 and broken_list[0] == 2) or \
 (len(broken_list) >= 2 and broken_list[1] == 2):
    trance_num_list.append(0)
else:
    if trance_num_list[0] == 0:
        trance_num_list.append(1)
    else:
        trance_num_list.append(2)
if stairs_num > 2:
    a = len(broken_list)
    for i in range(stairs_num - 2):
        key = 0
        left = 0
        right = a
        while left < right:
            midle = floor((left + right) / 2)
            if broken_list[midle] < i + 3:
                left = midle + 1
            elif broken_list[midle] == i + 3:
                key = 1
                break
            else:
                right = midle - 1
        if key:
            trance_num_list.append(0)
        else:
            trance_num_list.\
             append((trance_num_list[-1] + trance_num_list[-2]) % 1000000007)
print(trance_num_list[stairs_num - 1])

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
mod = 10 ** 9 + 7

def fibonacci(n):
  if n == 1:
    return 1
  if n == 2:
    return 2
  
  return fibonacci(n - 1) + fibonacci(n - 2)


temp = 0
pos = 0
for i in range(M):
  if pos == i:
    print(0)
    break
    
  temp += fibonacci(i - 1 - pos) % mod
  pos = i + 1
print(temp)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Wed Jun 19 17:29:01 2019

@author: makigon
"""
mod = 10 ** 9 + 7
N, M = map(int, input().split())
a = [int(input()) for i in range(M)]

aset = set(a)
f = [0 for i in range(N)]
f[0] = 1
if 1 in a and len(a)>=2 :
    f[1] = 0
elif 1 not in a and len(a)>=2:
    f[1] = 1

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

if N == 1:
    print(f[N-1])
else:       
    print((f[N-1]+f[N-2]) % mod)

Submission status: Wrong Answer

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

f = []
f.append(1)
if 1 in a:
    f.append(0)
else:
    f.append(1)

for i in range(2,N):
    if i in a:
        f.append(0)
    else:
        f.append(f[i-1]+f[i-2])
        
print((f[N-1]+f[N-2])%1000000007)

Submission status: Wrong Answer

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

f = [0 for i in range(N)]
f[0] = 1
if 1 in a:
    f[1] = 0
else:
    f[0] = 1

for i in range(2,N):
    if i in a:
        continue
    else:
        f[i] = f[i-1]+f[i-2]
        
print((f[N-1]+f[N-2])%1000000007)

Submission status: Wrong Answer

Solution code:
#ABC129-C
N,M=map(int,input().split())
a=[]
num=0 #N段までの行き方
check=0 #行けるかどうか
for i in range(M):
    a.append(int(input()))

for i in range(M-1):
    dif=a[i+1]-a[i]
    if dif==1:
        check=1
        break
        
f={}
f[0]=0 #番号を段数と一致させるため
if (1 in a)==True: #１が壊れているとき
    f[1]=0
else:
    f[1]=1
if (2 in a)==True: #１が壊れているとき
    f[2]=0
else:
    f[2]=2

if check==0:
    for i in range(1,N-1): #1~N-2
        if any(i+2==a[k] for k in range(M)): #壊れている階段は、２段前に見つけておく。
            f[i+2]=0
            continue
        f[i+2]=f[i+1]+f[i]
    num=f[N]

#for i in range(101):
    #print(str(i)+":"+str(f[i]))
print(num%1000000007)

Submission status: Wrong Answer

Solution code:
import math
# 組み合わせ
def ncr(n, r):
	return int(math.factorial(n) / (math.factorial(r) * math.factorial(n-r)))


n, m = map(int, input().split(' '))
# n, m = map(int, "100 5".split(' '))
# brokens = [int(input()) for _ in range(m)]
# brokens = [1, 23, 45, 67, 89]
brokens = [0 for _ in range(m)]
for i in range(m):
	brokens[i] = int(input())

steps = [0 for _ in range(m+1)]

# 移動する段数
if not m == 0:
	steps[0] = brokens[0] - 1
	steps[m] = n - (brokens[m-1] + 1)
else:
	steps[0] = n
for i in range(1, m):
	steps[i] = (brokens[i] - 1) - (brokens[i-1] + 1)

ans = 1
for i in range(m+1):
	stepComb = 1

	if(steps[i] < 0):
		ans = 0
		break
	
	twos = steps[i]//2

	for t in range(1, twos+1):
		stepComb += ncr((steps[i]-t), t)
	
	ans *= stepComb

print(ans % 1000000007)

Submission status: Wrong Answer

Solution code:
z = input().split()
z = [ int(x) for x in z]
broken = []
for i in range(z[1]):
    broken.append(input())
#print(broken)

max_step = z[0] 
import numpy as np

all_possible = []

def steps(cand):
  tmp = np.zeros_like(cand)
  for j in range(len(cand)):
    tmp[j] = sum(cand[:j+1])
  return tmp


count = 0
all_count = 0

for i in range(int(max_step/2), max_step+1):
    #iは段の数
        
    import itertools
    A = [1 , 2 ]
    for v in itertools.product(A, repeat = i):
      if sum(v) == max_step:
        all_count += 1
        for b in broken:
          if list(v).count(int(b)) > 0:
            count += 1
            break
        
#         all_possible.append(steps(v))
          
 

#for i in range(len(all_possible)):
  #all_possible[i] = steps(all_possible[i])
#  all_count += 1
 # for b in broken:
    #print( list(all_possible[i]).count(int(b)))
  #  if  list(all_possible[i]).count(int(b)) > 0:
    #    all_possible[i]= [0,0]
       # count += 1
        
print((all_count - count)%1000000007)

Submission status: Wrong Answer

Solution code:
z = input().split()
z = [ int(x) for x in z]
broken = []
for i in range(z[1]):
    broken.append(input())
#print(broken)

max_step = z[0] 
import numpy as np

all_possible = []

def steps(cand):
  tmp = np.zeros_like(cand)
  for j in range(len(cand)):
    tmp[j] = sum(cand[:j+1])
  return tmp


count = 0
all_count = 0

for i in range(int(max_step/2), max_step+1):
    #iは段の数
        
    import itertools
    A = [1 , 2 ]
    for v in itertools.product(A, repeat = i):
      if sum(v) == max_step:
        all_count += 1
        for b in broken:
          if list(v).count(int(b)) > 0:
            count += 1
        
#         all_possible.append(steps(v))
          
 

#for i in range(len(all_possible)):
  #all_possible[i] = steps(all_possible[i])
#  all_count += 1
 # for b in broken:
    #print( list(all_possible[i]).count(int(b)))
  #  if  list(all_possible[i]).count(int(b)) > 0:
    #    all_possible[i]= [0,0]
       # count += 1
        
print((all_count - count)%1000000007)

Submission status: Wrong Answer

Solution code:
z = input().split()
z = [ int(x) for x in z]
broken = []
for i in range(z[1]):
    broken.append(input())
#print(broken)

max_step = z[0] 
import numpy as np

all_possible = []
candidate = np.ones(max_step)

def steps(cand):
  tmp = np.zeros_like(cand)
  for j in range(len(cand)):
    for i in range(len(cand[0])):
        tmp[j][i] = sum(cand[j][:i+1])
  return tmp

original_step = []
template_steps = []
for i in range(int(max_step/2), max_step+1):
    template_steps = []
    #iは段の数
    #original_step.append(np.ones(i))
    
    
    #i = 5  1 = 0 ,2 = 5
    #i = 10 1 = 10, 2 = 0
    # 1 ... (i - 5) * 2  2 ... -1 * i + 10
    #1... (i - max_step/2)  2...-1 * i  + max_step
    #num_1 =int( (i - max_step/2)*2)
    #num_2 = (-1 * i + max_step)
    #for i in range(num_1):
     #   template_steps.append(1)
    #for i in range(num_2):
      #  template_steps.append(2)
        
    import itertools
    arrays = []
    #for v in itertools.permutations(template_steps):
      #  arrays.append(v)
    A = [1 , 2 ]
    for v in itertools.product(A, repeat = i):
      arrays.append(v)

    #array_unique = list(set(arrays))
    #print(arrays)
    all_possible.append(arrays)

    
count = 0
all_count = 0
for i in range(len(all_possible)):
  #print(i)
  all_possible[i] = steps(all_possible[i])
  
  for j in range(len(all_possible[i])):
    all_count += 1
    
    for b in broken:
      if  list(all_possible[i][j]).count(int(b)) > 0:
        all_possible[i][j]= 0
        count += 1
        
print((all_count - count)%1000000007)

Submission status: Wrong Answer

Solution code:
z = input().split()
z = [ int(x) for x in z]
broken = []
for i in range(z[1]):
    broken.append(input())
#print(broken)

max_step = z[0] 
import numpy as np

all_possible = []
candidate = np.ones(max_step)

def steps(cand):
  tmp = np.zeros_like(cand)
  for j in range(len(cand)):
    for i in range(len(cand[0])):
        tmp[j][i] = sum(cand[j][:i+1])
  return tmp

original_step = []
template_steps = []
for i in range(int(max_step/2), max_step+1):
    template_steps = []
    #iは段の数
    original_step.append(np.ones(i))
    #i = 5  1 = 0 ,2 = 5
    #i = 10 1 = 10, 2 = 0
    # 1 ... (i - 5) * 2  2 ... -1 * i + 10
    #1... (i - max_step/2)  2...-1 * i  + max_step
    num_1 =int( (i - max_step/2)*2)
    num_2 = (-1 * i + max_step)
    for i in range(num_1):
        template_steps.append(1)
    for i in range(num_2):
        template_steps.append(2)
        
    import itertools
    arrays = []
    for v in itertools.permutations(template_steps):
        arrays.append(v)

    array_unique = list(set(arrays))
    #print(array_unique)
    all_possible.append(array_unique)

    
count = 0
all_count = 0
for i in range(len(all_possible)):
  #print(i)
  all_possible[i] = steps(all_possible[i])
  for j in range(len(all_possible[i])):
    all_count += 1
    for b in broken:
      if  list(all_possible[i][j]).count(int(b)) > 0:
        all_possible[i][j]= 0
        count += 1
        
print((all_count - count)%1000000007)

Submission status: Wrong Answer

Solution code:
z = input().split()
z = [ int(x) for x in z]
broken = []
for i in range(z[1]):
    broken.append(input())
#print(broken)

max_step = z[0] 
import numpy as np

all_possible = []
candidate = np.ones(max_step)

def steps(cand):
  tmp = np.zeros_like(cand)
  for j in range(len(cand)):
    for i in range(len(cand[0])):
        tmp[j][i] = sum(cand[j][:i+1])
  return tmp

original_step = []
template_steps = []
for i in range(int(max_step/2), max_step+1):
    template_steps = []
    #iは段の数
    original_step.append(np.ones(i))
    #i = 5  1 = 0 ,2 = 5
    #i = 10 1 = 10, 2 = 0
    # 1 ... (i - 5) * 2  2 ... -1 * i + 10
    #1... (i - max_step/2)  2...-1 * i  + max_step
    num_1 =int( (i - max_step/2)*2)
    num_2 = (-1 * i + max_step)
    for i in range(num_1):
        template_steps.append(1)
    for i in range(num_2):
        template_steps.append(2)
        
    import itertools
    arrays = []
    for v in itertools.permutations(template_steps):
        arrays.append(v)

    array_unique = list(set(arrays))
    #print(array_unique)
    all_possible.append(array_unique)

    
count = 0
all_count = 0
for i in range(len(all_possible)):
  #print(i)
  all_possible[i] = steps(all_possible[i])
  for j in range(len(all_possible[i])):
    all_count += 1
    for b in broken:
      if  list(all_possible[i][j]).count(int(b)) > 0:
        all_possible[i][j]= 0
        count += 1
        
print(all_count - count)

Submission status: Wrong Answer

Solution code:
z = input().split()
z = [ int(x) for x in z]
broken = []
for i in range(z[1]):
    broken.append(input())
#print(broken)

max_step = z[0] 
import numpy as np

all_possible = []
candidate = np.ones(max_step)

def steps(cand):
  tmp = np.zeros_like(cand)
  for j in range(len(cand)):
    for i in range(len(cand[0])):
        tmp[j][i] = sum(cand[j][:i+1])
  return tmp

#all_possible.append(steps(candidate))
#print(steps(candidate))

original_step = []
template_steps = []
for i in range(int(max_step/2), max_step+1):
    template_steps = []
    #iは段の数
    original_step.append(np.ones(i))
    #i = 5  1 = 0 ,2 = 5
    #i = 10 1 = 10, 2 = 0
    # 1 ... (i - 5) * 2  2 ... -1 * i + 10
    #1... (i - max_step/2)  2...-1 * i  + max_step
    num_1 =int( (i - max_step/2)*2)
    num_2 = (-1 * i + max_step)
    for i in range(num_1):
        template_steps.append(1)
    for i in range(num_2):
        template_steps.append(2)
        
    import itertools
    arrays = []
    for v in itertools.permutations(template_steps):
        arrays.append(v)

    array_unique = list(set(arrays))
    #print(array_unique)
    all_possible.append(array_unique)

#    print(array_unique)
    
#   print(steps(array_unique))

    
#print(all_possible)

for i in range(len(all_possible)):
  #print(i)
  all_possible[i] = steps(all_possible[i])
  
  #print(all_possible[i], list(all_possible[i]).count("1"))
  for j in range(len(all_possible[i])):
    for b in broken:
      #print(all_possible[i][j], list(all_possible[i][j]).count(int(b) )
      if  list(all_possible[i][j]).count(int(b)) > 0:
        all_possible[i][j]= 0

#print(all_possible)

count = 0
for i in range(len(all_possible)):
  for j in range(len(all_possible[i])):
    if any(all_possible[i][j] ):
      count+=1
print(int(count % 1000000007))

Submission status: Wrong Answer

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

for _ in range(n):
    b.append(b[-1] + b[-2])

if m == 0:
    ans = b[n + 1]
else:
    c.append(a[0])
    for i in range(m - 1):
        c.append(a[i + 1] - a[i] - 1)
        c.append(n - a[m - 1])

        for i in c:
            ans *= b[i]

print(ans % 1000000007)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
a = [int(input())-1 for _ in range(M)]
mod =  1000000007
ret = [0] * N
for i in range(N):
    if i in a:
        continue
    elif i < 2:
        ret[i] = ret[i]+1
    else:
        ret[i] = ret[i-2] + ret[i-1]
        if ret[i] == 0:
            break


print(ret[len(ret)-1]%mod)

Submission status: Wrong Answer

Solution code:
n,m=[int(i) for i in input().split()]
a=[int(input()) for _ in range(m)]
broken=[False]*(n+1)
dp=[1]+[0]*100010
for i in range(m):
    broken[i]=True
for i in range(1,n+1):
    if broken[i]:
        dp[i]=0
    else:
        try:
            dp[i]=dp[i-1]+dp[i-2]
        except:
            dp[i]=dp[i-1]
        dp[i]%=1000000007
print(dp[n])

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
if N == 1:
    print(0 if M == 1 else 1)
    exit()

dp = [0] * N
dp[N - 1] = 1
dp[N - 2] = 1
lst = [int(input()) for _ in range(M)]

for x in reversed(range(N -2)):
    if x + 1 in lst:
        dp[x] = 0
    else:
        dp[x] = dp[x + 1] + dp[x + 2]

print(dp[0] + dp[1] % 1000000007)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
print(n,m)
dp = [-1]*(n+1)
for i in range(m):
    dp[int(input())] = 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])%1000000007
print(dp[n])

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
A = []
for i in range(M):
    A.append(int(input()))
print(A)
count = [0] * (N+1)
count[0] = 1
mod = 10 ** 9 + 7
if 1 in A:
    if 2 in A:
        print(0)
        exit()
    count[2] = 1
    start = 3
else:
    count[1] = 1
    start = 2
for i in range(start, N+1):
    if i in A:
        continue
    count[i] = count[i-1] + count[i-2]
    count[i] %= mod

print(count[N])

Submission status: Wrong Answer

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

count = [0] * (N+1)
count[0] = 1
if 1 in A:
    if 2 in A:
        print(0)
        exit()
    count[2] = 1
    start = 2
else:
    count[1] = 1
    start = 1
for i in range(start, N+1):
    if i in A:
        continue
    count[i] = count[i-1] + count[i-2]
    count[i] %= 10**9 + 7

print(count[N])

Submission status: Wrong Answer

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

count = [0] * (N+1)
count[0] = 1
if 1 in A:
    if 2 in A:
        print(0)
        exit()
    count[1] = 1
    start = 2
else:
    count[1] = 1
    start = 1
for i in range(start, N+1):
    if i in A:
        continue
    count[i] = count[i-1] + count[i-2]
    count[i] %= 10**9 + 7

print(count[N])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
MOD = 10 ** 9 + 7
dp = [0] * (N+1)
dp[0] = 1
a = set()
for _ in range(M):
    a.add(int(input()))

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

print(dp[N])

Submission status: Wrong Answer

Solution code:
import sys

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

def process(n): #n段目まで何通りでいけるか？
    if n == -1: # nが-1
        return 1
    if n < -1:
        return 0
    if n in a:
        memo[n] = 0
        return 0
    if n == 0:
        memo[0] = 1
        return 1
    cnt = memo[n-1] + memo[n-2]
    memo[n] = cnt
    return cnt

for i in range(N):
    process(i)

print(process(N-1) % 1000000007)

Submission status: Wrong Answer

Solution code:
import sys
import math

nm=list(map(int,input().split()))
N=nm[0]
M=nm[1]

A=[]
at=0
for i in range(M):
    a=int(input())
    if ((a-at)==1)& (a!=1):
        print(0)
        sys.exit()
    A.append(a)
    at=a

at=-1
np=1
for a in A:
    n=0
    ad=a-at-2
    q,mod=divmod(ad,2)
    #print('ad , q = {},{}'.format(ad,q))
    for i in range(q+1):
        c1=q-i
        c2=int(mod+2*i)
        #print(c1,c2)
        nt=int(math.factorial(c1+c2)/(math.factorial(c1)*math.factorial(c2)))
        n+=nt
    #print(n)
    np=np*n
    at=a

ad=N-at-1
q,mod=divmod(ad,2)
#print('ad , q = {},{}'.format(ad,q))  
n=0
for i in range(q+1):
    c1=q-i
    c2=int(mod+2*i)
    #print(c1,c2)
    nt=int(math.factorial(c1+c2)/(math.factorial(c1)*math.factorial(c2)))
    n+=nt
#print(n)
np=n*np

#print(int(np))
print(int(np%1000000007))

Submission status: Wrong Answer

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

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

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

print(dp)
print(dp[N]%1000000007)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
A = list(map(int,[input() for i in range(M)]))
dp = []
dp.append(1) # 0段目
if 1 in A: # 1段目
  dp.append(0) 
else :
  dp.append(1) 

for i in range(2,N+1):  
  if i in A:
    dp.append(0)
  else :
    dp.append(dp[i-1]+dp[i-2])
print(dp[N])

Submission status: Wrong Answer

Solution code:
maxNum, brokenCount = map(int,input().split(" "))

brokenIndexSet = set([int(input()) for i in range(brokenCount)])

ans = [0] * (maxNum + 1)
ans[0] = 1

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

print(ans[maxNum])

Submission status: Wrong Answer

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

li = [0]*10**6
lia = [-1]
ans = 1
mod = 1000000007

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

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

lia.append(n+1)

for i in range(len(lia)-1):
    if lia[i+1]-lia[i] != 1:
        ans *= li[lia[i+1]-lia[i]-2]
    else:
        ans = 0
    ans %= mod

print(ans%mod)

Submission status: Wrong Answer

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

if n==1:
  print(1)
  exit()
if n==2:
  print(2-m)
  exit()
kumiawase = [0 for i in range(n+1)]
kumiawase[0] = 1
kumiawase[1] = 1
kumiawase[2] = 2
for i in range(3,n+1):
  kumiawase[i] = kumiawase[i-2] + kumiawase[i-1]

if m==0:
  print(kumiawase[n])
  exit()
if m==1:
  if a[0]==1 or a[0]==n-1:
    print(kumiawase[n-2])
  else:
    print(kumiawase[a[0]-2]*kumiawase[n-1-a[0]])
houhou = 1
if a[0] != 1:
  houhou *= kumiawase[a[0]-1]
houhou %= 1000000007
if a[m-1] != n-1:
  houhou *= kumiawase[n-1-a[m-1]]
houhou %= 1000000007
for i in range(1,m):
  if a[i]-a[i-1]==1:
    print(0)
    exit()
  elif a[i]-a[i-1]==2:
    continue
  houhou *= kumiawase[a[i]-a[i-1]-2]
  houhou %= 1000000007
print(houhou)

Submission status: Wrong Answer

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

if n==1:
  print(1)
  exit()
if n==2:
  print(2-m)
  exit()
kumiawase = [0 for i in range(n+1)]
kumiawase[0] = 0
kumiawase[1] = 1
kumiawase[2] = 2
for i in range(3,n+1):
  kumiawase[i] = kumiawase[i-2] + kumiawase[i-1]

if m==0:
  print(kumiawase[n])
  exit()
if m==1:
  if a[0]==1 or a[0]==n-1:
    print(kumiawase[n-2])
houhou = 1
if a[0] != 1:
  houhou *= kumiawase[a[0]-1]
houhou %= 1000000007
if a[m-1] != n-1:
  houhou *= kumiawase[n-1-a[m-1]]
houhou %= 1000000007
for i in range(1,m):
  if a[i]-a[i-1]==1:
    print(0)
    exit()
  elif a[i]-a[i-1]==2:
    continue
  houhou *= kumiawase[a[i]-a[i-1]-2]
  houhou %= 1000000007
print(houhou)

Submission status: Wrong Answer

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

if n==1:
  print(1)
  exit()
if n==2:
  print(2-m)
  exit()
kumiawase = [0 for i in range(n+1)]
kumiawase[0] = 0
kumiawase[1] = 1
kumiawase[2] = 2
for i in range(3,n+1):
  kumiawase[i] = kumiawase[i-2] + kumiawase[i-1]

if m==0:
  print(kumiawase[n])
  exit()
if m==1:
  if a[0]==1 or a[0]==n-1:
    print(kumiawase[n-1])
houhou = 1
if a[0] != 1:
  houhou *= kumiawase[a[0]-1]
houhou %= 1000000007
if a[m-1] != n-1:
  houhou *= kumiawase[n-1-a[m-1]]
houhou %= 1000000007
for i in range(1,m):
  if a[i]-a[i-1]==1:
    print(0)
    exit()
  elif a[i]-a[i-1]==2:
    continue
  houhou *= kumiawase[a[i]-a[i-1]-2]
  houhou %= 1000000007
print(houhou)

Submission status: Wrong Answer

Solution code:
import itertools


def main():
    n, m = map(int, input().split())
    a = []
    ans = 0
    for i in range(m):
        a.append(int(input()))

    for numStep in range(-(-n // 2), n):
        step = []
        numDoubleStep = n - numStep
        for i in range(numDoubleStep):
            step.append(2)
        for i in range(numStep-numDoubleStep):
            step.append(1)
        step = list(set(itertools.permutations(step)))
        # print(step)  # debug
        for stepList in step:
            if isSuccess(stepList, a):
                ans += 1
    print(ans % 1000000007)
    return


def isSuccess(stepList, a):
    stepNum = 0
    for steps in stepList:
        stepNum += steps
        if stepNum in a:
            return False
    return True


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

readline = sys.stdin.readline

N, M = map(int, readline().split())
A = [int(readline()) for i in range(M)]
P = 1000000007

A = A + [N + 1]
ans = 1


current = 0

_count = 0
for a in A:
    diff = a - 1 - current
    current = a + 1

    if diff < 0:
        ans = 0
        break
    
    s = 1
    s_total = 1
    for x in range(1, diff // 2 + 1):
        _count += 1
        y = diff - x * 2
        s = s * (y + 1) * (y + 2) // (x + y + 1) // x
        s = s % P
        s_total = (s_total + s) % P
    
    ans = (ans * s_total) % P

print(ans)

Submission status: Wrong Answer

Solution code:
import sys

readline = sys.stdin.readline

N, M = map(int, readline().split())
A = [int(readline()) for i in range(M)]
P = 1000000007

A = A + [N + 1]
ans = 1


current = 0

_count = 0
for a in A:
    diff = a - 1 - current
    current = a + 1

    if diff < 0:
        ans = 0
        break
    
    s = 1
    s_total = 1
    for x in range(1, diff // 2 + 1):
        _count += 1
        y = diff - x * 2
        s = s * (y + 1) * (y + 2) // (x + y + 1) // x
        #s = s % P
        #s_total = (s_total + s) % P
    
    ans = (ans * s_total) % P

print(ans)

Submission status: Wrong Answer

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

print(b[n])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
#C問題
N,M = map(int,input().split())
a = []
for i in range(M):
    a.append(int(input()))
    
fibo = []
for i in range(N):
    if i == 0:
        fibo.append(1)
    elif i == 1:
        fibo.append(2)
    else:
        fibo.append(fibo[-1]+fibo[-2])
    
lens = []
nowlen = 1
for i in range(N):
    if i+1 in a:
        if nowlen != 1:
            lens.append(nowlen-1)
        else:
            lens.append(nowlen)
        nowlen = 0
    else:
        nowlen+=1
        
lens.append(nowlen-1)

lenlens = len(lens)
count = 1
for i in range(lenlens):
    if i == 0 and lens[i] == 0:
        pass
    else:
        ll = lens[i]
        if ll == 0:
            count*=0
        else:
            count*=fibo[lens[i]-1]

print(count%1000000007)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

dp = np.zeros(2, dtype=np.int64)
dp[0] = 1
dp[1] = 0 if 1 in holes else 1

for i in range(2, N+1):
    if i in holes:
        tmp = dp[1]
        dp[1] = 0
        dp[0] = tmp
    else:
        tmp = dp[1]
        dp[1] = dp[0] + tmp
        dp[0] = tmp

mod = 1e9 + 7
print(int(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
    
N,M = map(int,input().split())

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

step = [broken[i+1]-broken[i] for i in range(M+1)]

if 1 in step[1:-1]:
    print('0')
else:
    ans = 1
    for s in step:
        if s<2:
            continue
        a = Fib(s+2)
        ans = a*ans
    print(str(ans%1000000007))

Submission status: Wrong Answer

Solution code:
st=[1,1]
for i in range(10**5+1):
  st.append((st[-1]+st[-2])%1000000007)
st.append(0)
n,m=list(map(int,input().split()))
ret=1
x=-1
for i in range(m):
  y=int(input())
  ret=(ret*st[y-x-2])%1000000007
  print(x,y,y-x-2,st[y-x-2])
  x=y
ret=(ret*st[n-x-1])%1000000007
print(x,n,n-x-2,st[n-x-2])
print(ret)

Submission status: Wrong Answer

Solution code:
st=[1,1]
for i in range(10**5+1):
  st.append((st[-1]+st[-2])%1000000007)
st.append(0)
n,m=list(map(int,input().split()))
ret=1
x=0
for i in range(m):
  y=int(input())
  x=-1 if y==1 else x
  ret=(ret*st[y-x-2])%1000000007
  x=y
ret=(ret*st[n-x-1])%1000000007
print(ret)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
a_list=[]
for i in range(0,m):
     a_list.append(int(input()))
a=0
b=1
k=0
for i in range(0,n):
    if i+1 in a_list:
        (a,b)=(b,0)
    else:
        (a,b)=(b,a+b)
print(b)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
a_list=[]
for i in range(0,m):
  a_list.append(int(input()))
a=0
b=1
for i in range(0,n):
  if i+1 not in a_list:
  	(a,b)=(b,a+b)
  else:
    (a,b)=(b,0)
print(b)

Submission status: Wrong Answer

Solution code:
import itertools

lis=list(map(int,input().split()))
alist=[-1]
ans=1
mod=(10**9)+7
for i in range(lis[1]):
    alist.append(int(input()))
alist.append(lis[0]+1)

for i in range(lis[1]+1):
    l=alist[i+1]-alist[i]-2
    tmp=0
    t=int((l+l%2)/2)
    h=int((l-l%2)/2)
    for j in range(h+1):
        tmp+=len(list(itertools.combinations(range(t+j),h-j)))%mod
    ans=ans*tmp
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
line = input().split()
N = int(line[0])
M = int(line[1])
broken = []
count = 0
step = []
def check(value):
  if count < M:
    return broken[count]==value
  else:
    return False

for i in range(M):
  a = int(input())
  broken += [a]
if check(1):
  step+=[0]
  count += 1
else:
  step +=[1]
if check(2):
  step += [0]
  count += 1
else:
  step += [1+step[0]]
for j in range(2, N):
  if check(j+1):
    step += [0]
    count += 1
  else:
    step += [step[j-2]+step[j-1]]
ans = step[N-1]%(10^9+7)
print(ans)

Submission status: Wrong Answer

Solution code:
line = input().split()
N = int(line[0])
M = int(line[1])
broken = []
count = 0
step = []
def check(value):
  if count < M:
    return broken[count]==value
  else:
    return False

for i in range(M):
  a = int(input())
  broken += [a]
if check(1):
  step+=[0]
  count += 1
else:
  step +=[1]
if check(2):
  step += [0]
  count += 1
else:
  step += [1+step[0]]
for j in range(2, N):
  if check(j+1):
    step += [0]
    count += 1
  else:
    step += [step[j-2]+step[j-1]]
ans = step[N-1]%(10^9+7)
print(ans)