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 = [0]
for i in range(m):
    a.append(int(input()))
a.append(n)

def f(count, count_):
    return count + count_, count


pattern = 0
for i in range(1, len(a)):
    steps = a[i] - a[i-1] - 1
    j = steps
    c = 0
    c_ = 0
    if j > 3:
        c = 3
        c_ = 2
        while j > 0:
            c, c_ = f(c, c_)
            j -= 1
        pattern += c
    elif j == 2:
        pattern += 2
    elif j == 1:
        pattern += 1
    else:
        if i == 1:
            pattern += 1
        else:
            pattern = 0
            break
print(pattern % 1000000007)

Submission status: Wrong Answer

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
from bisect import bisect_left, bisect_right

# import numpy as np
# from scipy.special import perm
# from scipy.special import comb

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
INF = float("inf")

########

N, M = l_inpl()
a = { i_inpl(): True for _ in range(M)}
# for _ in range(M):
#     ai = i_inpl()
#     a.append(ai)

dp = [0] * (N+1)

dp[0] = 1

for now_i in range(N):
    for next_i in range(now_i+1, min(N, now_i+2)+1):
        if next_i not in a:
            dp[next_i] += dp[now_i]
            dp[next_i] % 1000000007

print(dp[N])

Submission status: Wrong Answer

Solution code:
def Fib(n):
    a,b = 1,1
    if n == 1:
        return 1
    elif n == 2:
        return 1
    else:
        for i in range(n-2):
            a,b = b,a+b
        return b
    
n,m = map(int,input().split())
start = []
for i in range(m):
    start.append(int(input()))

if start == []:
    print(Fib(n))
else:
    pstart = [-1]+start+[n+1] #スタートとゴールを追加
    newlist = [] #距離のリスト
    for j in range(len(pstart)-1):
        newlist.append(pstart[j+1]-pstart[j]) #障害物同士の距離を測る
    if 1 in newlist[1:len(newlist)-1]:
                 print(0)
    else: #ちゃんと距離が出そうなとき
        ans = 1
        #print(newlist)
        for w in newlist:
            #print(Fib(w-1))
            #print(ans)
            ans = (ans*Fib(w-1))%1000000007
        print(ans)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
A=[int(input()) for i in range(M)] #0からM-1まで


root=[0]*(N+2)   #間がiの時の行き方
for i in range(N+2):    #0からN-1まで
    if i==0:
        root[0]=0
    elif i==1:
        root[1]=1
    elif i==2:
        root[2]=1
    else:
        root[i]=root[i-1]+root[i-2]
#print(root)

ans=0
if M==0:
    print(root[N+1])
    exit()

if N==0:
    print(0)
    exit()

for i in range(M+1): #0からM
    if i==0:
        ans=root[A[0]]
    elif i==M:
        ans*=root[N-A[M-1]]
    else:
        ans*=root[A[i]-A[i-1]-1]
print(ans%(10**9+7))

Submission status: Wrong Answer

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

def f(count, count_):
    return count + count_, count


pattern = 0
for i in range(1, len(a)):
    steps = a[i] - a[i-1] - 1
    j = steps
    c = 0
    c_ = 0
    if j > 3:
        c = 3
        c_ = 2
        while j > 0:
            c, c_ = f(c, c_)
            j -= 1
        pattern += c
    elif j == 2:
        pattern += 2
    elif j == 1:
        pattern += 1
    else:
        pattern = 0
        break
print(pattern % 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)"""
"""def fib(n):
    a, b = 0, 1
    if(n == 1):
        return a
    elif(n == 2):
        return b
    else:
        for _ in range(n-2):
            a, b = b, a + b
        return b"""


class multipliable_2x2matrix(object):
    def __init__(self, a, b, c, d):
        self.a = a
        self.b = b
        self.c = c
        self.d = d

    def mul(self, b):
        return multipliable_2x2matrix(
            self.a * b.a + self.b * b.c,
            self.a * b.b + self.b * b.d,
            self.c * b.a + self.d * b.c,
            self.c * b.b + self.d * b.d)


def fib(n):
    if n == 0: return 0
    m = multipliable_2x2matrix(1, 1, 1, 0)
    f = multipliable_2x2matrix(1, 0, 0, 1)
    n = n - 1
    while n > 0:
        if n & 1 == 1:
            f = f.mul(m)
        n = n >> 1
        m = m.mul(m)
    return f.a


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"""
if(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 = map(int, input().split())
broken_stairs = list(int(input()) for _ in range(M))


def get_route_num(num):
    # print('step num', num)
    if num == 0:
        return 1
    if num < 4:
        return num
    prev_route = 3  # num = 3
    prev_prev_route = 2  # num = 2
    route = prev_route + prev_prev_route
    for _ in range(4, num + 1):
        route = prev_route + prev_prev_route
        prev_prev_route = prev_route
        prev_route = route
        # print('route', route)
    return route


if len(broken_stairs) == 0:
    print(get_route_num(N))
    exit()

cur = 0
possible_route = 1
for i in range(M):
    if not cur == 0 and broken_stairs[i] - cur == 0:
        print(0)
        exit()
    step = broken_stairs[i] - cur - 1
    possible_route *= get_route_num(step)
    cur = broken_stairs[i] + 1

possible_route *= get_route_num(N - cur)
print(possible_route % 1000000007)

Submission status: Wrong Answer

Solution code:
import sys
import re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from copy import copy
import numpy as np
from numpy.fft import fft, ifft
from fractions import gcd
import math


def input(): return sys.stdin.readline().strip()


def INT(): return int(input())


def MAP(): return map(int, input().split())


def LIST(): return list(map(int, input().split()))


sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7


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

a = [INT() for _ in range(m)]

a.insert(0,0)
a.append(n)

ans=1
for i in range(len(a) - 1):
    p = a[i + 1] - a[i]+2
    ans *= Fib(p)
    #print(ans)

print(ans%MOD)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
A=[int(input()) for i in range(M)] #0からM-1まで


root=[0]*(N+2)   #間がiの時の行き方
for i in range(N+2):    #0からN-1まで
    if i==0:
        root[0]=0
    elif i==1:
        root[1]=1
    elif i==2:
        root[2]=1
    else:
        root[i]=root[i-1]+root[i-2]
#print(root)

ans=0
if M==0:
    print(root[N+1])
    exit()

for i in range(M+1): #0からM
    if i==0:
        ans=root[A[0]]
    elif i==M:
        ans*=root[N-A[M-1]]
    else:
        ans*=root[A[i]-A[i-1]-1]
print(ans%(10**9+7))

Submission status: Wrong Answer

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

import math

def counter(x):
    import math
    arr= []
    u = int(x/2)
    for i in range(u+1):
        one = x-2*i
        two = i
        cnt = math.factorial(x-2*i)/(math.factorial(one)*math.factorial(two))
        arr.append(cnt)
    return(int(sum(arr)))

nList = list(set(List))
flg = 0

for j in range(len(nList)-1):
    if (nList[j+1]-nList[j]==1):
        flg = 1

if flg==1:
    print(0)
    
else:
    cnt = []
    arr = []
    nList = [0]+nList        
    for k in range(len(nList)-1):
        cnt.append(counter(nList[k+1]-nList[k]))
    ans = int(sum(cnt))*counter(N-nList[-1])
    print(ans%1000000007)

Submission status: Wrong Answer

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

def fib(n):
        a, b = 0, 1
        for i in range(n):
            a, b = b, a + b
        return b

if M == 0:
    print(fib(N))
    exit()

flag = 0
if M >= 2:
    for i in range(M-1):
        if a[i+1] - a[i] == 1:
            flag += 1
    if flag >= 1:
        print(0)
        exit()

ans = fib(a[0]-1)
for i in range(M-1):
    ans = (ans * fib(a[i+1]-a[i]-2))%(10**9+7)

ans = (ans * fib(N-a[-1]-1))%(10**9+7)

print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
MOD = 1000000007 
D=[0] * (n+2)
D[0] = 1
for _ in range(m):
    D[int(input())] = -1
for i in range(n):
    if D[i] == -1:
        continue
    if D[i+1] != -1:
        D[i+1] += D[i]
    if D[i+2] != -1:
        D[i+2] += D[i]
    D[i]%=MOD
print(D[n])

Submission status: Wrong Answer

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

b = [0]*(n+2)
b[0] = 1

for i in range(m):
    b[int(input())] = -1

for i in range(m):
    if b[i] != -1:
        if b[i+1] != -1:
            b[i+1] += b[i]
        if b[i+2] != -1:
            b[i+2] += b[i]
        b[i] %= 1000000007

print(b[n] % 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 = input().split()
breakFloor = []
for i in range(int(M)):
  breakFloor.append(int(input()))
outBreak = 0
jama = 0
for i in range(len(breakFloor)):
  jama += Fib(breakFloor[i])
  if i>=1 and breakFloor[i]-breakFloor[i-1]==1:
    outBreak = 1
all = Fib(int(N))

ans = (all - jama) % 1000000007
if outBreak ==1: ans = 0
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
pattern = [2]*N
pattern[-1] = 1
 
for i in range(M):
    a = int(input())
    if a == 1:
        pattern[a] = 1
        pattern[a-1] -= 1
    else:
        pattern[a] = 1
        pattern[a-1] -= 1
        pattern[a-2] -= 1
CP = 1
for i in range(N):
    CP *= pattern[i]
    CP %= 1000000007
print(CP % 1000000007)

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):
            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)
        ans = (ans * comb) % 1000000007
print(ans)

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

Submission status: Wrong Answer

Solution code:
broken_step = []
     
line = [int(s) for s in input().split()]
     
N, M = line[0], line[1]
     
for i in range(M):
    step_num = int(input().split()[0])
    broken_step.append(step_num)
        
        
dp = [0]*(N+1)
dp[0] = 1
if 1 in broken_step:
    dp[1] = 0
else:
    dp[0] = 1
     
for i in range(2, N+1):
    dp[i] = (dp[i-1]+dp[i-2])%1000000007 if i not in broken_step else 0
print(dp[N])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
n, m = map(int, input().split())
BIGNUM = 10 ** 9 + 7

if m > 0:
    last_ana = 0
    blocks = list()
    for _ in range(m):
        ana = int(input())
        blocks.append(ana - last_ana - 1)
        last_ana = ana
    blocks.append(n - last_ana)
else:
    blocks = [n + 1]

if 0 in blocks:
    ans = 0
else:
    b_max = max(blocks)
    c = [1, 1]
    for i in range(2, b_max):
        ctmp = c[i - 1] + c[i - 2]
        c.append(ctmp % BIGNUM)

    ans = 1
    for num in blocks:
        if num == 1:
            continue
        ans = (ans * c[num - 1]) % BIGNUM
        if ans == 0:
            break

print(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)"""
def fib(n):
    a, b = 0, 1
    if(n == 1):
        return a
    elif(n == 2):
        return b
    else:
        for _ in range(n-2):
            a, b = b, a + b
        return b


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"""
if(not flag):
    answer = 0
else:
    sum = 1
    for i in range(len(b)):
        sum *= fib(b[i] + 2)
        sum = sum % (10**9 + 7)
    answer = sum
print(answer)

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):
        a_list.append(a[i+1]-a[i]-1)
    a_list.append(n-a[-1]-1)
    if a_list[0] ==0:
        a_list.pop(0)
    for i in a_list:
        tmp = 0
        for j in range(i):
            if i - 2*j >=0:
                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:
a,b=map(int,input().split())
l=[]
m=[]
ans=1
for i in range(a):
    m.append(2)
for i in range(b):
   
    t=int(input()) 
    if(t>=2):
        m[t]=m[t]-1
        m[t-1]=m[t-1]-1
        m[t-2]=m[t-2]-1
    else:
        m[t]=m[t]-1
        m[t-1]=m[t-1]-1
m[a-1]=m[a-1]-1
#print(m)
for i in m:
    if(i==0):
        ans=0
        break
    ans*=i
 
print(ans%1000000007)

Submission status: Wrong Answer

Solution code:
from collections import deque

N, M = map(int, input().split())  # N…段数、M…壊れてる床
crashstep = [int(input()) for i in range(M)]

waru = 1000000007

# 階段マッピング
step = []
for i in range(N):
    if i in crashstep:
        step.append(1)
    else:
        step.append(0)

#print(step)

# 階段探索
stack = deque()
# for j in range(N):
cnt = 0
end = False
nodes = 0

while end == False:
    # １歩でも２歩でも登れる段は分岐するのでスタックに保存
    if cnt + 2 < N and step[cnt + 1] == 1 and step[cnt + 2] == 1:
        print("0")
        quit()

    if cnt + 2 < N and step[cnt + 1] == 0 and step[cnt + 2] == 0:
        stack.append(cnt)
        # print(cnt)

    if cnt == N:
        nodes += 1
        if len(stack) > 0:
            cnt = stack.pop()
        else:
            end = True

    cnt += 1
    # print(cnt)

print(nodes % waru)

Submission status: Wrong Answer

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

MOD = 1000000007

b = [0]*(N+2)
b[0] = 1

for i in range(M):
    b[int(input())] = -1

for i in range(N):
    if b[i] != -1:
        if b[i+1] != -1:
            b[i+1] += b[i]
        if b[i+2] != -1:
            b[i+2] += b[i]
        b[i] %= MOD

print(b[N])

Submission status: Wrong Answer

Solution code:
import math
N,M = map(int, input().split())
ans = 1
bro = list([])

def Comp (A , B):
    ans = math.factorial(A) // (math.factorial(A-B) * math.factorial(B))
    return ans

def Keisan (X):
    sum=0
    a = int(X//2+1)
    x = int(X)
    if X== -1:
        return 0

    for i in range(a):
        sum+= Comp(x-i , i)

    return sum


for i in range(M):
    bro.append(input())

bro.append(N+1) #最終段　＋１　をゴールとして設定


for i in range(len(bro)):
    if i == 0:
        a = int(bro[i])
        ans = ans*Keisan(a-1)
    else:
        a = int(bro[i])
        b = int(bro[i-1])
        ans = ans*Keisan(a-b-2)

ans = int(ans//(10**9+7))

print(ans)

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
        if dp != 0:
            Ans *= dp
        dp = 0
Ans *= dp
print(Ans % 1000000007)

Submission status: Wrong Answer

Solution code:
fiblist = [0] * 100001
fiblist[0] = 1
fiblist[1] = 1

n,m = map(int,input().split())

if m == 0:
    print(fiblist[n])
else:
    a = []
    for i in range(m):
        a.append(int(input()))

    d = [a[0]-1]
    for j in range(1,m):
        d.append(a[j]-a[j-1]-2)

    d.append(n-a[m-1]-1)


    for p in range(2,100001):
        fiblist[p] = (fiblist[p-1]+fiblist[p-2]) % 1000000007

#print(d)

    if (-1 in d) or (-2 in d):
        print(0)
    else:
        ans = 1
        for k in range(m+1):
            ans = (ans * fiblist[d[k]]) % 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:
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"""
    if cur + 1 == x:
        return 1
    else:
        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 sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''

mod = 10 ** 9 + 7
N, M = map(int, input().split())
a = [0] * M

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

now = 0
ans = 1
flag = 0

for i in range(M):
	if now == a[i]:
		flag = 1
		break
	
	next = a[i] - now - 1
	if next % 2 == 0:
		ans = (ans * 2 ** -(-next // 2)) % mod
	else:
		ans = (ans * (2 ** -(-next // 2)) - 1) % mod
	now = a[i] + 1

if flag == 1:
	print(0)
else:
	next = N - now
	if next % 2 == 0:
		ans = (ans * 2 ** -(-next // 2)) % mod
	else:
		ans = (ans * (2 ** -(-next // 2)) - 1) % mod
	print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
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 m!=0:
    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 flag==True:
    print(0)
elif m==0:
    print(fb(n))
else:
    print(key%1000000007)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
mList = []
for m in range(M):
  num = int(input())
  if num - 1 in mList:
    print("0")
    exit()
  mList.append(num)

l = [2]*(N-1)
l.append(1)
for i in range(N):
  for m in mList:
    l[m] = 0
    if l[m-1] != 0:
      l[m-1] = 1
    if l[m-2] != 0:
      l[m-2] = 1

cnt = l.count(2)
ans = 1
for i in range(cnt // 5):
  t = 2**5
  ans = (ans * t) % 1000000007

ans = (ans % 1000000007) * (2**(cnt%5)) % 1000000007
print(ans)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
A=[int(input()) for i in range(M)] #0からM-1まで


root=[0]*(N+2)   #間がiの時の行き方
for i in range(N+2):    #0からN-1まで
    if i==0:
        root[0]=0
    elif i==1:
        root[1]=1
    elif i==2:
        root[2]=1
    else:
        root[i]=root[i-1]+root[i-2]
#print(root)

ans=0
if M==0:
    print(root[N+1])
    exit()

for i in range(M+1): #0からM
    if i==0:
        ans=root[A[0]]
    elif i==M:
        ans*=root[N-A[M-1]]
    else:
        ans*=root[A[i]-A[i-1]-1]
print(ans%1000000007)

Submission status: Wrong Answer

Solution code:
#from itertools import accumulate

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

l = [0] * (n+1)
mod = 10 ** 9 + 7
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]) % mod

print(l[-1])

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:
n,m = map(int,input().split())

h = []
a = 1
b = 1
mod = 10 ** 9 + 7

for i in range(m):
    h += [int(input()),]

for i in range(1,n+1):
    if i in h:
        a,b = 0,a
        # b %= mod
    else:
        a,b = a + b,a
        # a %= mod
        # b %= mod

print(a % mod)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
pattern = [2]*N
pattern[-1] = 1

for i in range(M):
    a = int(input())
    if a == 1:
        pattern[a] = 1
        pattern[a-1] -= 1
    else:
        pattern[a] = 1
        pattern[a-1] -= 1
        pattern[a-2] -= 1
CP = 1
for i in range(N):
    CP *= pattern[i]
print(CP % 1000000007)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
pattern = [2]*N
pattern[-1] = 1

for i in range(M):
    a = int(input())
    if a == 1:
        pattern[a] = 1
        pattern[a-1] -= 1
    else:
        pattern[a] = 1
        pattern[a-1] -= 1
        pattern[a-2] -= 1
CP = 1
print(pattern)
for i in range(N):
    CP *= pattern[i]
print(CP % 1000000007)

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 flag==True:
    print(0)
elif m==0:
    print(fb(n))
else:
    print(key%1000000007)

Submission status: Wrong Answer

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

fib=[0,1,2]
for j in range(2, 100000):
    fib.append(fib[j]+fib[j-1])


if min(c)==0:
    if c.count(0)==1 and c[0]==0:
            ans=1
            for k in c[1:]:
                ans=(ans*fib[k])
            print(ans%1000000007)
    else:
        print(0)
else:
    ans=1
    for k in c:
        ans=(ans*fib[k])
    print(ans%1000000007)

Submission status: Wrong Answer

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

fib=[0,1,2]
for j in range(2, 100000):
    fib.append(fib[j]+fib[j-1])


if min(c)==0:
    if c.count(0)==1 and c[0]==0:
            ans=1
            for k in c[1:]:
                ans=(ans*fib[k])
            print(ans)
    else:
        print(0)
else:
    ans=1
    for k in c:
        ans=(ans*fib[k])
    print(ans%1000000007)

Submission status: Wrong Answer

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


def fib(n):
    first = 0
    second = 1
    for _i in range(n):
        third = second+first
        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:
import math

"""def fib(n):
    f = (((1 + math.sqrt(5)) / 2)**n - ((1 - math.sqrt(5)) / 2)**n ) / math.sqrt(5)
    return int(f)"""
def fib(n):
    a, b = 0, 1
    if(n == 1):
        return a
    elif(n == 2):
        return b
    else:
        for _ in range(n-2):
            a, b = b, a + b
        return b


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] + 2)
        sum = sum % (10**9 + 7)
    answer = sum
print(answer)

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

Submission status: Wrong Answer

Solution code:
N, M  = map(int, input().split())
a  = []
for _ in range(M):
  a.append(int(input()))
sdic  = {}
ans = 0
sdic[N] = 1
sdic[N+1] = 1
for n in reversed(range(N)[1:]):
  if n in a:
    continue
  if n+1 in sdic:
    ans += sdic[n+1]
  if not n+1 in sdic and not n+2 in sdic:
    print(0)
    quit()
  sdic[n] = ans
print(ans%1000000007)