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())
l = {int(input()) for _ in range(m)}
p = 10**9+7
f = [0] * (n + 1)
f[0], f[1] = 1, 0 if 1 in l else 1
for i in range(1, n+1):
    if not i in l:
        f[i] = (f[i - 1] + f[i - 2]) % p

print(f[n])

Submission status: Wrong Answer

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

#`dp[i] = i段目にいる通り数`
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]) % (10 ** 9 + 7)

print(dp[-1])

Submission status: Wrong Answer

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

#`dp[i] = i段目にいる通り数`
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]) % (10 ** 9 + 7)

print(dp[-1])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
def www(N,l):
  return True if N in l else False

N,M =map(int,input().rstrip().split(" "))
ans = [0 for _ in range(N + 3)]
ans[0] = 1
m = []
mc = 0
flag = True
for _ in range(M):
  m.append(int(input()))
  if m[len(m) - 1] == m[len(m) -2] + 1:
    print(0)
    flag = False
m.append(0)
if flag:
  for i in range(0,N + 1):
    if www(i + 1,m) == False:
      ans[i + 1] += ans[i]
      ans[i + 1] %= 1000000007
    if www(i + 2,m) == False:
      ans[i + 2] += ans[i]
      ans[i + 2] %= 1000000007
print(ans[N])

Submission status: Wrong Answer

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

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

if M == 0:
    arr = [N]
else:
    arr = [a[0] - 1]
    for i in range(M-1):
        diff = a[i+1] - a[i] - 1
        arr.append(diff)
        if diff == 0:
            print(0)
            exit()
    arr.append(N - a[-1] - 1)

count = [1, 1, 2]
for i in range(3, max(arr)+1):
    count.append(count[-1] + count[-2])

ans = 1
for value in arr:
    ans *= count[value]
    
print(ans%1000000007)

Submission status: Wrong Answer

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

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

if M == 0:
    arr = [N]
else:
    arr = [a[0] - 1]
    for i in range(M-1):
        diff = a[i+1] - a[i] - 1
        arr.append(diff)
        if diff == 0:
            print(0)
            exit()
    arr.append(N - a[-1] - 1)

count = [1, 1, 2]
for i in range(3, max(arr)+1):
    count.append(count[-1] + count[-2])

ans = 1
for value in arr:
    ans *= count[value]
    ans = ans % 1000000007

print(ans)

Submission status: Wrong Answer

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

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

if M == 0:
    arr = [N]
else:
    arr = [a[0] - 1]
    for i in range(M-1):
        print(a[i], a[i+1])
        diff = a[i+1] - a[i] - 1
        arr.append(diff)
        if diff == 0:
            print(0)
            exit()
    arr.append(N - a[-1] - 1)

count = [1, 1, 2]
for i in range(3, max(arr)+1):
    count.append(count[-1] + count[-2])

ans = 1
for value in arr:
    ans *= count[value]
    ans = ans % 1000000007

print(ans)

Submission status: Wrong Answer

Solution code:
def count_section_by_zero(data):
  count = 0
  flg = False
  start = 0
  for i, d in enumerate(data):
    if flg is False and d != 0:
      count += 1
      flg = True
      
    if d == 0:
      flg = False
  return count

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

def input_list_str():
  return list(map(str, input().split()))

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

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

# 2で割り切れる回数
def divide_two(arg):
  c = 0
  while True:
    if c >= 2:
      break
    if arg % 2 != 0:
      break
    arg //= 2
    c += 1
  return c

# 素因数分解
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

def main():
  n, m = input_list()
  falls = [False]*(n+1)
  for i in range(m):
    falls[int(input())] = True
  
  if n == 1:
    print(1)
    exit(0)

  dp = [0]*(n+1)
  dp[0] = 1
  dp[1] = 1
  for i in range(2, n+1):
    if falls[i]:
      continue
    dp[i] = dp[i-1] + dp[i-2]
  
  mod = 1000000007
  print(dp[-1]%mod)
import math
import fractions
import collections
import itertools
from functools import reduce
main()

Submission status: Wrong Answer

Solution code:
def mi():
    return map(int, input().split())
'''
3 4
*G*S
G**S
*G*S
'''
n,m = mi()
b = [1]*(n+1)
for i in range(m):
    b[int(input())] = 0
dp = [0]*(n+1)
if b[1]==0:
    dp[1] = 0
dp[0] = 1
for i in range(2, n+1):
    if b[i-1] and b[i-2]:
        dp[i] = dp[i-1]+dp[i-2]
    elif b[i-1]:
        dp[i] = dp[i-1]
    elif b[i-2]:
        dp[i] = dp[i-2]
    else:
        print(0)
        exit()
print(dp[-1]%(10**9+7))

Submission status: Wrong Answer

Solution code:
def mi():
    return map(int, input().split())
'''
3 4
*G*S
G**S
*G*S
'''
n,m = mi()
b = [1]*(n+1)
for i in range(m):
    b[int(input())] = 0
dp = [0]*(n+1)
if b[1]==0:
    dp[1] = 0
dp[0] = 1
for i in range(2, n+1):
    if not b[i]:
        dp[i] = 0
        continue
    if b[i-1] and b[i-2]:
        dp[i] = dp[i-1]+dp[i-2]
    elif b[i-1]:
        dp[i] = dp[i-1]
    elif b[i-2]:
        dp[i] = dp[i-2]
    else:
        print(0)
        exit()
print(dp[-1]%(10**9+7))

Submission status: Wrong Answer

Solution code:
def mi():
    return map(int, input().split())
'''
3 4
*G*S
G**S
*G*S
'''
n,m = mi()
b = [1]*(n+1)
for i in range(m):
    b[int(input())] = 0
dp = [0]*(n+1)
if b[1]==0:
    dp[1] = 0
dp[0] = 1
for i in range(2, n+1):
    if not b[i]:
        dp[i] = 0
        continue
    if b[i-1] and b[i-2]:
        dp[i] = dp[i-1]+dp[i-2]
    elif b[i-1]:
        dp[i] = dp[i-1]
    elif b[i-2]:
        dp[i] = dp[i-2]
    else:
        print(i, b[i-1], b[i-2])
        print(0)
        exit()
print(dp[-1]%(10**9+7))

Submission status: Wrong Answer

Solution code:
def mi():
    return map(int, input().split())
'''
3 4
*G*S
G**S
*G*S
'''
n,m = mi()
b = [1]*(n+1)
for i in range(m):
    b[int(input())] = 0
dp = [0]*(n+1)
if b[1]==1:
    dp[1] = 1
dp[0] = 1
for i in range(2, n+1):
    if b[i-1] and b[i-2]:
        dp[i] = dp[i-1]+dp[i-2]
    elif b[i-1]:
        dp[i] = dp[i-1]
    elif b[i-2]:
        dp[i] = dp[i-2]
    else:
        print(i, b[i-1], b[i-2])
        print(0)
        exit()
print(dp[-1]%(10**9+7))

Submission status: Wrong Answer

Solution code:
def mi():
    return map(int, input().split())
'''
3 4
*G*S
G**S
*G*S
'''
n,m = mi()
b = [1]*(n+1)
for i in range(m):
    b[int(input())] = 0
dp = [0]*(n+1)
if b[1]==0:
    dp[1] = 1
dp[0] = 1
for i in range(2, n+1):
    if b[i-1] and b[i-2]:
        dp[i] = dp[i-1]+dp[i-2]
    elif b[i-1]:
        dp[i] = dp[i-1]
    elif b[i-2]:
        dp[i] = dp[i-2]
    else:
        print(i, b[i-1], b[i-2])
        print(0)
        exit()
print(dp[-1]%(10**9+7))

Submission status: Wrong Answer

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


MOD = 1000000007

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

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[-1] % MOD)

Submission status: Wrong Answer

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


MOD = 1000000007
print(MOD)

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

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[-1] % MOD)

Submission status: Wrong Answer

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

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

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[-1])

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
A=[]
for i in range(M):
    a=int(input())
    A.append(a)
DP=[0]*(1+N)
DP[0]=1
DP[1]=1
damage=[0]*(N+1)
kotae=0
for m in A:
    damage[m]=-1
if N==1:
    print(1)
elif N==2:
    print(1)
else:
    for a in range(2,N+1):
        if damage[a-1]==-1 and damage[a-2]==-1:
            print(0)
            kotae+=1
            break
        if damage[a]==-1:
            continue
        elif damage[a-1]==-1:
            DP[a]=DP[a-2]
        elif damage[a-2]==-1:
            DP[a]=DP[a-1]
        else:
            DP[a]=DP[a-2]+DP[a-1]
    if kotae==0:
        print(DP[-1]%(pow(10,9)+7))

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
A=[]
for i in range(M):
    a=int(input())
    A.append(a)
DP=[0]*(1+N)
damage=[0]*(N+1)
kotae=0
for m in A:
    damage[m]=-1
if N==1:
    print(1)
elif N==2:
    print(1)
else:
    for a in range(2,N+1):
        if damage[a-1]==-1 and damage[a-2]==-1:
            print(0)
            kotae+=1
            break
        elif damage[a-1]==-1:
            DP[a]=DP[a-2]
        elif damage[a-2]==-1:
            DP[a]=DP[a-1]
        else:
            DP[a]=DP[a-2]+2
    if kotae==0:
        print(DP[-1]%(pow(10,9)+7))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
mod = 10**9 +7
dp = [0]*(N+1)
dp[0] = 1
if len(A)>=1 and N>=1:
    if A[0]==1:
        dp[1]=0
    else:
        dp[1]=1
for i in range(2, N+1):
    if i not in A:
        dp[i] = (dp[i-1]+dp[i-2])%mod
print(dp[-1])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from collections import deque
N, M = map(int, input().split())
broken = [int(input())-1 for i in range(M)] #indexは0からなので、-1
broken = set(broken)

if 0 in broken:
    if 1 in broken:
        stairs=deque([0,0])
    else:
        stairs=deque([0,1])
else:
    if 1 in broken:
        stairs=deque([1,0])
    else:
        stairs=deque([1,2])

for i in range(2,N):
    if i in broken:
        stairs.append(0)
    else:
        stairs.append((stairs[i-1]+stairs[i-2])%(10**9 + 7))
print(stairs[-1])

Submission status: Wrong Answer

Solution code:
def hoge():
  dp = [0] * (n + 5)
  dp[0] = 0
  dp[1] = 2
  for i in range(2, n):
    if step_list[i - 1] == True:
      dp[i] = dp[i - 2] + dp[i - 1]
      dp[i] %= 1000000007
  return dp[n - 1]

def solve():
  global n, m, a_list, step_list
  n, m = map(int, input().split())
  a_list = [0] * m
  step_list = [True] * (n + 5)
  for i in range(m):
    a_list[i] = int(input())
    step_list[a_list[i]] = False
  ans = hoge()
  print(ans)
  return 0

if __name__ == "__main__":
  solve()

Submission status: Wrong Answer

Solution code:
def hoge():
  dp = [0] * (n + 5)
  dp[0] = 0
  dp[1] = 2
  for i in range(2, n):
    if step_list[i - 1] == True:
      dp[i] = dp[i - 2] + dp[i - 1]
  return dp[n - 1]

def solve():
  global n, m, a_list, step_list
  n, m = map(int, input().split())
  a_list = [0] * m
  step_list = [True] * (n + 5)
  for i in range(m):
    a_list[i] = int(input())
    step_list[a_list[i]] = False
  ans = hoge()
  print(ans % 1000000007)
  return 0

if __name__ == "__main__":
  solve()

Submission status: Wrong Answer

Solution code:
def hoge():
  dp = [0] * (n + 5)
  dp[0] = 0
  dp[1] = 2
  for i in range(2, n):
    if step_list[i - 1] == True:
      dp[i] = dp[i - 2] + dp[i - 1]
  print(step_list)
  print(dp)
  return dp[n - 1]

def solve():
  global n, m, a_list, step_list
  n, m = map(int, input().split())
  a_list = [0] * m
  step_list = [True] * (n + 5)
  for i in range(m):
    a_list[i] = int(input())
    step_list[a_list[i]] = False
  ans = hoge()
  print(ans % 1000000007)
  return 0

if __name__ == "__main__":
  solve()

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
l = [int(input())-1 for _ in range(m)]
res = [0, 1]
skip = 0

if m != 0:
  for i in range(n):
    if i == l[skip]:
      res[0] = res[1]
      res[1] = 0
      if skip < m-1:
        skip += 1
    else:
      tmp = res[1]
      res[1] += res[0]
      res[0] = tmp
      res[1] %= 10**9 + 7
      res[0] %= 10**9 + 7
else:
    tmp = res[1]
    res[1] += res[0]
    res[0] = tmp
    res[1] %= 10**9 + 7
    res[0] %= 10**9 + 7
      
print(res[1])

Submission status: Wrong Answer

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

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

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
dp[1]=1
for i in range(1,n+1):
    dp[i]=dp[i-2]+dp[i-1]
    if i in a:
        dp[i]=0
print(dp[n]%1000000007)

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
dp[1]=1
for i in range(1,n+1):
    if i in a:
        dp[i]=0
    elif i in a and i+1 in a:
        print(0)
        exit()
    else:
        dp[i]=dp[i-2]+dp[i-1]
print(dp[n]%1000000007)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
dp=[1]*(n+1)
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(dp[n])

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, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_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()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
break_step = [INT() for _ in range(M)] + [0]

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

index = 0
for i in range(1, N + 1):
	if break_step[index] == i:
		comb[i] = 0
		index += 1
	else:
		comb[i] = comb[i - 2] + comb[i - 1]

print(comb[N]%mod)

Submission status: Wrong Answer

Solution code:
def main():
  N, M= map(int, input().split())
  a =[str(input()) for _ in range(M)]
  DP = [0]*(N+1)
  num = 1000000007
  DP[0] = 1
  for i in range(N):
    if str(i) in a:
      DP[i] = (DP[i-1] + DP[i-2]) % num
  print(DP[-1]%num)
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
  N, M= map(int, input().split())
  a =[str(input()) for _ in range(M)]
  DP = [0]*(N+1)
  num = 1000000007
  DP[0] = 1
  for i in range(N):
    if str(i) in a:
      DP[i] = (DP[i-1] + DP[i-2]) % num
  print(DP[-2]%num)
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
if __name__ == "__main__":
    mod = 10 ** 9 + 7
    n, m = map(int, input().split())
    a = list()
    for i in range(m):
        a.append(int(input()))

    dp = [0] * (n + 1)

    step = list()
    for i in range(n):
        if i not in a and i > 2:
            step.append(i)

    if 1 not in a:
        dp[1] = 1

    if n > 1:
        if 2 not in a:
            dp[2] = 1 + dp[1]

        for i in step:
            dp[i] = (dp[i-2] + dp[i-1]) % mod

    print(dp[n])

Submission status: Wrong Answer

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

dp=[0]*(n+1)
dp[0]=1
for i in range(m):
    dp[a[i]]=-1

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

Submission status: Wrong Answer

Solution code:
a=open(0)
N,_,*a = map(int, a.read().split())

l,m = [0,0]
for i in range(1, N+1):
    if i in a:
        l,m = m,0
    elif i<3:
        l,m = m,m+1
    else:
        l,m = m,l+m
print(m)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

N,M = list(map(int, input().rstrip().split()))
a_list = [int(input().strip()) for _ in range(M)]
#-----

step = ["x",1,2] + ["x"]*(N-2)

for i in a_list:
    step[i] = 0


for i in range(3,N+1):
    if step[i] == "x":
        step[i] = ( step[i-1] + step[i-2] ) % (10**9 + 7)

print(step[-1])

Submission status: Wrong Answer

Solution code:
import sys
from functools import lru_cache
sys.setrecursionlimit(1000000)
read=sys.stdin.read
N,M,*alst=map(int,read().split())
mod=10**9+7
dp = [1, 1 if 1 not in alst else 0]
@lru_cache(maxsize=None)
def a(n):
  if n==0:
    return dp[0]
  elif n==1:
    return dp[1]
  else:
    if n not in alst:
      return (a(n-2)+a(n-1))%mod
    else:
      return 0
print(a(100))

Submission status: Wrong Answer

Solution code:
def main():
    n, m = map(int,input().split())
    a = [0] * m
    for i in range(m):
        a[i] = int(input())
    ans = [0] * (n+1)
    head = 0
    MOD = 10**9 + 7
    ans[0] = 1
    for i in range(1,n+1):
        print(head,i)
        if head < m and a[head] == i:
            ans[i] = 0
            head += 1
        else:
            if i == 1:
                ans[i] = 1
            else:
                print(i,i-1,i-2)
                ans[i] = (ans[i-1] + ans[i-2]) % MOD

    print(ans[n] % MOD)



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
a = []
ans = 1
for _ in range(m):
    a.append(int(input()))
mod = 10**9 + 7
p = 0
for i in range(m):
    print(p)
    if i == m-1:
        ans *= n - a[i] - 1
        # print('Y')
        break
    if a[i] == 1:
        if a[i+1] == 2:
            ans *= 0
        else:
            pass
    else:
        if a[i] == a[i+1] - 1:
            ans *= 0
        else:
            ans *= a[i] - p - 1
            p = a[i]

print(ans % mod)

Submission status: Wrong Answer

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

ways = [0] * 3
ways[1] = 0 if 1 in a else 1
ways[2] = ways[1] + 0 if 2 in a else ways[1] + 1
for i in range(3, n+1):
    if i in a:
        ways.append(0)
    else:
        ways.append((ways[-2]+ways[-1])%(10**9+7))

print(ways[n])

Submission status: Wrong Answer

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

ways_prev = 0 if 1 in a else 1
ways_i = ways_prev + 0 if 2 in a else ways_prev + 1
for i in range(3, n+1):
    ways_prev, ways_i = ways_i, (ways_prev+ways_i)%(10**9+7)
    ways_i = 0 if i in a else ways_i
else:
    print(ways_i)

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
mod = 10**9+7

#フィボナッチ数列
dp = [0 for i in range(n+2)]
dp[0] = 1
dp[1] = 1
for i in range(2,n+2):
    dp[i] = dp[i-1] + dp[i-2]

#穴が無い場合
if m==0:
    print(dp[n])
    exit()

lst = []
for i in range(m):
    lst.append(int(input()))
lst.sort()

#2連続穴がある場合
for i in range(len(lst)-1):
    if lst[i]+1 == lst[i+1]:
        print(0)
        exit()

lst2 = []
for i in range(len(lst)):
    if i==0:
        lst2.append(lst[0]-1)
    else:
        lst2.append(lst[i]-lst[i-1]-2)
lst2.append(n-lst[-1]-1)

ans = 1
for i in lst2:
    ans *= dp[i]
    ans %= mod

# print(lst)
# print(lst2)
print(ans)

Submission status: Wrong Answer

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


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


mod = 10**9 + 7
dp = [0] * (N)
dp[0] = (1 if a[0] else 0)

if N == 1:
    print(dp[0])
    exit(0)

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

print(dp[N-1])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
def nCr(n, r):
    ans = 1
    for i in range(n,n-r,-1):
        ans = ans * i
    for i in range(1, r+1):
        ans = ans // i
    return ans

def count(n):
    if n == -1:
        return 0
    elif n == 0:
        return 1
    else:
        tmp = 0
        if n % 2 == 0:
            num = n // 2 + 1
        else:
            num = n // 2
        for i in range(num): #2歩で行く回数
            k = n - i #合計の歩数
            tmp += nCr(k, i)
        return tmp

N, M = list(map(int, input().split()))
a = []
current = 0
res = 1
for i in range(M):
    a = int(input())
    a_prev = a-1
    a_next = a+1
    leng = a_prev - current
    res = (res*count(leng))%(1e9+7)
    current = a_next

leng = N - current
res =(res*count(leng)) % (1e9+7)
print(int(res))

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
p = 1000000007
dp = [0] * n
c = 0
for _ in range(m):
    a = int(input())
    dp[a - 1] = -1
for i in range(1, n):
    if i <= 1:
        if dp[0] != -1 and dp[1] != -1:
            dp[0], dp[1] = 1, 2
        elif dp[0] == -1 and dp[1] != -1:
            dp[0], dp[1] = 0, 1
        elif dp[0] != -1 and dp[1] == -1:
            dp[0], dp[1] = 1, 0
        else:
            c = -1
    if i >= 2 and dp[i] != -1:
        if dp[i - 1] == -1 and dp[i - 2] != -1:
            dp[i] = dp[i - 2]
        elif dp[i - 1] != -1 and dp[i - 2] == -1:
            dp[i] = dp[i - 1]
        elif dp[i - 1] != -1 and dp[i - 2] != -1:
            dp[i] = (dp[i - 1] + dp[i - 2]) % p
        else:
            c = -1
if c == -1:
    print(0)
else:
    print(dp[n - 1])

Submission status: Wrong Answer

Solution code:
import sys

N, M = map(int, input().split())
A = []

for m in range(M):
  if m == 0:
    A.append(int(input()))
    continue

  i = int(input())
  if A[-1] == i-1:
    print(0)
    sys.exit()

  A.append(i)

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

for n in range(1, N+1):
  if n in A or n == 1:
    continue

  li[n] = li[n-1] + li[n-2]

print(li[-1] % (10**9 + 7))

Submission status: Wrong Answer

Solution code:
CONST = 10**9 + 7
n,m = map(int,input().split())

dp = [-1 for _ in range(n+1)]
dp[0] = 1
dp[1] = 2
for _ in range(m):
  a = int(input())
  dp[a] = 0
  if a == 0 and  dp[1] ==2:
    dp[1] = 1

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

Submission status: Wrong Answer

Solution code:
N, M = map(int,input().split())
a = [int(input()) for o in range(M)]
p = 10**9 + 7
a.insert(0, -1)
a.append(N+1)

def mod(n,p):
    return n % p

nk = [1]
for i in range(1,N+1):
    nk.append(mod((nk[-1] * i), p))

#ある数をAで割ったとき，その数をpで割ったときの余りを求めるのにかけるべき数を返す
def bunbo(A, p): 
    # p-2を2進数にする
    pp = p-2
    pb = list(str(format(pp, 'b')))
    # ひっくりかえす
    pb.reverse()
    # pbの要素の数lとして，A^1, A^2, A^4, A^8, ..., A^(2^l)をpで割った余りを求める
    lpp = [mod(A,p)]
    for _ in range(len(pb)-1):
        lpp.append(mod((lpp[-1] ** 2), p))
    # 必要なやつだけ足して，x=(A^(p-2)をpで割った余り)を求める
    x = 1
    for i in range(len(pb)):
        if pb[i] == '1':
            x *= lpp[i]
    return mod(x, p)
    
def nckp(a, b, c, p):
    # 0!, 1!, 2!, 3!, ..., n!をリストに入れる
    return mod((a * bunbo(b, p) * bunbo(c, p)),p)



for i in range(M-2):
    if a[i+1] - a[i] == 1:
        print(0)
        break
else:
    ans = 1
    for j in range(len(a)-1):
        if a[j] != N:
            up = a[j+1] - a[j] - 2
            step = 0
            for l in range(up//2 + 1):
                way = nckp(nk[up-l], nk[l], nk[up-2*l], p)
                step += way
            ans *= step
    print(ans)

Submission status: Wrong Answer

Solution code:
def mod(n,p):
    return n % p
#ある数をAで割ったとき，その数をpで割ったときの余りを求めるのにかけるべき数を返す
def bunbo(A, p): 
    # p-2を2進数にする
    pp = p-2
    pb = list(str(format(pp, 'b')))
    # ひっくりかえす
    pb.reverse()
    # pbの要素の数lとして，A^1, A^2, A^4, A^8, ..., A^(2^l)をpで割った余りを求める
    lpp = [mod(A,p)]
    for _ in range(len(pb)-1):
        lpp.append(mod((lpp[-1] ** 2), p))
    # 必要なやつだけ足して，x=(A^(p-2)をpで割った余り)を求める
    x = 1
    for i in range(len(pb)):
        if pb[i] == '1':
            x *= lpp[i]
    return mod(x, p)
    
def nckp(n, k, p):
    # 0!, 1!, 2!, 3!, ..., n!をリストに入れる
    nk = [1]
    for i in range(1,N+1):
        nk.append(mod((nk[-1] * i), p))
    return mod((nk[n] * bunbo(nk[k], p) * bunbo(nk[n-k], p)),p)

N, M = map(int,input().split())
a = [int(input()) for o in range(M)]
p = 10**9 + 7
a.insert(0, -1)
a.append(N+1)
for i in range(M-1):
    if a[i+1] - a[i] == 1:
        print(0)
        break
else:
    ans = 1
    for j in range(len(a)-1):
        up = a[j+1] - a[j] - 2
        step = 0
        for l in range(up//2 + 1):
            way = nckp(up-l, l, p)
            step += way
        ans *= step
    print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
a = []
mod = 10 ** 9 + 7
for _ 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:
        continue
    else:
        dp[i] = dp[i - 1] + dp[i - 2]
print(dp[-1] % mod)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

INF=-float("inf")

n,m=mii()

arr=lin(m)

dp=[0]*(n+1)

for i in arr:
    dp[i]=INF

if dp[1]!=INF:
    dp[1]=1

if dp[1]==INF and dp[2]!=INF:
    dp[2]=1

if dp[1]==INF and dp[2]==INF:
    print(0)
    exit()
    

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

print(dp[-1]%mod)

Submission status: Wrong Answer

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

x=[0]*(n+1)
x[0]=1
if 1 in A:
    x[1]=0
else:
    x[1]=1

for j in range(2,n+1):
    if j in A:
        x[j]=0
    else:
        x[j]=x[j-1]+x[j-2]
        x[j]%1000000007

print(x[n])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n, m = list(map(int, input().split(' ')))
aaa = [0] * (n + 3)
for i in range(m):
    aaa[int(input())] = True

dp = [1] * (n + 3)
for i in range(1, n+1):  # 1e5
    if not aaa[i]:
        dp[i]  = dp[i-1]
        dp[i] += dp[i-2]
        dp[i] = dp[i] % int(1e9 + 7)
    else:
        dp[i] = 0
print(dp[n])

Submission status: Wrong Answer

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

if N == 1:
    if M == 0:
        print(1)
    elif M == 1:
        print(0)
else:
    cost = [0 for _ in range(N + 1)]
    cost[0] = 1
    if 1 in A:
        cost[1] = 0
    else:
        cost[1] = 1
    cost[2] = cost[0] + cost[1]

    cnt = 0
    A.append([0])
    for i in range(1, N + 1):
        if i == A[cnt]:
            cost[i] = 0
            cnt += 1
        else:
            cost[i] = (cost[i - 1] + cost[i - 2]) % q

    print(cost[-1])

Submission status: Wrong Answer

Solution code:
import numpy as np

N, M = map(int, input().split())
A = np.array([int(input()) for _ in range(M)])
q = 1000000007

if N == 1:
    if M == 0:
        print(1)
    elif M == 1:
        print(0)
    else:
        cost = np.zeros(N + 1, dtype=np.int64)
        cost[0] = 1
        cost[1] = 1
        cost[A] = 0
        cost[2] = cost[0] + cost[1]

        for i in range(1, N + 1):
            cost[A] = 0
            cost[i] = (cost[i - 1] + cost[i - 2]) % q

        print(cost[-1] % q)