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 math

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

result = 0

N, M = map(int,input().split())
if M == 0:
    List = [0,0]
else:
    List = [int(input()) for i in range(M)]

if M == 0:
    for i in range(math.floor((N-1)/2) + 1):
        result += cmb(N - i,i)% 1000000007 
    result = result % 1000000007 
    print(result)

else:
    for i in range(math.floor((List[0]-1)/2) + 1):
        result += cmb(List[0]-1-i,i) 
            
    for i in range(M-1):
        if List[i+1] - List[i] == 1:
            result = 0
            break
        else:
            tmp = 0
            for j in range(math.floor((List[i+1]-List[i]-2)/2) + 1):
                tmp += cmb(List[i+1]-List[i]-2-j,j)
            result = result * tmp

    tmp = 0
    for i in range(math.floor((N - List[M-1]-1)/2) + 1):
        tmp += cmb(N - List[M-1]-1-i,i) 

    result = result * tmp
    result = result % 1000000007 
    print(result)

Submission status: Wrong Answer

Solution code:
mod = 1000000007

def add(a, b):
    return (a + b) % mod

def sub(a, b):
    return (a + mod - b) % mod

def mul(a, b):
    return ((a % mod) * (b % mod)) % mod
    
a = []
N, M = map(int, input().split())
for i in range(M):
    a.append(int(input()))

results = []

flag = True

for m in range(1, M):
    if a[m] - a[m - 1] == 1:
        flag = False
        break

flag_end = True
if M == 0:
    flag_end = False

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

if flag and flag_end:
    for m in range(M):
        if m == 0:
            results.append(Fib(a[m] + 1))
        else:
            results.append(Fib(a[m] - a[m - 1]))
    results.append(Fib(N - a[m] + 1))
    result = 1
    for i in range(len(results)):
        result = mul(result, results[i])
    print(result)
elif not flag:
    print(0)
else:
    print(Fib(N + 2))

Submission status: Wrong Answer

Solution code:
import math
N,M = map(int, input().split())
def C(a,b):
    return math.factorial(a+b)/(math.factorial(a)*math.factorial(b))
def pattern(n):
    ans = 0
    i = 0
    while n - 2*i >= 0:
        ans += C(n-i*2,i)
        i += 1
    return ans
ab = 0
ans = 1
mod = 10**9 + 7
for i in range(M):
    aa = int(input())
    if aa != 1:
        n = aa-ab-2
        ans *= pattern(n)
        ans = ans%mod
    ab = aa
if ab != N-1:
    n = N-ab-2
    ans *= pattern(n)
    ans = ans%mod
print(int(ans))

Submission status: Wrong Answer

Solution code:
def cmb(n, r):
    return fct[n] * inv[r] * inv[n - r] % md

md = 10 ** 9 + 7
n, m = map(int, input().split())
ans = 1
pa = 0
ds = []
for _ in range(m):
    a = int(input())
    if a == 1:
        pa = 1
        continue
    d = a - pa - 1
    if d == 0:
        print(0)
        exit()
    ds.append(d)
    pa = a
ds.append(n - pa - 1)
mxd = max(ds)
fct = [1, 1]
inv = [1] * (mxd + 1)
s = 1
for i in range(2, mxd + 1):
    s = (s * i) % md
    fct.append(s)
inv[-1] = s = pow(fct[-1], md - 2, md)
for i in range(mxd, 1, -1):
    s = s * i % md
    inv[i - 1] = s
for d in ds:
    tmp = 0
    for i in range(d // 2 + 1):
        tmp = (tmp + cmb(d - i, i)) % md
    ans = (ans * tmp) % md
print(ans)

Submission status: Wrong Answer

Solution code:
import math
import numpy as np

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

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

diff = np.array(A)[1:] - np.array(A)[:-1]
if any(diff == 1) :
    print(0)
else :
    S = []
    if M > 0 :
        A.insert(0, 1)
        A.insert(N-1, N + 1)
        D = list(np.array(A)[1:] - np.array(A)[:-1] - 1)
    else :
        D = [N + 1]
    R = []
    for d in D :
        P = d - 1
        K = int(P / 2)
        T = 1
        for k in range(1, K+1) :
            T += combinations_count(P - k, k)
        R.append(T)
    ans = R[0]
    #print(R)
    for r in R[1:] :
        #print(ans)
        ans = ans * r % (10 ** 9 + 7)
    print(ans)

Submission status: Wrong Answer

Solution code:
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 += 1
    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 += 1
      sum *= cnt

print(sum % 1000000007)

Submission status: Wrong Answer

Solution code:
import math

N,M=map(int,input().split())
A=[]
result=1
judge_out=0


a0=0
a=0
stairs_start=0
stairs_end=0

for i in range(M):
    a=int(input())
    result_i=0

    if a!=1:
        if a-a0==1 or a==N:
            result=0

        if judge_out!=1:
            if i==0:
                stairs_start=0
            else:
                stairs_start=a0+1
            stairs_end=a-1
            target=stairs_end-stairs_start
            n=target//2
            for j in range(n+1):
                if j==n and target%2==0:
                    result_i+=1
                else:
                    result_i+=int(math.factorial(target-j)/(math.factorial(j)*math.factorial(target-2*j)))
            result=result*result_i
    a0=a

if stairs_start<N:
    result_i=0
    stairs_start=a0+1
    stairs_end=N
    target=stairs_end-stairs_start
    n=target//2
    for j in range(n+1):
        if j==n and target%2==0:
            result_i+=1
        else:
            result_i+=int(math.factorial(target-j)/(math.factorial(j)*math.factorial(target-2*j)))
    result=result*result_i

print(result%1000000007)

Submission status: Wrong Answer

Solution code:
import numpy as np
N,M = map(int,input().split())
ans = []
a = [int(input()) for i in range(M)]
a.append(N)
a.append(0)
a.sort()
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
for j in range(1,M+2):
  if a[j] - a[j-1] == 1:
    continue
  else:
    m = a[j] - a[j-1] - 1 
    ans.append(fib(m+1))
print(ans)
print(np.prod(ans) % 1000000007)

Submission status: Wrong Answer

Solution code:

N, M = list(map(int, input().split()))
A = [int(input()) for _ in range(M)]
MOD = 1000000007

if M == 0:
    B = []
    B.append(N-1)
elif M == 1:
    B = []
    B.append(A[0])
    B.append(N - A[0])

else:
    B = [A[0]]
    for i in range(M-1):
        B.append(A[i+1] - A[i] - 1)
    B.append(N - A[M-1])


ans = 1
if 0 in B:
    ans = 0
else:
    F = [1,1]
    for n in B:
        while len(F) < n:
            F.append(F[-1] + F[-2])
        now = F[n-1]
        ans = ans * now % MOD
print(ans)

Submission status: Wrong Answer

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

diff_list = []
before_pos = 0
for i in range(m):
  if before_pos == 0:
    diff_list.append(list[i]-before_pos)
  else:
    diff_list.append(list[i]-before_pos-2)
  before_pos = list[i]
diff_list.append(n-before_pos-1)

max_num = max(diff_list)

ncklist=[]
ncklist.append(0)
for i in range(max_num+1):
  if i == 1:
    ncklist.append(1)
  if i == 2:
    ncklist.append(2)
  if i > 2:
    ncklist.append(ncklist[i-1]+ncklist[i-2])

ptn = 1
for i in diff_list:
  ptn = ptn * ncklist[i]
  if i < 0:
    ptn = 0
mod = ptn % 1000000007
print(mod)

Submission status: Wrong Answer

Solution code:
import sys

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

for i in range(1,len(a)-2):
    if a[i+1]-a[i]==1:
        print(0)
        sys,exit()

b = []
for i in range(1,len(a)):
    if i == 1:
        b.append(a[1]-1-a[0])
    elif i == len(a)-1:
        b.append(a[i]-(a[i-1]+1))
    else:
        b.append(a[i]-1-(a[i-1]+1))

dp = []
for i in range(10**6):
    if i == 0:
        dp.append(1)
        continue
    if i == 1:
        dp.append(1)
        continue
    if i == 2:
        dp.append(2)
        continue
    dp.append((dp[i-1]+dp[i-2])%mod)

for i in range(len(b)):
    l = b[i]
    ans = (ans*dp[l])%mod
    
print(ans)

Submission status: Wrong Answer

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

OK = "O"
BRO = "B"

K = ""
N += 1
for i in range(N):
  if i in Broken:
    K += BRO 
  else:
    K += OK
    
#print(K)

if BRO+BRO in K:
  print(0)
else:
  #count = 1;
  b = 0;
  for i in range(N):
    if i < N-2:
      if K[i] == OK and K[i+1] == OK and K[i+2]==OK:
        #count *= 2
        b += 1
  #print(2**b)
  #print(count)
  count = 2**b
  print(count % 1000000007)

Submission status: Wrong Answer

Solution code:
mod = 1000000007

def add(a, b):
    return (a + b) % mod

def sub(a, b):
    return (a + mod - b) % mod

def mul(a, b):
    return ((a % mod) * (b % mod)) % mod
    
a = []
N, M = map(int, input().split())
for i in range(M):
    a.append(int(input()))

results = []

flag = True

for m in range(1, M):
    if a[m] - a[m - 1] == 1:
        flag = False
        break

flag_end = True
if M == 0:
    flag_end = False

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

if flag and flag_end:
    for m in range(M):
        if m == 0:
            results.append(Fib(a[m] + 1))
        else:
            results.append(Fib(a[m] - a[m - 1]))
    results.append(Fib(N - a[m] + 1))
    result = 1
    for i in range(len(results)):
        result = mul(result, results[i])
    print(result)
elif not flag:
    print(0)
else:
    print(Fib(N + 1))

Submission status: Wrong Answer

Solution code:
import math

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

result = 0

N, M = map(int,input().split())
if M == 0:
    List = [0,0]
else:
    List = [int(input()) for i in range(M)]

if M == 0:
    for i in range(math.floor((N-1)/2) + 1):
        result += cmb(N - 1 - i,i)% 1000000007 
    result = result % 1000000007 
    print(result)

else:
    for i in range(math.floor((List[0]-1)/2) + 1):
        result += cmb(List[0]-1-i,i) 
            
    for i in range(M-1):
        if List[i+1] - List[i] == 1:
            result = 0
            break
        else:
            tmp = 0
            for j in range(math.floor((List[i+1]-List[i]-2)/2) + 1):
                tmp += cmb(List[i+1]-List[i]-2-j,j)
            result = result * tmp

    tmp = 0
    for i in range(math.floor((N - List[M-1]-1)/2) + 1):
        tmp += cmb(N - List[M-1]-1-i,i) 

    result = result * tmp
    result = result % 1000000007 
    print(result)

Submission status: Wrong Answer

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

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

ans = 1
for i in range(1, M+2):
    if (a[i] - a[i-1] == 1) and (a[i] != 1) and (a[i-1] != N-1):
        print(0)
        break
    else:
        ans *= fib[a[i]-a[i-1]-1]
else:
    print(ans % 1000000007)

Submission status: Wrong Answer

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

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

if 1 in lst and not 3 in lst:
  lst2 = [0,1,1]
  for j in range(4,N+1):
    #print(j)
    if j in lst:
      lst2.append(0)
    else:
      #print(lst2,lst2[-1],lst2[-2])
      lst2.append(lst2[-1]+lst2[-2])
elif 2 in lst:
  lst2 = [1,0,1]
  for j in range(4,N+1):
    #print(j)
    if j in lst:
      lst2.append(0)
    else:
      #print(lst2,lst2[-1],lst2[-2])
      lst2.append(lst2[-1]+lst2[-2])
elif 3 in lst and not 1 in lst:
  lst2 = [1,2,0]
  for j in range(4,N+1):
    #print(j)
    if j in lst:
      lst2.append(0)
    else:
      #print(lst2,lst2[-1],lst2[-2])
      lst2.append(lst2[-1]+lst2[-2])
elif 1 in lst and 3 in lst:
  lst2 = [0,1,0]
  for j in range(4,N+1):
    #print(j)
    if j in lst:
      lst2.append(0)
    else:
      #print(lst2,lst2[-1],lst2[-2])
      lst2.append(lst2[-1]+lst2[-2])
else:
  lst2 = [1,2,3]
  for j in range(4,N+1):
    #print(j)
    if j in lst:
      lst2.append(0)
    else:
      #print(lst2,lst2[-1],lst2[-2])
      lst2.append(lst2[-1]+lst2[-2])
#print(lst2)
#print(lst[-1])
#print(lst2[-1])
print(lst2[-1]%1000000007)

Submission status: Wrong Answer

Solution code:
import math

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

result = 0

N, M = map(int,input().split())
if M == 0:
    List = [0,0]
else:
    List = [int(input()) for i in range(M)]

if M == 0:
    for i in range(math.floor((N-1)/2) + 1):
        result += cmb(N - List[M-1]-1-i,i)% 1000000007 
    result = result % 1000000007 
    print(result)

else:
    for i in range(math.floor((List[0]-1)/2) + 1):
        result += cmb(List[0]-1-i,i) 
            
    for i in range(M-1):
        if List[i+1] - List[i] == 1:
            result = 0
            break
        else:
            tmp = 0
            for j in range(math.floor((List[i+1]-List[i]-2)/2) + 1):
                tmp += cmb(List[i+1]-List[i]-2-j,j)
            result = result * tmp

    tmp = 0
    for i in range(math.floor((N - List[M-1]-1)/2) + 1):
        tmp += cmb(N - List[M-1]-1-i,i) 

    result = result * tmp
    result = result % 1000000007 
    print(result)

Submission status: Wrong Answer

Solution code:
def mul(c):
  ANS = 0
  for t, o in zip(range(c, -1, -1), range(0, 2*(c + 1), 2)):
    ans = 1
    for m in range(t + o, max(t, o), -1):
      ans *= m 
    ANS += ans
  return ANS
 
def mul_odd(c):
  ANS = 0
  for t, o in zip(range(c, -1, -1), range(1, 2*c + 3, 2)):
    ans = 1
    for m in range(t + o, max(t, o), -1):
      ans *= m 
    ANS += ans
  return ANS
 
N, M = map(int, input().split())
D = 0
A = [0]
ans = []
aans = 1
for i in range(M + 1):
  if i != M :
  	A.append(int(input()))
  else: 
    A.append(N + 1)
  diff = A[i + 1] - A[i]
  if (diff == 1) & (i != 0):
    print(0)
    D = 1
    break
  
  temp = diff -1
  if (temp) % 2 == 0:
    aans *= mul(temp//2)
  else:
    aans *= mul_odd(temp//2)
if D == 0:   
	print(aans % 1000000007)

Submission status: Wrong Answer

Solution code:
def step(n):
    if n == 0:
        return 1
    steps = [0 for i in range(n + 2)]
    steps[1] = 1
    steps[2] = 2
    for i in range(3, n + 1):
        steps[i] = steps[i - 1] + steps[i - 2]
    return steps[n]

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

a.append(n)

sum = 1

for i in range(m + 1):

  if i == 0:
    sum *= step(a[i] - 1)
    continue
  
  elif i == m:
    sum *= step(a[m] - a[m-1] -1)
    
  elif a[i] - a[i-1] == 1:
    sum = 0
    break

  else:
    sum *= step(a[i] - a[i-1] -2)

print(sum % 1000000007)

Submission status: Wrong Answer

Solution code:
mod = 1000000007

def add(a, b):
    return (a + b) % mod

def sub(a, b):
    return (a + mod - b) % mod

def mul(a, b):
    return ((a % mod) * (b % mod)) % mod
    
a = []
N, M = map(int, input().split())
for i in range(M):
    a.append(int(input()))

results = []

flag = True

for m in range(1, M):
    if a[m] - a[m - 1] == 1:
        flag = False
        break

flag_end = True
if M == 0:
    flag_end = False

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

if flag and flag_end:
    for m in range(M):
        if m == 0:
            results.append(Fib(a[m] + 1))
        else:
            results.append(Fib(a[m] - a[m - 1]))
    results.append(Fib(N - a[m] + 1))
    result = 1
    for i in range(len(results)):
        result = mul(result, results[i])
    print(result)
else:
    print(0)

Submission status: Wrong Answer

Solution code:
import sys

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

for i in range(1,len(a)-2):
    if a[i+1]-a[i]==1:
        print(0)
        sys,exit()

b = []
for i in range(1,len(a)):
    if i == 1:
        b.append(a[1]-1-a[0])
    elif i == len(a)-1:
        b.append(a[i]-(a[i-1]+1))
    else:
        b.append(a[i]-1-(a[i-1]+1))

dp = []
for i in range(10**5):
    if i == 0:
        dp.append(1)
        continue
    if i == 1:
        dp.append(1)
        continue
    if i == 2:
        dp.append(2)
        continue
    dp.append((dp[i-1]+dp[i-2])%mod)

for i in range(len(b)):
    l = b[i]
    ans = (ans*dp[l])%mod
    
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = list(map(int, input().split(" ")))
A = [0] * (N+1)
for i in range(M):
    A[int(input())] = -1
count = 0
for i in reversed(range(N + 1)):
    if(i - 2 >= 0 and A[i - 2] != -1 and A[i - 1] != -1 and A[i] != -1):
        count += 1
    if(i - 2 >= 0 and (A[i - 2] == -1 and A[i - 1] == -1) ):
        count = -1
        break
if(count == -1):
    print(0)
else:
    print(pow(2,count, 100000007))

Submission status: Wrong Answer

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

diff_list = []
before_pos = 0
for i in range(m):
  if before_pos == 0:
    diff_list.append(list[i]-before_pos)
  else:
    diff_list.append(list[i]-before_pos-2)
  before_pos = list[i]
diff_list.append(n-before_pos-1)

max_num = max(diff_list)

ncklist=[]
ncklist.append(0)
for i in range(max_num+1):
  if i == 1:
    ncklist.append(1)
  if i == 2:
    ncklist.append(2)
  if i > 2:
    ncklist.append(ncklist[i-1]+ncklist[i-2])

ptn = 1
for i in diff_list:
  ptn = ptn * ncklist[i]
mod = ptn % 1000000007
print(mod)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

sys.setrecursionlimit(1000000)

N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
a.append(N+1)
a = np.array(a)
sum_move = 1
fact = [-1] * (N+1)
fact = np.array(fact)
fact[0] = 1


def factorial(num, fact):
    if fact[num] > 0:
        return fact[num]
    else:
        fact[num] = factorial(num-1, fact) * num
        return fact[num]


step_begin = 0
for i in range(M+1):
    tmp_sum = 0
    step_end = a[i] - 1
    step_num = step_end - step_begin
    for j in range(step_num//2 + 1):
        tmp_sum += factorial(step_num - j, fact) \
            // factorial(j, fact) // factorial(step_num - 2 * j, fact)
    if tmp_sum != 0:
        sum_move *= tmp_sum
    else:
        sum_move = 0
        break
    step_begin = step_end + 2

print(sum_move % 1000000007)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
a = [int(input()) for _ in range(M)]
k = 10**9+7
dp = [0]*(N+1)
dp[0] = 1
d = 1
if N == 1:
  print(1)
else:
  for i in range(1,N+1):
    if dp[i] == -1:
      continue
    elif i==1:
      dp[1] = 1
    else:
      dp1 = dp[i-1] if dp[i-1] != -1 else 0
      dp2 = dp[i-2] if dp[i-2] != -1 else 0
      dp[i] = dp1+dp2
  print(dp[N]%k)

Submission status: Wrong Answer

Solution code:
import math

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

result = 0

N, M = map(int,input().split())
if M == 0:
    List = [0,0]
else:
    List = [int(input()) for i in range(M)]

if M == 0:
    for i in range(math.floor((N-1)/2) + 1):
        result += cmb(N - List[M-1]-1-i,i) 
    result = result % 1000000007 
    print(result)

else:
    for i in range(math.floor((List[0]-1)/2) + 1):
        result += cmb(List[0]-1-i,i) 
            
    for i in range(M-1):
        if List[i+1] - List[i] == 1:
            result = 0
            break
        else:
            tmp = 0
            for j in range(math.floor((List[i+1]-List[i]-2)/2) + 1):
                tmp += cmb(List[i+1]-List[i]-2-j,j)
            result = result * tmp

    tmp = 0
    for i in range(math.floor((N - List[M-1]-1)/2) + 1):
        tmp += cmb(N - List[M-1]-1-i,i) 

    result = result * tmp
    result = result % 1000000007 
    print(result)

Submission status: Wrong Answer

Solution code:
mod = 1000000007

def add(a, b):
    return (a + b) % mod

def sub(a, b):
    return (a + mod - b) % mod

def mul(a, b):
    return ((a % mod) * (b % mod)) % mod
    
a = []
N, M = map(int, input().split())
for i in range(M):
    a.append(int(input()))

print(a)

results = []

flag = True

for m in range(1, M):
    if a[m] - a[m - 1] == 1:
        flag = False
        break

flag_end = True
if M == 0:
    flag_end = False

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

if flag and flag_end:
    for m in range(M):
        if m == 0:
            results.append(Fib(a[m] + 1))
        else:
            results.append(Fib(a[m] - a[m - 1]))
    results.append(Fib(N - a[m] + 1))
    result = 1
    for i in range(len(results)):
        result = mul(result, results[i])
    print(result)
else:
    print(0)
print(results)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
if m > 0:
    li = [int(input()) for i in range(m)]
else:
    li = [0]
#連続する壊れていない階段の数を求める
li_new = [-1]*(m+1)
li_new[0] = li[0]
for i in range(1,m):
    li_new[i] = li[i] - (li[i-1]+1)
li_new[m] = n - li[m-1]
#print(li_new)

#必用な部分までのフィボナッチ数をリストに保存
fib = [0] * (max(max(li_new)+1,3))
fib[0] = 0
fib[1] = 1
fib[2] = 1
for i in range(3,max(li_new)+1):
    fib[i] = fib[i-2] + fib[i-1]
#print(fib)

#連続する壊れていない階段の数ごとのフィボナッチ数の積
ans = 1
for i in li_new:
    ans *= fib[i]
print(ans%1000000007)

Submission status: Wrong Answer

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

mod=1000000007

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


if n==1:
  print(1)
  exit()

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

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



a_i2=0
a_i1=0
a_i=0

for i in range(n-1):
  if i+2 == a[a_i2]:
      a_i2 += 1
      if a_i2 == m:
        a_i2 -= 1
  else:
    if i+1 == a[a_i1]:
      if i == a[a_i]:
        dp[i+2]=0
        a_i += 1
        if a_i == m:
          a_i -= 1
      else:
        dp[i+2]=dp[i]
      a_i1 += 1
      if a_i1 == m:
        a_i1 -= 1
    else:
      if i == a[a_i]:
        dp[i+2]=dp[i+1]
        a_i += 1
        if a_i == m:
          a_i -= 1
      else:
        dp[i+2]=dp[i+1]+dp[i]

  dp[i+2] = dp[i+2] % mod
  #print(dp)

print(dp[n])

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
h = []
for i in range(0,m):
  h.append(int(input()))
now = 0
s = 1
arr = [0,1,2]
for i in range(1,n-1):
  arr.append(arr[i]+arr[i+1])

"""
def c(i):
  if 0 <= i <= 2:
    return i
  else:
    return c(i-2) + c(i-1)
"""
def check(h):
  if m == 1:
    return 0
  if m == 2 and h[0]+1 == h[1]:
    return -1
  for i in range(0,m-2):
    if h[i] + 1 == h[i+1]:
      return -1
  return 0

if check(h) == 0:
  for i in h:
    b = i - now - 1
    if b > 0:
      s = (s * arr[b]) % 1000000007
    now = i + 1
  s = (s * arr[n-now]) % 1000000007
  print(s)
else:
  print(0)

Submission status: Wrong Answer

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

for i in range(M-1):
  if lst[i] == lst[i+1]:
    print("0")


if 1 in lst and not 3 in lst:
  lst2 = [0,1,1]
  for j in range(4,N+1):
    #print(j)
    if j in lst:
      lst2.append(0)
    else:
      #print(lst2,lst2[-1],lst2[-2])
      lst2.append(lst2[-1]+lst2[-2])
elif 2 in lst:
  lst2 = [1,0,1]
  for j in range(4,N+1):
    #print(j)
    if j in lst:
      lst2.append(0)
    else:
      #print(lst2,lst2[-1],lst2[-2])
      lst2.append(lst2[-1]+lst2[-2])
elif 3 in lst and not 1 in lst:
  lst2 = [1,2,0]
  for j in range(4,N+1):
    #print(j)
    if j in lst:
      lst2.append(0)
    else:
      #print(lst2,lst2[-1],lst2[-2])
      lst2.append(lst2[-1]+lst2[-2])
elif 1 in lst and 3 in lst:
  lst2 = [0,1,0]
  for j in range(4,N+1):
    #print(j)
    if j in lst:
      lst2.append(0)
    else:
      #print(lst2,lst2[-1],lst2[-2])
      lst2.append(lst2[-1]+lst2[-2])
else:
  lst2 = [1,2,3]
  for j in range(4,N+1):
    #print(j)
    if j in lst:
      lst2.append(0)
    else:
      #print(lst2,lst2[-1],lst2[-2])
      lst2.append(lst2[-1]+lst2[-2])
#print(lst2)
#print(lst[-1])
#print(lst2[-1])
print(lst2[-1]%1000000007)

Submission status: Wrong Answer

Solution code:
#from itertools import accumulate

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

l = [1] * (n+1)

for i in range(n+1):
    if i in a:
        l[i] = 0
    elif i > 2:
        l[i] = l[i-2] + l[i-1]

print(l[-1] % 1000000007)

Submission status: Wrong Answer

Solution code:
def mul(c):
  ANS = 0
  for t, o in zip(range(c, -1, -1), range(0, 2*(c + 1), 2)):
    ans = 1
    for m in range(t + o, max(t, o), -1):
      ans *= m 
    ANS += ans
  return ANS

def mul_odd(c):
  ANS = 0
  for t, o in zip(range(c, -1, -1), range(1, 2*c + 3, 2)):
    ans = 1
    for m in range(t + o, max(t, o), -1):
      ans *= m 
    ANS += ans
  return ANS

N, M = map(int, input().split())
D = 0
A = [0]
ans = []
aans = 1
for i in range(M + 1):
  if i != M :
  	A.append(int(input()))
  else: 
    A.append(N + 1)
  diff = A[i + 1] - A[i]
  if (diff == 1) & (i != 0):
    print(0)
    D = 1
    break
  
  temp = diff -1
  if (temp) % 2 == 0:
    aans *= mul(temp//2)
  else:
    aans *= mul_odd(temp//2)
if D == 0:   
	print(aans)

Submission status: Wrong Answer

Solution code:
import sys

stdin = sys.stdin

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

mm = 1000000007
n, m = na()
ai = [-1]
for i in range(m):
    ai.append(int(input()))
ai.append(n+1)
li = [1, 1]
for i in range(n+2):
    li.append(li[i] + li[i+1])
ans = 1
#rint(li)
if m == 0:
    print(li[n])
else:
    for i in range(len(ai) - 1):
        if ai[i+1] - ai[i] == 1:
            ans = 0
        else:
            ans *= li[(ai[i+1] - ai[i]) - 2]
            ans = ans % mm
    print(ans)

Submission status: Wrong Answer

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

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

fib = get_fib(N)

a = 0
result = 1

if M == 0:
    result = fib[N-1]

for m in range(M):
    b = int(input())
    if b!=1 and b - a <= 1:
        result = 0
        break
    result += fib[b-a]
    a = b
    
mod = 1000000007
print(result%mod)

Submission status: Wrong Answer

Solution code:
#from itertools import accumulate

n, m = map(int, input().split())
a = [0]*m
for i in range(m):
    a[i] = int(input())
    # 2段続いている場合は最上段にたどり着けない
    if i>=2 and a[-2]+1 == a[-1]:
        print(0)
        exit()

l = [1] * (n+1)

for i in range(n+1):
    if i in a:
        l[i] = 0
    elif i > 2:
        l[i] = l[i-2] + l[i-1]

print(l[-1] % 1000000007)

Submission status: Wrong Answer

Solution code:
def count(b,a):
    c = 2
    d = 1
    for i in range(b - a):
        c,d = c+d,c
    return c

n,m = map(int,input().split())
li = []
for i in range(m):
    li.append(int(input()))
cnt = 1
if len(li) != 1:
    for i in range(len(li) - 1):
        if li[i+1] - li[i] == 1:
            cnt = 0
            break
        else:
            if i == 0:
                cnt *= count(li[1], li[0])
            else:
                cnt *= count(li[i], li[i - 1])
else:
    cnt = count(li[0] - 2,1) *count(n - 1,li[0] + 2)
print(cnt % 1000000007)

Submission status: Wrong Answer

Solution code:
import sys

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

steps = [0, 1, 2]
for i in range(3, N+1):
    steps.append(steps[i-1] + steps[i-2])
  
if M == 0:
    print(steps[N])
    sys.exit()
    
As = []
for i in range(M):
    As.append(int(input()))
    
deffs = []

if As[0] != 1:
    deffs.append(As[0] - 1)
else:
    deffs.append(1)

for i in range(1, M):
    d = As[i] - As[i-1] -2
    if d == 0:
        deffs.append(1)
    elif d == -1:
        deffs.append(0)
    else:
        deffs.append(d)

if N - As[M-1] - 1 != 0:
    deffs.append(N - As[M-1] - 1)
else:
    deffs.append(1)

ans = 1

for i in range(len(deffs)):
    ans *= steps[deffs[i]]
    
print(ans % 1000000007)