Problem:


Score : 300 points

Problem Statement

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

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

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

Constraints

1 \leq N \leq 10^5

0 \leq M \leq N-1

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

Input

Input is given from Standard Input in the following format:

N M
a_1
a_2
 .
 .
 .
a_M

Output

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

Sample Input 1

6 1
3

Sample Output 1

4

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

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

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

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

0 \to 2 \to 4 \to 6

Sample Input 2

10 2
4
5

Sample Output 2

0

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

Sample Input 3

100 5
1
23
45
67
89

Sample Output 3

608200469

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



Sample input:
6 1
3


Sample output:
4

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
a=[int(input()) for i in range(m)]
a.insert(0,0)
a.append(n)
b=[a[i+1]-a[i] for i in range(m+1)]
ans=1
z=[1,2]
for i in range(10**5):
    z.append(z[i]+z[i+1])
for i in b:
    ans =ans*z[i-1]
print(ans%1000000007)

Submission status: Wrong Answer

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

t = 1000000007
ans = 1


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


if m == 1:
    ans = ans * Fib(a[0] - 1) * Fib(n - a[0] - 1)
else:
    for i in range(m):
        # 最初の段
        if i == 0:
            ans = ans * Fib(a[i] - 1)
        # 二段壊れは0
        elif a[i] - a[i - 1] == 1:
            ans = 0
            break
        # 最後の段
        elif i == m - 1:
            ans = ans * Fib(a[i] - a[i - 1] - 2)
            if a[i] != n - 1:
                ans = ans * Fib(n - a[i] - 1)
            break
        # 壊れ段の間
        else:
            ans = ans * Fib(a[i] - a[i - 1] - 2)

print(ans % t)

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

p = [0]*(n+1)
for i in bk:
    p[i] = -100
if n == 1 and m == 0:
    print(1)
elif n == 1 and m == 1:
    print(0)
else:
    p[0] = 1
    if 1 in bk:
        p[1] = 0
    else:
        p[1] = 1
    for i in range(n-2):
        if p[i+2] < 0:
            p[i+2] = 0
        else:
            p[i+2] = p[i]+p[i+1]
            if p[i+2] >= 1000000007:
                p[i+2] -= 1000000007

    print(p[n])

Submission status: Wrong Answer

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

r = 1
a = 0
for i in range(M):
	b = int(input())
	r = r * int((b-a)*(b-a)/4)
	a = b
	r = r%1000000007

r = r*int((N-a)*(N-a)/4)
r = r%1000000007

print(r)

Submission status: Wrong Answer

Solution code:
import copy
n,m = map(int,input().split())
a = [int(input()) for i in range(m)]
if 1 in a:
    if 2 in a:
        a1 = 0
        a2 = 0
    else:
        a1 = 0
        a2 = 1
else:
    if 2 in a:
        a1 = 1
        a2 = 0
    else:
        a1 = 1
        a2 = 2
for i in range(3,n+1):
    if i in a:
        a1 = copy.copy(a2)
        a2 = 0
    else:
        an = a1 + a2
        a1 = copy.copy(a2)
        a2 = copy.copy(an)
print(a2 % 1000000007)

Submission status: Wrong Answer

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

amari = 1000000007
cnt = [0]*(N+1)
cnt[0] = 0
cnt[1] = 1
for i in range(2,N+1):
    t = (cnt[i-1]+cnt[i-2])
    cnt[i] = t % amari

ans = 1
for i in range(M): 
    if i == 0:
        if A[i] != 1:
            ans*= cnt[A[i]]
    elif i > 0 and i < M:
        ans*=cnt[A[i] - A[i-1]-1]

    if i == M-1:
        if A[i] != N -1:
            ans*= cnt[N - A[i]]
    
    if ans == 0:
        break
  
    ans %= amari

print(ans)

Submission status: Wrong Answer

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

m = 10**9+7

memo = [1]*(N+3)
for i in range(3,N+3):
    memo[i] = memo[i-1] + memo[i-2]

memo[0] = 0

if M == 0:
    N -= 1
    
A.append(N+1)
p = A[0]
ans = memo[p]
for i in range(1,M+1):
    ans *= memo[A[i]-p-1]
    ans %= m
    p = A[i]

print(ans)

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=[]
a=[0]+a+[n]
for i in range(len(a)-1):
    if i==0 and a[1]==1:
        step.append(1)
    elif i==len(a)-2 and a[-2]==n-1:
        step.append(1)
    elif a[i+1]-a[i]==0:
        step.append(1)
    elif i==0:
        step.append(S[a[i+1]-a[i]-2])
    
    elif i==len(a)-2:
        step.append(S[a[i+1]-a[i]-2])
     
    elif a[i+1]-a[i]==1:
        print(0)
        sys.exit()
    elif a[i+1]-a[i]==2:
        step.append(1)
    else:
        step.append(S[a[i+1]-a[i]-3])

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

Submission status: Wrong Answer

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

mod = 1000000007
def mul(a, b):
  return ((a % mod) * (b % mod)) % mod


N, M = map(int, input().split())
if M != 0:
  a = int(input())
  ret = mul(1, Fib(a))
  pre_a = a

for i in range(M-1):
  a = int(input())
  if a - pre_a <= 1:
    ret = 0
    break
  else:
    num_step = a - pre_a - 1
    ret = mul(ret, Fib(num_step))
  pre_a = a
    
if M != 0:
  num_step = N - a
  ret = mul(ret, Fib(num_step))
else:
  ret = mul(1, Fib(3+1))
print(ret)

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

broken = [0]*(M+2)
for i in range(M):
    broken[i+1] = int(input())
broken[-1] = N-1

step = [broken[i+1]-broken[i] for i in range(M+1)]

if 1 in step[1:-1]:
    print('0')
else:
    ans = 1
    for s in step:
        a = Fib(s+2)
        ans *= a
    ans = ans%1000000007
    print(str(ans))

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline

n, m = map(int, input().split())
a_list = []
comb_list = [0, 1, 2, 3]
n_2, n_1 = 2, 3
for i in range(3, n):
    n_2, n_1 = n_1, (n_2+n_1)%(10**9+7)
    comb_list.append(n_1)
for _ in range(m):
    a = int(input())
    a_list.append(a)
start = 0
ans = 1
if m == 0:
    ans = comb_list[n]
else:
    for a in a_list+[n+1]:
        if a == 1:
            start = a + 1
            continue
        elif a == n-1:
            tmp = a - start - 1
            ans = (ans * comb_list[tmp])%(10**9+7)
            break
        else:
            if start == a:
                ans = 0
                break
            else:
                tmp = a - start - 1
                ans = (ans * comb_list[tmp])%(10**9+7)
                start = a + 1
print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
a=[int(input()) for i in range(m)]
def fibonacci_dp(n):
    F = [1,1]
    for i in range(1,n-1):
        F.append((F[i]%(10**9+7)+F[i-1]%(10**9+7))%(10**9+7))
    return F[-1]

if n==1:
    print(1)
if n==2:
    if m==1:
        print(1)
    else:
        print(2)
else:
    for i in range(m):
        if a[i]+1 in a or a[i]-1 in a:
            print(0)
            exit()
    if m==0:
        print(fibonacci_dp(n+1))
    else:
        x=fibonacci_dp(min(a))
        a.append(n+1)
        for i in range(1,len(a)):
            x=(x*fibonacci_dp(a[i]-a[i-1]-1))%(10**9+7)
        print(x)

Submission status: Wrong Answer

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

import sys

input = sys.stdin.readline

cnt = 0

def main():
    N, M = map(int, input().split())
    m = {}
    for l in sys.stdin:
        m[int(l.strip())] = True

    # N 個の階段における移動方法
    dp = [0 for _ in range(N+1)]
    dp[0] = 1
    dp[1] = 1 if 1 not in m else 0

    # N-1の移動パターン + N-2の移動パターン
    for i in range(1, N+1):
        if i in m:
            dp[i] = 0
            continue
        dp[i] = dp[i-1] + dp[i-2]
    print(dp[N] % 1000000007)

main()

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
a=[]
for m in range(M):
    a.append(int(input()))
a=[-1]+a+[N+1]
b=[a[m+1]-a[m]-2 for m in range(M+1)]
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:
        A=[1,1]
        for i in range(2,n+1):
            A=[A[-1]]+[sum(A)]
        return A[-1]

def main():
    if check(a)==False:
        return 0
    else:
        x=1
        for _ in b:
            x*=fibo(_)
        return x

print(main()%1000000007)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
s=0
f=0
if m!=0:
    for i in range(m):
        a = int(input())
        if a==f+1 and a!=1:
            s=0
            f=-1
            break
        s+=a-f-1
        f=a

if f!=-1:
    s+=n-f-1
    s%=1000000007
print(s)

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

broken = [0]*(M+2)
for i in range(M):
    broken[i+1] = int(input())
broken[-1] = N-1

step = [broken[i+1]-broken[i] for i in range(M+1)]

if 1 in step[1:-1]:
    print('0')
else:
    ans = 1
    for s in step:
        a = Fib(s+2)
        print(a)
        ans *= a
    print(ans)

Submission status: Wrong Answer

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

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

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

    before = a[i]

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

print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
ans=-1
dp=[0 for i in range(n+1)]
dp[1]=1
if n>=2:
  dp[2]=2


q=1000000007
a=[]
if n>=3:
  for i in range(m):
    b=int(input())
    a.append(b)
    if b-a[i-1]==1:
      ans=0
      break
    if b==1:
      dp[1]=0
      dp[2]=1
    if b==2:
      dp[2]=0

  for i in range(3,n+1):
    if i in a:
      continue
    else:
      dp[i]=(dp[i-1]+dp[i-2])%q
      """print("dp[i]",i,dp[i])"""
  if ans==0:
    dp[n]=ans
print(dp[n])

Submission status: Wrong Answer

Solution code:
def howmany(n):
    if n <= 1:
        return n
    result = [1, 0, 0, 1]
    matrix = [1, 1, 1, 0]
    while n > 0:
        if n % 2:
            result = mul(matrix, result)
        matrix = mul(matrix, matrix)
        n //= 2
    return result[2]

def mul(a, b):
    return [a[0]*b[0] + a[1]*b[2],
            a[0]*b[1] + a[1]*b[3],
            a[2]*b[0] + a[3]*b[2],
            a[2]*b[1] + a[3]*b[3]]


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

x = 1
a = [0]*(m+2)
a[0] = -1
a[m+1] = n

if m == 0:
    print(howmany(n+1))
else:
    for i in range(1,m+1):
        a[i] = int(input())

    if all(a[i+1]-a[i] != 1 for i in range(1,m+1)):
        for i in range(1,m+1):
            x *= howmany(a[i] - a[i-1] -1)
        x *= howmany(a[m+1]-a[m])
        print(x % 1000000007)
    else: print(0)

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline

n, m = map(int, input().split())
a_list = []
comb_list = [0, 1, 2, 3]
n_2, n_1 = 2, 3
for i in range(3, n):
    n_2, n_1 = n_1, (n_2+n_1)%(10**9+7)
    comb_list.append(n_1)
for _ in range(m):
    a = int(input())
    a_list.append(a)
start = 0
ans = 1
if m == 0:
    ans = comb_list[n]
else:
    for a in a_list+[n+1]:
        if a == 1:
            start = a + 1
            continue
        elif a == n-1:
            break
        else:
            if start == a:
                ans = 0
                break
            else:
                tmp = a - start - 1
                ans = (ans * comb_list[tmp])%(10**9+7)
                start = a + 1
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys;
import string;
sys.setrecursionlimit(20000) # 再起呼び出しの最大数をセット

import copy
import itertools

from functools import lru_cache
#@lru_cache(maxsize = None)

PPP = 1000000007

# 整数の入力
#n = int(input())

# スペース区切りの整数の入力
#w = [x for x in map(int, input().split())]
n, m = map(int, input().split())
#print("sp", n, q, file=sys.stderr)
#p, q, r = map(int, input().split())

# 改行区切りの整数の入力
a = []
for x in range(m):
  a.append(int(input()))
#  a.append([int(x) for x in input().split()])
#p = [int(x) for x in input().split()]
print(a, file=sys.stderr)

# 文字列の入力
#s = input()

# 出力
#print("{} {}".format(a+b+c, s))
#a.sort()
#print(set(a), file=sys.stderr)
#print(len(set(a)))

#cache = dict()

import re

def comb(n):
  print("comb", n, file=sys.stderr)
  if n < 3:
    return 1
  return 2 ** (n-2)

def doit():
  prev = -1
  res = 1
  for x in a:
    res *= comb(x - 1 - prev)
    if prev == x - 1:
      return 0
    prev = x
  res *= comb(n - prev)
  
  return res % PPP

#print(doit([0] * 4))
#doit(s)
try:
  print(doit())
except Exception as e:
  print("e", e, file=sys.stderr)

Submission status: Wrong Answer

Solution code:
N,M = (int(i) for i in input().split())
a = [int(input()) for i in range(M)]
hoge = [0] * N
if 1 not in a:
    hoge[0] = 1
elif 2 not in a:
    hoge[1] = 2

for i in range(2,N):
    if i + 1 in a:
        hoge[i] = 0
    elif i in a and (i-1) in a:
        hoge[i] = 0
    elif i in a:
        hoge[i] = hoge[i - 2]
    elif (i-1) in a:
        hoge[i] = hoge[i - 1]
    else:
        hoge[i] = hoge[i-1] + hoge[i-2]
        hoge[i] = hoge[i] % (10**9 + 7)
print(hoge[N-1] % (10**9 + 7))

Submission status: Wrong Answer

Solution code:
N_M = list(map(int, input().split()))
N = N_M[0]
M = N_M[1]
dis = []
for _ in range(M):
    dis.append(input())

dp = [0 for i in range(N+2)]
dp[0] = 1
if 1 in dis:
    dp[1] = 0
else :
    dp[1] = 1

for i in range(N):
    if i+2 in dis:
        dp[i+2]=0 
    else:
        if i in dis and i+1 in dis:
            dp[i+2]=0 
        else:
            if i in dis :
                dp[i+2]=dp[i+1]%1000000007
            elif i+1 in dis :
                dp[i+2]=dp[i]%1000000007
            else :
                dp[i+2]=dp[i]%1000000007+dp[i+1]%1000000007

print(dp[N])

Submission status: Wrong Answer

Solution code:
from itertools import*
from math import*
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float("inf")
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

N,M = map(int,input().split())
c = [0]*(N+1)
c[0] = 1
c[1] = 1
ans = 1
a = []
for i in range(2,N+1):
    c[i] = c[i-1]+c[i-2]
for i in range(M):
    ai = int(input())
    a.append(ai)
for i in range(M-1):
    if a[i+1]-a[i] == 1:
        print(0)
        exit()
for i in range(M):
    if i == 0:
        ans *= c[a[i]-1]
        ans %= mod
    if i == M-1:
        ans *= c[N-a[i]-1]
        ans %= mod
    else:
        if a[i+1] != a[i]:
            ans *= c[a[i+1]-a[i]-2]
            ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
p = [0]*100001
p[0] = 1
p[1] = 1
p[2] = 2
ans = 1
flag = 0
for i in range(3,100001):
	p[i] = p[i-1] + p[i-2]


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

l1 = [0]*(m+1)
for i in range(m+1):
	l1[i] = l[i+1] - l[i]

# print(l1)

if m == 0:
	print(p[n])
	flag = 1
else:
	for i in range(m+1):
		if i == 0 or i == m:
			ans = ans * p[l1[i]-1]
		else:
			if l1[i] == 1:
				print(0)
				flag = 1
				break
			else:
				ans = ans * p[l1[i]-2]

if flag != 1:
	print(ans % 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=[]
a=[0]+a+[n]
for i in range(len(a)-1):
    if i==0 and a[1]==1:
        step.append(1)
    elif i==0:
        step.append(S[a[i+1]-a[i]-2])
    elif i==len(a)-2 and a[-2]==n-1:
        step.append(1)
    elif i==len(a)-2:
        step.append(S[a[i+1]-a[i]-2])
    elif a[i+1]-a[i]==1:
        print(0)
        sys.exit()
    elif a[i+1]-a[i]==2:
        step.append(1)
    else:
        step.append(S[a[i+1]-a[i]-3])

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import math

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


n, m = map(int, input().split())
if m == 0:
    b = [n]
else:
    a = [int(input()) for i in range(m)]
    b = []
    for i in range(m):
        if i == 0:
            b.append(a[i] - 1)
        else:
            b.append(a[i] - a[i - 1] - 2)
    b.append(n - a[-1] - 1)
if -1 in b:
    print(0)
    exit()
c = set(b)
d = {}
for i in c:
    k = 0
    s = 1
    while i - k > k:
        s += nCr(i - k, k)
        k += 1
    d[i] = s
ans = 1
d[1] = 1
for i in b:
    ans *= d[i] % (10 ** 9 + 7)
print(ans % (10 ** 9 + 7))

Submission status: Wrong Answer

Solution code:
import math

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

ng = 0
INF = pow(10, 9) + 7
ans = 1
now = 0
if M == 0:
    last = N
    if last % 2 == 0:
        tmp = 1
        i = int(last / 2)
        for j in range(1, i + 1):
            tmp += int(math.factorial(i + j) / (math.factorial(2 * j) * math.factorial(i - j)))
        ans *= tmp
        ans %= INF
    else:
        i = int(last / 2)
        tmp = i + 1
        for j in range(1, i + 1):
            tmp += int(math.factorial(i + j + 1) / (math.factorial(2 * j + 1) * math.factorial(i - j)))
        ans *= tmp
        ans %= INF
else:
    for ind in range(M):
        nex = int(input())
        broken = nex - now - 2
        if ind != 0 and broken == 0:
            ng = 1
            break
        if broken % 2 == 0:
            tmp = 1
            i = int(broken / 2)
            for j in range(1, i+1):
                tmp += int(math.factorial(i+j) / (math.factorial(2*j) * math.factorial(i-j)))
            ans *= tmp
            ans %= INF
        else:
            i = int(broken / 2)
            tmp = i + 1
            for j in range(1, i+1):
                tmp += int(math.factorial(i+j+1) / (math.factorial((2*j)+1) * math.factorial(i-j)))
            ans *= tmp
            ans %= INF
        now = nex
    else:
        last = N
        broken = last - now - 1
        if broken == 0:
            ng = 1
        if broken % 2 == 0:
            tmp = 1
            i = int(broken / 2)
            for j in range(1, i+1):
                tmp += int(math.factorial(i+j) / (math.factorial(2*j) * math.factorial(i-j)))
            ans *= tmp
            ans %= INF
        else:
            i = int(broken / 2)
            tmp = i + 1
            for j in range(1, i+1):
                tmp += int(math.factorial(i+j+1) / (math.factorial((2*j)+1) * math.factorial(i-j)))
            ans *= tmp
            ans %= INF

if ng:
    print(0)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
def fib(number):
    if(number<=2):
        return 1
    else:
        f = 1
        ff = 1
        for _ in range(number-1):
            tmp = ff
            ff = f + ff
            f = tmp
        return tmp

n, m = map(int, input().split())
a = []

frag = True
before = -100
for _ in range(m):
    tmp = int(input())
    if(tmp - before == 1):
        frag = False
    before = tmp
    a.append(tmp)


warukazu = 1000000007
if(frag):
    before = 0
    ans = 0
    if(m!=0):
        for i in range(m):
            if(i==0):
                ans = fib(a[i]-before)
            else:
                ans = ans * fib(a[i]-before-1)
                ans = ans % warukazu
            before = a[i]
        ans = ans * fib(n - before)
        ans = ans % warukazu
        print(ans)
    else:
        ans = fib(n - before)
        ans = ans % warukazu
        print(ans)
else:
    print(0)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
a = [int(input()) for _ in range(M)]
MOD = 10 **9 + 7

import sys
for i in range(M-1):
    flag = a[i+1]-a[i]
    if flag == 1:
        print(0)
        sys.exit()
        
        
dp = [0] * (N+10)
dp[1] = 1
dp[2] = 1
for i in range(1,N+5):
    dp[i+2] = dp[i+1] + dp[i]
    dp[i+2] %= MOD
    
if M == 0:
    print(dp[N])
    sys.exit()
ans = 1
for i in range(M+1):
    if i == 0:
        number = a[i]
    elif i == M:
        number = N - a[i-1]
    else:
        number = a[i]-a[i-1] - 1
    number = max(1,number)
    ans *= dp[number]
    ans %= MOD
print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
b=[]
b_clone=[]

for i in range(m):
    t=int(input())
    b.append(t)
    b_clone.append(t)


ans_list=[1]

if len(b)!=0 and b[0]==1:
    b.pop(0)
    ans_list.append(0)
else:
    ans_list.append(1)

for i in range(2,n+1):
    if len(b)!=0 and i==b[0]:
        b.pop(0)
        ans_list.append(0)
        continue
    else:
        ans_list.append((ans_list[i-2]+ans_list[i-1])%1000000007)

print(ans_list)

print(ans_list[n])

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())]
    b+=[a[-1]-a[-2]-2]
    if a[-1]-a[-2]==1:
        b=[]
        break
else:
    b+=[N-a[-1]-1]
if b==[]:
    sm=0
else:
    sm=culc(b[0])
for i in b[1:]:
    sm=sm*culc(i)
print(sm%1000000007)

Submission status: Wrong Answer

Solution code:
import sys
import math

def fb(num):
    a, b = 1, 0
    for _ in range(num-1):
        a, b = a + b, a
    return a


n, m = map(int, input().split())
a = []

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

ans = 1
p = 0
for j in range(len(a)):
    if j == 0:
        if a[j] == 0 or a[j] == 1:
            p = a[j]
            continue
        
    if a[j] - p - 1 == 0:
        print("0")
        sys.exit()
        
    ans *= fb(a[j] - p - 1)
    p = a[j]
    if ans > 1000000007:
        ans = ans % 1000000007


if n - p - 1 == 0:
        print("0")
        sys.exit()

        
ans *= fb(n - p)
print(ans % 1000000007)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
A = []
for i in range(m):
    A.append(int(input()))
    
dp = [0 for i in range(n + 1)]
dp[0] = 1
for i in range(n+1):
    if not i in A:
        if (dp[i-2] >= 1) and (i-2 >= 0):
            dp[i] += 1
        if (dp[i-1] >= 1) and (i-1 >= 0):
            dp[i] += 1
            
ans = 1
for i in dp:
    if i >= 1:
        ans *= i
        
A = sorted(A)
for i in range(len(A)-1):
    if A[i] + 1 == A[i+1]:
        ans = 0
print(ans % (10 ** 9 + 7))

Submission status: Wrong Answer

Solution code:
p = [0]*100001
p[0] = 1
p[1] = 1
p[2] = 2
ans = 1
flag = 0
for i in range(3,100001):
	p[i] = p[i-1] + p[i-2]


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

l1 = [0]*(m+1)
for i in range(m+1):
	l1[i] = l[i+1] - l[i]

# print(l1)

if m == 0:
	print(p[n])
else:
	for i in range(m+1):
		if i == 0 or i == m:
			ans = ans * p[l1[i]-1]
		else:
			if l1[i] == 1:
				print(0)
				flag = 1
				break
			else:
				ans = ans * p[l1[i]-2]

if flag != 1:
	print(ans % 1000000007)

Submission status: Wrong Answer

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

m = 10**9+7

memo = [1]*(N+3)
for i in range(3,N+3):
    memo[i] = memo[i-1] + memo[i-2]

memo[0] = 0

A.append(N+1)
p = A[0]
ans = memo[p]
for i in range(1,M+1):
    ans *= memo[A[i]-p-1]
    ans %= m
    p = A[i]

print(ans)

Submission status: Wrong Answer

Solution code:
from functools import lru_cache

n,m = map(int,input().split())
a = [-1]
for i in range(m):
  a.append(int(input()))
a.append(n+1)
  
@lru_cache(maxsize=1000)
def comb(n,k):
  m = 1
  if n<2*k:
    k = n-k
  for i in range(1,k+1):
    m = m*(n-i+1)/i
  return m

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

Submission status: Wrong Answer

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

dp_f = [None] * (10**5 + 1)
dp_f[1] = 1
dp_f[2] = 1
for i in range(3, 10**5 + 1):
    dp_f[i] = dp_f[i-1] + dp_f[i-2]
def f(n):
    if n == 1:
        return 1
    elif n == 2:
        return 1
    elif dp_f[n] is not None:
        return dp_f[n]
    v = f(n-1) + f(n-2)
    dp_f[n] = v
    return dp_f[n]

if M == 0:
    m = f(N)
    m %= 1000000007
    print(m)
    sys.exit(0)

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

S = []
S.append(A[0])
for i in range(1, M):
    if A[i] == A[i-1] + 1:
        print(0)
        sys.exit(0)
    S.append(A[i] - A[i-1] - 1)
S.append(N - A[-1])

m = 1
for s in S:
    m *= f(s)
    m %= 1000000007

print(m)

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=[]
a=[0]+a+[n]
for i in range(len(a)-1):
    if i==0 and a[1]==1:
        step.append(1)
    elif i==0:
        step.append(S[a[i+1]-a[i]-2])
    elif i==len(a)-2 and a[-2]==n-1:
        step.append(1)
    elif i==len(a)-2:
        step.append(S[a[i+1]-a[i]-2])
    elif a[i+1]-a[i]==1:
        print(0)
        sys.exit()
    else:
        step.append(S[a[i+1]-a[i]-3])

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

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
b = [int(input()) for _ in range(m)] + [n+1]
now = 0
A = [0,1]
if 0 in b:
  print(0)
else:
  for i in range(1,n+1):
    if b[now] == i:
      A.append(0)
    else:
      A.append( (A[-1]+A[-2]) % (10**9+7) )
  print(A[-1])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
import bisect

MOD = 1000000007  # type: int

def is_ok(i,a):
    ii = bisect.bisect_left(a,i)
    if ii >= len(a):
        return True
    return i != a[ii]


def solve(N: int, M: int, a: "List[int]"):
    ppc = 1 if is_ok(1,a) else 0

    pc = 0
    if is_ok(2,a):
        if is_ok(1,a):
            pc = 2
        else:
            pc = 1

    c = 0
    for i in range(2,N):
        if is_ok(i+1,a):
            c = ppc + pc
        else:
            c = 0
        c %= MOD
        ppc,pc = pc,c

    print(c)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [ int(next(tokens)) for _ in range(M) ]  # type: "List[int]"
    solve(N, M, a)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

p = [0]*(n+1)
if n == 1 and m == 0:
    print(1)
elif n == 1 and m == 1:
    print(0)
else:
    p[0] = 1
    if 1 in bk:
        p[1] = 0
    else:
        p[1] = 1
    for i in range(n-1):
        if i+2 in bk:
            p[i+2] = 0
        else:
            p[i+2] = p[i]+p[i+1]
            if p[i+2] >= 1000000007:
                p[i+2] -= 1000000007

print(p[n])

Submission status: Wrong Answer

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

A = []
for _ in range(M):
    A.append(int(input()))

step = [0 for _ in range(N+1)]

ptr = 0

step[0] = 1
if ptr < M and A[ptr] != 1:
    step[1] = 1
else:
    ptr += 1

for i in range(2, N+1):
    if ptr < M and i == A[ptr]:
        ptr += 1
    else:
        step[i] = step[i-1] + step[i-2]


print(step[N] % (10**9+7))

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
F = [1]+[2]+[0]*100000

for i in range(2, 100002):
    F[i] = F[i-1] + F[i-2]

ans = 1
cur = 0
pre = 0
for i in range(M):
    broken = int(input())
    if pre == broken:
        continue
    pre = broken
    if cur == broken:
        print(0)
        break
    elif broken - cur == 1:
        cur = broken + 1
    else:
        ans *= F[broken - cur - 2]
        ans %= 1000000007
        cur = broken + 1
else:
    ans *= F[N - cur - 1]
    print(ans % 1000000007)

Submission status: Wrong Answer

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

m = 10**9+7

memo = [1]*(N+3)
for i in range(3,N+3):
    memo[i] = memo[i-1] + memo[i-2]

A.append(N+1)
p = A[0]
ans = memo[p]
for i in range(1,M+1):
    if p+1 == A[i]:
        print(0)
        exit()
    else:
        ans *= memo[A[i]-p-1]
        ans %= m
    p = A[i]

print(ans)

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=[]
a=[0]+a+[n]
for i in range(len(a)-1):
    if i==0 and a[1]==1:
        step.append(1)
    elif i==0:
        step.append(S[a[i+1]-a[i]-2])
    elif i==len(a)-2 and a[-1]==n-1:
        step.append(1)
    elif i==len(a)-2:
        step.append(S[a[i+1]-a[i]-2])
    elif a[i+1]-a[i]==1:
        print(0)
        sys.exit()
    else:
        step.append(S[a[i+1]-a[i]-3])

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