Problem:


Score : 300 points

Problem Statement

There is a staircase with N steps. Takahashi is now standing at the foot of the stairs, that is, on the 0-th step.
He can climb up one or two steps at a time.

However, the treads of the a_1-th, a_2-th, a_3-th, \ldots, a_M-th steps are broken, so it is dangerous to set foot on those steps.

How many are there to climb up to the top step, that is, the N-th step, without setting foot on the broken steps?
Find the count modulo 1\ 000\ 000\ 007.

Constraints

1 \leq N \leq 10^5

0 \leq M \leq N-1

1 \leq a_1 < a_2 <  ...  < a_M \leq N-1

Input

Input is given from Standard Input in the following format:

N M
a_1
a_2
 .
 .
 .
a_M

Output

Print the number of ways to climb up the stairs under the condition, modulo 1\ 000\ 000\ 007.

Sample Input 1

6 1
3

Sample Output 1

4

There are four ways to climb up the stairs, as follows:

0 \to 1 \to 2 \to 4 \to 5 \to 6

0 \to 1 \to 2 \to 4 \to 6

0 \to 2 \to 4 \to 5 \to 6

0 \to 2 \to 4 \to 6

Sample Input 2

10 2
4
5

Sample Output 2

0

There may be no way to climb up the stairs without setting foot on the broken steps.

Sample Input 3

100 5
1
23
45
67
89

Sample Output 3

608200469

Be sure to print the count modulo 1\ 000\ 000\ 007.



Sample input:
6 1
3


Sample output:
4

Submission status: Wrong Answer

Solution code:
import sys

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



num=[1,1,2]

for i in range(3,n+1):
	num.append(1)
	num[i]=num[i-1]+num[i-2]

mod=1000000007

list=[]
count=0
y=1
ans=1
b=0
for i in range(n):
	if(y==0 and i in a):
		print("0")
		b=1
		break
	elif i in a:

		list.append(count-1)

		count=1
		y=0
	elif(i==n-1):
		count+=1
		y=1
		list.append(count-1)
		
		
	else:
		y=1
		count+=1

if(b==0):
	for j in range(len(list)):
		ans=((ans%mod)*(num[list[j]]%mod))%mod
		
	print(ans%mod)

Submission status: Wrong Answer

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

for i in range(2, n+1):
    if s[i] == 0:
        continue
    if s[i-1] + s[i-2] <= 0:
        s[n] = 0
        break
    s[i] = (s[i-1] + s[i-2]) % 1000000007
    
print(s[n])

Submission status: Wrong Answer

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

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

print(s[n])

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

# DP
dp = [1] * (N + 1)
for A in AL:
    dp[A] = 0

for i in range(2, N):
    if dp[i] == 1:
        dp[i] = (dp[i-1] + dp[i-2]) % (10**9 + 7)
print(dp[N])

Submission status: Wrong Answer

Solution code:
import sys
N, M = map(int, input().split())
if N == 1:
    print(1)
    sys.exit()
ana = [0] * M
ans = [0] * N
mod = 10 ** 9 + 7
if M != 0:
    for i in range(M):
      ans[int(input())-1] = -1

if ans[0] == -1:
    ans[0] = 0
    ans[1] = 1
elif ans[1] == -1:
    ans[0] = 1
    ans[1] = 0
else:
    ans[0] = 1
    ans[1] = 2

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

Submission status: Wrong Answer

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

step = [0 for _ in range(N + 1)]
step[0] = 1
step[1] = 1

for _ in range(M):
  i = int(input())
  step[i] = -1

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

print (step[-1] % 1000000007)

Submission status: Wrong Answer

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

step = [0 for _ in range(N + 2)]
step[0] = 1
step[1] = 1

for _ in range(M):
  i = int(input()) + 1
  step[i] = -1

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

print (step[-1] % 1000000007)

Submission status: Wrong Answer

Solution code:
N, M = tuple(map(int, input().split()))
mod = 10**9+7
broken = []
dp = []

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

for i in range(N+1):
    dp.append(0)

dp[0] = 1

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

print(dp[N])

Submission status: Wrong Answer

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

step = [0 for _ in range(N + 2)]
step[1] = 1

for _ in range(M):
  i = int(input()) + 1
  step[i] = -1

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

print (step[N] % 1000000007)

Submission status: Wrong Answer

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

step = [0 for _ in range(N + 2)]
step[1] = 1

for _ in range(M):
  i = int(input()) + 1
  step[i] = -1

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

print (step[N] % 1000000007)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
ana = []
mod = 10 ** 9 + 7
for _ in range(M):
  ana.append(input())
ans = []
ans.append(1)#一段目まで登る方法は一通り
ans.append(2)#二段目まで登る方法は二通り

for i in range(2,N):
    tmp = i+1
    tmp2 = str(tmp)
    if tmp2 in ana:
        ans.append(0)
    else:
        ans.append((ans[i-1]  + ans[i-2]) % mod)
print(ans[N-1])

Submission status: Wrong Answer

Solution code:
import sys

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



num=[1,1,2]

for i in range(3,n+1):
	num.append(1)
	num[i]=num[i-1]+num[i-2]


list=[]
count=0
y=1
ans=1
b=0
for i in range(n):
	if(y==0 and i in a):
		print("0")
		b=1
		break
	elif i in a:

		list.append(count-1)

		count=1
		y=0
	elif(i==n-1):
		count+=1
		y=1
		list.append(count-1)
		
		for j in range(len(list)):
			ans=ans*num[list[j]]
	else:
		y=1
		count+=1

if(b==0):
	print(ans%1000000007)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
ana = []
for _ in range(M):
  ana.append(input())
ans = []
ans.append(1)#一段目まで登る方法は一通り
ans.append(2)#二段目まで登る方法は二通り

for i in range(2,N):
    tmp = i+1
    tmp2 = str(tmp)
    if tmp2 in ana:
        ans.append(0)
    else:
        ans.append(ans[i-1]  + ans[i-2])
print(ans[N-1] % 1000000007)

Submission status: Wrong Answer

Solution code:
import sys

n1, n2 = [int(i) for i in input().split()]

na1 = []

for i1 in range(n2):
    na1.append(int(input()))

for i3 in range(n2):
    if i3 == 0:
        continue
    else:
        if na1[i3] == na1[i3 - 1] + 1:
            print("0")
            sys.exit()

n3 = 0
n4 = 0
n5 = 0
n6 = 0
n7 = 0
r1 = 1
r2 = []
f1 = False
for i2 in range(n1):
    if len(na1) > n7 and (na1[n7] == i2 + 1 ):
        n3 = 0
        n4 = 0
        n6 = 0
        n7 += 1
        r2.append(r1)
        r1 = 1
        f1 = True

    else:
        if f1 == True:
            f1 = False
            continue
        if n4 == 0 :
            n4 = 1
            r1 = 1
        elif n3 == 0 :
            n3 = 1
            n4 = 2
            r1 = 2
        else:
            n6 = n3 + n4
            r1 = n6
            n3 = n4
            n4 = n6
    if i2 == (n1 - 1) :
        r2.append(r1)

r3 = 1
print(r2)
for i6 in range(len(r2)):
    r3 *= r2[i6]

print(r3 % 1000000007)

Submission status: Wrong Answer

Solution code:
import sys

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

#while True:
#    try:
#        i = list(map(int, input().split()))
#        a += i
 #   except EOFError:
 #       break

num=[0,0,1,2]

for i in range(4,n+1):
	num.append(1)
	num[i]=num[i-1]+num[i-2]

#print(num)

list=[]
count=0
y=1
ans=1
for i in range(n):
	if(y==0 and i in a):
		print("0")
		break
	elif 1 in a and i==1:
		list.append(1)
		y=0
		count=1
	elif i in a:
		list.append(count-1)

		count=1
		y=0
	elif(i==n-1):
		count+=1
		y=1
		list.append(count-1)
		#print(list)
		for j in range(len(list)):
			ans=ans*num[list[j]+1]
	else:
		y=1
		count+=1
print(ans%1000000007)

Submission status: Wrong Answer

Solution code:
import sys

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

print(a)
#while True:
#    try:
#        i = list(map(int, input().split()))
#        a += i
 #   except EOFError:
 #       break

num=[0,0,1,2]

for i in range(4,n+1):
	num.append(1)
	num[i]=num[i-1]+num[i-2]

#print(num)

list=[]
count=0
y=1
ans=1
for i in range(n):
	if(y==0 and i in a):
		print("0")
		break
	elif 1 in a and i==1:
		list.append(1)
		y=0
		count=1
	elif i in a:
		list.append(count-1)

		count=1
		y=0
	elif(i==n-1):
		count+=1
		y=1
		list.append(count-1)
		#print(list)
		for j in range(len(list)):
			ans=ans*num[list[j]+1]
	else:
		y=1
		count+=1
print(ans%1000000007)

Submission status: Wrong Answer

Solution code:
import sys

n1, n2 = [int(i) for i in input().split()]

na1 = []

for i1 in range(n2):
    na1.append(int(input()))

for i3 in range(n2):
    if i3 == 0:
        continue
    else:
        if na1[i3] == na1[i3 - 1] + 1:
            print("0")
            sys.exit()

n3 = 0
n4 = 0
n5 = 0
n6 = 0
n7 = 0
r1 = 0
r2 = []
f1 = False
for i2 in range(n1 ):
    if len(na1) > n7 and (na1[n7] == i2 + 1 ):
        n3 = 0
        n4 = 0
        n6 = 0
        n7 += 1
        if r1 == 0:
            r1 = 1
        r2.append(r1)
        f1 = True

    else:
        if f1 == True:
            f1 = False
            continue
        if n4 == 0 :
            n4 = 1
            r1 = 1
        elif n3 == 0 :
            n3 = 1
            n4 = 2
            r1 = 2
        else:
            n6 = n3 + n4
            r1 = n6
            n3 = n4
            n4 = n6
    if i2 == (n1 - 1) :
        r2.append(r1)

r3 = 1
for i6 in range(len(r2)):
    r3 *= r2[i6]

print(r3 % 1000000007)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

sumList = [0] * (N+2)
sumList[0] = 0
sumList[1] = 1
sumList[2] = 2
for i in range(3, N+1) :
    sumList[i] = sumList[i-1] + sumList[i-2]
    sumList[i] %= 1000000007
if M == 0 :
    print(sumList[N])
    exit()

ans = 0
if a[0] == 1 :
    ans = 1
else :
    ans = sumList[a[0] - 1]
for i in range(1, M) :
    if a[i] - a[i-1] != 0 :
        if a[i] - a[i-1] == 1 :
            ans = 0
        else :
            ans *= sumList[a[i] - 2 - a[i-1]]
            ans = ans % 1000000007
if N - a[M-1] != 1 :
    ans *= sumList[N - 1 - a[M-1]]
print(ans % 1000000007)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

before1 = 1
before2 = 0
ai = a.popleft if len(a) else 0

for i in range(1, N+1):
    if i == ai:
        before2 = before1
        before1 = 0
        ai = a.popleft if len(a) else ai
    else:
        current = divmod(before1 + before2, 10**9+7)[1]
        before2 = before1
        before1 = current

print(before1)

Submission status: Wrong Answer

Solution code:
#C問題
N,M = map(int,input().split())
a = []
for i in range(M):
    a.append(int(input()))
    
way = []
for i in range(N+1):
    if i == 0:
        way.append(0)
    elif i == 1:
        way.append(1)
    else:
        way.append(way[i-1]+way[i-2])
    
ans = 1
now = 0
for i in range(N):
    if (i+1) in a:
        if now == 0 and i != 0:
            ans = 0
            break
        elif i == 0:
            pass
        else:
            ans*=way[now]
            now = 0
    else:
        now+=1
ans*=way[now]
print(ans%1000000007)

Submission status: Wrong Answer

Solution code:
N, M = list(map(int, input().split()))
alist = []
for m in range(M) :
    alist.append(int(input()))
    
a2 = 0
a1 = 1
for n in range(N) :
    a0 = (a1 + a2)*int((n+1) not in alist)%1000000007
    print(a0)
    a2, a1 = a1, a0
else :
    print(a0)

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

A = np.array([[0, 1], [1, 1]])
B = np.array([[0, 1], [0, 0]])

ans = np.array([1, 0 if (1 in a) else 1])

for j in range(2, N+1):
    ans = B.dot(ans) if j in a else A.dot(ans)

print(ans[-1] % 1000000007)

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

A = np.array([[0, 1], [1, 1]])
B = np.array([[0, 1], [0, 0]])

ans = np.array([1, 0 if (1 in a) else 1])

for j in range(2, N+1):
    if j in a:
        ans = B.dot(ans)
    else:
        ans = A.dot(ans)

print(ans[-1] % 1000000007)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
status = [True]*(N+2)
for _ in range(M):
    status[int(input())] = False

dp = [0]*(N+2)
dp[0] = 1
for i in range(N):
    dp[i] = dp[i] % (10**9 + 7)
    if status[i+1]:
        dp[i+1] += dp[i]
    if status[i+2]:
        dp[i+2] += dp[i]

print(dp[N] % (10**9+1))

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
status = [True]*(N+2)
for _ in range(M):
    status[int(input())] = False

dp = [0]*(N+2)
dp[0] = 1
for i in range(N):
    dp[i] = dp[i] % (10**9 + 7)
    if status[i+1]:
        dp[i+1] += dp[i]
    if status[i+2]:
        dp[i+2] += dp[i]
print(dp[N])

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
status = [True]*(N+2)
for _ in range(M):
    status[int(input())] = False

dp = [0]*(N+2)
dp[0] = 1
for i in range(N):
    if status[i+1]:
        dp[i+1] += dp[i]
    if status[i+2]:
        dp[i+2] += dp[i]
print(dp[N])

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
status = [True]*(N+2)
for _ in range(M):
    status[int(input())] = False

dp = [0]*(N+2)
for i in range(N):
    if status[i+1]:
        dp[i+1] += dp[i]
    if status[i+2]:
        dp[i+2] += dp[i]
print(dp[N])

Submission status: Wrong Answer

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

a.insert(0,-10)
a.append(-10)
route = True

abefore = -10
for i in range(M):
    if (abefore+1) == a[i]:
        route = False
    abefore = a[i] 

if route:
    ibefore = 0
    ans = 1
    for i in range(M):
        if(a[i+1] - ibefore - 1) != 0:
            ans = ans*(a[i+1] - ibefore - 1) 
        ibefore = a[i+1]
    if(N - a[M] - 1) != 0:
        ans = ans * (N - a[M] - 1)
    print(ans%1000000007)
else:
    print(0)

Submission status: Wrong Answer

Solution code:
n, m = list(map(int, input().split()))
a = [input() for i in range(m)]
b = []
c = []
total_act = 0
total_act2 = 1
total = 1
# for i in range(n + 1):
#     if str(i) in a:
#         total *= total_act
#         total_act = 0
#         total_act2 = 1
#     else:
#         total_act3 = total_act2 + total_act
#         total_act2 = total_act
#         total_act = total_act3
# total *= total_act
# print(total % 1000000007)
if m == 0:
    for i in range(n + 1):
        if str(i) in a:
            total *= total_act
            total_act = 0
            total_act2 = 1
        else:
            total_act3 = total_act2 + total_act
            total_act2 = total_act
            total_act = total_act3
    total *= total_act
    print(total % 1000000007)
else:
    b.append(int(a[0]))
    for i in range(len(a) - 1):
        b.append(int(a[i + 1]) - int(a[i]) - 1)
        if int(a[i + 1]) - int(a[i]) - 1 == 0:
            print(0)
            exit()
    b.append(n - int(a[-1]))
    print(b)
    for i in range(max(b)):
        total_act3 = total_act2 + total_act
        total_act2 = total_act
        total_act = total_act3
        c.append(total_act)
    print(c)
    for i in b:
        total *= c[i - 1]
        print(c[i - 1])
    print(total % 1000000007)

Submission status: Wrong Answer

Solution code:
def Fib(n):
    a, b = 0, 1
    if n == 1:
        return a
    elif n == 2:
        return b
    else:
        for i in range(n-2):
            a, b = b, a + b
        return b
a,b=input().split()
a=int(a)
b=int(b)
ll=[]
y=-1
s=0
for i in range(b):
    x=input()
    x=int(x)
    ll.append(x)
    if x-y==1:
        s=1
        break
    y=x
ll.append(a+1)
l2=[]
if s==1:
    print(0)
elif b==0:
    print(Fib(a+2))
else:
    x=-1
    for i in ll:
        l2.append(Fib(i-x))
        x=i
    ans=1
    for i in l2:
        ans*=i
    print(ans%1000000007)

Submission status: Wrong Answer

Solution code:
def Fib(n):
    a, b = 0, 1
    if n == 1:
        return a
    elif n == 2:
        return b
    else:
        for i in range(n-2):
            a, b = b, a + b
        return b
a,b=input().split()
a=int(a)
b=int(b)
ll=[]
y=-1
s=0
for i in range(b):
    x=input()
    x=int(x)
    ll.append(x)
    if x-y==1:
        s=1
        break
    y=x
ll.append(a+1)
l2=[]
if s==1:
    print(0)
elif b==0:
    print(Fib(a+2))
else:
    x=-1
    for i in ll:
        l2.append(Fib(i-x))
        x=i
    ans=1
    for i in l2:
        if i==0:
            i=1
        ans*=i
    print(ans%1000000007)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
dp = [0]*(n+1)
for i in range(m):
    a = int(input())
    dp[a] = -1
dp[0] = 1
if dp[1] != -1:
    dp[1] = 1
for i in range(2,n+1):
    if dp[i] == -1:
        dp[i] = 0
    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())
dp = [0]*(n+1)
for i in range(m):
    a = int(input())
    dp[a] = -1
dp[0] = 1
if dp[1] != -1:
    dp[1] = 1
for i in range(1,n+1):
    if dp[i] == -1:
        dp[i] = 0
    else:
        dp[i] = (dp[i-1]+dp[i-2])%1000000007
print(dp[n])

Submission status: Wrong Answer

Solution code:
import numpy as np
N , M = map(int,input().split())
ans = np.full(N+1,-1)
ans[0] = 1
for i in range(M):
	ans[int(input())] = 0
if ans[1] == -1:
	ans[1] = 1
for i in range(N-1):
	if ans[i+2] == -1:
		ans[i+2] = (ans[i+1] + ans[i]) % 1000000007
print(ans[N] % 1000000007)

Submission status: Wrong Answer

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

a = []

for i in range(M):
  a.append(int(input()))
  
for i in range(1, M):
  if a[i] - a[i-1] == 1:
    print(0)
    quit()

print(4)

Submission status: Wrong Answer

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

a = []

for i in range(M):
  a.append(int(input()))
  
print(0)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
now = 0
count = 1
flag = True
for _ in range(M):
        a = int(input())
        if a == now:
                print(0)
                flag = False
                break
        else:
                dif = a - now - 1
                x = int(dif / 2)
                y = 0
                for i in range(x+1):
                        z = 1
                        j = dif - 2*i
                        for k in range(i):
                                z *= (i+j-k)/(i-k)
                        y += z
                        if y > 1000000007:
                                y = y % 1000000007
                count *= y
                count = count % 1000000007
                now = a + 1
if flag:
        dif = N - now
        x = int(dif/2)
        y = 0
        for i in range(x+1):
                z = 1
                j = dif - 2*i
                for k in range(i):
                        z *= (i+j-k)/(i-k)
                y += z
        count *= y
        print(int(count%1000000007))

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
now = 0
count = 1
flag = True
for _ in range(M):
        a = int(input())
        if a == now:
                print(0)
                flag = False
                break
        else:
                dif = a - now - 1
                x = int(dif / 2)
                y = 0
                for i in range(x+1):
                        z = 1
                        j = dif - 2*i
                        for k in range(i):
                                z *= (i+j-k)/(i-k)
                        y += z
                count *= y
                count = count % 1000000007
                now = a + 1
if flag:
        dif = N - now
        x = int(dif/2)
        y = 0
        for i in range(x+1):
                z = 1
                j = dif - 2*i
                for k in range(i):
                        z *= (i+j-k)/(i-k)
                y += z
        count *= y
        print(int(count%1000000007))

Submission status: Wrong Answer

Solution code:
n,m = list(map(int, input().split()))
a=[]
a.append(-1)
for x in range(m):
  tmp=int(input())
  a.append(tmp)
a.append(n+1)
diff = []
for x in range(len(a)-1):
  diff.append(a[x+1]-a[x])
              
large = 0
small = 123456789012345
for x in diff:
  large=max(large,x)
  small=min(small,x)

num=[0,0,1]
for _ in range(large):
  num.append((num[-1]+num[-2])%1000000007)
    
answer=1
for x in diff:
  #print(x,num[x])
  answer *=num[x]
  answer%=1000000007
print("AN=",answer)

Submission status: Wrong Answer

Solution code:
def selector(flag):
    if flag:
        return 0
    else:
        return 1

def func(x, a, n):
    if not a[n]:
        x[n] = selector(a[n-1]) * x[n-1] + selector(a[n-2]) * x[n-2]
    else:
        x[n] = 0

K = 1000000007
line = input().split(' ')
N = int(line[0])
M = int(line[1])
a = [False] * (N + 1)
x = [0] * (N + 1)

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

x[0] = 1
if a[1]:
    x[1] = 1
else:
    x[1] = 0

for i in range(2, N+1):
    func(x, a, i)
    
print(x[N]%K)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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

memo = {}


def step(now):
    if now in a:
        return 0
    # print(now)
    if now == n:
        return 1
    if now > n:
        return 0
    if memo.get(now) != None:
        return memo[now]
    # print(now)
    memo[now] = step(now+1)+step(now+2)
    return memo[now]


print(step(0) % 1000000007)
print(memo)

Submission status: Wrong Answer

Solution code:
from collections import deque

def num_way(stair):
  memo = ["EMPTY"]*(stair+1)
  def _fib(stair):
    if stair == 1 or stair == 0:
      return 1
    elif stair == 2:
      return 2
    elif memo[stair] != "EMPTY":
      return memo[stair]
    else:
      memo[stair] = _fib(stair-1)+_fib(stair-2)
      return memo[stair]
  return 0

N, M = map(int,input().split())
a = deque([0])
path_poss = 1
ans = 1
for m in range(M):
  start = a.popleft()
  buff = int(input())
  end = buff-1
  if (end-start) <= -1:
    path_poss = 0
    break
  a.append(buff+1)
  ans *= num_way(end-start)
  ans %= 1000000007

if path_poss == 0:
  print(0)
else:
  start = a.popleft()
  end = N
  if(end-start) <= -1:
    path_poss = 0
  if path_poss == 0:
    print(0)
  else:
  	ans *= num_way(end-start)
  	print(ans%1000000007)

Submission status: Wrong Answer

Solution code:
try:
    a = list(map(int, input().split()))
    #print(a)
    b=[0]*a[1]
    c=[0]*(a[1]+1)
    b[0]=int(input())
    c[0]=b[0]-0
    for x in range(a[1]-1):
        b[x+1]=int(input())
        c[x+1]=b[x+1]-b[x]-1
    c[-1]=a[0]-b[-1]
    max = 0
    min = a[0]+100
    for x in c:
        if x>max:
            max=x
        if x<min:
            min=x
        
    #print(c)
    #print(max," ",min)
    if min==0:
        print(0)
    else:
        num=[0]*(max)
        for x in range(max):
            if x==0:
                num[0]=1
            elif x==1:
                num[1]=1
            else:
                num[x]=num[x-1]+num[x-2]
            #print("num[",x,"]=",num[x])
        
        answer=1
    
        for x in c:
            answer *=num[x-1]
            if answer==0:
                print(0)
                break
            else:
                answer%=1000000007
        print(answer)
except:
        print(0)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
from collections import deque

def num_way(stair):
  memo = ["EMPTY"]*(stair+1)
  def _fib(stair):
    if stair == 1 or stair == 0:
      return 1
    elif stair == 2:
      return 2
    elif memo[stair] != "EMPTY":
      return memo[stair]
    else:
      memo[stair] = _fib(stair-1)+_fib(stair-2)
      return memo[stair]
  return _fib(stair)

N, M = map(int,input().split())
a = deque([0])
path_poss = 1
ans = 1
for m in range(M):
  start = a.popleft()
  buff = int(input())
  end = buff-1
  if (end-start) <= -1:
    path_poss = 0
    break
  a.append(buff+1)
  ans *= num_way(end-start)
  ans %= 1000000007

if path_poss == 0:
  print(0)
else:
  start = a.popleft()
  end = N
  if (end-start) <= -1:
    path_poss = 0
  if path_poss == 0:
    print(0)
  else:
  	print(end-start)

Submission status: Wrong Answer

Solution code:
from collections import deque

def num_way(stair):
  memo = ["EMPTY"]*(stair+1)
  def _fib(stair):
    if stair == 1 or stair == 0:
      return 1
    elif stair == 2:
      return 2
    elif memo[stair] != "EMPTY":
      return memo[stair]
    else:
      memo[stair] = _fib(stair-1)+_fib(stair-2)
      return memo[stair]
  return _fib(stair)

N, M = map(int,input().split())
a = deque([0])
path_poss = 1
ans = 1
for m in range(M):
  start = a.popleft()
  buff = int(input())
  end = buff-1
  if (end-start) <= -1:
    path_poss = 0
    break
  a.append(buff+1)
  ans *= num_way(end-start)
  ans %= 1000000007

if path_poss == 0:
  print(0)
else:
  start = a.popleft()
  end = N
  if (end-start) <= -1:
    path_poss = 0
  if path_poss == 0:
    print(0)
  else:
  	print(ans%1000000007)

Submission status: Wrong Answer

Solution code:
from collections import deque

def num_way(stair):
  memo = ["EMPTY"]*(stair+1)
  def _fib(stair):
    if stair == 1 or stair == 0:
      return 1
    elif stair == 2:
      return 2
    elif memo[stair] != "EMPTY":
      return memo[stair]
    else:
      memo[stair] = _fib(stair-1)+_fib(stair-2)
      return memo[stair]
  return _fib(stair)

N, M = map(int,input().split())
a = deque([0])
path_poss = 1
ans = 1
for m in range(M):
  start = a.popleft()
  buff = int(input())
  end = buff-1
  if (end-start) <= -1:
    path_poss = 0
    break
  a.append(buff+1)
  ans *= num_way(end-start)
  ans %= 1000000007

if path_poss == 0:
  print(0)
else:
  start = a.popleft()
  end = N
  if (end-start) <= -1:
    path_poss = 0
  if path_poss == 0:
    print(0)
  else:
    print(0)

Submission status: Wrong Answer

Solution code:
from collections import deque

def num_way(stair):
  memo = ["EMPTY"]*(stair+1)
  def _fib(stair):
    if stair == 1 or stair == 0:
      return 1
    elif stair == 2:
      return 2
    elif memo[stair] != "EMPTY":
      return memo[stair]
    else:
      memo[stair] = _fib(stair-1)+_fib(stair-2)
      return memo[stair]
  return _fib(stair)

N, M = map(int,input().split())
a = deque([0])
path_poss = 1
ans = 1
for m in range(M):
  start = a.popleft()
  buff = int(input())
  end = buff-1
  if (end-start) <= -1:
    path_poss = 0
    break
  a.append(buff+1)
  ans *= num_way(end-start)
  ans %= 1000000007

if path_poss == 0:
  print(0)
else:
  start = a.popleft()
  end = N
  if (end-start) <= -1:
    path_poss = 0
  print(9)

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
dp[1]=0 if 1 in a else 1
mod=10**9+7

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

print(dp[N])

Submission status: Wrong Answer

Solution code:
from collections import deque

def num_way(stair):
  memo = ["EMPTY"]*(stair+1)
  def _fib(stair):
    if stair == 1 or stair == 0:
      return 1
    elif stair == 2:
      return 2
    elif memo[stair] != "EMPTY":
      return memo[stair]
    else:
      memo[stair] = _fib(stair-1)+_fib(stair-2)
      return memo[stair]
  return _fib(stair)

N, M = map(int,input().split())
a = deque([0])
path_poss = 1
ans = 1
for m in range(M):
  start = a.popleft()
  buff = int(input())
  end = buff-1
  if (end-start) <= -1:
    path_poss = 0
    break
  a.append(buff+1)
  ans *= num_way(end-start)
  ans %= 1000000007

print("0")

Submission status: Wrong Answer

Solution code:
from math import factorial
def c(n):
    c = 0
    if n != 0:
        for i in range(n):
            if n - i < i:
                pass
            else:
                x = n - i
                r = i
                c += factorial(x) // factorial(r) // factorial(x - r)
    return c
N, M = map(int,input().split())
ans = 1
pre_a = 0
for j in range(M+1):
    if j != M:
        a = int(input())

    else:
        if pre_a != N-1:
            a = N
        else:
            a = N+1
    n = a - pre_a - 1
    if a == 1:
        ans *= 1
    else:
        ans *= c(n)
    pre_a = a
print(int(ans%1000000007))

Submission status: Wrong Answer

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

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

print(dp[N])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n,m=map(int,input().split())
a=[int(input()) for i in range(m)]
mod=10**9+7
dp=[0]*(n+2)
dp[n]=1
if n==1:
    print("x")
    exit()
for i in range(n-1,-1,-1):
    if i in a:
        dp[i]=0
    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=[int(input()) for i in range(M)]
dp=[1]*(N+1)
dp[0]=1
dp[1]=1
print(a)

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

Submission status: Wrong Answer

Solution code:
N, M = list(map(int, input().split(" ")))
A = [1] * (N+1)
for i in range(M):
    A[int(input())] = -1
for i in range(2, N + 1):
    if(A[i] == -1):
        A[i] = 0
    else:
        A[i] = A[i-1] + A[i-2]
print(A[-1] % 1000000007)

Submission status: Wrong Answer

Solution code:
import itertools

lis=list(map(int,input().split()))
alist=[-1]
ans=1
mod=(10**9)+7
for i in range(lis[1]):
    alist.append(int(input()))
alist.append(lis[0]+1)

for i in range(lis[1]+1):
    l=alist[i+1]-alist[i]-2
    tmp=0
    t=int((l+l%2)/2)
    h=int((l-l%2)/2)
    for j in range(h+1):
        tmp+=len(list(itertools.combinations(range(t+j),h-j)))%mod
    ans=ans*tmp
print(ans)