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=[]
B=[]
a=[]
a.append(0)
x=0
d=1
A.append(1)
A.append(2)
B.append(1)
B.append(1)
for j in range(2,N):
    A.append(A[j-1]+A[j-2])
    B.append(B[j-1]+B[j-2])
for i in range(1,M+1):
    a.append(int(input()))
    if a[i-1]==0:
        if a[i]==1:
            d=1
        else:
            x=A[a[i]-a[i-1]-2]
            d=d*x%(10**9+7)
    else:
        x=B[a[i]-a[i-1]-2]
        d=d*x%(10**9+7)
    if i>1:
        if a[i]-a[i-1]==1:
            d=0
c=N-a[M]
if c==1:
    print(d)
else:
    x=A[N-a[M]-2]
    d=d*x%(10**9+7)
    print(d)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys
n,m=map(int,input().split())
if m==0:
    x=1
    y=2
    for i in range(n-2):
        if x<y:
            x+=y%1000000007
        else:
            y+=x%1000000007
    print(max(x,y)%1000000007)
    sys.exit()
a=list(int(input()) for i in range (m))

x=['']*n
x[0]=x[1]=0
if a[0]==1:
    x[0]=0
else:
    x[0]=1

if m>=2:
	if a[0]!=2 and a[1]!=2:
		x[1]=x[0]+1
    

else:
    if a[0]!=2:
	       x[1]=x[0]+1
    elif a[0]==2:
        x[1]=0


for z in range(m):
    x[a[z]-1]=0
        
if n>=3:
    for k in range(2,n):
        if x[k]!=0:
            x[k]=x[k-2]%1000000007+x[k-1]%1000000007
            
elif n==1:
    print(1)
    sys.exit()
    
elif n==2:
    print(x[0]+1)
    sys.exit()
    
print(x[n-1]%1000000007)

Submission status: Wrong Answer

Solution code:
import sys
n,m=map(int,input().split())
if m==0:
    x=1
    y=2
    for i in range(n-2):
        if x<y:
            x+=y%1000000007
        else:
            y+=x%1000000007
    print(max(x,y)%1000000007)
    sys.exit()
a=list(int(input()) for i in range (m))

x=['']*n
if a[0]==1:
    x[0]=0
else:
    x[0]=1

if m>=2:
	if a[0]!=2 and a[1]!=2:
		x[1]=x[0]+1
    

else:
    if a[0]!=2:
	       x[1]=x[0]+1
    elif a[0]==2:
        x[1]=0


for z in range(m):
    x[a[z]-1]=0
        
if n>=3:
    for k in range(2,n):
        if x[k]!=0:
            x[k]=x[k-2]%1000000007+x[k-1]%1000000007
            
elif n==1:
    print(1)
    sys.exit()
    
elif n==2:
    print(x[0]+1)
    sys.exit()
    
print(x[n-1]%1000000007)

Submission status: Wrong Answer

Solution code:
import sys
n,m=map(int,input().split())
if m==0:
    x=1
    y=2
    for i in range(n-2):
        if x<y:
            x+=y%1000000007
        else:
            y+=x%1000000007
    print(max(x,y)%1000000007)
    sys.exit()
a=list(int(input()) for i in range (m))

x=['']*n
if a[0]==1:
    x[0]=0
else:
    x[0]=1

if m>=2:
	if a[0]!=2 and a[1]!=2:
		x[1]=x[0]+1
    

else:
    if a[0]!=2:
	       x[1]=x[0]+1
    elif a[0]==2:
        x[1]=0


for z in range(m):
    x[a[z]-1]=0
        
if n>=4:
    for k in range(2,n):
        if x[k]!=0:
            x[k]=x[k-2]%1000000007+x[k-1]%1000000007
            
elif n==1:
    print(1)
    sys.exit()
    
elif n==2:
    print(x[0]+1)
    sys.exit()
    
print(x[n-1]%1000000007)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
a=[]
for i in range(m):
    a.append(int(input()))
res=1
count=0
for i in range(n):
    if i+1 in a and i+2 in a:
            res=0
            break
    else:
        if i not in a:
            if i<n-1:
                if i+1 not in a:
                    count+=1
                if i+2 not in a:
                    count+=1
                res=res*count
                print(count)
                count=0
print((res)%1000000007)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
mod = 10**9+7
n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
count = [0 for _ in range(n+1)]
for num in a:
  count[num] = -1
count[1] = 1
if len(count) >= 3:
  count[2] = 1
for i in range(2, n+1):
  if count[i] != -1:
    count[i] += (count[i-1] + count[i-2])%mod
  else:
    count[i] = 0

print(count[-1])

Submission status: Wrong Answer

Solution code:
import numpy as np

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

ans = np.zeros(N + 1)
ans[N] = 1

if N - 1 not in a:
    ans[N - 1] = 1

print(ans[N])

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

Submission status: Wrong Answer

Solution code:
import numpy as np

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

ans = np.zeros(N + 1)
ans[N] = 1

if N - 1 not in a:
    ans[N - 1] = 1

print(ans[N])

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
N, M = [int(nm) for nm in input().split()]
A = []
for m in range(M):
  A.append(int(input()))

C = [1, 0] # [-2段目, -1段目]
C += [0]*(N+10) # C = [-2段目, -1段目, 0段目, 1段目, 2段目, ...]
for n in range(0, N+1):
  if n not in A:
    C[n+2] = C[n] + C[n+1]
  else: # n in A:
    C[n+2] = 0

ans = C[N+2]
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
def main():
    N,M = map(int,input().split())
    A = [int(input()) for i in range(M)]
    MOD = 1000000007
    ans = []
    ans.append(0) if 1 in A else ans.append(1)
    ans.append(0) if 2 in A else ans.append(1)
    for i in range(2,N):
        ans.append(0)
        if i+1 in A:
            continue
        ans[i] += (ans[i-1] + ans[i-2])
    print(ans[N-1] % MOD)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N,m = map(int,input().split())
A = list(int(input()) for i in range(m))
A.append(N+1)
def Fibonacci(n):
    a=[1,1]
    if n <= 1:
        return a[n]
    else:#nが2以上
        for i in range(2,n+1):
            a.append(a[i-1]+a[i-2])
        return a[n]

for i in range(0,m):
    if A[i+1] == A[i] + 1:
        print(0)
        exit()
All = Fibonacci(A[0]-1)
for i in range(m):
    All *= Fibonacci( (A[i+1] - 1) - (A[i] + 1) )
    print(All)
print(All%1000000007)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
a = set([int(input()) for _ in range(m)])
print(a)
dp = [0] * (n+1)
dp[0] = 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:
#coding utf-8
N,M=map(int,input().split())
a =[int(input()) for i in range(M)]
mod =10**9+7
dp = [1]
for i in range(1,N+1):
  if i in a:
    dp.append(0)
  else:
    dp.append((dp[i-1]+dp[i-2])%mod)

print(dp[-1])

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
a, stack = [0]*(n+1), [0]*(n+1)
for _ in range(m):
    ai = int(input())
    a[ai] = 1
stack[0] = 1
for i in range(1, n+1):
    if a[i] == 1:
        pass
    else:
        stack[i] = stack[i-1] + stack[i-2]
print(stack[-1])

Submission status: Wrong Answer

Solution code:
def Fib(n):
    a, b = 1, 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
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]

flag = True
if M == 1:
    print(Fib(a[0])*Fib(N-a[M-1]))
elif M == 0:
    print(Fib(N))
else:
    m = Fib(a[0])*Fib(N-a[M-1])
    for i in range(M-1):
        if a[i] + 1 == a[i+1]:
            print(0)
            flag = False
            break
    if flag:
        for j in range(M-1):
            dev = a[j+1]-a[j]-1
            m = m*Fib(dev)%1000000007
        print(m%1000000007)

Submission status: Wrong Answer

Solution code:
def Fib(n):
    a, b = 1, 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
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]

flag = True
if M == 1:
    print(Fib(a[0])*Fib(N-a[M-1]))
elif M == 0:
    print(Fib(N+1))

Submission status: Wrong Answer

Solution code:
def Fib(n):
    a, b = 1, 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
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]

flag = True
if M == 1:
    print(Fib(a[0])*Fib(N-a[M-1]))
elif M == 0:
    print(Fib(N+1))
else:
    m = Fib(a[0])*Fib(N-a[M-1])
    for i in range(M-1):
        if a[i] + 1 == a[i+1]:
            print(0)
            flag = False
            break
    if flag:
        for j in range(M-1):
            dev = a[j+1]-a[j]-1
            m = m*Fib(dev)%1000000007
        print(m%1000000007)

Submission status: Wrong Answer

Solution code:
def Fib(n):
    a, b = 1, 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
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]

flag = True
if M == 1:
    print(Fib(a[0])*Fib(N-a[M-1]))
elif M == 0:
    print(Fib(N+1))
else:
    m = Fib(a[0])*Fib(N-a[M-1])
    for i in range(M-1):
        if a[i] + 1 == a[i+1]:
            print(0)
            flag = False
            break
    if flag:
        for j in range(M-1):
            dev = a[j+1]-a[j]-1
            m = m*Fib(dev)
        print(m%1000000007)

Submission status: Wrong Answer

Solution code:
def Fib(n):
    a, b = 1, 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
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]

flag = True
if M == 1:
    print(Fib(a[0])*Fib(N-a[M-1]))
elif M == 0:
    print(Fib(N+1))
else:
    m = Fib(a[0])*Fib(N-a[M-1])
    for i in range(M-1):
        if a[i] + 1 == a[i+1]:
            print(0)
            flag = False
            break
    if flag:
        for j in range(M-1):
            dev = a[j+1]-a[j]
            m = m*Fib(dev)
        print(m%1000000007)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
la = [int(input()) for i in range(m)]

p = [1] * (n+1)
ans = 0

for a in la:
	p[a] = 0

for i in range(n+1):
	if i == 0 and p[i] == 0:
		ans = 0
		break
	elif i > 1:
		if p[i] == 0 and p[i-1] == 0:
			ans = 0
			break
		elif p[i] > 0:
			ans = p[i-1] + p[i-2]
			p[i] = ans

print(ans % (10**9+7))

Submission status: Wrong Answer

Solution code:
Mod = 10**9+7
N,M = map(int, input().split())
a = [int(input()) for _ in range(M)]
b = [1]+[0]*N
t = 1
t_1 = 0
t_2 = 0
for i in range(1,N+1):
    if i in a:
        t_1 = t
        t = 0
        continue
    if i == 1:
        t += b[0]
        b[1] = t 
        continue
    t_2 = t_1
    t_1 = t
    t = 0
    t += t_2 + t_1
    b[i] += t
print(b[N]%Mod)

Submission status: Wrong Answer

Solution code:
def nCk(n, k):
    return bunshi(n,k)/bunbo(k)
def bunshi(n,k):
    p = 1
    for i in range(k):
        p = p*(n-i)
    return p%1000000007
def bunbo(k):
    p = 1
    for i in range(k):
        p = p*(i+1)
    return p%1000000007
    

N, M = map(int,input().split())
a=[-1]
for i in range(M):
    a.append(int(input()))
a.append(N+1)
#print(a)
D=[]
for i in range(M+1):
    D.append((a[i+1]-1)-(a[i]+1))
#print(D)

ans=1
for i in range(len(D)):
    temp = 0
    for j in range(D[i]//2+1):
        temp += ((nCk(D[i]-j,j))%1000000007)
    ans=(ans%1000000007)*(temp%1000000007)
print(int(ans%1000000007))

Submission status: Wrong Answer

Solution code:
def nCk(n, k):
    return fact(n)/(fact(k)*fact(n-k))
def fact(x):
    p = 1
    for i in range(x):
        p = p*(i+1)
    return p

N, M = map(int,input().split())
a=[-1]
for i in range(M):
    a.append(int(input()))
a.append(N+1)
#print(a)
D=[]
for i in range(M+1):
    D.append((a[i+1]-1)-(a[i]+1))
#print(D)

ans=1
for i in range(len(D)):
    temp = 0
    for j in range(D[i]//2+1):
        temp += nCk(D[i]-j,j)
    ans=(ans%1000000007)*(temp%1000000007)
print(int(ans%1000000007))

Submission status: Wrong Answer

Solution code:
def nCk(n, k):
    return fact(n)/(fact(k)*fact(n-k))
def fact(x):
    p = 1
    for i in range(x):
        p = p*(i+1)
    return p

N, M = map(int,input().split())
a=[-1]
for i in range(M):
    a.append(int(input()))
a.append(N+1)
#print(a)
D=[]
for i in range(M+1):
    D.append((a[i+1]-1)-(a[i]+1))
#print(D)

ans=1
for i in range(len(D)):
    temp = 0
    for j in range(D[i]//2+1):
        temp += nCk(D[i]-j,j)
#    print(temp)
    ans=(ans*temp)%1000000007
print(int(ans%1000000007))

Submission status: Wrong Answer

Solution code:
def nCk(n, k):
    return fact(n)/(fact(k)*fact(n-k))
def fact(x):
    p = 1
    for i in range(x):
        p = p*(i+1)
    return p

N, M = map(int,input().split())
a=[-1]
for i in range(M):
    a.append(int(input()))
a.append(N+1)
#print(a)
D=[]
for i in range(M+1):
    D.append((a[i+1]-1)-(a[i]+1))
#print(D)

ans=1
for i in range(len(D)):
    if i !=len(D) and i!=0 and D[i]==0:
        temp = 0
    else:
        temp = 0
        for j in range(D[i]//2+1):
            temp += nCk(D[i]-j,j)
#    print(temp)
    ans=(ans*temp)%1000000007
print(int(ans%1000000007))

Submission status: Wrong Answer

Solution code:
import math

N, M = map(int,input().split())
a=[-1]
for i in range(M):
    a.append(int(input()))
a.append(N+1)
#print(a)
D=[]
for i in range(M+1):
    D.append((a[i+1]-1)-(a[i]+1))
#print(D)
def nCk(n, k):
    return math.factorial(n)/(math.factorial(k)*math.factorial(n-k))
ans=1
for i in range(len(D)):
    if i !=len(D) and i!=0 and D[i]==0:
        temp = 0
    else:
        temp = 0
        for j in range(D[i]//2+1):
            temp += nCk(D[i]-j,j)
#    print(temp)
    ans=(ans*temp)%1000000007
print(int(ans%1000000007))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:

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

def fib(x):
    a = 1
    b = 1
    if x == 0:
        return 0
    elif x == 1:
        return a
    elif x == 2:
        return b
    else:
        for i in range(x-2):
            c = a + b
            a = b
            b = c
        return b 

before_a=1
output = 1
# A.append(N)
for a in A:
    sa = a-before_a-1
    before_a = a
    output *= fib(sa)
output *= fib(N-before_a)
    
for i in range(len(A)-1):
    if A[i]+1 == A[i+1]:
        output=0
        break
print(output%1000000007)

Submission status: Wrong Answer

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

dp = [0]*(N+1)
dp[0] = 1
ans = 0

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

print(ans)

Submission status: Wrong Answer

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

if 1 in a:
  fibo=[1,0]
else:
  fibo=[1,1]
mod=10**9+7
for i in range(2,n-1):
  if i in a:
    fibo[i-1]=0
  f=(fibo[-2]+fibo[-1])%mod
  fibo.append(f)

print(fibo[-1])

Submission status: Wrong Answer

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

dp = [0]*(N+1)
dp[0] = 1

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

print(dp[-1])

Submission status: Wrong Answer

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

fibo=[1,1]
mod=10**9+7
for i in range(n-1):
  if i in a:
    fibo[i]=0
    fibo[i+1]=(fibo[i-1]+fibo[i])%mod

  f=(fibo[-2]+fibo[-1])%mod
  fibo.append(f)
print(fibo[-1])

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

dp = [1, 2]
A = [int(input()) for _ in range(M)]
if M != 0:
    if M >= 2 and A[0] == 1 and A[1] == 2:
        dp = [0, 0]
    elif A[0] == 1:
        dp = [0, 1]
    elif A[0] == 2:
        dp = [1, 0]
else:
    A = [0]

MOD = 1000000007

if N == 1:
    print (0)
if N == 2:
    print (dp[-1])
else:
    cnt = 0
    for n in range(2, N):
        while(cnt < M - 1 and A[cnt] < n + 1):
            cnt += 1
        if A[cnt] == n + 1:
            dp[0] = dp[1]
            dp[1] = 0
        else:
            new_val = (max(dp[0], 0) + max(dp[1], 0)) % MOD
            dp[0] = dp[1]
            dp[1] = new_val

    print (dp[-1])

Submission status: Wrong Answer

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

dp = [1, 2]
A = [int(input()) for _ in range(M)]
if M != 0:
    if M >= 2 and A[0] == 1 and A[1] == 2:
        dp = [0, 0]
    elif A[0] == 1:
        dp = [0, 1]
    elif A[0] == 2:
        dp = [1, 0]
else:
    A = [0]

MOD = 1000000007

if N == 1:
    print (dp[0])
if N == 2:
    print (dp[-1])
else:
    cnt = 0
    for n in range(2, N):
        while(cnt < M - 1 and A[cnt] < n + 1):
            cnt += 1
        if A[cnt] == n + 1:
            dp[0] = dp[1]
            dp[1] = 0
        else:
            new_val = (max(dp[0], 0) + max(dp[1], 0)) % MOD
            dp[0] = dp[1]
            dp[1] = new_val

    print (dp[-1])

Submission status: Wrong Answer

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

dp = [1, 2]
A = [int(input()) for _ in range(M)]
if M != 0:
    if M >= 2 and A[0] == 1 and A[1] == 2:
        dp = [0, 0]
    elif A[0] == 1:
        dp = [0, 1]
    elif A[0] == 2:
        dp = [1, 0]
else:
    A = [0]

MOD = 1000000007

if N == 1:
    print (1)
if N == 2:
    print (dp[-1])
else:
    cnt = 0
    for n in range(2, N):
        while(cnt < M - 1 and A[cnt] < n + 1):
            cnt += 1
        if A[cnt] == n + 1:
            dp[0] = dp[1]
            dp[1] = 0
        else:
            new_val = (max(dp[0], 0) + max(dp[1], 0)) % MOD
            dp[0] = dp[1]
            dp[1] = new_val

    print (dp[-1])

Submission status: Wrong Answer

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

dp = [1, 2]
A = [int(input()) for _ in range(M)]
if M != 0:
    if M > 2 and A[0] == 1 and A[1] == 2:
        dp = [0, 0]
    elif A[0] == 1:
        dp = [0, 1]
    elif A[0] == 2:
        dp = [1, 0]
else:
    A = [0]

MOD = 1000000007

if N == 1:
    print (1)
if N == 2:
    print (dp[-1])
else:
    cnt = 0
    for n in range(2, N):
        while(cnt < M - 1 and A[cnt] < n + 1):
            cnt += 1
        if A[cnt] == n + 1:
            dp[0] = dp[1]
            dp[1] = 0
        else:
            new_val = (max(dp[0], 0) + max(dp[1], 0)) % MOD
            dp[0] = dp[1]
            dp[1] = new_val

    print (dp[-1])

Submission status: Wrong Answer

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

dp = [1, 2]
if M != 0:
    A = [int(input()) for _ in range(M)]
    if M > 2 and A[0] == 1 and A[1] == 2:
        dp = [0, 0]
    elif A[0] == 1:
        dp = [0, 1]
    elif A[0] == 2:
        dp = [1, 0]
else:
    A = [0]

MOD = 1000000007

if N == 1:
    print (1)
if N == 2:
    print (dp[-1])
else:
    cnt = 0
    for n in range(2, N):
        while(cnt < M - 1 and A[cnt] < n + 1):
            cnt += 1
        if A[cnt] == n + 1:
            dp[0] = dp[1]
            dp[1] = 0
        else:
            new_val = (max(dp[0], 0) + max(dp[1], 0)) % MOD
            dp[0] = dp[1]
            dp[1] = new_val

    print (dp[-1])

Submission status: Wrong Answer

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

dp = [1, 2]
if M != 0:
    A = [int(input()) for _ in range(M)]
    if M > 2 and A[0] == 1 and A[1] == 2:
        dp = [0, 0]
    elif A[0] == 1:
        dp = [0, 1]
    elif A[0] == 2:
        dp = [1, 0]
else:
    A = [0]

MOD = 1000000007

if N == 1:
    print (1)
if N == 2:
    print (1)
else:
    cnt = 0
    for n in range(2, N):
        while(cnt < M - 1 and A[cnt] < n + 1):
            cnt += 1
        if A[cnt] == n + 1:
            dp[0] = dp[1]
            dp[1] = 0
        else:
            new_val = (max(dp[0], 0) + max(dp[1], 0)) % MOD
            dp[0] = dp[1]
            dp[1] = new_val

print (dp[-1])

Submission status: Wrong Answer

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

dp = [1, 2]
if M != 0:
    A = [int(input()) for _ in range(M)]
    if M > 2 and A[0] == 1 and A[1] == 2:
        dp = [0, 0]
    elif A[0] == 1:
        dp = [0, 1]
    elif A[0] == 2:
        dp = [1, 0]
else:
    A = [0]

MOD = 1000000007

if N == 1:
    print (1)
if N == 2:
    print (2)
else:
    cnt = 0
    for n in range(2, N):
        while(cnt < M - 1 and A[cnt] < n + 1):
            cnt += 1
        if A[cnt] == n + 1:
            dp[0] = dp[1]
            dp[1] = 0
        else:
            new_val = (max(dp[0], 0) + max(dp[1], 0)) % MOD
            dp[0] = dp[1]
            dp[1] = new_val

print (dp[-1])

Submission status: Wrong Answer

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

dp = [1, 2]
if M != 0:
    A = [int(input()) for _ in range(M)]
    if M > 2 and A[0] == 1 and A[1] == 2:
        dp = [0, 0]
    elif A[0] == 1:
        dp = [0, 1]
    elif A[0] == 2:
        dp = [1, 0]
else:
    A = [0]

MOD = 1000000007

if N == 1:
    print (0)
if N == 2:
    print (dp[-1])
else:
    cnt = 0
    for n in range(2, N):
        while(cnt < M - 1 and A[cnt] < n + 1):
            cnt += 1
        if A[cnt] == n + 1:
            dp[0] = dp[1]
            dp[1] = 0
        else:
            new_val = (max(dp[0], 0) + max(dp[1], 0)) % MOD
            dp[0] = dp[1]
            dp[1] = new_val

print (dp[-1])

Submission status: Wrong Answer

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

dp = [1, 2]
if M != 0:
    A = [int(input()) for _ in range(M)]
    if M > 2 and A[0] == 1 and A[1] == 2:
        dp = [0, 0]
    elif A[0] == 1:
        dp = [0, 1]
    elif A[0] == 2:
        dp = [1, 0]
else:
    A = [0]

MOD = 1000000007

if N == 1:
    print (1)
if N == 2:
    print (dp[-1])
else:
    cnt = 0
    for n in range(2, N):
        while(cnt < M - 1 and A[cnt] < n + 1):
            cnt += 1
        if A[cnt] == n + 1:
            dp[0] = dp[1]
            dp[1] = 0
        else:
            new_val = (max(dp[0], 0) + max(dp[1], 0)) % MOD
            dp[0] = dp[1]
            dp[1] = new_val

print (dp[-1])

Submission status: Wrong Answer

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

dp = [1, 2]
if M != 0:
    A = [int(input()) for _ in range(M)]
    if A[0] == 1:
        dp = [0, 1]
    elif A[0] == 2:
        dp = [1, 0]
else:
    A = [0]

MOD = 1000000007

if N == 1:
    print (1)
if N == 2:
    print (dp[-1])
else:
    cnt = 0
    for n in range(2, N):
        while(cnt < M - 1 and A[cnt] < n + 1):
            cnt += 1
        if A[cnt] == n + 1:
            dp[0] = dp[1]
            dp[1] = 0
        else:
            new_val = (max(dp[0], 0) + max(dp[1], 0)) % MOD
            dp[0] = dp[1]
            dp[1] = new_val

print (dp[-1])

Submission status: Wrong Answer

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

dp = [1, 2]
if M != 0:
    A = [int(input()) for _ in range(M)]
    if A[0] == 1:
        dp = [0, 1]
    elif A[0] == 2:
        dp = [1, 0]
else:
    A = [0]

MOD = 1000000007

if N == 1:
    print (dp[0])
if N == 2:
    print (dp[-1])
else:
    cnt = 0
    for n in range(2, N):
        while(cnt < M - 1 and A[cnt] < n + 1):
            cnt += 1
        if A[cnt] == n + 1:
            dp[0] = dp[1]
            dp[1] = 0
        else:
            new_val = (max(dp[0], 0) + max(dp[1], 0)) % MOD
            dp[0] = dp[1]
            dp[1] = new_val

print (dp[-1])

Submission status: Wrong Answer

Solution code:
import numpy as np
N, M = map(int, input().split())

MOD = 1000000007
dp = np.zeros(N, dtype = int)
if M != 0:
    A = np.array([int(input()) for _ in range(M)], dtype = int)
    dp[A - 1] = -1

if dp[0] == -1 and dp[1] == -1:
    pass
elif dp[0] == -1:
    dp[1] = 1
# elif dp[1] == -1:
#     dp[0] = 1
# else:
#     dp[0] = 1
#     dp[1] = 2


if N >= 3:
    for n in range(2, N):
        if dp[n] != -1:
            dp[n] = (max(dp[n-1], 0) + max(dp[n-2], 0)) % MOD

print (dp[-1])

Submission status: Wrong Answer

Solution code:
import numpy as np
N, M = map(int, input().split())
if M == 1:
    A = int(input())
else:
    A = np.array([int(input()) for _ in range(M)], dtype = int)

MOD= 1000000007
dp = np.zeros(N, dtype = int)
dp[A - 1] = - 1
if dp[0] == -1 and dp[1] == -1:
    pass
elif dp[0] == -1:
    dp[1] = 1
# elif dp[1] == -1:
#     dp[0] = 1
# else:
#     dp[0] = 1; dp[1] = 2;


# if N >= 3:
#     for n in range(2, N):
#         if dp[n] != -1:
#             dp[n] = (max(dp[n-1], 0) + max(dp[n-2], 0)) % MOD

print (dp[-1])

Submission status: Wrong Answer

Solution code:
import numpy as np
N, M = map(int, input().split())
if M == 1:
    A = int(input())
else:
    A = np.array([int(input()) for _ in range(M)], dtype = int)

MOD= 1000000007
dp = np.zeros(N, dtype = int)
dp[A - 1] = - 1
# if dp[0] == -1 and dp[1] == -1:
#     pass
# elif dp[0] == -1:
#     dp[1] = 1
# elif dp[1] == -1:
#     dp[0] = 1
# else:
#     dp[0] = 1; dp[1] = 2;


# if N >= 3:
#     for n in range(2, N):
#         if dp[n] != -1:
#             dp[n] = (max(dp[n-1], 0) + max(dp[n-2], 0)) % MOD

print (dp[-1])

Submission status: Wrong Answer

Solution code:
import numpy as np
N, M = map(int, input().split())
if M == 1:
    A = int(input())
else:
    A = np.array([int(input()) for _ in range(M)], dtype = int)

MOD= 1000000007
dp = np.zeros(N, dtype = int)
# dp[A - 1] = - 1
# if dp[0] == -1 and dp[1] == -1:
#     pass
# elif dp[0] == -1:
#     dp[1] = 1
# elif dp[1] == -1:
#     dp[0] = 1
# else:
#     dp[0] = 1; dp[1] = 2;


# if N >= 3:
#     for n in range(2, N):
#         if dp[n] != -1:
#             dp[n] = (max(dp[n-1], 0) + max(dp[n-2], 0)) % MOD

print (dp[-1])

Submission status: Wrong Answer

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

s=[0]*n

for _ in range(m):
  s[int(input())-1]=""
  
#print(s)

if n==1:
  print(1)
  exit()
elif n==2:
  if s[0]=="":
    print(1)
  else:
    print(2)
  exit()
  
if s[0]=="":
  s[0]=0
  s[1]=1
elif s[1]=="":
  s[0]=1
  s[1]=0
else:
  s[0]=1
  s[1]=2

i=2
while i<n:
  if s[i]=="":
    s[i]=0
  else:
    s[i]=s[i-1]+s[i-2]
  i+=1
print(s[-1]%1000000007)

Submission status: Wrong Answer

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

s=[0]*n

for _ in range(m):
  s[int(input())-1]=""
  
#print(s)

if n==1:
  print(1)
  exit()
elif n==2:
  if s[0]=="":
    print(1)
  else:
    print(0)
  exit()
  
if s[0]=="":
  s[0]=0
  s[1]=1
elif s[1]=="":
  s[0]=1
  s[1]=0
else:
  s[0]=1
  s[1]=2

i=2
while i<n:
  if s[i]=="":
    s[i]=0
  else:
    s[i]=s[i-1]+s[i-2]
  i+=1
print(s[-1]%1000000007)

Submission status: Wrong Answer

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

s=[0]*n

for _ in range(m):
  s[int(input())-1]=""
  
#print(s)

if n==1:
  print(1)
  exit()
elif n==2:
  if s[0]=="":
    s[1]=1
  else:
    s[1]=2
  print(s[1])
  exit()
  
if s[0]=="":
  s[0]=0
  s[1]=1
elif s[1]=="":
  s[0]=1
  s[1]=0
else:
  s[0]=1
  s[1]=2

i=2
while i<n:
  if s[i]=="":
    s[i]=0
  else:
    s[i]=s[i-1]+s[i-2]
  i+=1
print(s[-1]%1000000007)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
l=[-1]
from math import factorial
for i in range(m):
  l.append(int(input()))
l.append(n+1)
ans=1
is_False=0
for i in range(m+1):
  if l[i+1]-l[i]<2:
    is_False+=1
  elif l[i+1]-l[i]>=2:
    a,s=l[i+1]-l[i]-2,0
    for n in range(a//2+1):
      s+=(factorial(a-n)/(factorial(n)*factorial(a-2*n)))%1000000007
    print(s)
    ans*=s
    ans=ans%1000000007
print(ans if is_False==0 else 0)