Problem:


Score : 300 points

Problem Statement

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

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

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

Constraints

1 \leq N \leq 10^5

0 \leq M \leq N-1

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

Input

Input is given from Standard Input in the following format:

N M
a_1
a_2
 .
 .
 .
a_M

Output

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

Sample Input 1

6 1
3

Sample Output 1

4

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

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

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

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

0 \to 2 \to 4 \to 6

Sample Input 2

10 2
4
5

Sample Output 2

0

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

Sample Input 3

100 5
1
23
45
67
89

Sample Output 3

608200469

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



Sample input:
6 1
3


Sample output:
4

Submission status: Wrong Answer

Solution code:
def main():

    # 保持しておく値は事前２つだけで十分なので巨大リストを作らない形

    def count_pattern(step, barrier):
        p = 1
        if 1 in barrier:
            q = 0
        else:
            q = 1
        if step == 1:
            return p
        elif step == 2:
            return q
        else:
            for i in range(2, n+1):
                p, q = q, p + q
                if i in barrier:
                    q = 0
            return q

    n, m = map(int, input().split())
    a = [int(input()) for i in range(m)]
    mod = 1000000007
    ans = count_pattern(n, a) % mod       
    print(ans)

    # # フィボナッチ数列を作る要領で行う
    # 巨大なリストをつくるとTLEになる
    # d = [0] * (n+1)
    # # d[0]とd[1]を規定。aに1が含まれていることを考慮して場合分けしておく
    # d[0] = 1
    # if 1 in a:
    #     d[1] = 0
    # else:
    #     d[1] = 1
    # # 階段番号は2~nまでを見る必要がある
    # for i in range(2, n+1):
    #     if i in a:
    #         d[i] = 0
    #     else:
    #         d[i] = d[i-1] + d[i-2]
    # print(d)  
    # ans = d[n] % mod        
    # print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
S=[0]*100010
S[1]=1
S[2]=1
for i in range(3,100010):
    S[i]=(S[i-2]+S[i-1])%1000000007

N,M=map(int,input().split())
if M==0:
    print(S[N])
    exit()
T=[]
for i in range(M):
    T.append(int(input()))
    if i>=1:
        if T[i]-1==T[i-1]:
            print(0)
            exit()

U=[]
U.append(T[0])
for i in range(1,M):
    U.append(T[i]-T[i-1]-1)

U.append(N-T[M-1])

ans=1
for i in range(len(U)):
    ans=(ans*S[U[i]])%1000000007
print(ans)

Submission status: Wrong Answer

Solution code:
N,M = [int(x) for x in input().split()]
a = []
mod = 10**9 + 7
DP = [0]*(N+1)
for i in range(M):
    aa = int(input())
    DP[aa] = -1
DP[0] = 1
if not 1 in a:
    DP[1] = 1
for i in range(2,N+1):
    if DP[i] != -1:
        DP[i] = max(0,DP[i-1]) + max(0,DP[i-2])
ans = DP[N] % mod
print(ans)

Submission status: Wrong Answer

Solution code:
import collections
n,m = map(int, raw_input().split(' '))
forbidden = set([int(raw_input()) for _ in range(m)])
q = collections.deque([1])
mod = (10 ** 9) + 7
w = 1
while(w <= n):
	q.append((1 if w not in forbidden else 0) * (sum(q) % mod))
	w += 1
	if len(q) == 3: q.popleft() 
q.pop()
print q[-1]

Submission status: Wrong Answer

Solution code:
import collections
n,m = map(int, raw_input().split(' '))
forbidden = set([int(raw_input()) for _ in range(m)])
q = collections.deque([1])
mod = (10 ** 9) + 7
w = 1
while(w <n):
	q.append((1 if w not in forbidden else 0) * (sum(q) % mod))
	w += 1
	if len(q) == 3: q.popleft() 
print q[-1]

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
if M == 0:
    B = [N]
else:
    A = []
    for i in range(M):
        A.append(int(input()))
    if A[0] == 1 or A[0] == 2:
        B = [0]
    else:
        B = [A[0]-1]
    for j in range(M-1):
        B.append(A[j+1]-A[j]-2)
    B.append(N-A[M-1]-1)
ans = 1
for p in range(M+1):
    if B[p] == -1:
        print(0)
        exit()
    elif B[p] == 0 or B[p] == 1:
        ans *= 1
    else:
        b = 0
        N = B[p]
        for v in range(N//2+1):
            a = 1
            for w in range(N-2*v+1,N-v+1):
                a *= w/(w-N+2*v)
            b += a
        ans *= b
        ans %= 1000000007
print(round(ans))

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
a = [int(input()) for i in range(m)]
mod = 1000000007
lis = []
if m == 0:
  print(0)
  exit()
  
if 1 not in a:
  lis.append(1)
  if 2 in a:
    lis.append(0)
  else:
    lis.append(2)
    
elif 1 in a:
  lis.append(0)
  if 2 in a:
    lis.append(0)
  else:
    lis.append(1)


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

Submission status: Wrong Answer

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

if 1 not in a:
  lis.append(1)
  if 2 in a:
    lis.append(0)
  else:
    lis.append(2)
    
elif 1 in a:
  lis.append(0)
  if 2 in a:
    lis.append(0)
  else:
    lis.append(1)


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

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
dp=[0]*(n+7)
dp[0]=1
a=[int(input())for _ in range(m)]
a=set(a)
for i in range(n):
  if i+1 not in a:
    dp[i+2]+=dp[i]
    dp[i+1]+=dp[i]
print(dp[n])

Submission status: Wrong Answer

Solution code:
import numpy as np

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

brk_stair = np.ones(N+1, dtype = int)
dp = np.zeros(N+1, dtype= int)

for _ in range(M):
    brk_stair[int(input())] = 0

#print(brk_stair)

dp[0] = 1
dp[1] = 1 * brk_stair[1]

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

#print(dp)
print(dp[-1] % 1000000007)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

brk_stair = np.ones(N+1, dtype = int)
dp = np.zeros(N+1, dtype= int)

for _ in range(M):
    brk_stair[int(input())] = 0

print(brk_stair)

dp[0] = 1
dp[1] = 1 * brk_stair[1]

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

print(dp)
print(dp[-1] % 1000000007)

Submission status: Wrong Answer

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import copy
from itertools import permutations
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

from itertools import permutations
from math import factorial, hypot

#############
# Main Code #
#############

N, M = getNM()
A = set(getArray(M))
print(A)

dp = [0] * (N + 1)
dp[0] = 1

for i in range(1, N + 1):
    if not i in A:
        if i == 1:
            dp[i] = dp[i - 1] % mod
        else:
            dp[i] = (dp[i - 1] + dp[i - 2]) % mod
print(dp[N] % mod)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
memo = [0]*(N+1)
memo[1] = 1
mod = 10**9+7

if N > 1:
    memo[2] = 2

for _ in range(M):
    ai = int(input())
    memo[ai] = None

if N > 1 and memo[1] == None:
    memo[2] = 1

for i in range(3, N+1):
    tmp = 0
    if memo[i] == None:
        continue
    if memo[i-1] != None:
        tmp += memo[i-1]
    if memo[i-2] != None:
        tmp += memo[i-2]
    memo[i] = tmp

if memo[N] == None:
    print(0)
else:
    print(memo[N]%mod)

Submission status: Wrong Answer

Solution code:
import numpy as np

#標準入力
N,M = list(map(int, input().split()))
aList = [int(input()) for _ in range(M)]

#dpと場合分け用の配列作成
trg = np.ones(N+1, dtype = np.int64)
dp = np.zeros(N+1, dtype = np.int64)

#壊れた床は0、通常の床は1となるよう配列作成
for a in aList:
    trg[a] -= 1


#DP
for i in range(1, N+1):
    if(i <= 2):
        dp[i] = (dp[i-1] + 1) * trg[i]
    
    else:
        dp[i] = (dp[i-1] + dp[i-2]) * trg[i]

#解答出力
print(dp[N] % 1000000007)

Submission status: Wrong Answer

Solution code:
import numpy as np
import math

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

aList = [int(input()) for _ in range(M)]

trg = np.ones(N+1, dtype = np.int64)
dp = np.zeros(N+1, dtype = np.int64)

for a in aList:
    trg[a] -= 1


for i in range(1, N+1):
    if(i <= 2):
        dp[i] = (dp[i-1] + 1) * trg[i]
    
    else:
        dp[i] = (dp[i-1] + dp[i-2]) * trg[i]

print(dp[N] % 1000000007)

Submission status: Wrong Answer

Solution code:
import numpy as np
import math

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

aList = [int(input()) for _ in range(M)]

trg = np.ones(N+1, dtype = np.int64)
dp = np.zeros(N+1, dtype = np.int64)

for a in aList:
    trg[a] -= 1

for i in range(1, N+1):
    if(i <= 2):
        dp[i] = 1 * trg[i]
    
    else:
        dp[i] = (dp[i-1] + dp[i-2]) * trg[i]

print(dp[N] % 1000000007)

Submission status: Wrong Answer

Solution code:
import math
# input
stairs, broken = map(int, input().split())
broken_list = []
for i in range(broken):
  broken_list.append(int(input()))
  
# main
goalable = True
for i in range(1, broken):
  if broken_list[i-1] == broken_list[i]-1:
    goalable = False
    break

if goalable:
  broken_list.append(stairs+1)
  now = 0
  ans_list = []
  for b in broken_list:
    cp = b - 1
    stg = cp - now
    tmp = 0
    
    for x in range(stg+1):
      if (stg - x) % 2 == 0:
        y = (stg - x) / 2
        tmp += math.factorial(x+y) / (math.factorial(x) * math.factorial(y))
    
    ans_list.append(int(tmp))
    now = b + 1
  
  ans = 1
  for i in ans_list:
    ans = (i * ans) % 1000000007
  print(ans)
else:
  print(0)

Submission status: Wrong Answer

Solution code:
import math
# input
stairs, broken = map(int, input().split())
broken_list = []
for i in range(broken):
  broken_list.append(int(input()))
  
# main
goalable = True
for i in range(1, broken):
  if broken_list[i-1] == broken_list[i]-1:
    goalable = False

if goalable:
  broken_list.append(stairs+1)
  now = 0
  ans_list = []
  for b in broken_list:
    cp = b - 1
    stg = cp - now
    tmp = 0
    
    for x in range(stg+1):
      if (stg - x) % 2 == 0:
        y = (stg - x) / 2
        tmp += math.factorial(x+y) / (math.factorial(x) * math.factorial(y))
    
    ans_list.append(int(tmp))
    now = b + 1
  
  ans = 1
  for i in ans_list:
    ans = (i * ans) % 1000000007
    
  print(ans)
else:
  print(0)

Submission status: Wrong Answer

Solution code:
MOD=10**10+7
n,m = list(map(int, input().split()))
a = set([int(input()) for _ in range(m)])

dp = [0] * (n+1)

init=1
for i in range(1, n+1):
    if i not in a:
        dp[i]=init
        init+=1
        if init > 2:
            break

for step in range(i+1, n+1):
    if dp[step-1]==0 and dp[step-2]==0:
        break
    if step not in a:
        dp[step] = (dp[step-1] + dp[step-2])%MOD
print(dp[-1])

Submission status: Wrong Answer

Solution code:
import sys
MOD = 10**9 + 7
n, m = map(int, input().split())
a = [int(x) for x in sys.stdin.readlines()]
p1, p2 = 0, 0
if 1 not in a:
    p1, p2 = 0, 1
if 2 not in a and n >=2:
    p1, p2 = p2, p2 + 1

for i in range(2, n):
    if i+1 not in a:
        p1, p2 = p2, (p2 + p1)%MOD
    else:
        p1, p2 = p2, 0
print(p2)

Submission status: Wrong Answer

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

dp =[0 for i in range(n+1)]
dp[0]=1

for i in range(n):
  if not i+1 in a:
    dp[i+1] += dp[i]
  if i < n-2:
    if not i+2 in a:
      dp[i+2] += dp[i]
if n in a:
  print(0)
else:
  print((dp[n-1]+dp[n-2])%1000000007)

Submission status: Wrong Answer

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

dp =[0 for i in range(n)]
dp[0]=1

for i in range(n-1):
  if not i+1 in a:
    dp[i+1] += dp[i]
  if i < n-2:
    if not i+2 in a:
      dp[i+2] += dp[i]
print((dp[n-1]+dp[n-2])%1000000007)

Submission status: Wrong Answer

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

dp =[0 for i in range(n)]
dp[0]=1

for i in range(n-1):
  if not (i+1 in a):
    dp[i+1] += dp[i]
  if (i < n-2) and not (i+2 in a):
    dp[i+2] += dp[i]
print(dp[n-1]%1000000007)

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
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()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7

N, M = MAP()
a = [INT() for _ in range(M)]

dp = [0]*(N+1)
dp[0] = 1
dp[1] = 1


for i in range(1, N+1):
	if i in a:
		dp[i] = 0
		dp[i+1] = dp[i-1]
	else:
		dp[i] = (dp[i-1] + dp[i-2])%mod

print(dp[N])

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
dp=[0]*(n+1)
dp[0]=1
a=[int(input()) for i in range(m)]
for i in range(1,n+1):
    dp[i]=(dp[i-1]+dp[i-2])%(1e9+7)
    if i in a:
        dp[i]=0
print(dp[n])

Submission status: Wrong Answer

Solution code:
import sys
import math 
n,m=map(int,input().split())
a=[]
for i in range(m):
    b=int(input())
    if b-1 in a:
        print(0)
        sys.exit()
    else:
        a.append(b)
        
state=0
step=0
ans=0

bunnbo=lambda n,r: math.factorial(r)*math.factorial(n-r)
bunshi=lambda n: math.factorial(n)

for i in range(m):
    temp=0
    step=(a[i]-1)-state
    
    for j in range(step//2+1):
        temp+=(bunshi(step-j)//bunnbo(step-j,j))
    
    if i==0:
        ans+=temp
    else:
        ans*=temp%(10**9+7)
    
    state=a[i]+1
    
    if i==m-1:
        temp=0
        step=n-state
        for j in range(step//2+1):
            temp+=(bunshi(step-j)//bunnbo(step-j,j))
        
        ans*=temp%(10**9+7)
            
print(ans%(10**9+7))

Submission status: Wrong Answer

Solution code:
import sys
import math 
n,m=map(int,input().split())
a=[]
for i in range(m):
    b=int(input())
    if b-1 in a:
        print(0)
        sys.exit()
    else:
        a.append(b)
        
state=0
step=0
ans=0

bunnbo=lambda n,r: math.factorial(r)*math.factorial(n-r)
bunshi=lambda n: math.factorial(n)

for i in range(m):
    temp=0
    step=(a[i]-1)-state
    
    for j in range(step//2+1):
        temp+=(bunshi(step-j)//bunnbo(step-j,j))
    
    if i==0:
        ans+=temp
    else:
        ans*=temp
    
    state=a[i]+1
    
    if i==m-1:
        temp=0
        step=n-state
        for j in range(step//2+1):
            temp+=(bunshi(step-j)//bunnbo(step-j,j))
        
        ans*=temp
            
print(ans%(10**9+7))

Submission status: Wrong Answer

Solution code:
import sys
import math 
n,m=map(int,input().split())
a=[]
for i in range(m):
    b=int(input())
    if b-1 in a:
        print(0)
        sys.exit()
    else:
        a.append(b)
        
state=0
step=0
ans=0

bunnbo=lambda n,r: math.factorial(r)*math.factorial(n-r)
bunshi=lambda n: math.factorial(n)

for i in range(m):
    temp=0
    step=(a[i]-1)-state
    
    for j in range(step//2+1):
        temp+=(bunshi(step-j)//bunnbo(step-j,j))
    print(temp)
    
    if i==0:
        ans+=temp
    else:
        ans*=temp
    
    state=a[i]+1
    
    if i==m-1:
        temp=0
        step=n-state
        for j in range(step//2+1):
            temp+=(bunshi(step-j)//bunnbo(step-j,j))
        
        print(temp)
        ans*=temp
            
print(ans%(10**9+7))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env pypy
import sys

readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
MOD = 10 ** 9 + 7


def main():
    n, m = map(int, readline().split())
    # a = readlines()
    As = list(map(int, readlines()))
    # diff_a = [a[i+1] - a[i] for i in range(m - 1)]
    # if 1 in diff_a:
    #     print(0)
    #     return
    broken = [False] * (n + 1)
    for a in As:
        broken[a] = True
    p1, p2 = 0, 1
    if broken[1]:
        p1 = 1

    for i in range(2, n + 1):
        if broken[i]:
            p1, p2 = 0, p1
        else:
            p1, p2 = (p1 + p2) % MOD, p1

    print(p1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

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

a = [int(input()) for _ in range(m)]

mod = 1000000007

a_2, a_1, a_now = 1, 0, 0

if 1 in a:
    a_1 = 0
else:
    a_1 = 1

for i in range(2, n+1):
    if i in a:
        a_now = 0
    else:
        a_now = a_1+a_2
    # print(a_now)
    a_1, a_2 = a_now, a_1

print(a_now % mod)

# 0, 1, 2, 3, 4, 5, 6

# 1, 1, 2, 0, 2, 2, 4

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

mod = 1000000007

dp = [0] * (N + 1)

if len(dp) == 2:
  if dp[0] not in A:
  	print(1)
  else:
    print(0)


dp[-1] = 1
dp[-2] = 1 if N - 1 not in A else 0

for i in range(N-2, -1, -1):
  if i not in A:
    dp[i] = dp[i+1] + dp[i+2]

print(dp[0] % mod)

Submission status: Wrong Answer

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

mod = 1000000007

dp = [0] * (N + 1)

if len(dp) <= 2:
  print(1)

dp[-1] = 1
dp[-2] = 1 if N - 1 not in A else 0

for i in range(N-2, -1, -1):
  if i not in A:
    dp[i] = dp[i+1] + dp[i+2]

print(dp[0] % mod)

Submission status: Wrong Answer

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

mod = 1000000007

A = []
for i in range(M):
    A.append(int(input()))
    
X = [0]*(N+2)

for i in range(2, N+2):
    if X[i] not in A:
        X[i] = min(X[i-1], X[i-2]) + 1

print(X[N+1]%mod)

Submission status: Wrong Answer

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

for i in range(n-1):
  if (i+2) in a:
    d[i+2]=0
  else:
    d[i+2]=(d[i]+d[i+1])%1000000007

print(d)

Submission status: Wrong Answer

Solution code:
from math import factorial as f


N, M = map(int, input().split())
broken = [int(input()) for _ in range(M)] + [N+1]
tmp = 0
ans = 1
FLG = True

for a in broken:
    if a == 1 or tmp == N:
        tmp = a + 1
        continue
    if a == tmp:
        FLG = False
        break

    interval = a - tmp - 1
    ans *= sum(int(f(j)/(f(i)*f(j-i))) for i,j in enumerate(range(interval, (interval+1)//2 - 1, -1)))
    tmp = a + 1

if FLG:
    print(ans % 1000000007)
else:
    print(0)

Submission status: Wrong Answer

Solution code:
from math import factorial as f


N, M = map(int, input().split())
broken = [int(input()) for _ in range(M)] + [N+1]
tmp = 0
ans = 1
FLG = True

for a in broken:
    if a == 1:
        tmp = a + 1
        continue
    if a == tmp:
        FLG = False
        break

    interval = a - tmp - 1
    ans *= sum(int(f(j)/(f(i)*f(j-i))) for i,j in enumerate(range(interval, (interval+1)//2 - 1, -1)))
    tmp = a + 1

if FLG:
    print(ans % 1000000007)
else:
    print(0)

Submission status: Wrong Answer

Solution code:
from math import factorial as f


N, M = map(int, input().split())
broken = [int(input()) for _ in range(M)] + [N+1]
tmp = -1
ans = 1
FLG = True

for i,a in enumerate(broken):
    if a == tmp:
        FLG = False
        break
    if i == 0:
        interval = a - 1
    else:    
        interval = a - tmp - 1
    ans *= sum(int(f(j)/(f(i)*f(j-i))) for i,j in enumerate(range(interval, (interval+1)//2 - 1, -1)))
    tmp = a + 1

if FLG:
    print(ans % 1000000007)
else:
    print(0)

Submission status: Wrong Answer

Solution code:
def Fib(n, memo={}):
    if n < 2:
        return 1
    elif n in memo:
        return memo[n]
    else:
        memo[n] = Fib(n - 1, memo) + Fib(n - 2, memo)
        return memo[n]


def resolve():
    N, M = [int(i) for i in input().split()]
    aa = []
    for _ in range(M):
        aa.append(int(input()))
    fib_l = list(Fib(i) for i in range(N))

    ans = 1
    now = 0
    if M == 0:
        ans = ans * fib_l[N - 1]
    else:
        for a in aa:
            if now == a:
                ans = 0
                break
            tmp = a - now - 1
            ans = ans * fib_l[tmp]
            now = a + 1
        else:
            ans = ans * fib_l[N - now]
    print(ans % (10**9 + 7))


resolve()

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
a = [0] * m

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

one = 1 in a
two = 2 in a

dp = [0] * (n + 1)

if (n == 1):
    if (one is True):
        ans = 0
    else:
        ans = 1

elif (n == 2):
    if (sum(a) == 0):
        ans = 2
    elif (sum(a) == 3):
        ans = 0
    else:
        ans = 1

else:
    dp[1] = 1
    dp[2] = 2
    if (one is True):
        dp[1] = 0
    if (one is True):
        dp[2] = 0

    for i in range(3, n + 1):
        if (i in a):
            pass
        else:
            dp[i] = dp[i - 1] + dp[i - 2]

    ans = dp[n]

print(ans)

Submission status: Wrong Answer

Solution code:
#import bisect,collections,copy,heapq,itertools,math,numpy,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
N, M = LI()
A = [I() for _ in range(M)][::-1]
md = 10**9+7

dp = [0] * (N+1)
dp[0] = 1

for now in range(N):
  for next in range(now+1, now+3):
    if next == N:
      dp[next] += dp[now]
      dp[next] %= md
      break
    if len(A) != 0 and next == A[len(A)-1]:
      A.pop()
    else:
      dp[next] += dp[now]
      dp[next] %= md

print(dp[N])

Submission status: Wrong Answer

Solution code:
MOD = 10 ** 9 + 7


def resolve():
    N, M = map(int, input().split())

    A = [True] * N
    for _ in range(M):
        broken = int(input()) - 1
        A[broken] = False

    ans = 1
    for j in range(N - 2):
        if not A[j] and not A[j + 1]:
            print(0)
            return

        if A[j] and A[j + 1]:
            ans = ans * 2

    print(ans % MOD)


resolve()

Submission status: Wrong Answer

Solution code:
from math import factorial
MOD = 1000000007

def calc_nCr(n, r):
    return (int(factorial(n) / (factorial(r) * factorial(n - r)))) % MOD
def count_patterns(stairs):
    if stairs == 0 or stairs == 1:
        return 1
    max_double_num = int(stairs/2)
    combs = [None]*(max_double_num+1)
    for i in range(max_double_num+1):
        double = i
        single = stairs - double*2
        n = double + single
        r = double
        nCr = calc_nCr(n, r)
        combs[i] = nCr
    return sum(combs) % MOD
  
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]

def main():
    now = 0
    total = 1
    for broken in a:
        if broken <= now:
            print(0)
            break
        total = (total * count_patterns(broken-now-1)) % MOD
        now = broken + 1
    else:
        total = (total * count_patterns(N-now)) % MOD
        print(total)
main()

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
a=[int(input()) for i in range(m)]
dp=[0]*(n+2)
dp[0]=0
dp[1]=1
if m==0:
  print(0)
  exit()
for j in range(n):
  if j+1 not in a:
    dp[j+2]=(dp[j]+dp[j+1])%(10**9+7)
  else:
    dp[j+2]=0
print(dp[j+2]%(10**9+7))

Submission status: Wrong Answer

Solution code:
from math import factorial

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
a = []
mod = 10**9+7
d = [0 for i in range(n+1)]
d[0] = 1
d[1] = 1
if n >1 :
    d[2] = 2
for i in range(3,n+1):
    d[i] = d[i-1] + d[i-2]
if m != 0:
    d.append(0)
    for i in range(m):
        b = int(input())
        a.append(b)
    ans = 1
    if a[0] == 1:
        ans = 1
    else:
        ans = ans*d[a[0]-1]%mod
    for i in range(m-1):
        ans = ans*d[a[i+1]-a[i]-2]%mod
    ans = ans*d[n-a[m-1]-1]%mod
else:
    ans = d[n]
print(ans)

Submission status: Wrong Answer

Solution code:
import math
N,M = list(map(int,input().split()))
A = [-1]+[int(input()) for _ in range(M)]+[N+1]
cnt = 0
ans = 1
for i in range(M+1):
  cnt = 1
  d = A[i+1]-A[i]-2
  for j in range(1,d//2+1):
    cnt += math.factorial(d-j)//(math.factorial(d-j*2)*math.factorial(j))
  ans *= cnt
print(ans%1000000007)

Submission status: Wrong Answer

Solution code:
import sys
N,M = list(map(int,input().split()))
A = sys.stdin.readlines()
B = []
cnt = 0
for i in range(N):
  if str(i) in A:
    B.append(cnt-1)
    cnt = 0
  cnt += 1
print(sum(B))

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
a = [int(input()) for nesya in range(m)]
hoge = [1]*(n+1)
for i in range(m):
  hoge[a[i]] = 0
for j in range(1,n+1):
  if hoge[j] == 0:
    continue
  else:
    hoge[j] = hoge[j-1] + hoge[j-2]
  hoge[j] = hoge[j] % (10**9+7)
print(hoge[j]%(10**9+7))

Submission status: Wrong Answer

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

s = [1]*(n+1)

if 1 in a:
    s[1] = 0

for i in range(n-1):
    if i+2 in a:
        s[i+2] = 0
        continue
    s[i+2] = (s[i+1] + s[i]) % (10**9+7)
    
print(s[-1])

Submission status: Wrong Answer

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

s = [1]*(n+1)

if 1 in a:
    s[1] = 0

for i in range(n-1):
    if i+2 in a:
        s[i+2] = 0
        continue
    s[i+2] = (s[i+1] + s[i]) % (10**9+7)
    
print(s[-1])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N,M = map(int,input().split())
lst=[int(input()) for i in range(M)]
t=0
ans=[0]*(N+1)
ans[0]=1
for j in range(N):
 if M!=0:
  if lst[t]==j+1:
   ans[j+1]=0
   t+=1
   t=min(M-1,t)
 else:
  ans[j+1]+=ans[j]
  if j!=0:
   ans[j+1]+=ans[j-1]
  ans[j+1]%=(10**9+7)
print(ans[N])

Submission status: Wrong Answer

Solution code:
def factorial(x, mod=10**9+7):
    # x!
    # 階乗
    # ex) factorial(5) = 120
    tmp = 1
    for i in range(1, x+1):
        tmp = (tmp * i)
    return tmp



def step(t):
    total = 0
    buf2 = int(t/2)

    for i in range(buf2+1):
        buf1 = t-(i*2)
        buf12 = buf1 + i
        buf_ue = factorial(buf12)
        buf_sita1 = factorial(buf1)
        buf_sita2 = factorial(i)
        total += int(buf_ue / (buf_sita1*buf_sita2))

    return total


n, m = map(int, input().split())
MOD = 10**9+7
total = 1
now = 0

for i in range(m):
    a = int(input())
    if a == now:
        total = 0
        break
    elif a == now+1:
        now = a+1
    else:
        print(a-1-now)
        total *= step(a-1-now)
        now = a+1

total *= step(n-now)
total = total%MOD
print(total)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
dp = [0] * (n + 1)
for i in range(m):
    dp[a[i]] = -1
mod = 10 ** 9 + 7
dp[0] = 1
dp[1] = 1
for i in range(2, n + 1):
    if dp[i - 1] == -1 and dp[i - 2] == -1:
        print(0)
        quit()
    if dp[i] == -1:
        continue
    if dp[i - 1] == -1:
        dp[i] = dp[i - 2] % mod
    elif dp[i - 2] == -1:
        dp[i] = dp[i - 1] % mod
    #dp[i] = max(dp[i - 1], dp[i - 2])
    else:
        dp[i] = (dp[i - 1] % mod + dp[i - 2] % mod) % mod
    #dp[i] %= mod
#dp[n]
print(dp[n])

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
dp = [0] * (n + 1)
for i in range(m):
    dp[a[i]] = -1
mod = 10 ** 9 + 7
dp[0] = 1
dp[1] = 1
for i in range(2, n + 1):
    if dp[i] == -1:
        continue
    if dp[i - 1] == -1:
        dp[i] = dp[i - 2] % mod
    elif dp[i - 2] == -1:
        dp[i] = dp[i - 1] % mod
    #dp[i] = max(dp[i - 1], dp[i - 2])
    else:
        dp[i] = (dp[i - 1] % mod + dp[i - 2] % mod) % mod
    #dp[i] %= mod
#dp[n]
if dp[n] == -1:
    print(0)
else:
    print(dp[n])

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
dp = [0] * (n + 1)
for i in range(m):
    dp[a[i]] = -1
mod = 10 ** 9 + 7
dp[0] = 1
dp[1] = 1
for i in range(2, n + 1):
    if dp[i] == -1:
        continue
    if dp[i - 1] == -1:
        dp[i] = dp[i - 2] % mod
    elif dp[i - 2] == -1:
        dp[i] = dp[i - 1] % mod
    #dp[i] = max(dp[i - 1], dp[i - 2])
    else:
        dp[i] = (dp[i - 1] % mod + dp[i - 2] % mod) % mod
    #dp[i] %= mod
print(dp[n])

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
a = [1]*(N+1)
Answer = []
for i in range(M):
    a[int(input())-1]  = 0
Answer.append(1*a[0])
Answer.append(1*a[1]+1*a[0])
for j in range(2,N):
    A = ((Answer[j-1]%(10**9+7)) + (Answer[j-2]%(10**9+7)))*a[j]
    Answer.append(A%(10**9+7))
print(Answer[-1])

Submission status: Wrong Answer

Solution code:
#C
n, m = map(int, input().split())
a = [1] * (n + 1)#進めるかどうか
b = [1] * (n + 1)#移動方法
#進めない:0 進める:1
for i in range(m):
    a[int(input())] = 0
mod = 1e9+7
print(a)
if a[1] == 0:
    b[1] == 0
for i in range(2, n+1):
    #b[i]=(b[2段前]+b[1段前])*a[i] 進めるかどうか(1,0)
    b[i] = (b[i - 1] + b[i - 2]) * a[i] % mod
print(int(b[n]))

Submission status: Wrong Answer

Solution code:
import itertools,sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,M = LI()
a = set([I() for _ in range(M)])
dp = [0]*(N+1) #1_indexed
dp[0] = 1
dp[1] = 0 if 1 in a else 0
for i in range(2,N+1):
    if i in a:
        dp[i] = 0
        continue
    dp[i] = (dp[i-1]+dp[i-2])%(10**9+7)
print(dp[-1])

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
a = [True]*(N+1)
for _ in range(M):
  b = int(input())
  a[b] = False

mod = 10**9+7
dp = [0]*(N+1)
dp[0] = 1
for i in range(N):
  for j in range(i+1,min(i+2,N)+1):
    if a[j]:
      dp[j] += dp[i]
      dp[j] %= mod


print(dp)

Submission status: Wrong Answer

Solution code:
# C - Typical Stairs

MOD = (10 ** 9) + 7
N, M = map(int, input().split())
A = [False] * (N + 1)
for _ in range(M):
    A[int(input())] = True
dp = [0] * (N + 1)
dp[0] = 1
if 1 not in A:
    dp[1] = 1

for i in range(2, N + 1):
    if A[i]:
        dp[i] = 0
    else:
        dp[i] = (dp[i - 1] + dp[i - 2]) % MOD

print(dp[N])

Submission status: Wrong Answer

Solution code:
# C - Typical Stairs

MOD = 10 ** 9 + 7
N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
dp = [0] * (N + 1)

def f(i):
    if dp[i] != None:
        return dp[i]
    else:
        if i in A:
            dp[i] = 0
        elif i < 2:
            dp[i] = 1
        else:
            dp[i] = (f(i - 1) + f(i - 2)) % MOD
        return dp[i]

print(f(N))