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())
a = [-1]+[int(input()) for _ in range(M)]+[N+1]
mod = 10**9+7
fact = [1]+[0]*N
finv = [1]+[0]*N
for i in range(1,N+1):
    fact[i] = fact[i-1]*i % mod
    finv[i] = pow(fact[i], mod-2, mod)

def cmb(a,b):
    n = max(a,b)
    r = abs(a-b)
    if not n or min(a,b) < 0:
        return 0
    else:
        return fact[n]*finv[n-r]*finv[r] % mod
ans = 1
for i in range(1,M+2):
    if a[i] == 1:
        continue
    elif a[i] == N and a[i-1] == N-1:
        continue
    b = a[i]-a[i-1]-2
    ansp = 0
    for j in range(b - (b+1) // 2 + 1):
        ansp = (ansp + cmb(b-j, j)) % mod
    ans = ans * ansp % mod

print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    N, M = list(map(int, input().split(' ')))
    hole_indice = [int(input()) - 1 for i in range(M)]
    holes = [True if i in hole_indice else False for i in range(N)]

    dp = [1]
    if not holes[0]:
        dp.append(2)
    else:
        dp.append(1)

    for i in range(2, N):
        if holes[i]:
            if holes[i-1]:
                print(0)
                return
            else:
                dp.append(dp[i-1])

        else:
            if not holes[i-1] and not holes[i-2]:
                dp.append((dp[i-1] + dp[i-2]) % 1000000007)
            else:
                dp.append(dp[i-1])

    print(dp[N-1])

main()

Submission status: Wrong Answer

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

print(dp[n])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import math

def fib(n):
  if n==1:
    return 1
  elif n<=0:
    return 0
  tmp1,tmp2=1,2
  for _ in range(n-2):
    tmp1,tmp2=tmp2,tmp1+tmp2
  return tmp2

n,m=map(int,input().split())
if m==0:
  print(fib(n))
  exit()
a=[int(input()) for _ in range(m)]
ans=1

if n==2 and a[0]==1:
  print(1)
  exit()

for i in range(m):
  if i==0 and a[0]==1:
    pass
  if i==0 and a[0]!=1:
    ans*=fib(a[i]-1)
  elif i>0 and a[i]-a[i-1]==2:
    pass
  elif i>0 and a[i]-a[i-1]!=2:
  	ans*=fib(a[i]-a[i-1]-2)
  ans%=1000000007
  
if n-a[-1]>1: 
  ans*=fib(n-a[-1]-1)
ans%=1000000007
print(ans)

Submission status: Wrong Answer

Solution code:
import math

def fib(n):
  if n==1:
    return 1
  elif n<=0:
    return 0
  tmp1,tmp2=1,2
  for _ in range(n-2):
    tmp1,tmp2=tmp2,tmp1+tmp2
  return tmp2

n,m=map(int,input().split())
if m==0:
  print(fib(n))
  exit()
a=[int(input()) for _ in range(m)]
ans=1

if n==2 and a[0]==1:
  print(1)
  exit()

for i in range(m):
  if i==0 and a[0]==1:
    pass
  if i==0 and a[0]!=1:
    ans*=fib(a[i]-1)
  elif i>0 and a[i]-a[i-1]==2:
    pass
  elif i>0 and a[i]-a[i-1]!=2:
  	ans*=fib(a[i]-a[i-1]-2)
  ans%=1000000007
  if ans==0:
    exit()
if n-a[-1]>1: 
  ans*=fib(n-a[-1]-1)
ans%=1000000007
print(ans)

Submission status: Wrong Answer

Solution code:
import math

def fib(n):
  if n==1:
    return 1
  elif n<=0:
    return 0
  tmp1,tmp2=1,2
  for _ in range(n-2):
    tmp1,tmp2=tmp2,tmp1+tmp2
  return tmp2

n,m=map(int,input().split())
if m==0:
  print(fib(n))
  exit()
a=[int(input()) for _ in range(m)]
ans=1

if n==2 and a[0]==1:
  print(1)
  exit()

for i in range(m):
  if i==0 and a[0]==1:
    pass
  if i==0 and a[0]!=1:
    ans*=fib(a[i]-1)
  elif i>0 and a[i]-a[i-1]==2:
    pass
  elif i>0 and a[i]-a[i-1]>2:
  	ans*=fib(a[i]-a[i-1]-2)
  ans%=1000000007
  if ans==0:
    print('i:{}\tans:0'.format(i))
    exit()
if n-a[-1]>1: 
  ans*=fib(n-a[-1]-1)
ans%=1000000007
print(ans)

Submission status: Wrong Answer

Solution code:
import math

def fib(n):
  if n==1:
    return 1
  elif n<=0:
    return 0
  tmp1,tmp2=1,2
  for _ in range(n-2):
    tmp1,tmp2=tmp2,tmp1+tmp2
  return tmp2

n,m=map(int,input().split())
if m==0:
  print(fib(n))
  exit()
a=[int(input()) for _ in range(m)]
ans=1

if n==2 and a[0]==1:
  print(1)
  exit()

for i in range(m):
  if i==0 and a[0]==1:
    pass
  if i==0 and a[0]!=1:
    ans*=fib(a[i]-1)
  elif i>0:
  	ans*=fib(a[i]-a[i-1]-2)
  ans%=1000000007
if n-a[i]>1: 
  ans*=fib(n-a[-1]-1)
ans%=1000000007
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
         
mat = np.array([[1, 1],[1, 0]])
n = np.array([[1, 1],[1, 0]])

cnt = 2
if 1 in a:n[0, 1] = 0

while cnt!=N:
    if cnt in a:n[0, 0]=0
    n = np.dot(n, mat) 
    cnt += 1
    if n[0, 0]==0:break

print(n[0, 0]%(10**9+7))

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
         
mat = np.array([[1, 1],[1, 0]])
n = np.array([[1, 1],[1, 0]])

cnt = 2
if 1in a:n[0, 1] = 0

while cnt!=N+1:
    if cnt-1 in a:n[0, 0]=0
    n = np.dot(n, mat) 
    cnt += 1
    if n[0, 0]==0:break

print(n[0, 0]%(10**9+7))

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
         
mat = np.array([[1, 1],[1, 0]])
n = np.array([[1, 1],[1, 0]])

cnt = 2
while cnt!=N+1:
    if cnt-1 in a:n[0, 0]=0
    n = np.dot(n, mat) 
    cnt += 1
    if n[0, 0]==0:break

if cnt-1 in a:n[0, 0]=0
print(n[0, 0]%(10**9+7))

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
         
mat = np.array([[1, 1],[1, 0]])
n = np.array([[1, 1],[1, 0]])

cnt = 2
while cnt!=N+1:
    if cnt-1 in a:n[0, 0]=0
    n = np.dot(n, mat) 
    cnt += 1
    if n[0, 0]==0:break

print(n[0, 0]%(10**9+7))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
a=[]
for i in range(m):
    a.append(int(input()))
ans=[10*9]*n
if len(a)>0:
    if a[0]==1:
        ans[0]=0
    else:
        ans[0]=1
if len(ans)>1:
    ans[1]=ans[0]+1
for i in range(m):
    ans[a[i]-1]=0
for j in range(n-2):
    if ans[j+2]==0:
        continue
    else:
        ans[j+2]=ans[j+1]+ans[j]
        ans[j+2]=ans[j+2]%(1000000007)
    #print(ans)
print(ans[n-1])
#print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
a=[]
for i in range(m):
    a.append(int(input()))
ans=[10*9]*n
ans[0]=1
for i in range(m):
    ans[a[i]-1]=0
if len(ans)>1:
    ans[1]=ans[0]+1
for j in range(n-2):
    if ans[j+2]==0:
        continue
    else:
        ans[j+2]=ans[j+1]+ans[j]
        ans[j+2]=ans[j+2]%(1000000007)
    #print(ans)
print(ans[n-1])
#print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N,M =map(int,input().split())
a = [int(input()) for i in range(M)]
DP = [1]*N
mod = 10**9 + 7
for i in a:
    DP[i-1] = 0
if(N != 1):
    for i in range(N):
        if(DP[i] != 0):
            if(i<1):
                DP[i+1] = DP[i]%mod
            else:
                DP[i] = (DP[i-2] + DP[i-1])%mod
else:
    DP = [1]
print(DP[-1])

Submission status: Wrong Answer

Solution code:
N,M =map(int,input().split())
a = [int(input()) for i in range(M)]
DP = [1]*N
mod = 10**9 + 7
for i in a:
    DP[i-1] = 0
if(N != 1):
    for i in range(N):
        if(DP[i] != 0):
            if(i<1):
                DP[i+1] = DP[i]%mod
            else:
                DP[i] = (DP[i-2]%mod + DP[i-1]%mod)
else:
    DP = [1]
print(DP[-1])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N, M = [int(x) for x in input().strip().split()]
A = [int(input()) for _ in range(M)]
s = 1
s_ = 0
for n in range(1, N+1):
  if n in A:
    s, s_ = 0, s
    continue
  s, s_ = s + s_, s
print(s)

Submission status: Wrong Answer

Solution code:
import math
import fractions
(n,m)=map(int,input().split())
a=[0]*(n+2)
b=[0]*(n+2)
for i in range(m):
    t=int(input())
    a[t]=1
b[0]=1
for i in range(n+1):
    if(a[i]==1):
        continue
    if(i==0):
        continue
    if(i==1):
        b[i]=b[i-1]
        continue
    b[i]=b[i-1]+b[i-2]

print(b[n])

Submission status: Wrong Answer

Solution code:
#c dp version
n,m = map(int,input().split())
a=[]
for i in range(m):
    a.append(int(input()) )
mod=10**9 + 7

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def sumcmb(T):
    count=0
    m=T
    while m>=0:
        count+=cmb(T,m)
        T-=1
        m-=2
    return(count)


N,M=map(int,input().split())
A=[int(input()) for i in range(M)]
mod=10**9+7
for i in range(M-1):
    if A[i]+1==A[i+1]:
        print(0)
        exit()

if 1 not in A:
    A.insert(0,-1)
if N not in A:
    A.append(N+1)


count=1
for i in range(len(A)-1):
    T=max(A[i+1]-1 - (A[i]+1),1)
    print(sumcmb(T))
    count*=sumcmb(T)
    count%=mod
print(count)

Submission status: Wrong Answer

Solution code:
#c
def main():
    import sys
    input = sys.stdin.readline
    n,m = map(int,input().split())
    a=[]
    for i in range(m):
        a.append(int(input()) )
    mod=10**9 + 7
    

    def cmb(n, r):
        if n - r < r: r = n - r
        if r == 0: return 1
        if r == 1: return n
        numerator = [n - r + k + 1 for k in range(r)]
        denominator = [k + 1 for k in range(r)]
        for p in range(2,r+1):
            pivot = denominator[p - 1]
            if pivot > 1:
                offset = (n - r) % p
                for k in range(p-1,r,p):
                    numerator[k - offset] /= pivot
                    denominator[k] /= pivot
        result = 1
        for k in range(r):
            if numerator[k] > 1:
                result *= int(numerator[k])
        return result

    
    c=0
    for i in range(m-1):
        if a[i]==a[i+1]-1: c+=1
    if c!=0:
        print(0)
    elif m==0:
         print( sum( cmb(n-i,i)%mod for i in range(n//2+1) )%mod )
        
        
    else:
        b=[a[0]-1] + [a[j+1]-a[j]-2 for j in range(m-1)] + [n-a[-1]-1]
        cc=[ sum( cmb(n-i,i)%mod for i in range(bb//2+1) )%mod for bb in b ]
    
        ans=1
        for ccc in cc:
            ans = ans*ccc%mod
        print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,m  = map(int, input().split())
A = set(int(input()) for _ in range(m))
mod = 10**9+7

if 1 in A:
  dp_l = [1, 0] + [0]*(n-1)
else:
  dp_l = [1, 1] + [0]*(n-1)
  
for i in range(1, len(dp_l)):
  
  if i in A:
    dp_l[i] = 0
  else:
    dp_l[i] = (dp_l[i-1]+dp_l[i-2])%mod 
  
print(dp_l.pop())

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

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

Submission status: Wrong Answer

Solution code:
import sys

n,m=map(int,input().split())
broken=set(map(int,sys.stdin))

if n==1:
  print (1)
  sys.exit()
if n==2:
  if 1 not in broken and 2 not in broken:
    print (2)
  elif 2 in broken:
    print(0)
  elif 1 in broken and 2 not in broken:
    print(1)

way = [0]*n
if 1 not in broken:
  way[0]=1
if 1 not in broken and 2 not in broken:
  way[1]=2
elif 1 in broken and 2 not in broken:
  way[1]=1
for i in range(2,n):
  if i+1 in broken:
    way[i]=0
    continue
  way[i]=(way[i-1]+way[i-2])%1000000007
print(way[n-1])

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
mod=10**9+7
A = {int(input()) for i in range(M)}

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

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

if sys.platform =='ios':
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline

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

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

for i in range(N+1):
	if np.any(a == i):
		continue
	for j in [1, 2]:
		if i - j >= 0 and not np.any(a == i-j):
			dp[i] += dp[i-j]
print(dp[-1]%1000000007)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import math

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

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

def one_two_comb(N):
    two_n = N//2
    comb_list = []
    for i in range(1,two_n+1):
        comb_list.append([N-i,i])
    return comb_list

def sum_comb(comb_list):
    comb_sum = 0
    for val in comb_list:
        comb_sum += combinations_count(val[0],val[1])
    return comb_sum
    

diff_list = []
current_num = 0
flag = False
for a in An:
    diff = a - current_num
    if diff == 0:
        print(0)
        exit(0)
    diff_list.append(diff)
    current_num = a +1
diff = N+1 - current_num
diff_list.append(diff)
print(diff_list)

all_sum = 1
for idx,diff in enumerate(diff_list):
    if idx == 0 or len(diff_list):
        diff -= 1
    '''
    else:
        diff -= 2
    '''

    if diff == 0:
        all_sum *= 1
    else:
        internal_comb_list = one_two_comb(diff)
        comb_count = sum_comb(internal_comb_list) + 1
        all_sum *= comb_count
print(all_sum%(10**9+7))

Submission status: Wrong Answer

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

Lst = list(int(input()) for x in range(M))

Now = 0
cnt = 1

while Now < N:
  if Now + 2 in Lst:
    if not Now + 1 in Lst:
      Now += 1
    else:
      cnt = 0
      break
  elif Now + 1 in Lst:
    if Now + 2 <= N:
      Now += 2
  elif Now + 2 <= N:
    cnt = cnt * 2
    Now += 2
  else:
    cnt = 0
    break

print(cnt % 1000000007)

Submission status: Wrong Answer

Solution code:
# どこでTLEになっているかテスト

import sys

mod = 10 ** 9 + 7
n, m, *a = [int(x) for x in sys.stdin.read().split()]

dp = [0] * (n + 2)
dp[0] = 0
dp[1] = 1
for i in range(2, n+2):
    # if i - 1 in a:
    #     if dp[i-1] == 0:
    #         print(0)
    #         sys.exit()
    #     else:
    #         dp[i] = 0
    # else:
    dp[i] = (dp[i-1] + dp[i-2]) % mod

print(dp[-1])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N, M = map(int,input().split())
hole = [0] * (N+1)
for i in range(M):
    hole[int(input())] = 1
if N == 1:
    print(1)
    exit()
if N == 2:
    if hole[1] == 1:
        print(1)
        exit()
    if hole[1] == 0:
        print(2)
        exit()
flg_one = False
flg_two = False
if hole[1] == 1:
    first = 0
    second = 1
    flg_one = True
elif hole[2] == 1:
    first = 1
    second = 0
    flg_two = True
else:
    first = 1
    second = 2

if flg_one and flg_two:
    print(0)
    exit()
for i in range(3,N):
    if hole[i] == 1:
        first = second
        second = 0
        continue
    tmp = first + second
    tmp %= 1000000007
    first = second
    second = tmp
tmp = first + second
tmp %= 1000000007
print(tmp)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N, M = map(int,input().split())
hole = [0] * (N+1)
for i in range(M):
    hole[int(input())] = 1
if N == 1:
    if hole[1] == 1:
        print(0)
        exit()
    print(1)
    exit()
if N == 2:
    if hole[1] == 1:
        print(1)
        exit()
    if hole[1] == 0:
        print(2)
        exit()
flg_one = False
flg_two = False
if hole[1] == 1:
    first = 0
    second = 1
    flg_one = True
elif hole[2] == 1:
    first = 1
    second = 0
    flg_two = True
else:
    first = 1
    second = 2

if flg_one and flg_two:
    print(0)
    exit()
flg = False

for i in range(3,N):
    if hole[i] == 1:
        if flg:
            print(0)
            exit()
        flg = True
        first = second
        second = 0
        flg = False
        continue
    tmp = first + second
    tmp %= 1000000007
    first = second
    second = tmp
    flg = False
tmp = first + second
tmp %= 1000000007
print(tmp)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N, M = map(int,input().split())
hole = [0] * (N+1)
for i in range(M):
    hole[int(input())] = 1
if N == 1:
    print(1)
    exit()
if N == 2:
    if hole[1] == 1:
        print(1)
        exit()
    if hole[1] == 0:
        print(2)
        exit()
flg_one = False
flg_two = False
if hole[1] == 1:
    first = 0
    second = 1
    flg_one = True
elif hole[2] == 1:
    first = 1
    second = 0
    flg_two = True
else:
    first = 1
    second = 2

if flg_one and flg_two:
    print(0)
    exit()
flg = False

for i in range(3,N):
    if hole[i] == 1:
        if flg:
            print(0)
            exit()
        flg = True
        first = second
        second = 0
        flg = False
        continue
    tmp = first + second
    tmp %= 1000000007
    first = second
    second = tmp
    flg = False
tmp = first + second
tmp %= 1000000007
print(tmp)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N, M = map(int,input().split())
hole = [0] * (N+1)
for i in range(M):
    hole[int(input())] = 1
if N == 1:
    print(1)
    exit()
if N == 2 and hole[0] == 0:
    print(1)
    exit()
flg_one = False
flg_two = False
if hole[1] == 1:
    first = 0
    second = 1
    flg_one = True
elif hole[2] == 1:
    first = 1
    second = 0
    flg_two = True
else:
    first = 1
    second = 2

if flg_one and flg_two:
    print(0)
    exit()
flg = False

for i in range(3,N):
    if hole[i] == 1:
        if flg:
            print(0)
            exit()
        flg = True
        first = second
        second = 0
        flg = False
        continue
    tmp = first + second
    tmp %= 1000000007
    first = second
    second = tmp
    flg = False
tmp = first + second
tmp %= 1000000007
print(tmp)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N, M = map(int,input().split())
hole = [0] * (N+1)
for i in range(M):
    hole[int(input())] = 1
if N == 1:
    print(1)
    exit()
if N == 2 and hole[0] == 0:
    print(2)
    exit()
flg_one = False
flg_two = False
if hole[1] == 1:
    first = 0
    second = 1
    flg_one = True
elif hole[2] == 1:
    first = 1
    second = 0
    flg_two = True
else:
    first = 1
    second = 2

if flg_one and flg_two:
    print(0)
    exit()
flg = False

for i in range(3,N):
    if hole[i] == 1:
        if flg:
            print(0)
            exit()
        flg = True
        first = second
        second = 0
        flg = False
        continue
    tmp = first + second
    tmp %= 1000000007
    first = second
    second = tmp
    flg = False
tmp = first + second
tmp %= 1000000007
print(tmp)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N, M = map(int,input().split())
hole = [0] * (N+1)
for i in range(M):
    hole[int(input())] = 1
if N == 1:
    print(1)
    exit()
if N == 2 and hole[0] == 1:
    print(1)
    exit()
flg_one = False
flg_two = False
if hole[1] == 1:
    first = 0
    second = 1
    flg_one = True
elif hole[2] == 1:
    first = 1
    second = 0
    flg_two = True
else:
    first = 1
    second = 2

if flg_one and flg_two:
    print(0)
    exit()
flg = False

for i in range(3,N):
    if hole[i] == 1:
        if flg:
            print(0)
            exit()
        flg = True
        first = second
        second = 0
        flg = False
        continue
    tmp = first + second
    tmp %= 1000000007
    first = second
    second = tmp
    flg = False
tmp = first + second
tmp %= 1000000007
print(tmp)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N, M = map(int,input().split())
hole = [0] * (N+1)
for i in range(M):
    hole[int(input())] = 1
if N == 1:
    print(1)
    exit()
if N == 2 and len(hole) == 1:
    print(1)
    exit()
flg_one = False
flg_two = False
if hole[1] == 1:
    first = 0
    second = 1
    flg_one = True
elif hole[2] == 1:
    first = 1
    second = 0
    flg_two = True
else:
    first = 1
    second = 2

if flg_one and flg_two:
    print(0)
    exit()
flg = False

for i in range(3,N):
    if hole[i] == 1:
        if flg:
            print(0)
            exit()
        flg = True
        first = second
        second = 0
        flg = False
        continue
    tmp = first + second
    tmp %= 1000000007
    first = second
    second = tmp
    flg = False
tmp = first + second
tmp %= 1000000007
print(tmp)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N, M = map(int,input().split())
if N == 1:
    print(1)
    exit()
hole = [0] * (N+1)
for i in range(M):
    hole[int(input())] = 1
flg_one = False
flg_two = False
if hole[1] == 1:
    first = 0
    second = 1
    flg_one = True
elif hole[2] == 1:
    first = 1
    second = 0
    flg_two = True
else:
    first = 1
    second = 2

if flg_one and flg_two:
    print(0)
    exit()
flg = False

for i in range(3,N):
    if hole[i] == 1:
        if flg:
            print(0)
            exit()
        flg = True
        first = second
        second = 0
        flg = False
        continue
    tmp = first + second
    tmp %= 1000000007
    first = second
    second = tmp
    flg = False
tmp = first + second
tmp %= 1000000007
print(tmp)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N, M = map(int,input().split())
if N == 1:
    print(1)
    exit()
if N == 2:
    print(2)
    exit()
hole = [0] * (N+1)
for i in range(M):
    hole[int(input())] = 1
flg_one = False
flg_two = False
if hole[1] == 1:
    first = 0
    second = 1
    flg_one = True
elif hole[2] == 1:
    first = 1
    second = 0
    flg_two = True
else:
    first = 1
    second = 2

if flg_one and flg_two:
    print(0)
    exit()
flg = False

for i in range(3,N):
    if hole[i] == 1:
        if flg:
            print(0)
            exit()
        flg = True
        first = second
        second = 0
        flg = False
        continue
    tmp = first + second
    tmp %= 1000000007
    first = second
    second = tmp
    flg = False
tmp = first + second
tmp %= 1000000007
print(tmp)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N, M = map(int,input().split())
hole = [0] * M
for i in range(M):
    hole[i] = int(input())
if 1 in hole:
    first = 0
    second = 1
elif 2 in hole:
    first = 1
    second = 0
else:
    first = 1
    second = 2

if first == 0 and second == 0:
    print(0)
    exit()
flg = False

for i in range(3,N):
    if i in hole:
        if flg:
            print(0)
            exit()
        flg = True
        first = second
        second = 0
        flg = False
        continue
    tmp = first + second
    tmp %= 1000000007
    first = second
    second = tmp
    flg = False
tmp = first + second
tmp %= 1000000007
print(tmp)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N, M = map(int,input().split())
hole = [0] * M
for i in range(M):
    hole[i] = int(input())
if 1 in hole:
    first = 0
    second = 1
elif 2 in hole:
    first = 1
    second = 0
else:
    first = 1
    second = 2

if first == 0 and second == 0:
    print(0)
    exit()
flg = False

for i in range(3,N):
    if i in hole:
        if flg:
            print(0)
            exit()
        flg = True
        first = second
        second = 0
        flg = False
        continue
    tmp = first + second
    first = second
    second = tmp
    flg = False
tmp = first + second
tmp %= 1000000007
print(tmp)

Submission status: Wrong Answer

Solution code:
import sys
n,m=map(int,input().split())
a=[]
step=[0]*(n+1)
step[0]=1
for i in range(m):
  a.append(int(input()))
if 1 in a:
  step[1]=0
else:
  step[1]=1
for j in range(m-1):
  if a[j+1]-a[j]==1:
    print(0)
    sys.exit()

j=0
while j<n-1:
  if j+1 in a:
    step[j+2]=step[j]
    if (10**9)+7<=step[j+2]:
      step[j+2]=step[j+2]%((10**9)+7)
    j+=2
  else:
    if j+2 in a:
      step[j+3]=step[j+1]
      if (10**9)+7<=step[j+3]:
        step[j+3]=step[j+3]%((10**9)+7)
      j+=3
    else:
      step[j+2]=step[j]+step[j+1]
      if (10**9)+7<=step[j+2]:
        step[j+2]=step[j+2]%((10**9)+7)
      j+=2
print(step[n])

Submission status: Wrong Answer

Solution code:
import sys
n,m=map(int,input().split())
a=[]
step=[0]*(n+1)
step[0]=1
for i in range(m):
  a.append(int(input()))
if 1 in a:
  step[1]=0
else:
  step[1]=1
for j in range(m-1):
  if a[j+1]-a[j]==1:
    print(0)
    sys.exit()

j=0
while j<n-1:
  if j+1 in a:
    step[j+2]=step[j]
    if (10**9)+7<=step[j+2]:
      step[j+2]=step[j+2]%((10**9)+7)
    j+=2
  else:
    if j+2 in a:
      step[j+1]=step[j]
      if (10**9)+7<=step[j+1]:
        step[j+1]=step[j+1]%((10**9)+7)
      j+=1
    else:
      step[j+2]=step[j]+step[j+1]
      if (10**9)+7<=step[j+2]:
        step[j+2]=step[j+2]%((10**9)+7)
      j+=2
print(step[n])

Submission status: Wrong Answer

Solution code:
import sys
n,m=map(int,input().split())
a=[]
step=[0]*(n+1)
step[0]=1
for i in range(m):
  a.append(int(input()))
if 1 in a:
  step[1]=0
else:
  step[1]=1
for j in range(m-1):
  if a[j+1]-a[j]==1:
    print(0)
    sys.exit()

j=0
while j<n-1:
  if j+1 in a:
    step[j+2]=step[j]
    if (10**9)+7<=step[j+2]:
      step[j+2]=step[j+2]%((10**9)+7)
    j+=2
  else:
    if j+2 in a:
      step[j+3]=step[j]
      if (10**9)+7<=step[j+3]:
        step[j+3]=step[j+3]%((10**9)+7)
      j+=3
    else:
      step[j+2]=step[j]+step[j+1]
      if (10**9)+7<=step[j+2]:
        step[j+2]=step[j+2]%((10**9)+7)
      j+=2
print(step[n])