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:
# 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)
print(out%1000000007)

Submission status: Wrong Answer

Solution code:

target=0
o_list=[1,2]
n=0
t_list=[]
try:
    input1=[int(n) for n in input().split(' ')]
    target=input1[0]
    n=input1[1]
    for x in range(n):
        t_list.append(int(x))
except:
  print('age,price must be numbers')
  sys.exit(1)

min_v = 10000
is_found = True
is_less = True
path=[0]
success = 0
d=1000000007
while(is_found or is_less):
    path_new=[]
    is_found=False
    is_less= False
    for i in o_list:
        for pre in path:
            new_n = i + pre
#             print(new_n)
            if not(new_n in t_list):
                if new_n < target:
                    is_less= True
                    path_new.append(new_n)
                if new_n == target:
                    success+=1
                    is_found=True
    if not is_found:
        path=[0]
    path = path_new
#     print(is_less)
#     print(is_found)
#     print("success")
#     print(success)
# print(success)
q, mod = divmod(success, d)
print(mod)

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(dp[n])

Submission status: Wrong Answer

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

for i in range(n-2):
    c =b[i]
    d = b[i+1]
    e = c + d
    b.append(e)

c = []
c.append(b[a[1] - a[0]  - 1])
i = 1
while i <= m:
    if a[i + 1] - a[i] > 1:
        c.append(b[a[i + 1] - a[i]  - 3])
        i += 1
    else:
        c.append(0)
        break
#print(c)
d = c[0] 
i = 1
#print(d)
while i < len(c):
    d = d * c[i]
    i += 1
print(d % 1000000007)

Submission status: Wrong Answer

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

p = 1
for i in range(N-1):
#  i += 1
  if i in A:
    continue
  elif i+1 in A and i+2 in A:
    p = 0
    break
  elif i+1 in A or i+2 in A:
    p *= 1    
  else:
    p *= 2
    
print(p % 1000000007)

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("fake")
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())
a = [int(input())-1 for i in range(m)]
l = [True]*(n+1)
count = 1
for i, v in enumerate(l,0):
  if i in a:
    l[i+1] = False
for i in range(len(l)-2):
  if l[i] == True and l[i+1] == True and l[i+2] == True:
    count *= 2
  elif l[i] == True and l[i+1] == True and l[i+2] == False:
    count *= 1
  elif l[i] == True and l[i+1] == False:
    count *= 1
  elif l[i] == False and l[i+1] == True:
    continue
  elif l[i] == False and l[i+1] == False:
    count = 0
    break
print(count%1000000007)

Submission status: Wrong Answer

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

a.insert(0,-10)
a.append(-10)
route = True

abefore = -10
for i in range(M):
    if (abefore+1) == a[i]:
        route = False
    abefore = a[i] 

if route:
    ibefore = 0
    ans = 1
    for i in range(M):
        if(a[i+1] - ibefore - 1) != 0:
            ans = ans*(a[i+1] - ibefore - 1) 
        ibefore = a[i+1]
    if(N - a[M] - 1) != 0:
        ans = ans * (N - a[M] - 1)
    print(ans%1000000007)
else:
    print(0)

Submission status: Wrong Answer

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

sumList = [0] * (N+2)
sumList[0] = 0
sumList[1] = 1
sumList[2] = 2
for i in range(3, N+1) :
    sumList[i] = sumList[i-1] + sumList[i-2]
if M == 0 :
    print(sumList[N])
    exit()

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

Submission status: Wrong Answer

Solution code:
import math
n, m = map(int, input().split())
a = [0]
sum = 0
flag = 0
for i in range(m):
    ain = int(input())
    a.append(ain)
a.append(n)
for i in range(len(a)-1):
    if a[i+1] - a[i] == 1 and a[i] != 0:
        flag = 1
        break
    if a[i+1] - a[i] >= 2 and (a[i+1] - a[i])%2 == 0:
        for j in range(int((a[i+1]-a[i])/2+1)):
            sum += math.factorial((a[i+1]-a[i])/2+j)/(math.factorial((a[i+1]-a[i])/2-j) * math.factorial(2*j))
    if a[i+1] - a[i] >= 2 and (a[i+1] - a[i])%2 == 1:
        for j in range(int(math.ceil((a[i+1]-a[i])/2))):
            sum += math.factorial(math.ceil((a[i+1]-a[i])/2))/((math.factorial(math.floor((a[i+1]-a[i])/2)-j))*math.factorial(1+j*2))
if flag == 1:
    print(0)
else:
    print(int(sum%1000000007))

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+1))
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 = (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]
for i in range(n-2):
    fibo.append(fibo[-1]+fibo[-2])
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:
       ans *= fibo[a[x+1]-a[x]-3]
print(ans%1000000007)

Submission status: Wrong Answer

Solution code:
import math
def cmb(n, r):
    return math.factorial(n)// ( math.factorial(n-r) * math.factorial(r) )



N,M = input().split()

N = int(N)
M = int(M)

a = []
ans = 1

for i in range(M):
    newa = int(input())
    a.append(newa)

if (M != 0):
    for k in range(M-1):
        if (a[k+1] - a[k] == 1):
            ans = 0
            
    
    
    for i in range(M + 1):
    

        if (i == 0):
            dan = a[i] - 1
        elif (i == M):
            dan = N - a[i - 1] - 1
        else:
            dan = a[i] - a[i - 1] - 2

        abletwo = (dan - (dan % 2)) // 2
        now = 0

        if (dan != 0):

            for j in range(abletwo + 1):

                now += cmb (dan - j , j )

        else:
            now = 1
        
        ans *= now

else:
    ans = 1

ans = ans % 1000000007
print (ans)

Submission status: Wrong Answer

Solution code:
n, m = list(map(int, input().split(' ')))
a = []
c = 1
p = 0

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

while p < n:
    if p+2 not in a:
        p += 2
    elif p+1 not in a:
        p += 1
    else:
        c = 0
        break
    c += 1

print(c%1000000007)

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
    if b < 0:
        ans *= 0
        break
    c = a+1
    ans *= (1 + sum([i for i in range(-(-b//2), b)])) % e
    
b = n - c
ans *= (1 + sum([i for i in range(-(-b//2), b)])) % e
print(ans)

Submission status: Wrong Answer

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

cur_step = 0
steps = []
ans = 1
for a in A:
	if a-cur_step == 0:
		ans = -1
		break
	if a == 1:
		steps.append(1)
		cur_step = 2
		continue
	steps.append(a-1-cur_step)
	cur_step = a+1
# print(steps)
#ごり押しパターン計算
pat = [1,2]
inf = 10**9+7
while len(pat) < max(steps):
	pat.append((pat[-1]+pat[-2])%inf)

if ans == -1:
	print(0)
else:
	for step in steps:
		ans = (ans*pat[step-1])%inf
	print(ans)

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 = [0] * (n+1)

for i in range(n+1):
    if i == 0:
        l[i] = 1
        continue
    
    if i == 1:
        l[i] = 1

    if i in a:
        l[i] = 0
    else:
        l[i] = l[i-2] + l[i-1]

print(l[-1] % 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:
    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:
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:
import math
N,M = map(int,input().split(" "))
a = []
for i in range(M):
    a.append(int(input()))
#print(a)

NG_FLAG1 = 0
for i in range(M-1):
    if a[i+1] - a[i] == 1:
        NG_FLAG1 = 1

if NG_FLAG1 == 1:
    print(0)
else:   
    STEP = [0] * N
    for i in range(M):
        STEP[a[i]-1] = "x"
    #print(STEP)
    comb_list = []
    comb_count = 0
    for i in range(N):
        if STEP[i] == "x":
            comb_list.append(comb_count)
            comb_count = 0
        elif STEP[i] == 0:
            comb_count += 1
            if i == N-1:
                comb_list.append(comb_count)
        #print(i)
    #print(comb_list)
    """
    for i in range(len(comb_list)):
        comb_list[i] = math.floor(comb_list[i]/2) + 1
    print(comb_list)"""
    def permutations_count(n, r):
        return math.factorial(n) // math.factorial(n - r)
    def stepper(step_num):
        looper = math.floor(step_num/2) + 1
        calc = 0
        for j in range(looper):
            calc += permutations_count(step_num, step_num - (j+2))
            step_num -= 2
        return calc

    ans = 0
    for i in range(len(comb_list)):
        cf = stepper(comb_list[i])
        ans += cf
    print(ans%1000000007)

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
    if b < 0:
        ans *= 0
        break
    c = a+1
    print(sum([i for i in range(-(-b//2), b)]))
    ans *= (1 + sum([i for i in range(-(-b//2), b)])) % e
    
b = n - c
ans *= (1 + sum([i for i in range(-(-b//2), b)])) % e
print(ans)

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 a[i] - a[i-1] == 1:
    print(0)
    break

  elif i == m:
    sum *= step(a[m] - a[m-1] -1)

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

print(sum % 1000000007)

Submission status: Wrong Answer

Solution code:
import math

#n = int(input())
n, m = [int(i) for i in input().split()]
#table = [[int(i) for i in input().split()] for n in range(n)]
#list = [int(i) for i in input().split()]
#s = input()
#list = list(s)

s = [int(input()) for i in range(m)] #m行1列入力

MOD = 1000000007


def fib(n):
    a = 0
    b = 1
    temp = 0
    if (n == 0) :
        return 0
    elif (n == 1) :
        return 1
    else:
        for i in range(n-1) :
            temp = b
            b = (a + b) % MOD
            a = temp
        return b

kotae = 1

if (m == 0) :
    kotae = (kotae * fib(n)) % MOD
else :
    for i in range(m + 1) :
        if (i == 0) :
            kotae = (kotae * fib(s[i])) % MOD
        elif (i == m) :
            kotae = (kotae * fib(n - s[i-1])) % MOD
        else :
            kotae = (kotae * fib(s[i] - s[i-1] - 1)) % MOD


print(kotae)

Submission status: Wrong Answer

Solution code:
def Fib(n):
    a, b = 1, 2
    if n == 1:
        return a
    elif n == 2:
        return b
    else:
        for i in range(n - 2):
            a, b = b, a + b
        return b

now_step = 0
ans = 1
N, M = map(int, input().split(" "))
for i in range(M):
    a = int(input())
    if now_step == a:
        ans *= 0
        break
    elif now_step == (a - 1):
        now_step = a + 1
        continue
    else:
        ans *= Fib((a - 1) - now_step)
        now_step = a + 1
ans *= Fib(N - now_step)
print(ans % 1000000007)

Submission status: Wrong Answer

Solution code:
from math import factorial
"m段登る時の登り方の総数"
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:
        s+=int(factorial(m1+m2)/(factorial(m1)*factorial(m2)))
        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:
inputs = [int(s) for s in input().split()]
n = inputs[0]
m = inputs[1]
a = [int(input()) for i in range(m)]
con = 1000000007

if(n != 1 and n != 2):
    cache = [-1]*n
    if(1 in a and 2 in a):
        cache[0] = 0
        cache[1] = 0
    elif(1 in a):
        cache[0] = 0
        cache[1] = 1
    elif(2 in a):
        cache[0] = 1
        cache[1] = 0
    else:
        cache[0] = 1
        cache[1] = 2
    result = -1
    for i in range(2, n):
        if(cache[i-1] == 0 and cache[i-2] == 0):
            result = 0
            break
        elif(cache[i] == -1 and (i+1 not in a)):
            cache[i] = (cache[i-1] + cache[i-2]) % con
        elif(cache[i] == -1 and (i+1 in a)):
            cache[i] = 0

    print(cache)
    if(result == 0):
        print(result)
    else:
        print(cache[n-1])
elif(n == 1):
    print(1)
else:
    if(m == 0):
        print(2)
    else:
        print(1)

Submission status: Wrong Answer

Solution code:
N,M = list(map(int,input().split()))
a = [int(input()) for i in range(M)]
dekai = 1000000007
"""
import sympy as sym

def Fib(n):
	x = sym.symbols('x',nonnegative=True,integer=True)
	Fib=1/sym.sqrt(5)*(((1+sym.sqrt(5))/2)**(n-1)-((1-sym.sqrt(5))/2)**(n-1))
	result=Fib.subs(x,n)
	result=result.evalf(int(n*3/14)+1)
	return int(result)


"""
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
ans = 1

if M == 0:
	print(Fib(N+1-(-1)))
	exit()

for i in range(M+1):
	if i == 0:
		ans = (ans*(Fib(a[0]-(-1))%dekai))%dekai
	elif i == M:
		ans = (ans*(Fib(N+1-a[M-1])%dekai))%dekai
	else:
		ans = (ans*(Fib(a[i]-a[i-1])%dekai))%dekai
print(ans)

Submission status: Wrong Answer

Solution code:

n, m = map(int, input().split())
an = [0]*m

for i in range(m):
#    s = input()
    an[i] = int( input() )
#an[-1] = n

#an.sort()
disjoint = False
for i in range(len(an)-1):
    if an[i] + 1 == an[i+1]:
        disjoint = True





if disjoint:
    print(0)

else:

    mod = 10**9+7
    tab = [0]*(10**5+1)
    tab[0] = 0
    tab[1] = tab[2]= 1

    for i in range(3, len(tab)):
        tab[i] = tab[i-1]+tab[i-2]
#        if i<100:
#            print(tab[i])

    an.append(n)
    prev = 0
    ans = 1
    for a in an:
        index = a-prev + (1 if prev != 0 and a == n else 0)
#        print(a,prev,index,tab[index])
        ans *= tab[index]
        ans %= mod
        prev = a+1

    #ans *= tab[n - prev]
    #ans %= 1000000007

    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
n, m = map(int, input().split())
if m == 0:
    if n == 1:
        print(1)
    elif n == 2:
        print(2)
    else:
        fib = [1, 2]
        for j in range(n):
            fib.append(fib[j] + fib[j + 1])
        print(fib[n])
    sys.exit()

a = [int(input()) for i in range(m)]
a.insert(0, -1)
a.append(n + 1)

l = [a[i + 1] - a[i] for i in range(m + 1)]
error = 0
for i in range(m + 1):
    if l[i] == 1:
        error = 1
if error == 1:
    print(0)
    sys.exit()

ma = max(l) #ここまでFibを計算する
fib = [1, 1]
for j in range(ma):
    fib.append(fib[j] + fib[j + 1])
ans = 1
for i in range(len(l)):
    ans = ans * fib[(l[i] - 2)]
print(int(ans % 1000000007))

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))
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:
import math
def cmb(n, r, mod, g1, g2):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

def main():
    N, M = map(int, input().split())
    A = [-1] + [int(input()) for i in range(M)] + [N + 1]

    mod = 10**7+7 #出力の制限
    N = 10**5
    g1 = [1, 1] # 元テーブル
    g2 = [1, 1] #逆元テーブル
    inverse = [0, 1] #逆元テーブル計算用テーブル
    for i in range( 2, N + 1 ):
        g1.append( ( g1[-1] * i ) % mod )
        inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
        g2.append( (g2[-1] * inverse[-1]) % mod )

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

    ans = 1
    for dd in d:
        if dd > 1:
            tmp = 0
            for j in range(dd//2 + 1):
                tmp += cmb(dd - j, j, mod, g1, g2)
            ans *= tmp

    print(ans % 1000000007)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def calcPatt(steps):
    if steps <= 1:
        return 1
    elif steps == 2:
        return 2
    ll = {}
    # ここからは3以上
    for i in range(steps)[::-1]:
        if i + 1 == steps:
           ll[i] = 1
        elif i + 2 ==steps:
            ll[i] = 2
        else:
            ll[i] = ll[i+1] + ll[i+2]
    
    return ll[0]

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

before = 0
ll = []
for i in range(M):
    a = int(input()) - 1
    stepRenge = a  - before
    ll.append(calcPatt(stepRenge))
    before = a + 2
    

# 最後の一回分が残ってるのでやる
stepRenge = N  - before
ll.append(calcPatt(stepRenge))

pro = 1
for i in ll:
    pro = (pro * i) % 1000000007
 
print(pro)

Submission status: Wrong Answer

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

import functools
import operator

import sys
n, m = map(int, input().split())
a = sorted(list(set(map(int, sys.stdin.readlines()))))
m = len(a)

s = 0
e = n
xs = [0] * (m + 1)
for i, j in enumerate(a):
  xs[i] = fb(j - s - 1)
  s = j + 1
xs[m] = fb(n - s)
if 0 in xs:
  print(0)
else:
  result = functools.reduce(operator.mul, xs)
  print(result % 1000000007)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
N, M = map(int, input().split())
A = []
for _ in range(M):
    A.append(int(input()))

for s1, s2 in zip(A[1:], A[:-1]):
    if s1 - s2 == 1:
        print(0)

else:
    
    num_goup = [1]
    for s in range(1, N + 1):
        if s in A:
            num_goup.append(0)
            continue
    
        if s == 1:
            num_goup.append(1)
            continue
    
        if num_goup[-1] == 0:
            num_goup.append(num_goup[-2])
        else:
            if num_goup[-2] == 0:
                num_goup.append(num_goup[-1])
            else:
                num_goup.append(num_goup[-1] + num_goup[-2])
    
    print(num_goup[-1] % 1000000007)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import numpy as np
import scipy as sp


def rec_stairs(step, broken, pattern_n, N):
    # print(step, broken, pattern_n, N)
    if step == N:
        pattern_n = pattern_n + 1
    elif step > N:
        pass
    else:
        if (step+1) in broken:
            pass
        else:
            pattern_n = rec_stairs(step+1, broken, pattern_n, N)
            # print(step, broken, pattern_n, N)
            # print('a', pattern_n)

        if (step+2) in broken:
            pass
        else:
            pattern_n = rec_stairs(step+2, broken, pattern_n, N)
            # print(step, broken, pattern_n, N)
            # print('b', pattern_n)

    return pattern_n


def main():
    try:
        in1 = list(map(int, input().split()))
        N = in1[0]
        M = in1[1]

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

        sum_pattern_n = rec_stairs(0, in2, 0, N)
        print(sum_pattern_n % 1000000007)
    except:
        pass

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

def check(A):
    for m in range(M-1):
        if A[m+1]-A[m]==1:
            return False
    return True

def fibo(n):
    if n==0 or n==1:
        return 1
    else:
        L=[1,1]
        for i in range(2,n+1):
            L=[L[-1]]+[sum(L)]
        return L[-1]

def main(A,N):
    if check(A)==False:
        return 0
    else:
        A=[0]+A+[N+1]
        B=[max(A[n+1]-A[n]-2,0) for n in range(M+1)]
        x=1
        for b in B:
            x*=fibo(b)
        return x%mod

print(main(A,N))

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 - a <= 1:
        result = 0
        break
    result += fib[b-a]
    a = b
    
mod = 1000000007
print(result%mod)

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
ans = 1
while i < n:
  if i+1 in t_list:
    ans = ans * 1
    i += 1
    if i+1 in t_list:
      ans = 0
      break
  else:
    if i+2 in t_list and not i+3 in t_list:
      ans = ans * 1
      i += 2
    elif i+1 == n:
      ans = ans * 1
    else:
      ans = ans * 2
  i += 1
    
print(ans % 1000000007)

Submission status: Wrong Answer

Solution code:
def Fib(n):
    a, b = 0, 1
    if n == 1:
        return a
    elif n == 2:
        return b
    else:
        for i in range(n-2):
            a, b = b, a + b
        return b

N,M = map(int,input().split())
if M == 0:
  print(Fib(N+2))
else:
  S = []
  for _ in range(M):
    S.append(int(input()))
  S.append(-1)
  S.append(N+1)
  S.sort()  
  P = 1

  for i in range(M+1):
    P *= Fib(S[i+1]-S[i]) 

  print(P%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])
    print(steps)
    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)

Submission status: Wrong Answer

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

ways = [1] * (n+1)
for i in broken:
  ways[i] = 0
  
keep = 1
for i in range(1, n+1):
  if ways[i]:
    if keep == 2:
      ways[i] = ways[i-1] + ways[i-2]
    elif keep == 1:
      ways[i] = ways[i-1]
      keep += 1
    else:
      ways[i] = ways[i-2]
      keep += 1
  else:
    keep = 0
      
print(ways[-1] % 1000000007, ways)

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] == -1:
        dp[i + 1] = (dp[i] + dp[i - 1]) % mod
print(dp[n])

Submission status: Wrong Answer

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


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


ans = 1
for i in range(m + 1):
    if i == 0 or i == m:
        ra = a[i+1] - a[i] - 1
    else:
        ra = a[i+1] - a[i] - 2
    if ra < 0:
        if i == 0 or i == m:
            continue
        else:
            ans = 0
            break
    elif ra == 0:
        continue
    elif ra == 1:
        continue
    else:
        aaa = 1
        for n in range(1, ra // 2 + 1):
            length = ra - (2 * n) + n
            aaa += combinations_count(length, n)
        ans *= aaa

print(ans % 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 = 1
	for i, vol in enumerate(a):
		if base == 0:
			ans = ans * fb(vol)
			base = vol
		else:
			ans = (ans% 1000000007) * (fb(vol-base)% 1000000007)
			base = vol

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

	print(ans % 1000000007)


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().strip().split())
c = []
dic = {}
for i in range(m):
    a = int(input())
    c.append(a)
c.insert(0,0)
c.append(n)
dic[0] = 0
dic[1] = 1
dic[2] = 2
for i in range(100002):
    dic[i+3] = dic[i+1]+dic[i+2]
dic
res = 1
for i in range(len(c)-1):
    a = c[i+1]-c[i]-1
    res = res * dic[a]
print(res)

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;
  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
  #print(count)
  print(count % 1000000007)

Submission status: Wrong Answer

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

b = 0
for i in range(m-1):
    if a[i+1] - a[i] == 1:
        b = 1
if b == 1:
    print(0)
else:
    kaidan = [1,2]
    for i in range(2,n):
        kaidan.append(kaidan[i-1]+kaidan[i-2])
    kaidan = [0] + kaidan