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 = [int(input()) for _ in range(m)]
if 1 in a:
    ans = [0,1]+([0]*(n-2))
elif 2 in a:
    ans = [1,0]+([0]*(n-2))
else:
    ans = [1,2]+([0]*(n-2))
if n == 1:
    print(ans[0])
    sys.exit()
elif n == 2:
    print(ans[1])
    sys.exit()
else:
    for i in range(2,n):
        if i+1 not in a:
            ans[i] = (ans[i-1]+ans[i-2])%1000000007
        else:
            ans[i] = 0
    print(ans[len(ans)-1]%1000000007)

Submission status: Wrong Answer

Solution code:
import sys
n,m=map(int, input().split())
a = [int(input()) for _ in range(m)]
if 1 in a:
    ans = [0,1]
elif 2 in a:
    ans = [1,0]
else:
    ans = [1,2]
if n == 1:
    print(ans[0])
    sys.exit()
elif n == 2:
    print(ans[1])
    sys.exit()
else:
    for i in range(2,n):
        if i+1 not in a:
            ans.append((ans[i-1]+ans[i-2])%1000000007)
        else:
            ans.append(0)
    print(ans[len(ans)-1]%1000000007)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

dp = [1, 1]
def fib(n,a):
  n += 1  
  for i in range(max(n-2,0)):
      dp.append(dp[i]+dp[i+1] if not i+2 in a else 0)
  return dp[n-1]%1000000007

print(fib(n,a))

Submission status: Wrong Answer

Solution code:
def rec(i):
    global ans
    ans[N] = 1
    for i in range(N-1,-1,-1):
        if a[i+1] and a[i+2]:
            ans[i] = (ans[i+1] + ans[i+2])
        elif a[i+1]:
            ans[i] = ans[i+1]
        else:
            ans[i] = ans[i+2]
    return ans[0]

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

hantei = False
a = [True] * (N+1) + [False]
for i in range(0,M-1,2):
    if A[i+1] - A[i] == 1:
        hantei = True
        break

ans = [1] * (N+1)
if not hantei:
    for i in range(M):
        a[A[i]] = False
    Answer = rec(0)

if hantei:
    print(0)
else:
    print(Answer%1000000007)

Submission status: Wrong Answer

Solution code:
import bisect
M = 1000000007

# def dfs(i):
#     if i >= n - 1:
#         return 1
#     if dp[i] is not None:
#         return dp[i]
#     if i <= maxv and a[bisect.bisect_left(a, i)] == i:
#         dp[i] = 0
#         return 0
#     r = (dfs(i + 1) + dfs(i + 2)) % M
#     dp[i] = r
#     return r

n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
a.sort()
maxv = m and max(a) or -1
# dp = [None] * n
# print(dfs(0) % M)

dp = [1] * (n + 2)
for i in range(n - 2, -1, -1):
    if i <= maxv and a[bisect.bisect_left(a, i)] == i:
        dp[i] = 0
    else:
        dp[i] = (dp[i + 1] + dp[i + 2]) % M

print(dp[0] % M)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
a=[]
for i in range(m):
    a.append(int(input()))
flag=0
c=[0 for i in range(n+1)]
b=0
a.append(-2)
if(m!=0):
    for i in range(m):
        if(a[i+1]-a[i]==1):
            print('0')
            flag=1
if(flag==0):
    c[0]=1
    if(a[b]==1):
        c[1]=0
        b+=1
    else:
        c[1]=1
    for i in range(2,n+1):   # iは段目
        if (i==a[b]):
            c[i]=0
            b+=1
        else:
            c[i]=c[i-1]+c[i-2]
            c[i]=c[i] %1000000007
    print('{0}'.format(c[n]))

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
a=[]
for i in range(m):
    a.append(int(input()))
flag=0
c=[0 for i in range(n+1)]
b=0
a.append(-2)
if(m!=0):
    for i in range(m-1):
        if(a[i+1]-a[i]==1):
            print('0')
            flag=1
if(flag==0):
    c[0]=1
    if(a[b]==1):
        c[1]=0
        b+=1
    else:
        c[1]=1
    for i in range(2,n+1):   # iは段目
        if (i==a[b]):
            c[i]=0
            b+=1
        else:
            c[i]=c[i-1]+c[i-2]
            c[i]=c[i] %1000000007
    print('{0}'.format(c[n]))

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
step_list = list(range(N+1))
denger_list = list()
for i in range(M):
	denger_list.append(int(input()))

ppre_step = None
pre_step  = None
now_step  = 0

for i in range(N+1):
	if i == 0:
		continue
	if i == 1:
		if i not in denger_list:
			ppre_step,pre_step,now_step = pre_step,0,1

		if i in denger_list:
			ppre_step,pre_step,now_step = pre_step ,0,0

	if i == 2:
		if i not in denger_list:
			ppre_step,pre_step,now_step = pre_step,now_step,2
		if i in denger_list:
			ppre_step,pre_step,now_step = pre_step ,now_step,0

	else:
		#そのステップが危険でない場合、そこのステップ
		#への移動は、2つ前までの移動方法数の和となる
		if i not in denger_list:
			ppre_step = pre_step
			pre_step  = now_step
			now_step  = ppre_step + pre_step
		#そのステップが危険な場合、そこの値は
		#移動不可能なので0通りとなる
		elif i in denger_list:
			ppre_step = pre_step
			pre_step  = now_step
			now_step  = 0 
	# print('========')
	# print('i:',i)
	# print('ppre_step:',ppre_step)
	# print('pre_step:',pre_step)
	# print('now_step:',now_step)



print(now_step%1000000007)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
step_list = list(range(N+1))
denger_list = list()
for i in range(M):
	denger_list.append(int(input()))

print(denger_list)
ppre_step = None
pre_step  = None
now_step  = 0

for i in range(N+1):
	if i == 0:
		continue
	if i == 1:
		if i not in denger_list:
			ppre_step,pre_step,now_step = pre_step,0,1

		if i in denger_list:
			ppre_step,pre_step,now_step = pre_step ,0,0

	if i == 2:
		if i not in denger_list:
			ppre_step,pre_step,now_step = pre_step,now_step,2
		if i in denger_list:
			ppre_step,pre_step,now_step = pre_step ,now_step,0

	else:
		#そのステップが危険でない場合、そこのステップ
		#への移動は、2つ前までの移動方法数の和となる
		if i not in denger_list:
			ppre_step = pre_step
			pre_step  = now_step
			now_step  = ppre_step + pre_step
		#そのステップが危険な場合、そこの値は
		#移動不可能なので0通りとなる
		elif i in denger_list:
			ppre_step = pre_step
			pre_step  = now_step
			now_step  = 0 
	# print('========')
	# print('i:',i)
	# print('ppre_step:',ppre_step)
	# print('pre_step:',pre_step)
	# print('now_step:',now_step)



print(now_step%1000000007)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
step_list = list(range(N+1))
denger_list = list()
for i in range(M):
	denger_list.append(int(input()))

print(denger_list)
ppre_step = None
pre_step  = None
now_step  = 0

for i in range(N+1):
	if i == 0:
		continue
	if i == 1:
		if i not in denger_list:
			ppre_step,pre_step,now_step = pre_step,0,1

		if i in denger_list:
			ppre_step,pre_step,now_step = pre_step ,0,0

	if i == 2:
		if i not in denger_list:
			ppre_step,pre_step,now_step = pre_step,now_step,2
		if i in denger_list:
			ppre_step,pre_step,now_step = pre_step ,now_step,0

	else:
		#そのステップが危険でない場合、そこのステップ
		#への移動は、2つ前までの移動方法数の和となる
		if i not in denger_list:
			ppre_step = pre_step
			pre_step  = now_step
			now_step  = ppre_step + pre_step
		#そのステップが危険な場合、そこの値は
		#移動不可能なので0通りとなる
		elif i in denger_list:
			ppre_step = pre_step
			pre_step  = now_step
			now_step  = 0 
	print('========')
	print('i:',i)
	print('ppre_step:',ppre_step)
	print('pre_step:',pre_step)
	print('now_step:',now_step)



print(now_step%1000000007)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
step_list = list(range(N+1))
denger_list = list()
for i in range(M):
	denger_list.append(int(input()))

ppre_step = None
pre_step  = None
now_step  = 0

for i in range(N+1):
	if pre_step == None or ppre_step == None:
		ppre_step = pre_step
		pre_step  = now_step
		now_step  = 1
	else:
		#そのステップが危険でない場合、そこのステップ
		#への移動は、2つ前までの移動方法数の和となる
		if i not in denger_list:
			ppre_step = pre_step
			pre_step  = now_step
			now_step  = ppre_step + pre_step
		#そのステップが危険な場合、そこの値は
		#移動不可能なので0通りとなる
		elif i in denger_list:
			ppre_step = pre_step
			pre_step  = now_step
			now_step  = 0 

print(now_step%1000000007)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
import sys

def input():
    return sys.stdin.readline().strip()

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

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

Submission status: Wrong Answer

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

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

ans = 0
for i in range(2, N+1):
    if i in A:
        continue
    if i - 2 in A and i - 1 in A:
        print(0)
        exit()
    if i - 2 not in A and i - 1 not in A:
        ans += 1

print(2 ** ans % MOD)

Submission status: Wrong Answer

Solution code:
import sys
#from scipy.special import comb
from scipy.misc import comb

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

A = [0]*M

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

A.append(N+1)

def step_comb(L):
    c = 0
    if L==1 or L == 0:
        c = 1
    else:
        for i in range(L//2 +1):
            j = L - 2*i
            c += comb(j+i, i, exact=True)
    return c

total_comb = 1
NOW = 0
for a in A:
    if NOW == a:
        print(0)
        sys.exit()
    L = a-1-NOW
    total_comb *= step_comb(L)
    NOW = a + 1
    
print(total_comb)

Submission status: Wrong Answer

Solution code:
import sys
#from scipy.special import comb
from scipy.misc import comb

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

A = [0]*M

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

A.append(N+1)

total_combo = 1
NOW = 0
for a in A:
    if NOW == a:
        print(0)
        sys.exit()
    L = a-1-NOW
    combo = 0
    if L==1:
        combo = 1
    else:
        for i in range(L//2 +1):
            j = L - 2*i
            combo += comb(j+i, i, exact=True)
    total_combo *= combo
    NOW = a + 1
    
print(total_combo)

Submission status: Wrong Answer

Solution code:
import sys
#from scipy.special import comb
from scipy.misc import comb

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

A = [0]*M

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

A.append(N+1)

total_combo = 1
NOW = 0
for a in A:
    if NOW == a:
        print(0)
        sys.exit()
    L = a-1-NOW
    combo = 0
    if L==1:
        combo = 1
    else:
        for i in range(L//2 +1):
            j = L - 2*i
            combo += comb(j+1, i, exact=True)
    total_combo *= combo
    NOW = a + 1
    
print(total_combo)

Submission status: Wrong Answer

Solution code:
import sys
#from scipy.special import comb
from scipy.misc import comb

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

A = [0]*M

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

A.append(N+1)

total_combo = 1
NOW = 0
for a in A:
    if NOW == a:
        print(0)
        sys.exit()
    L = a-1-NOW
    combo = 0
    for i in range(L//2 +1):
        j = L - 2*i
        combo += comb(j+1, i, exact=True)
    total_combo *= combo
    NOW = a + 1
    
print(total_combo)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
MOD = 1000000007
s = [int(input()) for i in range(M)]
s.append(N+1)#最後の段は踏まないといけないので+1

def fiv(n):
  a, b = 0, 1
  if n == 0:
    return 1
  elif n == 1:
    return 1
  else:
    for i in range(n):
      a, b = b, a+b
    return b

r = 1

for j in range(1,M):
  if s[j-1] +1 == s[j]:r = 0

if M == 1:
  r = fiv(s[0]-1)*fiv(N-s[0]-1)
else:
  r = r*fiv(s[0]-1)
  print(r)
  for j in range(1,M+1):
      r = r*fiv(s[j]-s[j-1]-2)

print(r%MOD)

Submission status: Wrong Answer

Solution code:
MOD = 10 ** 9 + 7

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

broken = [False for _ in range(N+1)]
for _ in range(M):
	broken[int(input())] = True

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

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

Submission status: Wrong Answer

Solution code:
import itertools


def judge(judge_list):
	for i in range(len(judge_list)-1):
		if judge_list[i+1]-judge_list[i] >2:
			return False
	return True


N,M = map(int,input().split())
step_list = list(range(N+1))

for i in range(M):
	step_list.remove(int(input()))

count = 0
ans_list = list()
for i in range(N,int((N+1)/2),-1):
	for i in itertools.combinations(step_list,i):
		if judge(i):
			if N in i and 0 in i :
				ans_list.append(i)

print(len(ans_list)%1000000007)

Submission status: Wrong Answer

Solution code:
import itertools


def judge(judge_list):
	for i in range(len(judge_list)-1):
		if judge_list[i+1]-judge_list[i] >2:
			return False
	return True


N,M = map(int,input().split())
step_list = list(range(N+1))

for i in range(M):
	step_list.remove(int(input()))

count = 0
ans_list = list()
for i in range(N,int((N+1)/2),-1):
	for i in itertools.combinations(step_list,i):

		if judge(i):
			if N in i and 0 in i and M not in i:
				ans_list.append(i)
print(len(ans_list)%1000000007)

Submission status: Wrong Answer

Solution code:
import itertools


def judge(judge_list):
	for i in range(len(judge_list)-1):
		if judge_list[i+1]-judge_list[i] >2:
			return False
	return True


N,M = map(int,input().split())
step_list = list(range(N+1))

for i in range(M):
	step_list.remove(int(input()))

count = 0
ans_list = list()
for i in range(N,int((N+1)/2),-1):
	for i in itertools.combinations(step_list,i):

		if judge(i):
			if N in i and 0 in i and M not in i:
				ans_list.append(i)
print(len(ans_list))
print(len(ans_list)%1000000007)

Submission status: Wrong Answer

Solution code:
a = input().split()
a = [int(i) for i in a]

broken_stairs = []
kekka_flag = False


def fib(x, broken_stairs):
    count = [1, 2]
    if 1 in broken_stairs:
        count[0] = 0
        count[1] = 1
    if 2 in broken_stairs:
        count[1] = 0
    for i in range(x - 2):
        if i + 3 in broken_stairs:
            count.append(0)
        else:
            count.append(count[i] + count[i + 1])
    return count


for i in range(a[1]):
    broken_stairs.append(int(input()))

count = fib(a[0],broken_stairs)
print(count[-1] % 1000000007)

Submission status: Wrong Answer

Solution code:
N,M = map(int, input().split())
brk = []
for h in range(0,M):
    brk.append(int(input()))
flt = [0]
put = [1]
for i in range(1,N+1):
    if i in brk:
        flt.append(put[i-1])
        put.append(0)
    else:
        flt.append(put[i-1])
        put.append(put[i-1]+flt[i-1])
A = put[N] % 1000000007
print(A)
print(flt)
print(put)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
aa = {int(input()) for _ in range(m)}
dp = [0 for _ in range(n + 1)]
dp[0] = 1

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

for i in range(2, n + 1):
    if dp[i - 1] > 0 and (i - 1) not in aa:
        dp[i] += dp[i - 1]
    if dp[i - 2] > 0 and (i - 2) not in aa:
        dp[i] += dp[i - 2]

print(dp[-1] % 1000000007)
print(dp[-1])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
n,m=map(int,input().split())
a=[]
ans=[1]+[1]+[0]*(n-1)
mod=1000000007
for _ in range(m):
    a.append(int(input()))
for i in range(2,n+1):
    if i in a:
        ans[i]=0
    else:
        ans[i]=(ans[i-1]+ans[i-2])%mod
print(ans[n])

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
broken = [True] * (n+1)
for _ in range(m):
    broken[int(input())] = False

mod = 10 ** 9 + 7

dp = [0] * (n+1)
dp[-1] = 1
if broken[n-1]:
    dp[n-1] = 1

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

Submission status: Wrong Answer

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

dp = [0] * (n + 1)

i = n
while i > -1:
    if i >= n-1:
        dp[i] = 1
        i -= 1
        continue
    if i in broken:
        dp[i] = 0
        i -= 1
        continue
        
    dp[i] = dp[i+1] + dp[i+2]
    i -= 1
    
print(dp[0]%1000000007)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
rt=[1,1]
mod=10**9+7
for i in range(2,n):
    rt.append(rt[i-1]+rt[i-2])
rt.append(0)
a=[-1]
for _ in range(m):
    a.append(int(input()))
a.append(n+1)
ans=1

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

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
rt=[1,2]
mod=10**9+7
for i in range(2,n):
    rt.append(rt[i-1]+rt[i-2])
rt.insert(0,0)
a=[-1]
for _ in range(m):
    a.append(int(input()))
a.append(n+1)
ans=1

for i in range(m+1):
    if a[i+1]==1:
        continue
    ans=ans*rt[max(a[i+1]-a[i]-2,0)]%mod
print(ans)

Submission status: Wrong Answer

Solution code:
n, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
dp = [-1 for _ in range(n+1)]
dp[0] = 1
dp[1] = 1
if 1 in A:
    dp[1] = 0

step = 2
while True:
    if step == n+1:
        break
    
    if step in A:
        dp[step] = 0
    else:
        dp[step] = dp[step-1] + dp[step-2]
        
    step += 1
    
print(dp[n])

Submission status: Wrong Answer

Solution code:
N,M =map(int,input().split())
if M>0:
    a = [0]*M
    for i in range(M):
        a[i] = int(input())

ans = int(1)

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


SA =[0]*(N+1)
SA[0] = int(1)
SA[1] = int(1)
if N>2:
    for i in range(N - 1):
        SA[i + 2] = SA[i + 1] + SA[i]
        SA[i + 2] = SA[i + 2] % 1000000007

for i in range(M+1):
    ans *= SA[A[i]]
    ans = ans%1000000007


print(ans)

Submission status: Wrong Answer

Solution code:
N,M =map(int,input().split())
if M>0:
    a = [0]*M
    for i in range(M):
        a[i] = int(input())

ans = int(1)

A = [0]*(M+1)
A[0]=N
if M!=0:
    A[0] = a[0] - 1
    A[M] = N - a[M-1]-1
    for i in range(M-1):
        A[i+1] = a[i+1] - a[i]- 2
        if A[i+1]==-1:
            ans = 0


SA =[0]*(N+1)
SA[0] = int(1)
SA[1] = int(1)
if N>2:
    for i in range(N - 1):
        SA[i + 2] = SA[i + 1] + SA[i]
        SA[i + 2] = SA[i + 2] % 1000000007

for i in range(M+1):
    if A[i]>=0:
        ans *= SA[A[i]]
        ans = ans%1000000007


print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

x=[0]*(N+1)
j=0
if N!=0:
    x[0]=1
if N>1 and M!= 0 and a[0]==1:
    j+=1
else:
    x[1]=1

for i in range(2,N+1): 
    if j==M or i!=a[j]:
        x[i]=x[i-1]+x[i-2]
    else:
        x[i]=0
        j+=1
print(int(x[N]%(10000000007)))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
arr=[1,2]
arr=arr+[0]*(n-2)
danger=[int(input()) for _ in range(m)]
for i in range(n):
  if i+1 in danger:
    arr[i]=0
  elif i==0 or i==1:
    continue 
  else:
    arr[i]=arr[i-1]+arr[i-2]
print(arr[-1])

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())  # N段の階段, 壊れている床の個数M

A = []

flag = True
for i in range(M):
    A.append(int(input()))
    if len(A) > 1:
        if A[i] == A[i-1]+1:
            print(0)
            flag = False
            break

dp = [0] * (N+1)
if flag:
    dp[0] = 1
    dp[1] = 1
    for i in range(2, N+1):
        if i-1 not in A:
            dp[i] += dp[i-1]
        if i-2 not in A:
            dp[i] += dp[i-2]

print(dp[-1] % 1000000007)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
mod = 1000000007
def add(a, b):
    return (a + b) % mod

N, M = map(int, input().split())
Broken_set = set([])
for _ in range(M):
    Broken_set.add(int(input()))

if 1 in Broken_set:    
    dp = [0]*(N+1)
    dp[0] = 1
    dp[1] = 0
    for i in range(3, N+1):
        if i in Broken_set:
            dp[i] = 0
        else:
            dp[i] = add(dp[i-1], dp[i-2])

else:
    dp = [0]*(N+1)
    dp[0] = 1
    dp[1] = 1
    for i in range(2, N+1):
        if i in Broken_set:
            dp[i] = 0
        else:
            dp[i] = add(dp[i-1], dp[i-2])

print(dp[N])

Submission status: Wrong Answer

Solution code:
from sys import stdin

def main():
  N, M = map(int, stdin.readline().rstrip().split())
  beforeA=-1
  Mlist=[]

  for i in range(M):
    a = int(stdin.readline().rstrip())
    if (a-beforeA)==1:
      print("0")
      exit()
    Mlist.append(a)
    beforeA = a
      
  if N == 1 or (N == 2 and M==1):
    print("1")
    exit()
  if N == 2:
    print("2")
    exit()

  Mindex=0
  broken=-2
  if len(Mlist) >0:
    broken = Mlist[Mindex]
  an2=0
  an1=1
  patern=0
  brokenNext=False
  for i in range(1,N+1):
    if broken == i:
      Mindex+=1
      if len(Mlist) > Mindex:
        broken = Mlist[Mindex]
      brokenNext=True
      continue
    if brokenNext:
      brokenNext=False
      an2=0
      continue
    patern=(an1+an2)%1000000007
    an2=an1
    an1=patern
    #print("{}: {}".format(i,patern))
  print(patern%1000000007 )

main()

Submission status: Wrong Answer

Solution code:
mod = 1000000007
def add(a, b):
    return (a + b) % mod

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

print(dp[N])

Submission status: Wrong Answer

Solution code:
mod = 1000000007
def add(a, b):
    return (a + b) % mod

N, M = map(int, input().split())
Broken_set = set([])
for _ in range(M):
    Broken_set.add(int(input()))
dp = [0]*(N+1)
dp[0] = 1
dp[1] = 1

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

print(dp[N])

Submission status: Wrong Answer

Solution code:
mod = 1000000007

N, M = map(int, input().split())
Broken_set = set([])
for _ in range(M):
    Broken_set.add(int(input()))
dp = [0]*(N+1)
dp[0] = 1
dp[1] = 1

for i in range(2, N+1):
    if i in Broken_set:
        pass
    else:
        dp[i] = dp[i-1] + dp[i-2]

print(dp[N])

Submission status: Wrong Answer

Solution code:
mod = 1000000007
def add(a, b):
    return (a + b) % mod

N, M = map(int, input().split())
Broken_set = set([])
for _ in range(M):
    Broken_set.add(int(input()))
dp = [0]*(N+1)
dp[0] = 1
dp[1] = 1

for i in range(2, N+1):
    if i in Broken_set:
        pass
    else:
        dp[i] = add(dp[i-1], dp[i-2])

print(dp[N])

Submission status: Wrong Answer

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

# a = set()
# for i in range(m):
#     a_tmp = int(input())
#     a.add(a_tmp)

a = [1 for i in range(m)]

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

Submission status: Wrong Answer

Solution code:
import numpy as np


def chmin(a1, a2):
    if a1 <= a2:
        return a1
    elif a1 > a2:
        return a2


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

dp = np.full(n + 1, np.inf)
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]) % 1000000007

print(int(dp[n]))

"""
100 5
1
23
45
67
89
"""

Submission status: Wrong Answer

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

for i in range(M):
  d[a[i]] = 1

t[0]=1
if M>0:
  t[1] = 0 if (a[0]==1) else 1

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

Submission status: Wrong Answer

Solution code:
import scipy.misc as scm

N, M = list(map(int, input().split()))
A = [0]
for m in range(M):
  A.append(int(input()))
  if m != 0 and A[m + 1] - A[m] == 1:
    print(0)
    exit()
A.append(N)
ans = 1
for m in range(1, len(A)):
  n = A[m] - A[m - 1] - 1
  c = [scm.comb(n - k, k, exact=True) for k in range(n // 2 + 1)]
  ans *= sum(c)
print(ans % 1000000007)

Submission status: Wrong Answer

Solution code:
import scipy.misc as scm

N, M = list(map(int, input().split()))
A = [0]
for m in range(M):
  A.append(int(input()))
  if m != 0 and A[m] - A[m - 1] == 1:
    print(0)
    exit()
A.append(N)
ans = 1
for m in range(1, len(A)):
  n = A[m] - A[m - 1] - 1
  c = [scm.comb(n - k, k, exact=True) for k in range(n // 2 + 1)]
  ans *= sum(c)
print(ans % 1000000007)

Submission status: Wrong Answer

Solution code:
Num = 1000000007 
N,M = map(int,input().split())
a = [int(input()) for i in range(M)]
now = 0
if 1 in a:
    prev1 = 0
else:
    prev1 = 1
prev2 = 1

for i in range(2,N+1):
    if i in a:
        now = 0
        prev2 = prev1
        prev1 = now 
    else:
        now = prev1 +prev2
        prev2 = prev1
        prev1 = now

print(now%Num)

Submission status: Wrong Answer

Solution code:
Num = 1000000007 
N,M = map(int,input().split())
a = []
for i in range(M):
    a.append(int(input()))
now = 0
if 1 in a:
    prev1 = 0
else:
    prev1 = 1
prev2 = 1

for i in range(2,N+1):
    if i in a:
        now = 0
        prev2 = prev1
        prev1 = now 
    else:
        now = prev1 +prev2
        prev2 = prev1
        prev1 = now

print(now%Num)

Submission status: Wrong Answer

Solution code:
Num = 1000000007 
N,M = map(int,input().split())
a = []
for i in range(M):
    a.append(int(input()))
now = 0
if 1 in a:
    prev1 = 0
else:
    prev1 = 1
prev2 = 1

for i in range(2,N+1):
    if i in a:
        now = 0
        prev2 = prev1
        prev1 = now 
        continue
    else:
        now = prev1 +prev2
        prev2 = prev1
        prev1 = now

print(now%Num)

Submission status: Wrong Answer

Solution code:
Num = 1000000007 
N,M = map(int,input().split())
a = []
for i in range(M):
    a.append(int(input()))
now = 0
if 1 in a:
    prev1 = 0
else:
    prev1 = 1
prev2 = 1

for i in range(2,N+1):
    if i in a:
        now = 0
        prev2 = prev1
        prev1 = now 
        continue
    else:
        now = prev1 +prev2
        prev2 = prev1
        prev1 = now
    print(prev1,prev2)

print(now%Num)

Submission status: Wrong Answer

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

Keiro = [0 for _ in range(N+1)]
Keiro[0] = 1
Keiro[1] = 1
for i in range(2,N+1):
    if i in a:
        continue
    else:
        Keiro[i] = (Keiro[i-1]+Keiro[i-2])%Num

print(Keiro[-1])

Submission status: Wrong Answer

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

Keiro = [0 for _ in range(N+1)]
Keiro[0] = 1
Keiro[1] = 1
for i in range(2,N+1):
    if i in a:
        continue
    else:
        Keiro[i] = (Keiro[i-1]+Keiro[i-2])%(1e9+7)

print(Keiro)
print(Keiro[-1])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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