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

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

Submission status: Wrong Answer

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

ans = [0]*(n+1)
ans[0] = 1
ans[1] = 1
for i in range(n+1):
    if i==0:
        continue
        
    elif i in stair:
        ans[i] = 0
    else:
        ans[i] = ans[i-2] + ans[i-1]
print(ans[n]%1000000007)

Submission status: Wrong Answer

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

ans = [0 for i in range(n+1)]
ans[0] = 1
ans[1] = 1
for i in range(n+1):
    if i==0:
        continue
        
    elif i in stair:
        ans[i] = 0
    else:
        ans[i] = ans[i-2] + ans[i-1]
print(ans[n]%1000000007)

Submission status: Wrong Answer

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

ans = [0 for i in range(n+1)]
ans[0] = 1
ans[1] = 1
for i in range(n+1):
    if i==0:
        continue
        
    elif i in stair:
        ans[i] = 0
    else:
        ans[i] = ans[i-2] + ans[i-1]
print(ans[n])

Submission status: Wrong Answer

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

mod = 1000000007;

# dpテーブル, 壊れた階段を記録するテーブル用意
dp = [0]*(N+1)
broken = [0]*(N+1)

# 初期化
dp[0] = 1
dp[1] = 1

# 壊れている階段は-1で定義
for _ in range(M) :
    broken[int(input())] = -1

# 漸化式から求めていく
for i in range(2, N+1):
    if i == 3:
        print(dp[i-1])
        print(dp[i-2])
        
    if (broken[i-1] != -1):
        dp[i] += dp[i-1]
    
    if (broken[i-2] != -1):
        dp[i] += dp[i-2]
    
    dp[i] %= mod

print(dp[-1])

Submission status: Wrong Answer

Solution code:
def fib(nn):
    if nn == 0:
        return 0
    aa, bb = 1, 1
    for ii in range(nn-1):
        aa, bb = bb, aa + bb
    return bb

n, m = map(int, input().split())
a = []
b = []
for i in range(m):
    a.append(int(input()))
if m == 0:
    pass
else:
    if a[0] == 1:
        b.append(1)
    else:
        b.append(a[0] - 1)
    for i in range(1, m):
        b.append(a[i] - a[i-1] - 1)
    b.append(n - a[len(a)-1] - 1)
c = []
for i in b:
    c.append(fib(i))

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

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
oks = [True]*(n+1)
for i in range(m):
    a = int(input())
    oks[a] = False
print(oks)
dp = [0]*(n+1)
dp[0] = 1
for i in range(n+1):
    for j in range(i+1,min(n+1,i+3)):
        if oks[j]:
            dp[j] += dp[i]
            dp[j] %= 1000000007
print(dp[n])

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
mod = int(1e9 + 7)
notbroken = [True for _ in range(n+1)]

for i in a:
  notbroken[i] = False

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

print(dp[n])

Submission status: Wrong Answer

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

def check(arr):
    for i in range(m-1):
      if a[i] + 1 == a[i+1]: return 0
    dp = [0 for _ in range(n+1)]
    dp[0] = 0
    dp[1] = 1
    for i in range(2, n+1):
        if i in a: continue
        dp[i] += dp[i-1] + dp[i-2]
        dp[i] %= mod
    #print(dp)
    return dp[n]

print(check(n))

Submission status: Wrong Answer

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

factorial=[1]
for i in range(1, n+1):
    factorial.append(factorial[-1] * i % mod)

inv_factorial = [-1] * (n+1)
inv_factorial[-1] = pow(factorial[-1], mod-2, mod)

for i in reversed(range(n)):
    inv_factorial[i] = inv_factorial[i+1] * (i+1) % mod

def fact(n):
    return factorial[n]

def nck(n, k):
    if k>n or k<0:
        return 0
    else:
        return factorial[n] * inv_factorial[n-k] * inv_factorial[k]

def cnt(n):
    ans=0
    for i in range(n//2+1):
      ans+=nck(n-i,i)
      ans%=mod
    return ans

ans=cnt(broken[0]-1)
for i in range(1,m):
  tmp=broken[i]-broken[i-1]-2
  if tmp==-1:
    ans=0
    break
  else:
    ans*=cnt(tmp)
    ans%=mod
    
tmp=n-broken[m-1]-1
ans*=cnt(tmp)
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

mod = 1000000007

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

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

print(dp[n])

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
aset = set([int(input()) for _ in range(M)])
dp = [0] * (N + 1)
dp[0] = 1
if 1 not in aset:
    dp[1] = 1
for i in range(2, N + 1):
    if i in aset:
        dp[i] = 0
    else:
        dp[i] = dp[i - 1] + dp[i - 2]
print(dp[-1])

Submission status: Wrong Answer

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

dp = [0] * (n + 1)
if 0 not in a:
    dp[0] = 1
if 1 not in a:
    dp[1] = 1
if 2 not in a and n >= 2:
    if 1 in a:
        dp[2] = 1
    else:
        dp[2] = 2
if (n >= 10**4):
    exit()

mod = 10**9+7

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

print(dp[-1])

Submission status: Wrong Answer

Solution code:
N,M,*a=map(int,open(0).read().split())
dp=[1]*(N+1)
for i in range(2,N+1):
    if i in a:
        dp[i]=0
        continue
    dp[i]=(dp[i-1]+dp[i-2])%1000000007
print(dp[-1])

Submission status: Wrong Answer

Solution code:
import sys

N, M = map(int, input().split())
li = [int(input()) for i in range(M)]

count = 0
flag = False

dp = [0] * (N+1)

for n in range(1, N+1):
  if n == 1 and not n in li:
    dp[1] = 1
    continue
  
  if n == 2 and not n in li:
    dp[2] = dp[1] + 1
    continue
  
  if n in li:
    if flag:
      print(0)
      sys.exit()

    flag = True
    continue

  if not (n-1) in li:
    dp[n] += dp[n-1]
    
  if not (n-2) in li:
    dp[n] += dp[n-2]
    
  dp[n] %= 1000000007
    
  flag = False
  
print(dp[N])

Submission status: Wrong Answer

Solution code:
import sys

N, M = map(int, input().split())
li = [int(input()) for i in range(M)]

count = 0
flag = False

dp = [0] * (N+1)

for n in range(1, N+1):
  if n == 1 and not n in li:
    dp[1] = 1
    continue
  
  if n == 2 and not n in li:
    dp[2] = dp[1] + 1
    continue
  
  if n in li:
    if flag:
      print(0)
      sys.exit()

    flag = True
    continue

  if not (n-1) in li:
    dp[n] += dp[n-1]
    
  if not (n-2) in li:
    dp[n] += dp[n-2]
    
  flag = False
  
print(dp[N] % 1000000007)

Submission status: Wrong Answer

Solution code:
import sys

N, M = map(int, input().split())
li = [int(input()) for i in range(M)]

count = 0
flag = False

dp = [0] * (N+1)

for n in range(1, N+1):
  if n == 1 and not n in li:
    dp[1] = 1
    continue
  
  if n == 2 and not n in li:
    dp[2] = 2
    continue
  
  if n in li:
    if flag:
      print(0)
      sys.exit()

    flag = True
    continue

  if not (n-1) in li:
    dp[n] += dp[n-1]
    
  if not (n-2) in li:
    dp[n] += dp[n-2]
    
  flag = False

print(dp[N] % 1000000007)

Submission status: Wrong Answer

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

f = [0]*(n+3)
f[0] = 1
endf = 0
for i in range(1,n+1):
    if i in xx:
        endf += 1
        print('skip',i)
        if endf ==2:
            print(0)
            break
        continue
    else :
        if endf == 1:
            endf = 0
            f[i] = f[i-2]
        else :
            endf = 0
            f[i] = f[i-1] + f[i-2]
else:
    print(f[n]%1000000007)

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

Solution code:
MOD = 1e9 + 7

N, M = [int(i) for i in input().split()]
issafe = [True] * (N + 1)
for i in range(M):
    a = int(input())
    # a 段目は壊れている
    issafe[a] = False

# dp
dp = [0] * (N + 1)
# 初期化
dp[0] = 1
if issafe[1]:
    dp[1] = 1

for i in range(2, N + 1):
    # i - 1 段目が安全なら
    if issafe[i - 1]:
        dp[i] += dp[i - 1]
    # i - 2 段目が安全なら
    if issafe[i - 2]:
        dp[i] += dp[i - 2]
    dp[i] %= MOD
print(dp[N])

Submission status: Wrong Answer

Solution code:
from scipy.misc import comb

def LI():
  return [int(s) for s in input().split()]

def dansu(a,b):
    one_count = b - a
    two_count = 0
    count = 1
    for i in range((b-a) // 2):
        one_count -= 2
        two_count += 1
        count += comb(one_count+two_count,one_count,exact = True)
        
    return count
        
N,M = LI()
MOD = 10**9 + 7

total_count = 1

m1 = 0
#m2 = int(input())

total_count = 1

#m1 = m2 + 1

for i in range(M+1):
  
  if i == 0:
    m1 = 0
  m2 = N if i == M else (int(input()) - 1)

  if m2 - m1 <= 0 and i != 0:
    print(0)
    exit()
    
  total_count = (total_count * dansu(m1,m2)) % MOD
  m1 = m2 + 2
  
print(total_count % MOD)

Submission status: Wrong Answer

Solution code:
def main():
    mod = 1000000007
    N, M, *A = map(int, open(0).read().split())
    A = set(A)
    F = [0] * (N + 1)
    F[0] = 1
    if 1 in A:
        F[1] = 1
    for i in range(2, N + 1):
        if i not in A:
            F[i] = (F[i-1] + F[i-2])
    print(F[N] % mod)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def ways_to_climb(total_steps, broken_steps):
	if total_steps < 2:
		return 0 if 1 in broken_steps else 1

	steps = [0] * (total_steps + 1)
	steps[1] = 1 if 1 not in broken_steps else 0
	steps[2] = 2 if 2 not in broken_steps else 0

	for i in range(3, len(steps)):
		if i not in broken_steps:
			steps[i] = steps[i - 1] + steps[i - 2]
		else:
			steps[i] = 0

	return steps[-1] % (10**9 + 7)

if __name__ == '__main__':
	n, m = tuple(input().split())
	n = int(n)
	m = int(m)

	broken = set()
	for i in range(m):
		broken.add(int(input()))

	print(ways_to_climb(n, broken))

Submission status: Wrong Answer

Solution code:
import numpy as np
n, m = map(int, input().split())
stairs = set([int(input()) for i in range(m)])
ans = np.ones(n+1, dtype=int)
mod = 10**9 + 7
if 1 in stairs:
    ans[1] -= 1
for i in range(2, n+1):
    if i in stairs:
        ans[i] = 0
    else:
        ans[i] = ans[i-1] + ans[i-2]

print(int(ans[-1]) % mod)

Submission status: Wrong Answer

Solution code:
from math import factorial
def c(n,k):
  a = factorial(n) // factorial(k) // factorial(n - k)
  return a
def num(k): # k段昇る場合の数
  l = k // 2
  r = 0
  for i in range(l+1):
    e = k-2*i
    r += c(e+i,i)
    if r >= mod:
      r %= mod
  return r
n,m=map(int,input().split())
mod = 10**9+7
a=[int(input()) for i in range(m)]
if len(a)>1:
  sa = [a[i+1]-a[i] for i in range(m-1)]
  if min(sa)<=1:
    print(0)
    exit()
  ans=(num(a[0]-1) % mod) * (num(n-1-a[-1]) % mod)
  for i in sa:
    ans *= num(i-2) % mod
    ans %= mod
  print(ans)
  exit()
elif len(a) == 1:
  ans=(num(a[0]-1) % mod) * (num(n-1-a[0]) % mod)
  print(ans % mod)
else:
  ans = num(n) % mod

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
memo = {}
b = {}
for i in range(M):
  val = int(input())
  b[val] = True

for i in range(N+1):
  if i == 0:
    memo[i] = 0
    continue
  if i == 1:
    memo[i] = 1
    continue
  memo[i] = memo[i-1] + memo[i-2]
  
ans = memo[N]
print(ans % 1000000007)

Submission status: Wrong Answer

Solution code:
def main():
    mod = 1000000007
    N, M, *A = map(int, open(0).read().split())
    A = set(A)
    F = [0] * (N + 1)
    F[0] = 1
    if 1 in A:
        F[1] = 1
    for i in range(2, N + 1):
        if i not in A:
            F[i] = (F[i-1] + F[i-2]) % mod
    print(F[N])


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    mod = 1000000007
    N, M, *A = map(int, open(0).read().split())
    F = [0] * (N + 1)
    F[0] = 1
    if 1 in A:
        F[1] = 1
    for i in range(2, N + 1):
        if i not in A:
            F[i] = (F[i-1] + F[i-2]) % mod
    print(F[N])


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

fib=[1]*(N+1)
for i in range(2,N+1):
    fib[i]=fib[i-1]+fib[i-2]
fib.append(0)

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

Submission status: Wrong Answer

Solution code:
def main():
    N, M = map(int, input().split(" "))
    mod = 1000000007
    A = []
    for _ in range(M):
        A.append(int(input()))
    F = [0] * (N + 1)
    if 1 not in A:
        F[0] = 1
    if 2 not in A:
        F[1] = 1
    for i in range(2, N + 1):
        if i not in A:
            F[i] = (F[i-1] + F[i-2]) % mod
    print(F[-1])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
brokensteps = set([int(input()) for x in range(m)])
dp = [0] * (n+1)
for i in range(n+1):
    if i in brokensteps:
        dp[i] = 0
        continue
    
    elif i <= 1:
        dp[i] = 1

    else:
        dp[i] = (dp[i-1] + dp[i-2])%(10**9+7)

print(dp)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline


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

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

    for i in range(2, N+1):
        if i in a:
            dp[i] = 0
            continue


        dp[i] = dp[i-1] + dp[i-2]


    print(dp)

main()

Submission status: Wrong Answer

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

mod = 1000000007
brok = [False] * (n+1)

for i in a:
    brok[i] = True

dp = [1] * (n+2)

for i in range(n-1, -1, -1):
    if brok[i]:
        dp[i] = 0
        continue
    else:
        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 = [i for i in range(m)]

mod = 1000000007
brok= [False] * (n+1)

for i in a:
    brok[i] = True

dp = [1] * (n+2)
for i in range(0, n-1)[::-1]:
    if brok[i]:
        dp[i] = 0
        continue
    else:
        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 = [i for i in range(m)]

mod= 1000000007
oks = [True] * (n+1)
for i in a:
    oks[i] = False

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

for i in range(n):
    for j in range(i+1, min(n, i+2)):
        if oks[j]:
            dp[j] += dp[i]
            dp[j] %= mod

print(dp[n])

Submission status: Wrong Answer

Solution code:
import sys
def fb(num):
    a, b = 1, 0
    for _ in range(num):
        a, b = a + b, a
    return b

n,m = map(int,input().split())
broken = []
for i in range(m):
  broken.append(int(input()))
  if(len(broken) >= 2):
    if(broken[i] - broken[i-1] == 1):
      print("0")
      sys.exit()

ans = fb(n)//(2**m) % 1000000007 
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
def fb(num):
    a, b = 1, 0
    for _ in range(num):
        a, b = a + b, a
    return b

n,m = map(int,input().split())
broken = []
for i in range(m):
  broken.append(int(input()))
  if(len(broken) >= 2):
    if(broken[i] - broken[i-1] == 1):
      print("0")
      sys.exit()

ans = fb(n-m) % 1000000007 -1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
n,m = map(int,input().split())
broken = []
for i in range(m):
  broken.append(int(input()))
  if(len(broken) >= 2):
    if(broken[i] - broken[i-1] == 1):
      print("0")
      sys.exit()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

MOD = 1000000007


def main():
    n, m = [int(i) for i in input().split()]
    a = [int(input()) for _ in range(m)]
    steps = [0] * (n + 1)
    steps[0] = 1

    for now in range(n):
        for next_ in range(now + 1, min(now + 2, n) + 1):
            if next_ not in a:
                steps[next_] += steps[now] % MOD
    print(steps[-1])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
MOD = 1000000007

n, m = [int(i) for i in input().split()]
a = [int(input()) for _ in range(m)]
steps = [0] * (n + 1)
steps[0] = 1

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

Submission status: Wrong Answer

Solution code:
import numpy as np

n, m = map(int, input().strip().split())
array = [int(input()) for _ in range(m)]
is_broken = np.zeros(n + 1, dtype=np.bool)
for a in array:
    is_broken[a] = 1

a0 = 1
a1 = 1

if n == 1:
    if is_broken[n]:
        print(0)
    else:
        print(1)

else:
    for i in range(2, n + 1):
        if is_broken[i]:
            a2 = 0
        else:
            a2 = (a1 + a0) % 1000000007

        a0 = a1
        a1 = a2

    print(a1)

Submission status: Wrong Answer

Solution code:
import numpy as np

n, m = map(int, input().strip().split())
array = [int(input()) for _ in range(m)]
is_broken = np.zeros(n + 1, dtype=np.bool)
for a in array:
    is_broken[a] = 1

a0 = 1
a1 = 1

if n == 1:
    if is_broken[n]:
        print(0)
    else:
        print(1)

else:
    for i in range(2, n + 1):
        if is_broken[i]:
            a2 = 0
        else:
            a2 = (a1 + a0) % 1000000007

        a0 = a1
        a1 = a2

print(a1)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

if M > 0:
  A = []
  for i in range(M):
    A.append(int(input()))

  A.sort()
  ida = 0
  a = A[ida]
  if a == 1:
    ida += 1
    if M >= 2:
      a = A[ida]
  else:
    x[1] = 1

  for i in range(2, N+1):
    if i == a:
      ida += 1
      if ida >= M:
        a = N+1
      else:
        a = A[ida]

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

print(x[N])

Submission status: Wrong Answer

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

if M > 0:
  A = []
  for i in range(M):
    A.append(int(input()))

  A.sort()
  ida = 0
  a = A[ida]
  if a == 1:
    ida += 1
    if M >= 2:
      a = A[ida]
    else:
      x[1] = 1

  for i in range(2, N+1):
    if i == a:
      ida += 1
      if ida >= M:
        a = N+1
      else:
        a = A[ida]

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

print(x[N])

Submission status: Wrong Answer

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

# 壊れた階段の位置
a=[]
for _ in range(M):
    a.append(int(input()))
    
dp=[0]*(N+1)
dp[0]=1

# dp[i+1] : 壊れた階段を踏まずに i 段目に到達する方法の総数
for i in range(1,N):
    if i in a:
        dp[i+1]=0
        continue
    elif (i-1) not in a:
        dp[i+1] = max(dp[i+1], dp[i]+dp[i-1])
    elif (i-1) in a and (i-2) not in a:
        dp[i+1] = max(dp[i+1], dp[i-1])


print(dp[N]%100000007)
print(dp)

Submission status: Wrong Answer

Solution code:
N, M=map(int, input().split())
mod=10**9+7
dp=[0 for i in range(N+1)]
dp[N] = 1
is_broken =[False for i in range(N+1)]

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

for i in reversed(range(N)):
    if is_broken[i]:
        dp[i] = 0
        continue
    dp[i] = (dp[i+1] + dp[i+1]) % mod

print(dp[0])

Submission status: Wrong Answer

Solution code:
N, M=map(int, input().split())
items=[int(input()) for i in range(M)]
mod=10**9+7
dp=[0 for i in range(N+1)]
dp[N] = 1
is_broken =[1 for i in range(N+1)]

for i in range(M):
    is_broken[items[i]] = 0

for i in reversed(range(N)):
    if is_broken[i]:
        dp[i] = 0
        continue
    dp[i] = (dp[i+1] + dp[i+1]) % mod

print(dp[0])

Submission status: Wrong Answer

Solution code:
N, M=map(int, input().split())
items=[int(input()) for i in range(M)]
mod=10**9+7
dp=[0 for i in range(N+1)]
dp[0] = 1
is_broken =[1 for i in range(N+1)]

for i in range(M):
    is_broken[items[i]] = 0

for i in reversed(range(N)):
    if is_broken[i]:
        dp[i] = 0
        continue
    dp[i] = (dp[i+1] + dp[i+1]) % mod

print(dp[0])

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc129/tasks/abc129_c
# 典型的なDP

MOD = 10**9 + 7

# dp[i]をi段目までの通りの数とする。
N, M = list(map(int, input().split()))
to_zero = [False] * (N + 1)
for _ in range(M):
    to_zero[int(input())] = True  # 床が抜けているところ

# dpテーブルの用意
dp = [-1] * (N + 1)
dp[0] = 1
dp[1] = 1
for i in range(2, N + 1):
    dp[i] = dp[i - 1] + dp[i - 2]
    if to_zero[i]:
        dp[i] = 0

    if dp[i] > MOD:
        dp[i] %= MOD

print(dp[-1])

Submission status: Wrong Answer

Solution code:
def examC():
    N, M = LI()
    A = [I() for _ in range(M)]
    A.append(N+1)
    fib = [1]*(N+2)
    for i in range(1,N):
        fib[i+2] = fib[i+1] + fib[i]
    fib[0] = 0
#    print(fib)
    ans = fib[A[0]]
    for i in range(M):
        ans *= fib[A[i+1]-A[i]-1]
        ans %=mod
    print(ans)
    return

def examD():
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,inf
mod = 10**9 + 7
inf = float('inf')

if __name__ == '__main__':
    examC()

Submission status: Wrong Answer

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

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

    if ans[0] != 0 and ans[1] != 0:
        ans[0] = 1
        ans[1] = 2

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

Submission status: Wrong Answer

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

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

    if ans[0] != 0 and ans[1] != 0:
        ans[0] = 1
        ans[1] = 2

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys

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

if M != 0:
    A = int(input())
    n = 1
else:
    A = 0

dp = [0]*(N+1)
if N == 1:
    if 1 == A:
        print('0')
        sys.exit()
    else:
        print('1')
        sys.exit()
if 1 == A:
    dp[1] = 0
    if M == 0 and M != n:
        A = int(input())
        n += 1
else:
    dp[1] = 1
dp[0] = 1
for i in range(2, N+1):
    if i == A:
        dp[i] = 0
        if M == 0 and M != n:
            A = int(input())
            n += 1
    else:
        dp[i] = dp[i-1]%1000000007 + dp[i-2]%1000000007

print(dp[N]%1000000007)

Submission status: Wrong Answer

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

dp = [0] * (N+1)
#どうやってもスタート地点から始まるから、0に行く方法は1通りのみ
dp[0] = 1

#1が壊れていなければ1に行く方法は0->1の1通りのみ
if 1 in a:
    dp[1] = 1
    not_broken_stairs = set(range(2, N+1)) - set(a)
else:
    not_broken_stairs = set(range(1, N+1)) - set(a)    

#i=2or3から始まる。
#１が壊れていなければ2に行く方法は(0->2の1通り)+(1->2の1通り)で2通り。
for i in not_broken_stairs:
    dp[i] = dp[i-2] + dp[i-1]
    
print(dp[-1] % (10 ** 9 + 7))

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
ans = 1
bool = 0
broken = []
for i in range(M):
  K = int(input())
  broken.append(K)
broken.append(N+1)
dp = [-1]*(N+1)
for i in range(len(broken)-1):
  if broken[i+1] - broken[i] == 1:
    print(0)
    bool = 1
  break
  dp[broken[i]] = 0
if bool == 0:
  
  dp[0]= 1
  dp[1]= 1
  for k in range(1,N+1):
    if k == 1:
      if k in broken:
        dp[k] = 0
      else:
        dp[1] = 1
    else:
      if dp[k]==0:
        continue
      else:
        dp[k] = dp[k-2]+dp[k-1]
  print(dp[N]%(10**9+7))

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
ans = 1
bool = 0
broken = []
for i in range(M):
  K = int(input())
  broken.append(K)
broken.append(N+1)
dp = [-1]*(N+1)
dp[0]= 1
dp[1]= 1
for i in range(len(broken)-1):
  if broken[i+1] - broken[i] == 1:
    print(0)
    bool = 1
  dp[broken[i]] = 0
if bool == 0:
  for k in range(1,N+1):
    if k == 1:
      if k in broken:
        dp[k] = 0
      else:
        dp[1] = 1
    else:
      if dp[k]==0:
        continue
      else:
        dp[k] = dp[k-2]+dp[k-1]
  print(dp[N]%(10**9+7))

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
ans = 1
bool = 0
broken = []
for i in range(M):
  K = int(input())
  broken.append(K)
broken.append(N+1)
dp = [-1]*(N+1)
for i in range(len(broken)-1):
  if broken[i+1] - broken[i] == 1:
    print(0)
    bool = 1
  dp[broken[i]] = 0
if bool == 0:
  
  dp[0]= 1
  dp[1]= 1
  for k in range(1,N+1):
    if k == 1:
      if k in broken:
        dp[k] = 0
      else:
        dp[1] = 1
    else:
      if dp[k]==0:
        continue
      else:
        dp[k] = dp[k-2]+dp[k-1]
  print(dp[N]%(10**9+7))

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
ans = 1
bool = 0
broken = [-1]
for i in range(M):
  K = int(input())
  broken.append(K)
broken.append(N+1)
for i in range(len(broken)-1):
  if broken[i+1] - broken[i] == 1:
    print(0)
    bool = 1
if bool == 0:
  dp = [0]*(N+1)
  dp[0]= 1
  dp[1]= 1
  for k in range(1,N+1):
    if k == 1:
      if k in broken:
        dp[k] = 0
      else:
        dp[1] = 1
    else:
      if k in broken:
        dp[k] = 0
      else:
        dp[k] = dp[k-2]+dp[k-1]
  print(dp[N]%(10**9+7))

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
ans = 1
bool = 0
broken = [-1]
for i in range(M):
  K = int(input())
  broken.append(K)
broken.append(N+1)
for i in range(len(broken)-1):
  if broken[i+1] - broken[i] == 1:
    print(ans)
    bool = 1
if bool == 0:
  dp = [0]*(N+1)
  dp[0]= 1
  dp[1]= 1
  for k in range(1,N+1):
    if k == 1:
      if k in broken:
        dp[k] = 0
      else:
        dp[1] = 1
    else:
      if k in broken:
        dp[k] = 0
      else:
        dp[k] = dp[k-2]+dp[k-1]
  print(dp[N]%(10**9+7))

Submission status: Wrong Answer

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

dp[0]=0
dp[1]=1
for i in range(m):
    dp[t[i]-1]=0


for i in range(3,n):
    if dp[i]!=0:
        dp[i]=dp[i-1]+dp[i-2]
print(dp[-2])

Submission status: Wrong Answer

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

dp = [0] * (n + 10)
dp[0] = 1
mod = 1e9 + 7

ok = [1] * (n + 10)
for i in a:
    ok[i] = 0

for i in range(n):
    if ok[i + 1]:
        dp[i + 1] += dp[i]
        dp[i + 1] %= mod
    if ok[i + 2]:
        dp[i + 2] += dp[i]
        dp[i + 2] %= mod
print(dp[n])

Submission status: Wrong Answer

Solution code:
import sys
from functools import reduce

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

l = [0]
for i in range(m):
    l.append(int(input()))
    if l[i] - l[i - 1] == 1:
        sys.exit()
else:
    l.append(n)


result = []

for j in range(len(l)-1):

    z = l[j+1]-l[j]
    dp = [1, 1]

    for i in range(2, z):
        dp.append( dp[i - 1] + dp[i - 2])
    else:
        result.append(dp[-1])

        
result = reduce(lambda x,y:x * y,result)

print(result%1000000007)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
p = {int(input()) for _ in range(m)}
s = 10 ** 9 + 7

dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1
if 1 in p:
    dp[1] = 0

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

Submission status: Wrong Answer

Solution code:
import sys
def input():
  return sys.stdin.readline().rstrip()
mod = 10**9 + 7
n, m = [int(i) for i in input().split()]
a = [int(input()) for _ in range(m)]
notin = [1] * n
for i in a:
  notin[i] = 0
dp = [0] * n
dp[n - 1] = 1
dp[n - 2] = 1 + notin[n - 1]
for i in range(n - 3, -1, -1):
  dp[i] += dp[i + 1] * notin[i + 1] % mod
  dp[i] += dp[i + 2] * notin[i + 2] % mod
  dp[i] %= mod
print(dp[0])