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

N,M=map(int,input().split())
a=[int(input()) for i in range(M)]
c=[0]*(N+1)
c[0]=1
MOD=7+10**9
if M==0:
    c[1]=1
    for i in range(1,N):
        c[i+1]=c[i]+c[i-1]
    print(c[N])
elif N==1:
    print(1)
else:
    j=0
    for i in range(1,N+1):
        if i==a[j]:
            if j+1<M:
                if i+1==a[j+1]:
                    print(0)
                    sys.exit(0)
                else:
                    j+=1
        elif i==1:
            c[i]=c[i-1]
        else:
            c[i]=(c[i-1]+c[i-2])%MOD
    print(c[-1]%MOD)

Submission status: Wrong Answer

Solution code:
import sys

N,M=map(int,input().split())
a=[int(input()) for i in range(M)]
c=[0]*(N+1)
c[0]=1
MOD=7+10**9
if M==0:
    c[1]=1
    for i in range(1,N):
        c[i+1]=c[i]+c[i-1]
    print(c[N])
else:
    j=0
    for i in range(1,N+1):
        if i==a[j]:
            if j+1<M:
                if i+1==a[j+1]:
                    print(0)
                    sys.exit(0)
                else:
                    j+=1
        elif i==1:
            c[i]=c[i-1]
        else:
            c[i]=(c[i-1]+c[i-2])%MOD
    print(c[-1]%MOD)

Submission status: Wrong Answer

Solution code:
import sys

N,M=map(int,input().split())
a=[int(input()) for i in range(M)]
c=[0]*(N+1)
c[0]=1
MOD=7+10**9
if M==0:
    c[1]=1
    for i in range(1,N):
        c[i+1]=c[i]+c[i-1]
    print(c[N])
else:
    j=0
    for i in range(1,N+1):
        if i==a[j]:
            if j+1<M:
                if i+1==a[j+1]:
                    print(0)
                    sys.exit(0)
                else:
                    j+=1
        elif i==1:
            c[i]=c[i-1]
        else:
            c[i]=c[i-1]+c[i-2]
    print(c[-1]%MOD)

Submission status: Wrong Answer

Solution code:
#129
N,M=map(int,input().split())
a=[int(input()) for i in range(M)]
f=[1,2,3,5,8]
def cu(x):
    global f
    if len(f)<x:
        for i in range(len(f),x):
            f.append( f[i-1]+f[i-2] )
    return f[x-1]

if M==0:
    print(cu(N))
    exit(0)
else:

    a_d=[a[0]-1]
    for i in range(M-1):
        a_d.append( a[i+1]-a[i]-1 )
    a_d.append(N-a[-1]-1)
    if 0 in a_d[1:-1]:
        print(0)
        exit(0)
    else:
        count=1
        for i in range(M+1):
            if i==0 and a_d[0]!=0:
                count=cu(a_d[0])
            elif i==M and a_d[i]!=0:
                count=count*cu(a_d[-1])
            else:
                if a_d[i]>=3:
                    count=count*cu(a_d[i]-1)
        print(count%(10**9+7))

Submission status: Wrong Answer

Solution code:
#129
N,M=map(int,input().split())
a=[int(input()) for i in range(M)]
f=[1,2,3,5,8]
def cu(x):
    global f
    if len(f)<x:
        for i in range(len(f),x):
            f.append( f[i-1]+f[i-2] )
    return f[x-1]

if M==0:
    print(cu(N))
    exit(0)
else:

    a_d=[a[0]-1]
    for i in range(M-1):
        a_d.append( a[i+1]-a[i]-1 )
    a_d.append(N-a[-1]-1)
    if 0 in a_d[1:]:
        print(0)
        exit(0)
    else:
        count=1
        for i in range(M+1):
            if i==0 and a_d[0]!=0:
                count=cu(a_d[0])
            elif i==M:
                count=count*cu(a_d[-1])
            else:
                if a_d[i]>=3:
                    count=count*cu(a_d[i]-1)
        print(count%(10**9+7))

Submission status: Wrong Answer

Solution code:
#129
N,M=map(int,input().split())
a=[int(input()) for i in range(M)]
f=[1,2,3,5,8]
def cu(x):
    global f
    if len(f)<x:
        for i in range(len(f),x):
            f.append( f[i-1]+f[i-2] )
    return f[x-1]

if M==0:
    print(cu(N))
    exit(0)
else:

    a_d=[a[0]-1]
    for i in range(M-1):
        a_d.append( a[i+1]-a[i]-1 )
    a_d.append(N-a[-1]-1)
    if 0 in a_d[1:]:
        print(0)
        exit(0)
    else:
        count=1
        for i in range(M+1):
            if i==0 and a_d[0]!=0:
                count=cu(a_d[0])
            elif i==M:
                count=count*cu(a_d[-1])
            else:
                if a_d[i]>=3:
                    count=count*cu(a_d[i]-1)
    print(count%(10**9+7))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
MOD=10**9+7
n,m=map(int,input().split())
A=[1 for i in range(n)]
if n!=1:
  A[1]=2
  for i in range(m):
    A[int(input())-1]=0
  
  if A[0]==0:
    A[1]=1


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

    
  print(A[n-1])
  
else:print(1)

Submission status: Wrong Answer

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

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

ans = int(0)
answer = int(0)

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

for i in l:
  k.remove(i)

for i in range(n-m-1):
  if k[i]+1 == k[i+1] and  k[i+1] + 1 == k[i+2]:
    ans += 2

answer = ans%1000000007
print(answer)

Submission status: Wrong Answer

Solution code:
def resolve():
    n,m= map(int,input().split())
    a = [int(input()) for _ in range(m)]
    d = [0]*(n+1)
    if not 1 in a : d[1] = 1
    if not 2 in a : d[2] = d[1] + 1
    for i in range(3,n+1):
        if not i in a :
            d[i] += d[i-1] + d[i-2]
    print(d[i]%1000000007)

Submission status: Wrong Answer

Solution code:
N, M = [int(nm) for nm in input().split()]
A = [-1]
for m in range(M):
  A.append(int(input()))
A.append(N+1)

import math
total_case = 1
for m in range(M+1):
  a1 = A[m]
  a2 = A[m+1]
  safe_stairs = a2 - a1 - 1
  if safe_stairs == 0:
    print(0)
    break
  howmany_jump1 = safe_stairs - 1
  mx_jump2 = howmany_jump1 // 2
  #２のジャンプは０回～（mx_jump2）回
  case = 0
  for j2 in range(mx_jump2 + 1):
    jump2 = j2
    jump1 = howmany_jump1 - (j2 * 2)
    c = int(math.factorial(jump1 + jump2)) / (int(math.factorial(jump1)) * int(math.factorial(jump2)))
    case += c
  total_case *= case
else:
  ans = total_case % (10**9 + 7)
  print(ans)

Submission status: Wrong Answer

Solution code:
N, M = [int(nm) for nm in input().split()]
A = [-1]
for m in range(M):
  A.append(int(input()))
A.append(N+1)

import math
total_case = 1
for m in range(M+1):
  a1 = A[m]
  a2 = A[m+1]
  safe_stairs = a2 - a1 - 1
  if safe_stairs == 0:
    print(0)
    break
  howmany_jump1 = safe_stairs - 1
  mx_jump2 = howmany_jump1 // 2
  #２のジャンプは０回～（mx_jump2）回
  case = 0
  for j2 in range(mx_jump2 + 1):
    jump2 = j2
    jump1 = howmany_jump1 - (j2 * 2)
    c = int(math.factorial(jump1+jump2) / (math.factorial(jump1)*math.factorial(jump2)))
    case += c
  total_case *= case
else:
  ans = total_case % (10**9 + 7)
  print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
a = [int(input()) for i in range(m)]
broken = set(a)
dp=[0]*(n-1)+[1]+[1]
mod = 10**9 + 7

for i in range(n-2,-1,-1):
  if i in broken:
    continue
  dp[i]=dp[i+1]+dp[i+2]
  dp[i]%=mod
print(dp[0])

Submission status: Wrong Answer

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

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

ans = 1
for i in range(m):
    if a[i-1]-a[i]-1 == 0:
        ans = 0
        break
    elif a[i-1]-a[i]-1 == 1:
        continue
    else:
        dp = [1] + [0]*(a[i+1]-a[i]-2)
    for j in range(1, a[i+1]-a[i]-1):
        dp[j] = dp[j-1] + dp[j-2]
    ans *= dp[-1]

print(ans%1000000007)

Submission status: Wrong Answer

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

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


dp = [0] * (N + 1)
dp[N-1] = dp[N] = 1
for i in reversed(range(N-1)):
    if broken[i]:
        dp[i] = 0
        continue
    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

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


dp = [0] * (N + 1)
dp[N-1] = dp[N] = 1
for i in reversed(range(N-1)):
    if broken[i]:
        dp[i] = 0
        continue
    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

broken = []
for i in range(M):
    broken.append(int(input()))

ans = 1

dp = [0] * (N + 1)
dp[N-1] = dp[N] = 1
for i in reversed(range(N-1)):
    if i in broken:
        dp[i] = 0
        continue
    dp[i] = (dp[i+1] + dp[i+2]) % MOD

print(dp[0])

Submission status: Wrong Answer

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

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

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

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

print(dp[-1])

Submission status: Wrong Answer

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)

#  f = open('C_input.txt')
#  lines = f.readlines()
#  f.close()
#  N, M = map(int, lines[0].split())
#  A = []
#  for line in lines[1:]:
#      A.append(int(line))
#  print(A)
N, M = LI()
A = []
for i in range(M):
    A.append(_I())

"""
考え方
xにたどり着く通りは、x-1とx-2段目にたどり着く通りの合計
dp
3が障害のとき
1へは1通り
2へは0からと1からの2通り
3へは0通り
4へは2からの2通りと、3からの0通りで2通り
5へは3からの0通りと4からの2通りで2通り
6へは4からの2通りと5からの2通りで4通り
"""
dp = [None if i not in A else 0 for i in range(0, N+1)]
dp[0] = 1
dp[1] = 1
for i in range(2, N+1):
    # i段目までの通りを計算する
    if dp[i] == 0:
        # i段目が障害のときは0になっているので飛ばす
        continue
    
    dp[i] = dp[i-1] + dp[i-2]

print(dp[-1] % mod)

Submission status: Wrong Answer

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

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

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

c = 0
d = [0]*(m+1)
for j in range(m+1):
    c = a[j+1] - a[j] -1
    
    e, f = 0,0
    while c - e*2 >= 0:
        f += comb(c-e,c-2*e)
        e +=1
    d[j] = f
    
    


    
answer = 1
for number in range(m+1):
    answer *= d[number]

ch = 1
for k in range(m-1):
    if check[k] == check[k+1] - 1:
        ch =0


if ch == 0:
    print(0)
else:
    print(answer % (10**9+7))

Submission status: Wrong Answer

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)

N, M = LI()
A = []
for i in range(M):
    A.append(_I())

"""
飛び越える前までの道筋の通りを調べてかけていく
"""

if M != 0:
    # 連続した壊れた段がある場合は0
    B = [i for i in A]
    B.remove(B[0])
    B.append(10**15)
    diffs = [b - a for a, b in zip(A,B)]
    #  print(diffs)

    if any(i == 1 for i in diffs):
        # 隣同士なので0
        print(0)
        exit()

# 隣り合うものがないので、各区間の通りを出していく
res = [0 for _ in range(N)]
memo = {}
for aidx in range(len(A)+1):
    if aidx == 0:
        start = 0
    else:
        start = A[aidx-1] + 1

    if aidx == len(A):
        # last item
        end = N
    else:
        end = A[aidx] - 1
    #ぐうきで分ける、一箇所を2とびにした場合、2箇所を2とびにした場合などで変える
    r = end - start
    if r in memo.keys():
        res[aidx] += memo[r]
        continue
    max_2_steps = r // 2
    #  print('ma', max_2_steps)
    for i in range(max_2_steps + 1):
        tmp = r
        tmp -= 2 * i
        #  print('i,r,tmp', i, r, tmp)
        # tmpが1段ずつになる
        res[aidx] += int(math.factorial(i + tmp) / (math.factorial(tmp) * math.factorial(i)))
    memo[r] = res[aidx]

#  print(res)
ans = 0
for r in res:
    if r == 0:
        continue
    if ans == 0:
        ans = r
    else:
        ans *= r
print(ans % mod)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
#ABC130C
import sys


tmp = input().split()
hoge = list(map(lambda a: int(a), tmp))
n=hoge[0]
m=hoge[1]

a=[]
for i in range(0,n):
	a.append(1)

#print(a)

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

#print(a)

for i in range(2,n):
	a[i]=a[i]*(a[i-1]+a[i-2])


print((a[n-1]+a[n-2])% 1000000007)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
#ABC130C
import sys


tmp = input().split()
hoge = list(map(lambda a: int(a), tmp))
n=hoge[0]
m=hoge[1]

a=[]
for i in range(0,n):
	a.append(1)

print(a)

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

print(a)

for i in range(2,n):
	a[i]=a[i]*(a[i-1]+a[i-2])


print((a[n-1]+a[n-2])% 1000000007)

Submission status: Wrong Answer

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)

N, M = LI()
A = []
for i in range(M):
    A.append(_I())

"""
飛び越える前までの道筋の通りを調べてかけていく
"""

if M != 0:
    # 連続した壊れた段がある場合は0
    B = [i for i in A]
    B.remove(B[0])
    B.append(10**15)
    diffs = [b - a for a, b in zip(A,B)]
    #  print(diffs)

    if any(i == 1 for i in diffs):
        # 隣同士なので0
        print(0)
        exit()

# 隣り合うものがないので、各区間の通りを出していく
res = [0 for _ in range(N)]
memo = {}
for aidx in range(len(A)+1):
    if aidx == 0:
        start = 0
    else:
        start = A[aidx-1] + 1

    if aidx == len(A):
        # last item
        end = N
    else:
        end = A[aidx] - 1
    #ぐうきで分ける、一箇所を2とびにした場合、2箇所を2とびにした場合などで変える
    r = end - start
    if r in memo.keys():
        res[aidx] += memo[r]
        continue
    max_2_steps = r // 2
    #  print('ma', max_2_steps)
    for i in range(max_2_steps + 1):
        tmp = r
        tmp -= 2 * i
        #  print('i,r,tmp', i, r, tmp)
        # tmpが1段ずつになる
        res[aidx] += int(math.factorial(i + tmp) / (math.factorial(tmp) * math.factorial(i)))
        memo[r] = int(math.factorial(i + tmp) / (math.factorial(tmp) * math.factorial(i)))

#  print(res)
ans = 0
for r in res:
    if r == 0:
        continue
    if ans == 0:
        ans = r
    else:
        ans *= r
print(ans % mod)

Submission status: Wrong Answer

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)

N, M = LI()
A = []
for i in range(M):
    A.append(_I())

"""
飛び越える前までの道筋の通りを調べてかけていく
"""

if M != 0:
    # 連続した壊れた段がある場合は0
    B = [i for i in A]
    B.remove(B[0])
    B.append(10**15)
    diffs = [b - a for a, b in zip(A,B)]
    #  print(diffs)

    if any(i == 1 for i in diffs):
        # 隣同士なので0
        print(0)
        exit()

# 隣り合うものがないので、各区間の通りを出していく
res = [0 for _ in range(N)]
memo = {}
for aidx in range(len(A)+1):
    if aidx == 0:
        start = 0
    else:
        start = A[aidx-1] + 1

    if aidx == len(A):
        # last item
        end = N
    else:
        end = A[aidx] - 1
    #ぐうきで分ける、一箇所を2とびにした場合、2箇所を2とびにした場合などで変える
    r = end - start
    if r in memo.keys():
        res[r] += memo[r]
        continue
    max_2_steps = r // 2
    #  print('ma', max_2_steps)
    for i in range(max_2_steps + 1):
        tmp = r
        tmp -= 2 * i
        #  print('i,r,tmp', i, r, tmp)
        # tmpが1段ずつになる
        res[aidx] += int(math.factorial(i + tmp) / (math.factorial(tmp) * math.factorial(i)))
        memo[r] = int(math.factorial(i + tmp) / (math.factorial(tmp) * math.factorial(i)))

#  print(res)
ans = 0
for r in res:
    if r == 0:
        continue
    if ans == 0:
        ans = r
    else:
        ans *= r
print(ans % mod)

Submission status: Wrong Answer

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)

N, M = LI()
A = []
for i in range(M):
    A.append(_I())

"""
飛び越える前までの道筋の通りを調べてかけていく
"""

if M != 0:
    # 連続した壊れた段がある場合は0
    B = [i for i in A]
    B.remove(B[0])
    B.append(10**15)
    diffs = [b - a for a, b in zip(A,B)]
    #  print(diffs)

    if any(i == 1 for i in diffs):
        # 隣同士なので0
        print(0)
        exit()

# 隣り合うものがないので、各区間の通りを出していく
res = [0 for _ in range(N)]
for aidx in range(len(A)+1):
    if aidx == 0:
        start = 0
    else:
        start = A[aidx-1] + 1

    if aidx == len(A):
        # last item
        end = N
    else:
        end = A[aidx] - 1
    #ぐうきで分ける、一箇所を2とびにした場合、2箇所を2とびにした場合などで変える
    r = end - start
    max_2_steps = r // 2
    #  print('ma', max_2_steps)
    for i in range(max_2_steps + 1):
        tmp = r
        tmp -= 2 * i
        #  print('i,r,tmp', i, r, tmp)
        # tmpが1段ずつになる
        res[aidx] += int(math.factorial(i + tmp) / (math.factorial(tmp) * math.factorial(i)))

#  print(res)
ans = 0
for r in res:
    if r == 0:
        continue
    if ans == 0:
        ans = r
    else:
        ans *= r
print(ans % mod)

Submission status: Wrong Answer

Solution code:
# 解き直し
# 名前にTypicalって書いてあるのでTypicalです


n, m = map(int, input().split())
step_count = [0 for _ in range(n+1)]
ng_step = [False for _ in range(n+1)]
for _ in range(m):
  ng = int(input())
  ng_step[ng] = True

for i in range(n+1):
  if ng_step[i]:
    step_count[i] = 0
  else:
    if i==1:
      step_count[i] = 1
    elif i==2:
      step_count[i] = 1 + step_count[i-1]
    else:
      step_count[i] = (step_count[i-2]+step_count[i-1])%(10**9+7)

print(step_count) 
print(step_count[-1])

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
mod = 1000000007
if 1 not in a  and 2 not in a:
    c = [1,2]
elif 1 in a and 2 not in a:
    c = [0,1]
elif 1 not in a and 2 in a:
    c = [1,0]
else:
    c = [0,0]

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

print(c[len(c)-1])

Submission status: Wrong Answer

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

dp=['inf']*(n+1)
for i in range(m):
    dp[a[i]]=0
dp[0]=1
dp[1]=1
for i in range(2,n+1):
    if dp[i]==0:
        if dp[i+1]==0:
            print(0)
            exit()
        else:
            pass
    else:
        dp[i]=dp[i-1]+dp[i-2]
print(dp[n]%(10**9+7))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a,b,c = LI()
    ans = 10 ** 5
    ans = min(ans, a + b)
    ans = min(ans, a + c)
    ans = min(ans, c + b)
    print(ans)
    return

#B
def B():
    n = II()
    w = LI()
    ans = inf
    for i in range(n):
        ans = min(ans, abs(sum(w[:i]) - sum(w[i:])))
    print(ans)
    return

#C
def C():
    n, m = LI()
    a = IR(m)+[inf]
    dp = [0] * (n + 3)
    dp[0] = 1
    for i in range(n + 1):
        if a[bisect_left(a, i + 1)] != i + 1:
            dp[i + 1] += dp[i] % mod
        if a[bisect_left(a, i + 2)] != i + 2:
            dp[i + 2] += dp[i] % mod
    print(dp[n])
    return

#D
def D():
    return


#Solve
if __name__ == '__main__':
    C()

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
B = [0 for _ in range(N+1)]
for a in A:
  B[a] = 1
 
dp = [0 for _ in range(N+1)]
dp[0] = 1
dp[1] = 1
for i in range(2, N+1):
  if B[i] != 1:
    if B[i-2] == 0 and B[i-1] == 1:
      dp[i] = dp[i-2]
    elif B[i-2] == 1 and B[i-1] == 0:
      dp[i] = dp[i-1]
    elif B[i-2] == 0 and B[i-1] == 0:
      dp[i] = dp[i-1] + dp[i-2]
    else:
      dp[i] = 0

if dp[-1] == -1:
  print(0)
else:
  print(dp[-1])

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
B = [0 for _ in range(N+1)]
for a in A:
  B[a] = 1
 
dp = [-1 for _ in range(N+1)]
dp[0] = 1
dp[1] = 1
for i in range(2, N+1):
  if B[i-2] == 0 and B[i-1] == 1:
    dp[i] = dp[i-2]
  elif B[i-2] == 1 and B[i-1] == 0:
    dp[i] = dp[i-1]
  elif B[i-2] == 0 and B[i-1] == 0:
    dp[i] = dp[i-1] + dp[i-2]
  else:
    dp[i] = 0
 
print(dp[-1])

Submission status: Wrong Answer

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

step = [-1] * (N+1)
if 1 in A:
  step[1] = 0
  step[2] = 1
else:
  step[1] = 1
if 2 in A:
  step[2] = 0

for i in range(3, N+1):
  if i in A:
    step[i] = 0
  else:
    step[i] = step[i-1] + step[i-2]
print(step[N])

Submission status: Wrong Answer

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

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

print(dp[-1])

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
bro = [int(input()) for i in range(M)]
mod = 10**9 + 7
dp = [0]*(N+1)
if N == 1:
    print(1)
    exit()
dp[0:2] = 1,1
for i in range(2,N+1):
    if i in bro:
        continue
    else:
        dp[i]= dp[i-1] + dp[i-2]
print(dp[-1] % mod)

Submission status: Wrong Answer

Solution code:
def calc_pattern(stair_num, damaged_step_list, state_number):
    if stair_num == 1:
        return 1
    if stair_num == 3 and damaged_step_list==[1]:
        return 1
    
    
if __name__ == '__main__':
    N, M = map(int, input().split())
    a = [int(input()) for _ in range(M)]
    a = sorted(a)

    answer = 1
    if a[-1::] == N:
        answer = 0

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

    if answer != 0:
        for i in range(1, N+1):
            if i+1 in a:
                continue
            else:
                answer = (answer * 2)%1000000007
            print(str(i) + ' ' + str(answer))
    print(answer)

Submission status: Wrong Answer

Solution code:
ini=input().split()
ini=[int(i) for i in ini]
N=ini[0]
M=ini[1]

a=[0]
for i in range(M):
    a.append(int(input()))
a.append(N)

#print(a)
ans=1
def fib(n):
    
    atai = 1
    atai2 = 2
   # global atai,atai2
    if n==1:
        atai2=1
        return atai2
    if n==2:
        atai2=2
        return atai2
    else:
        for i in range(1,n):
            temp=atai2
            atai2=atai+temp
            atai=temp
            if atai2>1000000007:
                atai%=1000000007
                atai2%=1000000007
        return atai2
#print(N,M)
for i in range(M+1):
    b=a[i+1]-a[i]
    # if i==M:
    #     ans=ans*fib(N-a[i]-1)
    #     print("iff",ans,fib(N-a[i]-1))
    if b==0 and a[1]!=1:
        ans=0
        break
    if b>0:
        ans=ans*fib(b)
#        if ans>1000000007:
        ans=ans % 1000000007
        print(ans,b,fib(b))
#        print("if",ans,fib(b))
#        print(ans,fib(b),c[i])

ans=ans % 1000000007
print(ans)

Submission status: Wrong Answer

Solution code:
ini=input().split()
ini=[int(i) for i in ini]
N=ini[0]
M=ini[1]

a=[0]
for i in range(M):
    a.append(int(input()))
a.append(N)

#print(a)
ans=1
def fib(n):
    
    atai = 1
    atai2 = 2
   # global atai,atai2
    if n==1:
        atai2=1
        return atai2
    if n==2:
        atai2=2
        return atai2
    else:
        for i in range(1,n):
            temp=atai2
            atai2=atai+temp
            atai=temp
            if atai2>1000000007:
                atai%=1000000007
                atai2%=1000000007
        return atai2
#print(N,M)
for i in range(M+1):
    b=a[i+1]-a[i]-1
    # if i==M:
    #     ans=ans*fib(N-a[i]-1)
    #     print("iff",ans,fib(N-a[i]-1))
    if b==0 and a[1]!=1:
        ans=0
        break
    if b>0:
        ans=ans*fib(b)
#        if ans>1000000007:
        ans=ans % 1000000007
#        print("if",ans,fib(b))
#        print(ans,fib(b),c[i])

ans=ans % 1000000007
print(ans)

Submission status: Wrong Answer

Solution code:
ini=input().split()
ini=[int(i) for i in ini]
N=ini[0]
M=ini[1]

a=[0]
for i in range(M):
    a.append(int(input()))
a.append(N)

#print(a)
ans=1
def fib(n):
    
    atai = 1
    atai2 = 2
   # global atai,atai2
    if n==1:
        atai2=1
        return atai2
    if n==2:
        atai2=2
        return atai2
    else:
        for i in range(1,n):
            temp=atai2
            atai2=atai+temp
            atai=temp
        return atai2
#print(N,M)
for i in range(M+1):
    b=a[i+1]-a[i]-1
    # if i==M:
    #     ans=ans*fib(N-a[i]-1)
    #     print("iff",ans,fib(N-a[i]-1))
    if b==0 and a[1]!=1:
        ans=0
        break
    if b>0:
        ans=ans*fib(b)
#        if ans>1000000007:
        ans=ans % 1000000007
#        print("if",ans,fib(b))
#        print(ans,fib(b),c[i])

ans=ans % 1000000007
print(ans)

Submission status: Wrong Answer

Solution code:
ini=input().split()
ini=[int(i) for i in ini]
N=ini[0]
M=ini[1]

a=[0]
for i in range(M):
    a.append(int(input()))
a.append(N)

#print(a)
ans=1
def fib(n):
    
    atai = 1
    atai2 = 2
   # global atai,atai2
    if n==1:
        atai2=1
        return atai2
    if n==2:
        atai2=2
        return atai2
    else:
        for i in range(1,n):
            temp=atai2
            atai2=atai+temp
            atai=temp
        return atai2
#print(N,M)
for i in range(M+1):
    b=a[i+1]-a[i]-1
    # if i==M:
    #     ans=ans*fib(N-a[i]-1)
    #     print("iff",ans,fib(N-a[i]-1))
    if b==0 and a[1]!=1:
        ans=0
        break
    if b>0:
        ans=ans*fib(b)
        if ans>1000000007:
            ans=ans % 1000000007
#        print("if",ans,fib(b))
#        print(ans,fib(b),c[i])

ans=ans % 1000000007
print(ans)

Submission status: Wrong Answer

Solution code:
ini=input().split()
ini=[int(i) for i in ini]
N=ini[0]
M=ini[1]

a=[0]
for i in range(M):
    a.append(int(input()))
a.append(N)

#print(a)
ans=1
def fib(n):
    
    atai = 1
    atai2 = 2
   # global atai,atai2
    if n==1:
        atai2=1
        return atai2
    if n==2:
        atai2=2
        return atai2
    else:
        for i in range(1,n):
            temp=atai2
            atai2=atai+temp
            atai=temp
        return atai2
#print(N,M)
for i in range(M+1):
    b=a[i+1]-a[i]-1
    # if i==M:
    #     ans=ans*fib(N-a[i]-1)
    #     print("iff",ans,fib(N-a[i]-1))
    if b==0 and a[1]!=1:
        ans=0
        break
    if b>0:
        ans=ans*fib(b)
        if ans>1000000007:
            ans=ans-1000000007
#        print("if",ans,fib(b))
#        print(ans,fib(b),c[i])

ans=ans % 1000000007
print(ans)

Submission status: Wrong Answer

Solution code:
ini=input().split()
ini=[int(i) for i in ini]
N=ini[0]
M=ini[1]

a=[0]
for i in range(M):
    a.append(int(input()))
a.append(N)

#print(a)
ans=1
def fib(n):
    
    atai = 1
    atai2 = 2
   # global atai,atai2
    if n==1:
        atai2=1
        return atai2
    if n==2:
        atai2=2
        return atai2
    else:
        for i in range(1,n):
            temp=atai2
            atai2=atai+temp
            atai=temp
        return atai2
#print(N,M)
for i in range(M+1):
    b=a[i+1]-a[i]-1
    # if i==M:
    #     ans=ans*fib(N-a[i]-1)
    #     print("iff",ans,fib(N-a[i]-1))
    if b==0 and a[1]!=1:
        ans=0
        break
    if b>0:
        ans=ans*fib(b)
#        print("if",ans,fib(b))
#        print(ans,fib(b),c[i])

ans=ans % 1000000007
print(ans)