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())
mod=10**9+7
pre=-1
hole=[]
for i in range(M):
  a=int(input())
  hole.append(a-1-pre)
  pre=a
hole.append(N-pre)

  

dp=[0]*(N+3)
dp[1]=1
dp[2]=1
for i in range(3,N+3):
  dp[i]=(dp[i-1]+dp[i-2])%mod
if len(hole)==1:
  print(dp[N])
  
#print(dp)
#print(hole)
ans=1
for h in hole:
  ans*=dp[h]
  ans%=mod
  
print(ans)

Submission status: Wrong Answer

Solution code:
from functools import lru_cache

def main():
    n,m = map(int,input().split())
    A = []
    for _ in range(m):
        a = int(input())
        A.append(a)
    mod = 10**9+7
    if 1 in A:
        ans = [1,0]
    else:
        ans = [1,1]
    for i in range(2,n):
        if i in A:
            ans.append(0)
        else:
            ans.append((ans[i-1]+ans[i-2])%mod)
    print((ans[-1]+ans[-2])%mod)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def fib(n, broken):
    a = 1
    b = 1
    for i in range(n-2):
        # if i in broken:

        a, b = b, a + b
    print(b)


# t = int(input())
t = 1

for _ in range(t):
    n, m = [int(x) for x in input().split()]
    broken = set()
    for _ in range(m):
        broken.add(int(input()))

    x = 0
    y = 1
    i = 1
    impossible = False
    c = 0
    while i <= n:
        # print(f'degrau: {i}')
        # print(f'main loop: i: {i}')
        if i in broken:
            # print('broken')
            x = y
            if i + 1 in broken:
                impossible = True
                break
            while not ((i + 1) not in broken and (i + 2) not in broken and (i + 3) not in broken):
                c = 0
                for x in range(i+1, i+4):
                    if x in broken:
                        c += 1
                if c >= 2:
                    impossible = True
                i += 1
            i += 2
            # while True:
            #     print('entrei')

            #     if not ((i + 1) not in broken and (i + 2) not in broken and (i + 3) not in broken):
            #         print('aqui')

            #         i += 1
            #         print(f'i: {i}')
            #         break
            #     i += 3
            #     break

            #     c = 0
            #     for x in range(i + 1, i + 4):
            #         if x in broken:
            #             c += 1
            #     if c >= 2:
            #         impossible = True

            #     print(f'i: {i}')
            # if i + 1 not in broken and i + 2 not in broken and i + 3 not in broken:
            #     i += 1

            # print('broken')
            # x = y
            # # y = x
            # print(f'x: {x}, y: {y}')
            # previous_broken = False
            # while i not in broken and (i + 1) not in broken and (i + 2) not in broken:
            #     i += 1
            # while c < 2:
            #     i += 1
            #     if i in broken:
            #         if previous_broken:
            #             impossible = True
            #         previous_broken = True
            #         continue
            #     else:
            #         previous_broken = False
            #         c += 1
            # i += 2
            # c = 0
        else:
            y, x = (x + y) % 1000000007, y % 1000000007
            # print(f'x: {x}, y: {y}')
            c = 0
        i += 1
        # print(y)
    print(0) if impossible else print(y % 1000000007)

Submission status: Wrong Answer

Solution code:
def fib(n, broken):
    a = 1
    b = 1
    for i in range(n-2):
        # if i in broken:

        a, b = b, a + b
    print(b)


# t = int(input())
t = 1

for _ in range(t):
    n, m = [int(x) for x in input().split()]
    broken = set()
    for _ in range(m):
        broken.add(int(input()))

    x = 0
    y = 1
    i = 1
    impossible = False
    c = 0
    while i <= n:
        # print(f'degrau: {i}')
        # print(f'main loop: i: {i}')
        if i in broken:
            # print('broken')
            x = y
            if i + 1 in broken:
                impossible = True
                break
            while not ((i + 1) not in broken and (i + 2) not in broken and (i + 3) not in broken):
                i += 1
            i += 2
            # while True:
            #     print('entrei')

            #     if not ((i + 1) not in broken and (i + 2) not in broken and (i + 3) not in broken):
            #         print('aqui')

            #         i += 1
            #         print(f'i: {i}')
            #         break
            #     i += 3
            #     break

            #     c = 0
            #     for x in range(i + 1, i + 4):
            #         if x in broken:
            #             c += 1
            #     if c >= 2:
            #         impossible = True

            #     print(f'i: {i}')
            # if i + 1 not in broken and i + 2 not in broken and i + 3 not in broken:
            #     i += 1

            # print('broken')
            # x = y
            # # y = x
            # print(f'x: {x}, y: {y}')
            # previous_broken = False
            # while i not in broken and (i + 1) not in broken and (i + 2) not in broken:
            #     i += 1
            # while c < 2:
            #     i += 1
            #     if i in broken:
            #         if previous_broken:
            #             impossible = True
            #         previous_broken = True
            #         continue
            #     else:
            #         previous_broken = False
            #         c += 1
            # i += 2
            # c = 0
        else:
            y, x = (x + y) % 1000000007, y % 1000000007
            # print(f'x: {x}, y: {y}')
            c = 0
        i += 1
        # print(y)
    print(0) if impossible else print(y % 1000000007)

Submission status: Wrong Answer

Solution code:
def fib(n, broken):
    a = 1
    b = 1
    for i in range(n-2):
        # if i in broken:

        a, b = b, a + b
    print(b)


# t = int(input())
t = 1

for _ in range(t):
    n, m = [int(x) for x in input().split()]
    broken = set()
    for _ in range(m):
        broken.add(int(input()))

    x = 0
    y = 1
    i = 1
    impossible = False
    c = 0
    while i <= n:
        # print(f'degrau: {i}')
        if i in broken:
            x = y
            if i + 1 in broken:
                impossible = True
                break
            while not (i + 1 not in broken and i + 2 not in broken and i + 3 not in broken):
                c = 0
                for x in range(i + 1, i + 4):
                    if x in broken:
                        c += 1
                if c >= 2:
                    impossible = True

                # print(f'i: {i}')
                i += 3
            # if i + 1 not in broken and i + 2 not in broken and i + 3 not in broken:
            #     i += 1

            # print('broken')
            # x = y
            # # y = x
            # print(f'x: {x}, y: {y}')
            # previous_broken = False
            # while i not in broken and (i + 1) not in broken and (i + 2) not in broken:
            #     i += 1
            # while c < 2:
            #     i += 1
            #     if i in broken:
            #         if previous_broken:
            #             impossible = True
            #         previous_broken = True
            #         continue
            #     else:
            #         previous_broken = False
            #         c += 1
            # i += 2
            # c = 0
        else:
            y, x = (x + y) % 1000000007, y % 1000000007
            # print(f'x: {x}, y: {y}')
            c = 0
        i += 1
        # print(y)
    print(0) if impossible else print(y % 1000000007)

Submission status: Wrong Answer

Solution code:
def fib(n, broken):
    a = 1
    b = 1
    for i in range(n-2):
        # if i in broken:

        a, b = b, a + b
    print(b)


# t = int(input())
t = 1

for _ in range(t):
    n, m = [int(x) for x in input().split()]
    broken = set()
    for _ in range(m):
        broken.add(int(input()))

    x = 0
    y = 1
    i = 1
    impossible = False
    c = 0
    while i <= n:
        # print(f'degrau: {i}')
        if i in broken:
            x = y
            if i + 1 in broken:
                impossible = True
                break
            while not (i + 1 not in broken and i + 2 not in broken and i + 3 not in broken):
                # print(f'i: {i}')
                i += 3
            # if i + 1 not in broken and i + 2 not in broken and i + 3 not in broken:
            #     i += 1

            # print('broken')
            # x = y
            # # y = x
            # print(f'x: {x}, y: {y}')
            # previous_broken = False
            # while i not in broken and (i + 1) not in broken and (i + 2) not in broken:
            #     i += 1
            # while c < 2:
            #     i += 1
            #     if i in broken:
            #         if previous_broken:
            #             impossible = True
            #         previous_broken = True
            #         continue
            #     else:
            #         previous_broken = False
            #         c += 1
            # i += 2
            # c = 0
        else:
            y, x = (x + y) % 1000000007, y % 1000000007
            # print(f'x: {x}, y: {y}')
            c = 0
        i += 1
        # print(y)
    print(0) if impossible else print(y % 1000000007)

Submission status: Wrong Answer

Solution code:
line = input()
X, Y = [int(n) for n in line.split()]

broken_steps = set()
for _ in range(Y):
    line = input()
    broken_steps.add(int(line))

if 1 in broken_steps:
    stairs = [0]
else:
    stairs = [1]

if 2 in broken_steps:
    stairs.append(0)
else:
    stairs.append(2)

for i in range(2, X):
    number_of_steps = 0
    if i+1 not in broken_steps:
        number_of_steps = stairs[i - 1] + stairs[i-2]
    stairs.append(number_of_steps)
predicted_value = stairs[X-1]
print(predicted_value % 1000000007)

Submission status: Wrong Answer

Solution code:
def fib(n, broken):
    a = 1
    b = 1
    for i in range(n-2):
        # if i in broken:

        a, b = b, a + b
    print(b)


# t = int(input())
t = 1

for _ in range(t):
    n, m = [int(x) for x in input().split()]
    broken = set()
    for _ in range(m):
        broken.add(int(input()))

    x = 0
    y = 1
    i = 1
    impossible = False
    while i <= n:
        # print(f'degrau: {i}')
        c = 0
        if i in broken:
            if i + 1 in broken:
                impossible = True
            # print('broken')
            x = y
            # y = x
            # print(f'x: {x}, y: {y}')
            previous_broken = False
            while c < 2:
                i += 1
                if i in broken:
                    if previous_broken:
                        impossible = True
                    previous_broken = True
                    continue
                else:
                    previous_broken = False
                    c += 1
            # i += 2
        else:
            y, x = x + y % 1000000007, y % 1000000007
            # print(f'x: {x}, y: {y}')
        i += 1
    print(0) if impossible else print(y % 1000000007)

Submission status: Wrong Answer

Solution code:
def fib(n, broken):
    a = 1
    b = 1
    for i in range(n-2):
        # if i in broken:

        a, b = b, a + b
    print(b)


n, m = [int(x) for x in input().split()]
broken = set()
for _ in range(m):
    broken.add(int(input()))

x = 0
y = 1
i = 1
impossible = False
while i <= n:
    # print(f'degrau: {i}')
    c = 0
    if i in broken:
        if i + 1 in broken:
            impossible = True
        # print('broken')
        x = y
        # y = x
        # print(f'x: {x}, y: {y}')
        previous_broken = False
        while c < 2:
            i += 1
            if i in broken:
                if previous_broken:
                    impossible = True
                previous_broken = True
                continue
            else:
                previous_broken = False
                c += 1
        # i += 2
    else:
        y, x = x + y % 1000000007, y % 1000000007
        # print(f'x: {x}, y: {y}')
    i += 1
print(0) if impossible else print(y % 1000000007)

Submission status: Wrong Answer

Solution code:
def fib(n, broken):
    a = 1
    b = 1
    for i in range(n-2):
        # if i in broken:

        a, b = b, a + b
    print(b)


n, m = [int(x) for x in input().split()]
broken = set()
for _ in range(m):
    broken.add(int(input()))

x = 0
y = 1
i = 1
impossible = False
while i <= n:
    # print(f'degrau: {i}')
    c = 0
    if i in broken:
        if i + 1 in broken:
            impossible = True
        # print('broken')
        x = y
        # print(f'x: {x}, y: {y}')
        previous_broken = False
        while c < 2:
            i += 1
            if i in broken:
                if previous_broken:
                    impossible = True
                previous_broken = True
                continue
            else:
                previous_broken = False
                c += 1
        # i += 2
    else:
        y, x = x + y, y
        # print(f'x: {x}, y: {y}')
    i += 1
print(0) if impossible else print(y % 1000000007)

Submission status: Wrong Answer

Solution code:
def fib(n, broken):
    a = 1
    b = 1
    for i in range(n-2):
        # if i in broken:

        a, b = b, a + b
    print(b)


n, m = [int(x) for x in input().split()]
broken = set()
for _ in range(m):
    broken.add(int(input()))

x = 0
y = 1
i = 1
impossible = False
while i <= n:
    # print(f'degrau: {i}')
    c = 0
    if i in broken:
        if i + 1 in broken:
            impossible = True
        # print('broken')
        x = y
        # print(f'x: {x}, y: {y}')
        while c < 2:
            i += 1
            if i in broken:
                continue
            else:
                c += 1
        # i += 2
    else:
        y, x = x + y, y
        # print(f'x: {x}, y: {y}')
    i += 1
print(0) if impossible else print(y % 1000000007)

Submission status: Wrong Answer

Solution code:
def fib(n, broken):
    a = 1
    b = 1
    for i in range(n-2):
        # if i in broken:

        a, b = b, a + b
    print(b)


n, m = [int(x) for x in input().split()]
broken = set()
for _ in range(m):
    broken.add(int(input()))

x = 0
y = 1
i = 1
impossible = False
while i <= n:
    # print(f'degrau: {i}')
    if i in broken:
        if i + 1 in broken:
            impossible = True
        # print('broken')
        x = y
        # print(f'x: {x}, y: {y}')
        i += 2
    else:
        y, x = x + y, y
        # print(f'x: {x}, y: {y}')
    i += 1
print(0) if impossible else print(y % 1000000007)

Submission status: Wrong Answer

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

f = [0] * (n + 1)

f[0] = 1
f[1] = 1

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

print(f[n] % 1000000007)

Submission status: Wrong Answer

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

a = [0] * m

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

mod = 10 ** 9 + 7
f = [0] * (n + 1)

f[0] = 1
f[1] = 1

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

print(f[n])

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
H = []
for i in range(M):
  H.append(int(input()))

dp = [0]*(N+1) # 初期条件
dp[0] = 1
dp[1] = 0 if 1 in H else 1
for i in range(2,N+1):
  if i in H:
    dp[i] = 0
  else:
    dp[i] = (dp[i-1]+dp[i-2])%1000000007

Submission status: Wrong Answer

Solution code:
def main():
    N, M = map(int, input().split())
    broken = [int(input()) for _ in range(M)]
    div = 1000000007

    comb_list = [0] * (N + 1)
    comb_list[0] = 1
    if 1 not in broken:
        comb_list[1] = 1

    for i in range(2, N + 1):
        if i in broken:
            continue
        comb_list[i] = (comb_list[i - 1] + comb_list[i - 2]) % div

    print(comb_list[-1])


if __name__ == "___main__":
    main()

Submission status: Wrong Answer

Solution code:
import functools
import operator

n,m= map(int,input().split())
def fib(n):
  x,y=1,2
  if n==1 or n==0:
    return x
  elif n==2:
    return y
  else:
    for i in range(n-2):
      x, y = y,x+y
    return y
if m==0:
  print(fib(n))
else:
  li=[int(input()) for i in range(m)]
  l=len(li)
  a=0
  b=0
  c=[]
  for i in range(l):
    b=li[i]-1
    c.append(b-a)
    a=li[i]+1
  c.append(n-(li[-1]+1))
  c2=[i for i in c if i<0]
  if sum(c2)<0:
    print(0)
  else:
    ans=list(map(fib,c))
    result = functools.reduce(operator.mul, ans)
    print(result%1000000007)

Submission status: Wrong Answer

Solution code:
from sys import exit
from math import factorial

N, M = map(int, input().split())
broken = [-1]
for i in range(M):
    broken.append(int(input()))
broken.append(N + 1)
ways = 1
for i in range(M + 1):
    interval = broken[i + 1] - broken[i]
    if i < M and interval == 1 and broken[i + 2] - broken[i + 1] == 1:
        print(0)
        exit()
    ways_ = 0
    if interval >= 2:
        for k in range((interval - 2) // 2 + 1):
            ways_ += (factorial(interval - 2 - k)) // (factorial(k) * factorial(interval - 2 - 2 * k))
        ways *= ways_
print(ways % (10 ** 9 + 7))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
def steps(N,M):
	if M==0:
		return print(0)
	else:
		a=[]
		for i in range(M):
			a.append(int(input()))
		for i in range(M-1):
			if a[i+1]-a[i]==1:
				return print(0)
		b=[1,1]
		for j in range(N):
			b.append(b[-1]+b[-2])
		ans=1
		a.append(N+1)
		a.insert(0,-1)
		for i in range(M+1):
			c=a[i+1]-a[i]-2
			ans*=(b[c])
		return print(ans%1000000007)
steps(N,M)

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

Solution code:
from scipy.misc import comb as combination

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

route = []
start = 0
for i in range(M+1):
  stair = a[i]-1
  space = stair - start
  flag = stair%2
  if flag == 0:
    comb = [j for j in range(0, space+1, 2)]
  else:
    comb = [j+1 for j in range(0, space+1, 2)]
  total = [combination((space-tmp)//2+tmp, tmp, exact=True) for tmp in comb]
  route.append(sum(total))
  start = stair+2
ans = 1
for i in route:
	ans *= i  
print(ans%1000000007)

Submission status: Wrong Answer

Solution code:
from scipy.misc import comb as combination

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

if M != 1:
  for i in range(M-1):
    if a[i+1] - a[i] == 1:
      print(0)
      exit()

route = []
begin = 0
for i in range(M+1):
  stair = a[i]-1
  space = stair - begin
  flag = stair%2
  if flag == 0:
    comb = [j for j in range(0, space+1, 2)]
  else:
    comb = [j+1 for j in range(0, space+1, 2)]
  total = [combination((space-tmp)//2+tmp, tmp, exact=True) for tmp in comb]
  route.append(sum(total))
  begin = stair+2
ans = 1
for i in route:
	ans *= i  
print(ans%1000000007)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import collections
import itertools
import numpy as np
import sys
sys.setrecursionlimit(100000000)
MOD = 10**9+7

def binary_search(a,val):
    n = len(a)
    low = 0
    high = n-1
    mid =(low+high)//2
    cnt = 1
    while low < high + 1:
        if a[mid] == val:
            return True
        elif a[mid]>val:
            high = mid - 1
        else:
            low = mid + 1
        mid =(low+high)//2
        cnt += 1
    return False
#入力
n,m = map(int,input().split())
a = [int(input()) for i in range(m)]
dp = [1]*(n+2)
dp[-1] = 0
broke = [0]*(n+1)
for i in range(m):
    broke[a[i]] = 1
for i in range(n-2,-1,-1):
    if broke[i]:
        dp[i] = 0
        continue
    dp[i] = dp[i+1] + dp[i+2]
    dp[i]%=MOD
print(dp[0])

Submission status: Wrong Answer

Solution code:
import collections
import itertools
import numpy as np
import sys
sys.setrecursionlimit(100000000)
MOD = 10**9+7

def binary_search(a,val):
    n = len(a)
    low = 0
    high = n-1
    mid =(low+high)//2
    cnt = 1
    while low < high + 1:
        if a[mid] == val:
            return True
        elif a[mid]>val:
            high = mid - 1
        else:
            low = mid + 1
        mid =(low+high)//2
        cnt += 1
    return False
#入力
n,m = map(int,input().split())
a = [int(input()) for i in range(m)]
dp = [1]*(n+2)
broke = [0]*(n+1)
for i in range(m):
    broke[a[i]] = 1
for i in range(n-2,-1,-1):
    if broke[i]:
        dp[i] = 0
        continue
    dp[i] = dp[i+1] + dp[i+2]
    dp[i]%=MOD
print(dp[0])

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
S = [int(input()) for _ in range(W)]
    
floor = list(range(0,H+1))
 
if S.count(1) >0:
	floor[1]=0
	floor[2]=1
	if S.count(2) >0:
		floor[2]=0
elif S.count(2) >0:
	floor[1]=1
	floor[2]=0
 
teiou = [0]*H
for i in range (0, H):
	teiou[i] = S.count(i)
    
for i in range (3, H+1):
	if teiou[i-2] == 0 and teiou[i-1]==0:
		print(0)
		quit()
	else:
		floor[i]=floor[i-2]*(1-teiou[i-2])+floor[i-1]*(1-teiou[i-1])

print(floor[H]%(10**9+7))

Submission status: Wrong Answer

Solution code:
import sys
import math

from collections import defaultdict
from collections import deque
def load(vtype=int):
    return vtype(input().strip())
def load_list(seplator=" ", vtype=int):
    return [vtype(v) for v in input().strip().split(seplator)]
def exit():
    import sys
    sys.exit(0)
def perm_sub(li, used):
    if len(li) == len(used):
        return [deque()]
    k = []
    for i in range(len(li)):
        if i in used:
            continue
        used.add(i)
        sub_list = perm_sub(li, used)
        for sub in sub_list:
            sub.appendleft(li[i])
        k.extend(sub_list)
        used.discard(i)
    return k
def perm_li(li):
    return perm_sub(li, set())
def perm_n(n):
    return perm_sub(list(range(n)), set())
def join_i(li, sep=""):
    return sep.join([str(e) for e in li])
def li2n(li):
    n, base = 0, 1
    for i in range(len(li)-1, -1, -1):
        n += li[i] * base
        base *= 10
    return n
def sli2ili(li):
    return [int(s) for s in li] 
def prime_list(n):
    li = [i for i in range(2, n+1)]
    for i in range(len(li)):
        if li[i] >= int(math.sqrt(n)):
            break
        if li[i] == -1:
            continue
        for j in range(i+1, len(li)):
            if li[j] % li[i] == 0:
                li[j] = -1
    return [n for n in li if n != -1]
def gcd(a, b):
    a, b = max(a, b), min(a, b)
    while True:
        r = a % b
        if r == 0: return b
        a, b = b, r
def lcm(a, b):
    return int(a * b / gcd(a,b))
def all_subset(li):
    s = []
    n = len(li)
    for bit in range(0, (1<<(n+1))):
        ss = set()
        for i in range(0, n):
            if (bit & (1 << i)):
                ss.add(li[i])
        s.append(ss)
    return s
def factorial(n):
    if n == 1:
        return 1
    return n * factorial(n-1)
def mCn(m, n):
    def factorial_ntimes(m, n):
        r = 1
        while n:
            r *= m
            m -= 1
            n -= 1
        return r
    return int(factorial_ntimes(m, n) / factorial(n))


n, m = load_list()
A = []
for _ in range(m):
    A.append(load())
A = set(A)

dp = dict()

s = list()
s.append(0)

def f(now, goal, A):
    print(now)
    if now > goal:
        return 0
    if now == goal:
        return 1
    
    cnt = 0
    if now + 1 in A:
        pass
    elif now + 1 in dp:
        cnt += dp[now+1]
    else: 
        dp[now+1] = f(now+1, goal, A) 
        cnt += dp[now+1]

    if now + 2 in A:
        pass
    elif now + 2 in dp:
        cnt += dp[now+2]
    else:
        dp[now+2] = f(now+2, goal, A) 
        cnt += dp[now+2]
    return cnt
sys.setrecursionlimit(1000000) 
cnt = f(0, n, A)
print(cnt % 1000000007)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

#n = int(input())
#l = list(map(int, input().split()))

'''
A=[]
B=[]
for i in range():
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)'''

fibo = [1, 1]
for i in range(1, 10**5+2):
    fibo.append(fibo[i]+fibo[i-1])

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

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

flg=True
for i in range(m-1):
    if a[i]+1==a[i+1]:
        flg=False
        break

if not flg:
    print(0)
    
else:
    ans=1
    if m==1:
        print(fibo[a[0]-1]*fibo[n-a[0]-1] % (10**9+7))

    elif m==0:
        print((fibo[n-1]) % (10**9+7))

    else:
        for i in range(1,m):
            ans*=fibo[a[i]-a[i-1]-2]   
        print(ans*fibo[a[0]-1]*fibo[n-a[m-1]-1]%(10**9+7))

Submission status: Wrong Answer

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

#n = int(input())
#l = list(map(int, input().split()))

'''
A=[]
B=[]
for i in range():
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)'''

fibo = [1, 1]
for i in range(1, 10**5+2):
    fibo.append(fibo[i]+fibo[i-1])

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

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

flg=True
for i in range(m-1):
    if a[i]+1==a[i+1]:
        flg=False
        break
#print(a[0]==a[1],flg)
if not flg:
    print(0)
else:
    ans=1
    if m==1:
        #print(fibo[a[0]-1],fibo[n-a[0]-1])
        print(fibo[a[0]-1]*fibo[n-a[0]-1] % (10**9+7))
    elif m==0:
        print((fibo[n]-2)%(10**9+7))
    else:
        for i in range(1,m):
            #print(a[i],a[i-1])
            #print(fibo[21])
            #print(fibo[a[i]-a[i-1]-1])
            ans*=fibo[a[i]-a[i-1]-2]
            print(ans % (10**9+7))
        #print(fibo[a[0]-1],fibo[n-a[m-1]-1],fibo[10])
        print(ans*fibo[a[0]-1]*fibo[n-a[m-1]-1]%(10**9+7))

Submission status: Wrong Answer

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

n,m=map(int,input().split())
S=[]
now=0
for i in range(m):
    a=int(input())
    if i==0 and a==1:
        now=a
        continue
    elif i==0:
        S.append(a-now)
        now=a
        continue
    elif i!=0 and a-now==1:
        print(0)
        sys.exit()
    S.append(a-now-1)
    now=a
S.append(n-now)

mod=10**9+7
N=10**5+10
g1=[1,1]
g2=[1,1]
inverse=[0,1]

for i in range(2,N+1):
    g1.append((g1[-1]*i)%mod)
    inverse.append((-inverse[mod%i]*(mod//i))%mod)
    g2.append((g2[-1]*inverse[-1])%mod)

def cmb(n,r):
    if (r<0 or r>n):
        return 0
    r=min(r,n-r)
    return g1[n]*g2[r]*g2[n-r]%mod


ans=1

for s in S:
    cnt=0
    for i in range((s-1)//2+1):
        cnt+=cmb(s-i-1,i)
        cnt%=mod
    ans=ans*cnt%mod

print(ans%mod)