Problem:


Score : 300 points

Problem Statement

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

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

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

Constraints

1 \leq N \leq 10^5

0 \leq M \leq N-1

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

Input

Input is given from Standard Input in the following format:

N M
a_1
a_2
 .
 .
 .
a_M

Output

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

Sample Input 1

6 1
3

Sample Output 1

4

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

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

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

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

0 \to 2 \to 4 \to 6

Sample Input 2

10 2
4
5

Sample Output 2

0

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

Sample Input 3

100 5
1
23
45
67
89

Sample Output 3

608200469

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



Sample input:
6 1
3


Sample output:
4

Submission status: Wrong Answer

Solution code:
def 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] - 1, 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:
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:
n, m = map(int,input().split())
lists = [1,2]
last = 0
conbi = 1

def conbination(num):
    if len(lists) >= num:
        return lists[num-1]
    for i in range(len(lists),num):
        lists.append(lists[i-1]+lists[i-2])
    return lists[num-1]

for i in range(m):
    step = int(input()) #穴が空いているステップ
    if step - last== 1:  #ラストステップが穴が空いているステップの次だったとき
        if last != 0:
            conbi = 0
            break
        else:
            last = step

            continue
    if step - last == 0:
        continue
    if last == 0:
        conbi = (conbi * conbination(step - last - 1)) % (1000000007)
    else:
        conbi = (conbi * conbination(step - last - 2))%(1000000007)
    last = step


if conbi != 0 or last != n:
    step = n
    conbi = (conbi * conbination(step - last - 1))%(1000000007)

print(conbi)

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 = -1
ds = []
for _ in range(m):
    a = int(input())
    if a == 1:
        pa = 1
        continue
    d = a - pa-2
    if d == -1:
        print(0)
        exit()
    ds.append(d)
    pa = a
ds.append(n - pa-1)
print(ds)
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:
def step(n) :
  if(n <=2) :
    return n
  else :
    return step(n - 1) + step(n - 2)

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

for i in range(M - 1) :
  if(M != 1) :
    if(a[i + 1] - a[i] == 1) :
      pass
    else :
      for j in range(M + 1) :
          if(j == 0) :
            S += step(a[j] - 1)
          elif(j == M) :
            S += step(N - a[j - 1] - 1)
          else :
            x = a[j] - a[j - 1] - 1
            S += step(x)
    
print(S % 1000000007)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
A = [int(input()) for i in range(M)]
A.append(N+1)
out = 1
s = [1,2]
if A[0] != 1:
    hoge = [A[0]-2]
else:
    hoge = []

for i in range(N-M):
    s.append(s[i]+s[i+1])

for k in range(M):
    if A[k+1]-A[k]-2 != int(-1):
        hoge.append(A[k+1]-A[k]-3)
    else:
        out = 0
        break

for j in hoge:
    out *= s[j]
    out = out%10000000007

print(out%10000000007)

Submission status: Wrong Answer

Solution code:
import sys

n, m = map(int, input().split())
holes = []
pos = [1] * (n+1)
ans = 0

def calc(n):
    if n == 1:
        pos[1]  = 1
        return 1
    elif n == 2:
        pos[2] = 2
        return 2
    else:
        pos[n] = pos[n-1] + pos[n-2]
        return pos[n]

for i in range(n):
    calc(i)

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

for i in range(m):
    if i > 0 and holes[i] == holes[i - 1] + 1:
        print(0)
        sys.exit()

for i in range(len(holes)):
#for i in range(1, len(holes) + 1):
    print("\n # i: " + str(i))
    if i == 0:
        ans = calc(holes[i] - 1)
        print("# ans: " + str(ans))
    else:
#        ans = ans * (calc(holes[i] - holes[i - 1]))
        ans = ans * (calc(holes[i] - holes[i - 1] - 1))
        print("# ans: " + str(ans))

    if i == len(holes) - 1:
        print("\nlast!")
        print("holes[i]: " + str(holes[i]))
#        print("calc: " + str((calc(n - holes[i]))))
        print("dif: " + str(n - holes[i]))
#        ans = ans * (calc(n - holes[i]))
        ans = ans * (calc(n - holes[i] - 1))

#print(ans)
print(ans % 1000000007)

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 = -1
ds = []
for _ in range(m):
    a = int(input())
    if a == 1:
        pa = 1
        continue
    d = a - pa-2
    if d == 1:
        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:
N,M = map(int,input().split())
A = [int(input()) for i in range(M)]
A.append(N+1)
out = 1
s = [1,2]
if A[0] != 1:
    hoge = [A[0]-2]
else:
    hoge = []

for i in range(N-M):
    s.append(s[i]+s[i+1])

for k in range(M):
    if A[k+1]-A[k]-2 != int(-1):
        hoge.append(A[k+1]-A[k]-3)
    else:
        out = 0
        break

print(hoge)

for j in hoge:
    out *= s[j]
    out = out%10000000007

print(out%10000000007)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
n,m=map(int,input().split())
key=0
flag=False
a=[int(input()) for i in range(m)]
for i in range(m-1):#answer 0
    if a[i+1]-a[i]==1:
        flag=True

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

if m!=0:
    key=fb(a[0]-1)

if key==0: key=1

for i in range(m-1):
    key*=fb(a[i+1]-a[i]-2)

if m!=0:
    key*=fb(n-a[len(a)-1]-1)

if m!=0 and flag!=True:
    print(key%1000000007)
elif flag==True:
    print(0)
else: print(fb(n-1))

Submission status: Wrong Answer

Solution code:
import sys
n,m=map(int,input().split())
a=[int(input()) for i in range(m)]
s=n-len(a)*2
S=[1,2]
for i in range(s):
    S.append((S[-1]+S[-2])%1000000007)

step=['00']+['1']*(n+1)
for i in range(m):
    step[a[i]+1]='0'
    step[a[i]+2]='0'
st=''.join(step)
#print(st)
st=st.split('00')
#print(st)
ans=[]
if '0' in st:
    print(0)
    sys.exit()
else:
    for i in range(1,len(st)):
        ans.append(S[len(st[i])-1])
#print(ans)
p=1
for i in range(len(ans)):
    p*=ans[i]
print(p%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-1]

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:
mod = 10**9+7

def fac(n):
    fac = [1]*(n+1)
    fac[0] = 1
    fac[1] = 1
    for i in range(1,n+1):
        fac[i] = fac[i-1]*i%mod
    return fac

def main():
    n,m=map(int,input().split(' '))
    fact = fac(n)
    check = 0
    pattern = 1
    a = [0]
    a_list = []
    tmp = -1
    for i in range(m):
        an = int(input())
        a.append(an)
    for i in range(m):
        if a[i] !=1:
            a_list.append(a[i+1]-a[i]-1)
    for i in a_list:
        tmp = 0
        for j in range(i):
            tmp +=(fact[(i-j)]/fact[j]/fact[i-2*j])%mod
        pattern *= tmp
        pattern %= mod

    print(int(pattern))

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
N,M = [int(i) for i in input().split()]
A = [0]
for _ in range(M):
    A.append(int(input()))
A.append(N)
ans = 1
for n in range(len(A)):
    if n ==0:
        pass
    else:
        div = (A[n]-A[n-1]-1) // 2
        mod = (A[n]-A[n-1]-1) % 2
        div_mod = div+mod
        comb = 0
        for _ in range(div):
            print(div_mod,div)
            comb += combinations_count(div_mod,div)
            div_mod += 1
            div -=1
            if div == 0:
                div = 1
                div_mod = 1
        comb += combinations_count(div_mod,div)
        print(comb)
        ans = ans * comb

Submission status: Wrong Answer

Solution code:
MOD = 10**9+7

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

now = 0
a0 = -1
ans = 1
for a in A:
    if a - a0 == 1:
        print(0)
        exit()
    else:
        tmp = 1
        for j in range(2, 10**9, 2):
          if (a - 1 - now - j + 1) > 0:
          	tmp += (a - 1 - now - j + 1)
          else:
            break
        ans = (ans%MOD) * tmp
        now = a + 1
        a0 = a
print(ans%MOD)

Submission status: Wrong Answer

Solution code:
import sys

def fibo(n):
    a, b = 0, 1
    if n == 1:
        return 1
    else:
        for i in range(n):
            a0 = a
            a = b
            b = a0 + b
        return b
        
N, M = map(int, input().split())
a = []

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

for i in range(M):
    a.append(int(input()))
    
for j in range(len(a)-1):
    if a[j+1] - a[j] == 1:
        print(0)
        sys.exit()
    
hole = 0
pattern = 1

for i, k in enumerate(a):
    if i == 0:
        pattern *= fibo(k-1)
    else:
        if i > 0:
            pattern *= fibo(a[i]-a[i-1]-2)
        
pattern *= fibo(N-a[-1]-1)
print(pattern % 1000000007)

Submission status: Wrong Answer

Solution code:
import sys
from math import factorial

def combination(n,r,n_b):

    nCr = n_b // factorial(r) // factorial(n - r)
    return(nCr)

n, m = [int(i) for i in input().split()]
a = [-1]
for i in range(m):
    a.append(int(input()))
    if a[-1] - a[-2] == 1:
        print(0)
        sys.exit()
a.append(n+1)
# print(a)

ans = 1
for i in range(len(a)-1):
    # print('i',i,ans)
    a_begin = a[i]
    a_end = a[i+1]
    # print(a_begin,a_end)
    num_stair = a_end - a_begin - 2
    max_num_two_up = num_stair // 2
    # print(num_stair,max_num_two_up)
    ans_tmp = 0
    n_b = factorial(n)
    for j in range(max_num_two_up+1):
        ans_tmp += combination(num_stair-j,j,n_b)
    ans *= ans_tmp

ans = ans % 1000000007
print(ans)

Submission status: Wrong Answer

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

narray = [0]*(n+1)
back = 0
tmp = 1
cnt = 1

for i in a:
    for j in range(m-1):
        if a[j] == a[j+1]:
            print(0)
            break
    else:
        if cnt == 1:
            size = len(narray[0:i])
            tmp = len(list(itertools.permutations(range(size-1))))
            size = len(narray[i:+1])
            tmp = len(list(itertools.permutations(range(size-1))))*tmp
            cnt = cnt -1
        else:
            size = len(narray[i+1:])
            tmp = len(list(itertools.permutations(range(size-1))))*tmp
        continue
    break

ans = tmp%1000000007
print(int(ans))

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+1):
    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] == 1):
        ans *= 1
    elif  (a[i-1] == N-1):
        ans *= 1
    elif (a[i] - a[i-1] == 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 = map(int, input().split())
a = [-1] + [int(input()) for i in range(m)] + [n+1]

res = 1
for i in range(1, len(a)):
    if a[i] == 1:
        continue
    tmp = a[i] - a[i-1] - 2
    if tmp < 0:
        tmp2 = 0
    elif tmp <= 1:
        tmp2 = 1
    elif tmp <= 2:
        tmp2 = 2
    else:
        tmp2 = 2
        for j in range(1, tmp-1):
            tmp2 += j
    res *= tmp2
    res %= 1000000007

print(res)

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()

	if N == 1 and M == 1:
		print(0)
		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:
n,m = map(int, input().split())
e = 10**9 + 7
c = 0
ans = 1
for _ in range(m):
    a = int(input())
    b = a-1-c
    c = a+1
    if b < 0:
        ans *= 0
        break
    ans *= (1 + sum([i for i in range(-(-b//2), b)]))
    
b = n - c
ans *= (1 + sum([i for i in range(-(-b//2), b)]))
print(ans%e)

Submission status: Wrong Answer

Solution code:
n, m = map(int,input().split())
lists = [1,2]
last = 0
conbi = 1

def conbination(num):
    if len(lists) >= num:
        return lists[num-1]
    for i in range(len(lists),num):
        lists.append(lists[i-1]+lists[i-2])
    return lists[num-1]

for i in range(m):
    step = int(input()) #穴が空いているステップ
    if step - last== 1:  #ラストステップが穴が空いているステップの次だったとき
        if last != 0:
            conbi = 0
            break
        else:
            last = step

            continue
    if step - last == 0:
        continue
    if last == 0:
        conbi = (conbi * conbination(step - last - 1)) % (1000000007)
    else:
        conbi = (conbi * conbination(step - last - 2))%(1000000007)
    last = step


if conbi != 0:
    step = n
    conbi = (conbi * conbination(step - last - 1))%(1000000007)

print(conbi)

Submission status: Wrong Answer

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

def f(n):
    n += 1
    if n==2:
        return 1 
    else:
        fib1 = 1
        fib2 = 1
        for i in range(n-2):
            fib3 = fib1+fib2
            fib1 = fib2
            fib2 = fib3
        return fib2

ans = 0
flag = True
if m > 1:
    for i in range(1, m):
        if a[i+1] - a[i] == 1:
            print(0)
            flag = False
if flag:
    for i in range(m):
        s = f(a[i+1]-(a[i])-1)
        ans += s%1000000007
    print(ans)

Submission status: Wrong Answer

Solution code:

# coding: utf-8
N, M = map(int, input().split())
a = []
for i in range(M):
    a.append(int(input()))
a.append(N+1)
#print("a", a)

out = 1
t = 0

while(t<N):
    if t+1 in a:
        if t+2 in a: # x x
            #print("d")
            out = 0
            break
        else: # x o
            #print("c")
            #out *= 1
            t += 2
    else:
        if t+2 in a: # o x
            #print("b")
            #out *= 1
            t += 1           
        else: # o o
            #print("a")
            out = out * 2
            t += 2            
    #print(t, out)
    #out = out%1000000007
print(out%1000000007)

Submission status: Wrong Answer

Solution code:
div = 1000000007
N,M = map(int,input().split())
A = []
for i in range(M):
    A.append(int(input()))
flag = False
step = [0]*N
step[0:2] = [1,1]
for i in range(2,N):
    step[i] = (step[i-1]+step[i-2])%div
if M == 0:
    ans = step[N-1]%div
else:
    ans = (step[A[0]-1])%div
    for i in range(1,M):
        tmp = A[i] - A[i-1]
        if tmp == 1:
            flag = True
            break
        else:
            ans = (ans*step[tmp-1])%div
    ans = (ans*step[N-A[M-1]-1])%div
if flag: ans = 0
print(ans)

Submission status: Wrong Answer

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

pre=-1

li=[0]

for i in range(m):
  a=int(input())
  if pre+1==a:
    print(0)
    exit()
  pre=a
  li.append(a)

li.append(n)

result=[]
for i in range(1,len(li)):
  sum1=1
  sum2=1
  sum3=1
  if 3>li[i]-li[i-1]:
    continue
  for j in range(3,li[i]-li[i-1]+1):
    sum3=sum1+sum2
    sum1=sum2
    sum2=sum3
  result.append(sum3)

result_=1
for i in result:
  result_*=i
#print(result)  
print(result_%1000000007)

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]
    a = b+1

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

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10000)

n, m = map(int, raw_input().split())
a_arr = []
count_sum = 0


for idx in range(0, m):
  a_arr.append(int(raw_input()))

from operator import mul
from functools import reduce

def cmb(n,r):
    # print(n, r)
    r = min(n-r,r)
    
    if r == 0:
      return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

def calc_ans(a_len):

  b_max = a_len//2
  temp_sum = 0

  for idx_b in range(0, b_max + 1):
    idx_a = a_len - (idx_b * 2)

    print(a_len, idx_a, idx_b)

    total_num = idx_a + idx_b

    temp_sum += cmb(total_num, idx_a)
    print(a_len, idx_a, idx_b, total_num, cmb(total_num, idx_a))

  return temp_sum

ans_val = 1

for idx in range(0, len(a_arr)):
  if idx == 0:
    a_len = a_arr[0]
  elif idx < len(a_arr)-1:
    a_len = a_arr[idx] - a_arr[idx-1]
  else:
    a_len = n - a_arr[idx]
  
  
  temp_ans = calc_ans(a_len - 1)

  # print(a_len)
  # print(temp_ans)

  ans_val = ans_val * temp_ans

print(ans_val % 1000000007)

Submission status: Wrong Answer

Solution code:
n, m = map(int,input().split())
broken = [0] + [int(input()) for i in range(m)] + [n]
l = []

for i in range(m + 1):
    if broken[i] != 0 and broken[i + 1] - broken[i] == 1:
        exit()
    else:
        dif = broken[i + 1] - (broken[i] + 1)
        l.append(int(-(-(dif / 2 + 1))))

ans = 1

for i in l:
    ans *= i
    
print(ans % 1000000007)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000)

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

fibmemo={1:1,2:1}
for i in range(3,100001):
    fibmemo[i]=fibmemo[i-1]+fibmemo[i-2]
def fib(n):
    return fibmemo[n]

n,m=intinput()
mod=10**9+7
a=[int(sys.stdin.readline()) for _ in range(m)]
if a!=[]:
    m=fib(a[0])
    tmp=a[0]
    for i in a:
        if i+1 in a:
            print(0)
            sys.exit()
        if a[0]==i:
            continue
        m=fib(i-tmp-1)*m%mod
        tmp=i
    m=fib(n-tmp)*m%mod
    print(m)
else:
    print(fib(n))

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
key=0
flag=False
a=[int(input()) for i in range(m)]
for i in range(m-1):#answer 0
    if a[i+1]-a[i]==1:
        flag=True

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

if m!=0:
    key=fb(a[0]-1)

if key==0: key=1

for i in range(m-1):
    key*=fb(a[i+1]-a[i]-2)

if m!=0:
    key*=fb(n-a[len(a)-1]-1)

if m!=0 and flag!=True:
    print(key%1000000007)
elif flag==True:
    print(0)
else: print(fb(n))

Submission status: Wrong Answer

Solution code:
def fib(num):
    a, b = 0, 1 
    for _ in range(num - 1):
#         print(a)
        a, b = a + b, a
    return a + b

def culcC(num):
    return fib(num) + fib(num-1)
            
n,m = map(int,input().split())
aa = [int(input()) for i in range(m)]

if n == 1:
    print(1)
elif m == 0:
    print(culcC(n) % 1000000007)
else:
    ans = 1
    stand = 0
    for i,a in enumerate(aa):
#        連続穴
        if stand == a:
            ans = 0
            break
        step_num = a - stand - 1
        c = culcC(step_num)
        ans *= c if c > 0 else 1
        stand = a + 1
        
    # 最後のaからnまでで計算
    ans *= culcC(n - aa[-1] - 1)
    
    print(ans % 1000000007)

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:
    print(fib(N)) 
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:
from math import factorial
n, m = map(int, input().split())
broken = [-1]
x = 0
y = 0
for i in range(m):
    b = int(input())
    broken.append(b)
    if x == 1:
        if b == broken[i-1] + 1:
            print(0)
            y = 1
            break
    x = 1
broken.append(n+1)
anslist = []
for i in range(m-1):
    d = broken[i+1] - broken[i] - 1
    if d == 0:
        continue
    dd = d - 1
    mskip = dd // 2
    d_way = 0
    for j in range(1, mskip+1):
        d_way += factorial(dd-j*2+ j) /(factorial(dd-j*2) * factorial(j))
    d_way += 1 
    anslist.append(d_way)
    
ans = sum(anslist)
if y == 0:
    if ans == 0:
        print(1)
    else:
        print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys

n, m = [int(x) for x in input().rstrip().split(" ")]

broken_stairs = []
stair_tmp = -1
for i in range(m):
    stair = int(input())
    if stair - stair_tmp == 1:
        print(0)
        sys.exit(0)
    stair_tmp = stair
    broken_stairs.append(stair)

last_section = n + 1
broken_stairs.append(last_section)
pattern = 1
for i in range(len(broken_stairs) - 1):
    section_pattern = 0
    section_length = broken_stairs[i + 1] - broken_stairs[i] - 1
    if section_length <= 2:
        section_pattern += 1
        pattern *= section_pattern
        continue
    if section_length == 3:
        section_pattern += 2
        pattern *= section_pattern
        continue
    r = int(section_length / 2) if section_length % 2 == 1 else -1 + (section_length // 2)
    pattern *= (2 ** r)

print(pattern % 1000000007)

Submission status: Wrong Answer

Solution code:
import sys
n,m=map(int,input().split())
a=[int(input()) for i in range(m)]
s=n-len(a)*2
S=[1,2]
for i in range(s):
    S.append((S[-1]+S[-2])%1000000007)

step=['00']+['1']*(n+1)
for i in range(m):
    step[a[i]+1]='0'
    step[a[i]+2]='0'
st=''.join(step)
#print(st)
st=st.split('00')
print(st)
ans=[]
if '0' in st:
    print(0)
    sys.exit()
else:
    for i in range(1,len(st)):
        ans.append(S[len(st[i])-1])
#print(ans)
p=1
for i in range(len(ans)):
    p*=ans[i]
print(p%1000000007)

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)

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:
import math

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

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

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

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

if M == 0:
  cnt = 0
  diff = N - current
  for i in range(diff + 1):
    for j in range(diff // 2 + 1):
      if (i + 2 * j) == diff:
        cnt += math.factorial(i + j) // math.factorial(i) // math.factorial(j)
        sum *= cnt

print(sum % 1000000007)

Submission status: Wrong Answer

Solution code:
N, M = map(int,input().split())
N_list = range(N+1)
a = [0] * M
for i in range(M):
    a[i] = int(input())
Comp_list = list(set(N_list)-set(a))
print(Comp_list)

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
  print(s_a)
if not flg:
  ans = 2 ** (n - s_a - m - 1)
  if ans < 1:
    ans = 1
    
print(ans % 1000000007)

Submission status: Wrong Answer

Solution code:
n,m = map(int,raw_input().split())
a = []
buf = -111
for q in range(m):
  a.append(int( raw_input() ))
  buf = a[q]
  if buf - a[q] == 1:
    print 0
    exit(0)

if n==1:
  print 1
  exit(0)
if n==2:
  if m==1:
    print 0
    exit(0)
  if m==0:
    print 2
    exit(0)

now = [-1]*100001

if m == 0:
  now[0] = 1
  now[1] = 1
  for q in range(2,n+1):
    now[q] = (now[q-1] + now[q-2]) % 1000000007
  print now[q] % 1000000007
  exit(0)
    
now[0] = 1
if a[0] == 1: now[1] = 0
else: now[1] = 1

for q in a:
  now[q] = 0

for q in range(2,n+1):
  if now[q] != -1: continue
  now[q] = (now[q-1] + now[q-2]) % 1000000007
  
print now[q] % 1000000007

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)
n,m=map(int,input().split())
al=[int(input()) for i in range(m)]+[n+1]
mod=1000000007
ms=[0]*(n+1)

def dd(n):
    if ms[n]>0:
        return ms[n]
    if n==1:
        ms[n]=1
        return 1
    if n==2:
        ms[n]=2
        return 2
    m=dd(n-1)+dd(n-2)
    ms[n]=m
    return m

if m==0:
    print(dd(n))
    exit()

ans=1
now=0
b=-1
for a in al:
    if a-1==b:
        print(0)
        exit()
    b=a
    if a-1!=now:
        ans=(ans%mod)*(dd(a-now-1)%mod)%mod
    now=a+1

print(ans)

Submission status: Wrong Answer

Solution code:
import math
import functools
import operator


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

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
    
def sum_comb(gap):
    if gap < 0:
        return 0
    elif gap < 2:
        return 1
    else:
        return sum([combinations_count(gap-i, i) for i in range((gap//2+1))])

combs = []
now = 0
for step in break_steps:
    gap = step - 1 - now
    if gap < 0:
        print(0)    
    else:
        combs.append(sum_comb(gap))
        now = step + 1 
gap = n - now
combs.append(sum_comb(gap))
print(functools.reduce(operator.mul, combs) % 1000000007)

Submission status: Wrong Answer

Solution code:
a=input().split()
a=list(map(int,a))
l=[]
for i in range(a[0]+1):
    l.append(i)
v=0
while v<a[1]:
    h=int(input())
    l.remove(h)
    v+=1
b=0
pos=1
while b<len(l)-2:
    if l[b+1]==(l[b]+1) and (l[b+2])== (l[b]+2):
        pos=((pos%1000000007)*2)%1000000007
    elif l[b+1]==l[b]+1 and l[b+2]!= l[b]+2:
        pass
    elif l[b+1]!=l[b]+1 and l[b+2]== l[b]+2:
        pass
    elif l[b+1]==l[b]+2:
        pass
    else:
        pos=0
        break
    b+=1
print(pos%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)
 
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)