Problem: 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.

Submission attempts (in order):
N,M = (int(i) for i in input().split())
a = [int(input()) for i in range(M)]
hoge = [0] * N
hoge[0] = 1
for i in range(N):
    if i == 0 and (i+1) not in a:
        hoge[i] = 1
    elif i == 1 and (i+2) not in a:
        hoge[i] = hoge[i-1] + 1
    elif i + 1 in a:
        hoge[i] = 0
    elif i in a and (i-1) in a:
        hoge[i] = 0
    elif i in a:
        hoge[i] = hoge[i - 2]
    elif (i-1) in a:
        hoge[i] = hoge[i - 1]
    else:
        hoge[i] = hoge[i-1] + hoge[i-2]
        hoge[i] = hoge[i] % (10**9 + 7)
print(hoge[N-1] % (10**9 + 7))



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

for i in range(2,N):
    if i + 1 not in a:
        hoge[i] = 0
        if i not in a:
            hoge[i] += hoge[i - 1]
        elif (i-1) not in a:
            hoge[i] += hoge[i - 2]

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

N,M = (int(i) for i in input().split())
a = [int(input()) for i in range(M)]
hoge = [0] * N
hoge[0] = 1
for i in range(N):
    if i = 0:
        hoge[i] = 0
    elif (i-1) in a and (i-2) in a:
        hoge[i] = 0
    elif (i-1) in a:
        hoge[i] = hoge[i - 2]
    elif (i-2) in a:
        hoge[i] = hoge[i - 1]
    else hoge[i] = hoge[i-1] + hoge[i-2]
print(hoge[N])

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

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

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

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

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

for i in range(2,N):
    if i + 1  not in a:
        if i not in a:
            hoge[i] += hoge[i - 1]
        elif (i-1) not in a:
            hoge[i] += hoge[i - 2]

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

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

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

for i in range(2,N):
    if i + 1  in a:
        hoge[i] = 0
        if i not in a:
            hoge[i] += hoge[i - 1]
        elif (i-1) not in a:
            hoge[i] += hoge[i - 2]

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

N,M = (int(i) for i in input().split())
a = set([int(input()) for i in range(M)])
hoge = [0] * N
if 1 not in a:
    hoge[0] = 1
if 2 not in a and N >= 2:
    hoge[1] = hoge[0] + 1

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

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


Verdicts: Wrong Answer

Wrong Answer

Runtime Error

Wrong Answer

Wrong Answer

Wrong Answer

Wrong Answer

Wrong Answer

Accepted