Problem:


Score : 300 points

Problem Statement

There is a staircase with N steps. Takahashi is now standing at the foot of the stairs, that is, on the 0-th step.
He can climb up one or two steps at a time.

However, the treads of the a_1-th, a_2-th, a_3-th, \ldots, a_M-th steps are broken, so it is dangerous to set foot on those steps.

How many are there to climb up to the top step, that is, the N-th step, without setting foot on the broken steps?
Find the count modulo 1\ 000\ 000\ 007.

Constraints

1 \leq N \leq 10^5

0 \leq M \leq N-1

1 \leq a_1 < a_2 <  ...  < a_M \leq N-1

Input

Input is given from Standard Input in the following format:

N M
a_1
a_2
 .
 .
 .
a_M

Output

Print the number of ways to climb up the stairs under the condition, modulo 1\ 000\ 000\ 007.

Sample Input 1

6 1
3

Sample Output 1

4

There are four ways to climb up the stairs, as follows:

0 \to 1 \to 2 \to 4 \to 5 \to 6

0 \to 1 \to 2 \to 4 \to 6

0 \to 2 \to 4 \to 5 \to 6

0 \to 2 \to 4 \to 6

Sample Input 2

10 2
4
5

Sample Output 2

0

There may be no way to climb up the stairs without setting foot on the broken steps.

Sample Input 3

100 5
1
23
45
67
89

Sample Output 3

608200469

Be sure to print the count modulo 1\ 000\ 000\ 007.



Sample input:
6 1
3


Sample output:
4

Submission status: Wrong Answer

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

tmp = [1, 2]
for i in range(10 ** 5):
    tmp.append(tmp[-1] + tmp[-2])

ans = 1
before = -1
if m != 0:
    for i in range(m):
        step = a[i] - before - 2
        if step == -1:
            ans = 0
            break
        elif step > 0:
            ans = ans * tmp[step-1]
            ans = ans % 1000000007

        before = a[i]

# final steps
step = n - before - 1
if step == 0:
    ans = 0
elif step > 0:
    ans *= tmp[step-1]
    ans = ans % 1000000007

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
 
n,m=map(int,input().split())
A=[int(input()) for __ in range(m)]
bef=0
ans=0
fib=[0,2,3]
 
dist=[]
for a in A:
    if a-bef-1 == 0 and a != 1:
        print(0)
        sys.exit()
    else:
        dist.append(a-bef-1)
    bef=a
dist.append(n-bef-1)
 
for a in dist:
    if len(fib)<=a:
        for i in range(len(fib),a):
            fib.append(fib[i-1]+fib[i-2])
    ans+=fib[a-1]
    if ans >= 1000000007:
        ans-=1000000007
    bef=a+1
 
print(ans)

Submission status: Wrong Answer

Solution code:
import math
n, m = map(int, input().split(' '))
a = []
for _ in range(m):
  a.append(int(input()))
ans = -1

block = []
if m == 0:
  block.append(n)
else:
  block.append(a[0]-1)
  for i in range(1, m):
    d = a[i] - a[i-1] - 1
    if d == 0:
      ans = 0
      break
    else:
      block.append(d)
  block.append(n - a[-1]-1)

print(block,ans)
if ans != 0:
  b_p = [0]*len(block)
  for i in range(len(block)):
    b_n = block[i]
    if b_n == 0:
      b_p[i] = 1
      continue
    for t in range(math.ceil(b_n/2)-1, b_n):
      b_p[i] += math.factorial(b_n-1) // (math.factorial((b_n-1) - t) * math.factorial(t))
  
  ans = 1
  for b in b_p:
    if b != 0:
      ans *= b

print(ans % (10**9+7))

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
A=[]
count=[]
for i in range(m):
  a=int(input())
  if a-1 in A:
    print(0)
    break
  A.append(a)
A.append(0)
A.append(n)
A=sorted(list(set(A)))
for i in range(len(A)-1):
  a=1
  b=1
  for j in range(A[i+1]-A[i]-1):
    a=b%((10**9)+7)
    b=(a+b)%((10**9)+7)
  count.append(a)
Total=1
for i in range(len(count)):
  Total*=count[i]%((10**9)+7)
print(Total%((10**9)+7))

Submission status: Wrong Answer

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

AAA = [0]
for i in range(M):
    AAA.append(int(input()))
AAA.append(N)

ans = 1
for i in range(len(AAA)-1):

    mitinori = AAA[i+1] - AAA[i]

    if mitinori == 1 and i != 0:
        print(0)
        exit()

    if mitinori >= 2:
        ans *= 2**(mitinori-2)

print(ans % 1000000007)

Submission status: Wrong Answer

Solution code:
from scipy.misc import comb
import numpy as np

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


def get_comb(cur, x):
    """cur: current step / x: next obstacle"""
    y1 = x - 1 - cur
    y2 = int(y1/2)
    z = 0
    for i in range(y2+1):
        z += comb(y1 - i, i, 1)
    return z


a.append(n+1)

i = 0
pos = []
broken = False
for j in range(m+1):
    if j < m and a[j] + 1 == a[j+1]:
        print(0)
        broken = True
        break
    hoge = get_comb(i, a[j])
    pos.append(hoge)
    i = a[j] + 1

if broken is False:
    c = int(np.prod(pos))
    print(c % 1000000007)

Submission status: Wrong Answer

Solution code:
import math

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

sum = 1 # パターン総数
current = 0 # 現在の段数

# 連続で階段が壊れていたら上がるのは不可能
for i in range(M - 1):
  if lista[i + 1] - lista[i] == 1: 
    sum = 0
    break

# 連続では階段が壊れていない
if sum == 1:
  for a in lista:
    cnt = 0
    diff = a -current - 1
    for i in range(diff + 1):
      for j in range(diff // 2 + 1):
        if (i + 2 * j) == diff:
          cnt += math.factorial(i + j) // math.factorial(i) // math.factorial(j)
    current = a + 1
    sum *= cnt
    
    # 最後の段
    if a == lista[M - 1]:
      cnt = 0
      diff = N - current
      for i in range(diff + 1):
          for j in range(diff // 2 + 1):
            if (i + 2 * j) == diff:
              cnt += math.factorial(i + j) // math.factorial(i) // math.factorial(j)
      sum *= cnt

print(sum % 1000000007)

Submission status: Wrong Answer

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

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

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

def main():
	N,M = map(int, input().split(" "))
	#N = int(input())
	#S = input()
	#S = list(S)
	
	a = []
	for _ in range(M):
		tmp = int(input())
		if len(a) != 0:
			if tmp-1 == a[-1]:
				print(0)
				sys.exit()
		a.append(tmp)

	if M == 0:
		print(fb(N+1))
		sys.exit()

	base = 0
	ans = []
	for i, vol in enumerate(a):
		if base == 0:
			ans.append(fb(vol))
			base = vol
		else:
			ans.append(fb(vol-base-1)% 1000000007)
			base = vol

	if N != base:
		ans.append(fb(N-base)% 1000000007)

	tmp = 1
	for i in ans:
		tmp = (tmp % 1000000007) * i

	print(tmp % 1000000007)
	#print(ans)


def fb(num):
    """num番目のフィボナッチ数を返す
    """
    a, b = 1, 0
    for _ in range(num):
        a, b = a + b, a
    return b

if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
from operator import mul
from functools import reduce
import itertools


n, m = 100, 5
a = [1, 23, 45, 67, 89]

n, m = 6, 1
a = [3]

a.append(n)
a.insert(0, 0)
#print(a)
def count_ways(steps, jumps):
    jav_steps = steps - 2
    ls = list(itertools.combinations(range(jav_steps), jumps))
    return len(ls)
    
def count_block(b1, b2):
    steps = b2 - b1
    jump_types = steps//2 + 1
    block_ans = sum([count_ways(steps, jumps) for jumps in range(1, jump_types-1)])    
    return block_ans

ans  = [count_block(a[i], a[i+1]) for i in range(len(a)-1) if a[i+1]!=1]

print(reduce(mul, ans))

Submission status: Wrong Answer

Solution code:
def fib(n):
    a1 = 2
    a2 = 1 
    if n==2:
        return 2
    elif n==1:
        return 1
    else:
        count = 1
        for i in range(n-2):
            count = a1 + a2
            a2 = a1
            a1 = count
        return count
        
N,M = list(map(int,input().split()))
ans = 1
z = False

if M == 0:
    ans *= fib(N)
    print(ans) 
else:
    a = [int(input()) for _ in range(M)]

    for i in range(M):
        if i != 0:
            if a[i]-a[i-1] != 1:
                ans *= fib(a[i]-a[i-1]-2)
            else:
                z = True
                break
        else:
            ans *= fib(a[i]-1)

    ans *= fib(N-a[-1]-1)

    if z:
        print(0)
    else:
        print(str(ans%1000000007))

Submission status: Wrong Answer

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

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

for i in range(1, len(A)):
    if A[i]-A[i-1]==1:
        print(0)
        exit()

ans = 0

m = []
now = 0
rlt = 0
for a in A:
    n = a-now
    if n==1 or n==2: s = 1
    else: s = int((float(1)/2)*(pow(n-2,2)-n+2+4))

    m.append(s)
    now = a

n = N-now
if n==1 or n==2: s = 1
else: s = int((float(1)/2)*(pow(n-2,2)-n+2+4))
m.append(s)

ans = 1

for i in m:
    ans *= i

print(ans%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])% 1000000007

    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/2) + 1)):
        result += cmb(N - i,i) 
    result = result % 1000000007 
    print(result)

else:
    for i in range(math.floor((List[0])/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())
dp = [-1] * (n + 1)
for i in range(m):
    a = int(input())
    dp[a] = 0
    if i == 0 and a != 1:
        dp[1] = 1
mod = 10 ** 9 + 7

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

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

for m in range(M):
    b = int(input())
    if b!=1 and b - a <= 1:
        result = 0
        break
    result *= fib[b-1-a]
    # print(a,b,result)
    a = b

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

Submission status: Wrong Answer

Solution code:
#ABC129C-TypicalStairs.py

#import list
from sys import stdin

input = stdin.readline

#constant
#N = int(input())
N, M = list(map(int,input().split()))
A = [int(input()) for _ in range(M)]+[N+1]

#variable

#function
def partition(two_steps,total_steps):
    if two_steps == 0:
        return 1
    elif two_steps == 1:
        return total_steps-1
    else:
        result = 0
        for i in range(total_steps-(2*(two_steps-1))):
            result += partition(two_steps-1,total_steps-(i+2))
        return result

def sectorSum(total_steps):
    if total_steps == 0:
        return 0
    result = 0
    max_two_steps = total_steps//2
    for two_steps in range(max_two_steps+1):
        result += partition(two_steps,total_steps)
    return result
#class

#main function
def main():
    totalResult = 1
    position = 0
    i = 0
    while position < N:
        a = A.pop(0)
        if position+1 == a:
            position = a+1
            if position == A[0]:
                totalResult = 0
                break
        else:
            totalResult = totalResult*sectorSum(a-1-position)
            print(a-1-position)
            position = a+1
    print(totalResult%1000000007)




if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
t_list = []
for _ in range(m):
  t = int(input())
  t_list.append(t)
i = 0
s_a = 0
flg = False
ans = 1
for j in range(m):
  if j < len(t_list)-1 and (t_list[j+1] - t_list[j]) == 1:
    ans = 0
    flg = True
    break
  if t_list[j] == 1:
    s_a += 1
  else:
    s_a += 2
if not flg:
  ans = 2 ** (n - s_a - m - 1)
    
print(ans % 1000000007)

Submission status: Wrong Answer

Solution code:
def culc(m):
    s=0
    if m%2==1:
        m1=1 #1の個数
        m2=m//2 #2の個数
    else:
        m1=0
        m2=m//2
    
    while m2>=0:
        l1=1
        l2=1
        for i in range(m2):
            l1=l1*(m1+i+1)
            l2=l2*(i+1)
        s+=int(l1/l2)
        m1+=2
        m2+=-1
    return s

N,M=map(int,input().split())
a1=-1
a2=0
b=[]
for i in range(M):

    a2=int(input())
    da=a2-a1
    a1=a2
    if da==1:
        b=[]
        break
    elif da!=0:
        b+=[da-2]

else:
    b+=[N-a2-1]


if b==[]:
    sm=0
else:
    b.sort()
    c=culc(b[0])
    sm=c
    s1=b[0]
    for i in b[1:]:
        if s1==i:
            sm=sm*c
        else:
            c=culc(i)
            sm=sm*c
print(sm%1000000007)

Submission status: Wrong Answer

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


def fib(n):
    if n <= 4:
        return n
    else:
        first = 3
        second = 4
        for _i in range(n-4):
            third = second+first-1
            first = second
            second = third
        return second


a = [0]
for i in range(M):
    a.append(int(input()))
a.append(N)

possibilities = 1
for i in range(len(a)-1):
    if a[i+1] == 1:
        continue
    dif = a[i+1]-a[i]-1
    if dif == 0:
        possibilities *= 0
        break
    else:
        possibilities *= fib(dif)
print(possibilities%1000000007)

Submission status: Wrong Answer

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

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

for i in range(1, len(A)):
    if A[i]-A[i-1]==1:
        print(0)
        exit()

ans = 0

m = []
now = 0
rlt = 0
for a in A:
    n = a-now
    if n==1 or n==2: s = 1
    else: s = int((float(1)/2)*(pow(n-2,2)-n+2+4))

    m.append(s)
    now = a

n = N-now
if n==1 or n==2: s = 1
else: s = int((float(1)/2)*(pow(n-2,2)-n+2+4))
print('n:{}, s:{}'.format(n, s))
m.append(s)

ans = 1

for i in m:
    ans *= i

print(ans%1000000007)

Submission status: Wrong Answer

Solution code:
import sys

n,m=map(int,input().split())
A=[int(input()) for __ in range(m)]
bef=0
ans=0
fib=[0,2,3]

dist=[]
for a in A:
    if a-bef-1 == 0 and a != 1:
        print(0)
        sys.exit()
    else:
        dist.append(a-bef-1)
    bef=a
dist.append(n-bef-1)
print(dist)

for a in dist:
    if len(fib)<=a:
        for i in range(len(fib),a):
            fib.append(fib[i-1]+fib[i-2])
    ans*=fib[a-1]
    ans%=1000000007
    bef=a+1

print(max(1,ans))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

memo=[0,1,1]
for i in range(2,n):
    memo.append(memo[i]+memo[i-1])

if m==0:
    print(n-1)
elif m==1:
    print((temp[0]-1)*(n-temp[0]-1))
elif m>1:
    for i in range(m-1):
        if (temp[i]+1)==temp[i+1]:
            k=1
        else:
            kumi=temp[i+1]-temp[i]-1
            ans=(ans*(memo[kumi]%mod))%mod
    if k==1:
        print("0")
    else:
        end=memo[n-temp[m-1]-1]
        first=memo[temp[0]]
        if end<2 and first<2:
            print(ans)
        elif end<2 and first>1:
            print((ans*(first%mod))%mod)
        elif end>1 and first<2:
            print((ans*(end%mod))%mod)
        elif end>1 and first>1:
            print((ans*(end%mod)*(first%mod))%mod)

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
invalid = 0

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

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

Submission status: Wrong Answer

Solution code:
import math
from fractions import Fraction
import sys
sys.setrecursionlimit(15000)

def fibMul(fn1, fn2):
  a = fn1[0]
  b = fn1[1]
  c = fn2[0]
  d = fn2[1]
  return (a*c + 5*b*d, a*d + b*c)

def fibExp(fn, n):
  if (n == 0):
    return (Fraction(1), Fraction(1));
  if (n % 2 == 0):
    return fibExp(fibMul(fn, fn), n / 2);
  return fibMul(fn, fibExp(fn, n - 1));

def fibMin(fn1, fn2):
  a = fn1[0]
  b = fn1[1]
  c = fn2[0]
  d = fn2[1]
  return (a - c, b - d)

def fibMain(n):
  fibNum1 = (Fraction(1, 2), Fraction( 1, 2))
  fibNum2 = (Fraction(1, 2), Fraction(-1, 2))

  fibNum3 = fibMin(fibExp(fibNum1, n), fibExp(fibNum2, n))
  fibNum4 = (Fraction(0, 1), Fraction(1, 5))
  return fibMul(fibNum3, fibNum4)

def fib(n):
  return fibMain(n)[0].numerator
"""def fib(n):
    f = (((1 + math.sqrt(5)) / 2)**n - ((1 - math.sqrt(5)) / 2)**n ) / math.sqrt(5)
    return int(f)"""


NM = [int(i) for i in input().split()]
a = []
b = []
answer = 0
flag = True
for i in range(NM[1]):
    a.append(int(input()))
    if(i == 0):
        if(a[i] - 1 != 0):
            b.append(a[i] - 1)
        if(a[i] - 1 < 0):
            flag = False
    else:
        if(a[i] - a[i - 1] - 2 != 0):
            b.append(a[i] - a[i - 1] - 2)
        if(a[i] - a[i - 1] - 2 < 0):
            flag = False

    if(i == NM[1] - 1):
        if(NM[0] - a[i] - 1 != 0):
            b.append(NM[0] - a[i] - 1)
        if(NM[0] - a[i] - 1 < 0):
            flag = False

if(NM[1] > NM[0]/2):
    answer = 0
elif(not flag):
    answer = 0
else:
    sum = 1
    for i in range(len(b)):
        sum *= fib(b[i] + 1)
        sum = sum % (10**9 + 7)
    answer = sum
print(answer)

Submission status: Wrong Answer

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

for i in range(m):
    a.append(int(input()))
a .append(n+1)
fibo = [1,2,3]

ans = 1
start =0
if(a[1]==1):
    start =1
for x in range(start,m+1):
    if(abs(a[x+1]-a[x])==1):
       ans = 0
    else:
        l = len(fibo)
        while(a[x+1]-a[x]-3>l-1):
            fibo.append(fibo[-1]+fibo[-2])
            l += 1
        ans = (ans*fibo[a[x+1]-a[x]-3])%1000000007
print(ans)

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
listA = [int(input()) for i in range(m)]
if(listA.count(1)==1 and listA.count(2)==1):
    a,b = 0,0
elif(listA.count(1)==1):
    a,b = 0,1
elif(listA.count(2)==1):
    a,b = 1,0
else:
    a,b = 1,2
    
for j in range(1, n-1):
    if(listA.count(j+2)!=0):
        a,b = b,0
    if(listA.count(j+2)==0):
        a,b = b,a+b

print(b%1000000007)

Submission status: Wrong Answer

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

def check(h):
  if m == 1 or m == 0:
    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:
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/2) + 1)):
        result += cmb(N - i,i) % 1000000007 
    result = result % 1000000007 
    print(result)

else:
    for i in range(math.floor((List[0])/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())

ret = list([2]*N)
ret[0] = 1

for m in range(M):
  idx = int(input()) - 1
  ret[idx] = -1

  if idx < (N - 2):
    ret[idx+2] = ret[idx+2] - 1
  if idx < (N - 1):
    ret[idx+1] = ret[idx+1] - 1
#  print(ret)

ans = 1
for r in ret:
  ans *= abs(r)

print(ans % 1000000007)

Submission status: Wrong Answer

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

def comb(n,k):
  m = 1
  if n<2*k:
    k = n-k
  for i in range(1,k+1):
    m = m*(n-i+1)/i
  return m
 
pat = 1
for i in range(m+1):
  step = a[i+1]-a[i]-2
  patj = 0
  if(step<0):
    pat = 0
    break
  for j in range(step//2+1):
    patj += comb(step-j,j)
  patj = int(patj%1000000007)
  pat = int(pat*patj%1000000007)
  
print(pat)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
bool = [True] * N
for i in range(M):
    bool[int(input())-1] = False

dp = 0
m0 = 0
m1 = 1
Ans = 1
for i in range(N):
    if bool[i]:
        dp = m0 + m1
        m0 = m1
        m1 = dp
        if dp == 0:
            m1 = 1
    else:
        if i == N-1:
            print(0)
            exit()
        elif not bool[i+1]:
            print(0)
            exit()
        m0 = 0
        m1 = 0
        Ans *= dp
        dp = 0
Ans *= dp
print(Ans % 1000000007)

Submission status: Wrong Answer

Solution code:
import sys

n,m=map(int,input().split())
A=[int(input()) for __ in range(m)]
bef=0
ans=0
fib=[0,2,3]

dist=[]
for a in A:
    if a-bef-1 == 0 and a != 1:
        print(0)
        sys.exit()
    else:
        dist.append(a-bef-1)
    bef=a
dist.append(n-bef-1)
print(dist)

for a in dist:
    if len(fib)<=a:
        for i in range(len(fib),a):
            fib.append(fib[i-1]+fib[i-2])
    ans+=fib[a-1]
    if ans >= 1000000007:
        ans-=1000000007
    bef=a+1

print(max(1,ans))

Submission status: Wrong Answer

Solution code:
import math

def fib(n):
    f = (((1 + math.sqrt(5)) / 2)**n - ((1 - math.sqrt(5)) / 2)**n ) / math.sqrt(5)
    return int(f)


NM = [int(i) for i in input().split()]
a = []
b = []
answer = 0
flag = True
for i in range(NM[1]):
    a.append(int(input()))
    if(i == 0):
        if(a[i] - 1 != 0):
            b.append(a[i] - 1)
        if(a[i] - 1 < 0):
            flag = False
    else:
        if(a[i] - a[i - 1] - 2 != 0):
            b.append(a[i] - a[i - 1] - 2)
        if(a[i] - a[i - 1] - 2 < 0):
            flag = False

    if(i == NM[1] - 1):
        if(NM[0] - a[i] - 1 != 0):
            b.append(NM[0] - a[i] - 1)
        if(NM[0] - a[i] - 1 < 0):
            flag = False

if(NM[1] > NM[0]/2):
    answer = 0
elif(not flag):
    answer = 0
else:
    sum = 1
    for i in range(len(b)):
        sum *= fib(b[i] + 1)
        sum = sum % (10**9 + 7)
    answer = sum
print(answer)

Submission status: Wrong Answer

Solution code:
import numpy as np
from math import factorial as fac
FLG=False
N,M=  map(int, input().split())
broken_steps=[]

for m in range(M):
    broken_steps.append(int(input()))

for i in range(len(broken_steps)-1):
    if broken_steps[i+1]-broken_steps[i]==1:
        print("{}".format(0))
        FLG=True

if FLG!=True:        
    count=0
    for two_step in range(M,N//2+2):
        one_step=N-two_step*2
        if one_step>0:
            count+=fac(two_step+one_step)/(fac(two_step)*fac(one_step)*fac(M))

    print("{}".format(count))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(200000)
input = sys.stdin.readline

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

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

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])/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:
import math
n, m = [int(i) for i in input().split()]
p = [int(input()) for i in range(m)]

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

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
A = []
index = 0
is_zero = False
patterns = []
ret = 1

for _ in range(M):
  a = int(input())
  dist = (a-1) - index
  if dist < 0:
    is_zero = True
    break
  A.append(dist)
  patterns.append(2**( dist // 2 + (dist % 2 if dist > 2 else 0)))
  ret *= 2**( dist // 2 + (dist % 2 if dist > 2 else 0))
  index = a+1
dist = N - index
A.append(dist)
patterns.append(2**( dist // 2 + (dist % 2 if dist > 2 else 0)))
ret *= 2**( dist // 2 + (dist % 2 if dist > 2 else 0))

if is_zero:
  print(0)
else:
  print(int(ret))

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+2):
  arr.append(arr[i]+arr[i+1])

def check(h):
  if m == 1 or m == 0:
    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:
def Fib(n):
    a, b = 0, 1
    if n == 1:
        return a
    elif n == 2:
        return b
    else:
        for i in range(n-2):
            a, b = b, a + b
        return b
a,b=input().split()
a=int(a)
b=int(b)
ll=[]
y=-1
s=0
for i in range(b):
    x=input()
    x=int(x)
    ll.append(x)
    if x-y==1:
        s=1
        break
    y=x
ll.append(a+1)
l2=[]
if s==1:
    print(0)
elif b==0:
    print(Fib(a+2))
else:
    x=ll[0]
    l2.append(Fib(x+1))
    del ll[0]
    for i in ll:
        l2.append(Fib(i-x))
        x=i
    ans=1
    for i in l2:
        ans*=i

Submission status: Wrong Answer

Solution code:
def culc(m):
    s=0
    if m%2==1:
        m1=1 #1の個数
        m2=m//2 #2の個数
    else:
        m1=0
        m2=m//2
    
    while m2>=0:
        l1=1
        l2=1
        for i in range(m2):
            l1=l1*(m1+i+1)
            l2=l2*(i+1)
        s+=int(l1/l2)
        m1+=2
        m2+=-1
    return s

N,M=map(int,input().split())
a=[-1]
b=[]
for i in range(M):
    a+=[int(input())]
    da=a[-1]-a[-2]

    if da==1:
        b=[]
        break
    elif da!=0:
        b+=[da-2]

else:
    b+=[N-a[-1]-1]


if b==[]:
    sm=0
else:
    b.sort()
    c=culc(b[0])
    sm=c
    s1=b[0]
    for i in b[1:]:
        if s1==i:
            sm=sm*c
        else:
            c=culc(i)
            sm=sm*c
print(sm%1000000007)

Submission status: Wrong Answer

Solution code:
import math

def fib(n):
    f = (((1 + math.sqrt(5)) / 2)**n - ((1 - math.sqrt(5)) / 2)**n ) / math.sqrt(5)
    return int(f)


NM = [int(i) for i in input().split()]
a = []
b = []
answer = 0
flag = True
for i in range(NM[1]):
    a.append(int(input()))
    if(i == 0):
        if(a[i] - 1 != 0):
            b.append(a[i] - 1)
        if(a[i] - 1 < 0):
            flag = False
    else:
        if(a[i] - a[i - 1] - 2 != 0):
            b.append(a[i] - a[i - 1] - 2)
        if(a[i] - a[i - 1] - 2 < 0):
            flag = False

    if(i == NM[1] - 1):
        if(NM[0] - a[i] - 1 != 0):
            b.append(NM[0] - a[i] - 1)
        if(NM[0] - a[i] - 1 < 0):
            flag = False

if(NM[1] > NM[0]/2):
    answer = 0
elif(not flag):
    answer = 0
else:
    sum = 1
    for i in range(len(b)):
        sum *= fib(b[i] + 1)
    answer = sum % (10**9 + 7)
print(answer)

Submission status: Wrong Answer

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

for i in range(m):
    a.append(int(input()))
a .append(n+1)
fibo = [1,2,3]

ans = 1
start =0
if(a[1]==1):
    start =1
for x in range(start,m+1):
    if(abs(a[x+1]-a[x])==1):
       ans = 0
    else:
        l = len(fibo)
        while(a[x+1]-a[x]-3>l-1):
            fibo.append(fibo[-1]+fibo[-2])
            l += 1
        ans *= fibo[a[x+1]-a[x]-3]
print(ans%1000000007)