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:
#bin/usr/env python3

n,m = map(int, input().split())
mod = 10**9+7

br = [0 for i in range(n+2)]
for i in range(m):
    a = int(input())
    br[a] = 1

can = [0 for i in range(n+2)]

can[1] = 1
can[2] = 2

if br[1] == 1:
    can[2] = 1
if br[2] == 1:
    can[2] = 0

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

print(can[n])

Submission status: Wrong Answer

Solution code:
#bin/usr/env python3

n,m = map(int, input().split())
mod = 10**9+7

br = [0 for i in range(n+2)]
for i in range(m):
    a = int(input())
    br[a] = 1

can = [0 for i in range(n+2)]

can[1] = 1
can[2] = 2

if br[1] == 1:
    can[1] = 0
    can[2] = 1
if br[2] == 1:
    can[1] = 1
    can[2] = 0

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

print(can[n])

Submission status: Wrong Answer

Solution code:
n,m=list(map(int,input().split()))
a=[int(input()) for i in range(m)]
b=[0]*(n+1)
b[0]=1
if 1 not in a:
    b[1]=1
for i in range(2,n):
    if i in a:
        b[i]=0 #0の代入で2連続以上の場合もカバー
    else:
        b[i]=b[i-1]+b[i-2]
print(b[n]%1000000007)

Submission status: Wrong Answer

Solution code:
n,m=list(map(int,input().split()))
a=[int(input()) for i in range(m)]
n1,n2=1,0

for i in range(m-1):
  if a[i]+1==a[i+1]:
    print(0)
    exit()
  else:
    for j in range(1,n):
        if j in a:
            break
        else:
            if j-1 in a:
                n2=n1
            else:
                tmp=n1
                n1=n1+n2
                n2=tmp
    ans=n1%1000000007
    print(ans)

Submission status: Wrong Answer

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

for i in range(m-1):
  if a[i]+1==a[i+1]:
    print(0)
    exit()
    
n1,n2=1,0
for j in range(1,n):
  if j in a:
    break
  else:
    if j-1 in a:
        n2=n1
    else:
        tmp=n1
        n1=n1+n2
        n2=tmp
ans=n1%1000000007
print(ans)

Submission status: Wrong Answer

Solution code:
BASE =  1000000007

class Counter(object):
    def __init__(self):
        self.counter = []
    def append(self, elem):
        self.counter.append(elem)
    def getCount(self, idx):
        pass

if __name__ == '__main__':
    N, M = [int(i) for i in input().split()]
    not_available = set()
    for i in range(M):
        not_available.add(int(input()))
    x = 0
    y = 1
    predicted_next = 1
    available = {i + 1 for i in range(N)} - not_available
    for elem in available:
        if predicted_next + 2 <= elem:
            y = 0
            break
        elif predicted_next + 1 == elem:
            x = 0
            predicted_next = elem + 2
        else:
            z = x + y
            x = y
            y = z
            predicted_next = elem + 1
    print(y % BASE)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
A = [int(input()) for i in range(M)]
dp = [0] * (N + 1)
dp[0] = 1
dp[1] = 1
for i in range(2,N+1):
    if A.count(i) != 0 and A.count(i-1) != 0:
        print(0)
        exit(0)
    if A.count(i) != 0:
        dp[i] = 0
    else:
        dp[i] = dp[i - 1] + dp[i - 2]
#print(dp)
print(dp[N] % 1000000007)
#print(13 % 4)

Submission status: Wrong Answer

Solution code:
def fib(n):
    if n==1:
        a=1
        return ans
    if n==2:
        a=1
        return ans
    a0=1
    a1=1
    cnt=2
    while cnt <n:
        a=a0+a1
        cnt+=1
        a0=a1
        a1=a
    return a


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

mod=10**9+7

if N==1:
    print(1)
    exit()

a0=-1
ans=1
for i in range(M):
    a=int(input())
    n=(a-1)-(a0+1)
    if a-a0==1:
        print(0)
        exit()
    c=fib(n+1)
    ans=(ans*c)%mod
    a0=a

a = N+1
n = (a - 1) - (a0 + 1)
c = fib(n+1)
ans=(ans*c)%mod

print(ans)

Submission status: Wrong Answer

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

chk=[True]*(10**5+1)
for i in range(M):
    a=int(input())
    chk[a]=False

mod=10**9+7

if N==1:
    print(1)
    exit()

f=[0]*(N+1)

if chk[1]:
    f[1]=1
else:
    f[1]=0


for i in range(2,N+1):
    if chk[i-2]:
        f[i]+=f[i-2]
    if chk[i-1]:
        f[i]+=f[i-1]
    f[i]=f[i]%mod

print(f[N])

Submission status: Wrong Answer

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

mod=10**9+7

if N==1:
    print(1)
    exit()

f=[0]*(N+1)

if 0 in a:
    f[0]=0
else:
    f[0]=1

if 1 in a:
    f[1]=0
else:
    f[1]=f[0]+1

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

    f[i]=f[i]%mod

print(f[N-1])

Submission status: Wrong Answer

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

mod=10**9+7

if N==1:
    print(1)
    exit()

f=[0]*N

if 0 in a:
    f[0]=0
else:
    f[0]=1

if 1 in a:
    f[1]=1
else:
    f[1]=1+f[0]

for i in range(2,N):

    if i in a:
        f[i]=0
    else:
        f[i]=f[i-2]+f[i-1]

    f[i]=f[i]%mod

print(f[N-1])

Submission status: Wrong Answer

Solution code:
import math


def combi(a, b):
    ans = math.factorial(a) / (math.factorial(a - b) * math.factorial(b))
    ans=int(ans)
    return ans

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

mod=10**9+7

if N==1:
    print(1)
    exit()
if M>=N//2:
    print(0)
    exit()

a0=-1
ans=1
for i in range(M):
    a=int(input())
    n=(a-1)-(a0+1)
    if a-a0==1:
        print(0)
        exit()
    c=0
    for k in range(n // 2 + 1):
        c += combi(n - k, k) % mod
    ans=(ans*c)%mod
    a0=a

a = N+1
n = (a - 1) - (a0 + 1)
c = 0
for k in range(n // 2 + 1):
    c += combi(n - k, k) % mod
ans=(ans*c)%mod

print(ans)

Submission status: Wrong Answer

Solution code:
import math


def combi(a, b):
    ans = math.factorial(a) / (math.factorial(a - b) * math.factorial(b))
    ans=int(ans)
    return ans

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

mod=10**9+7

if N==1:
    print(1)
    exit()

if M==0:
    a=N-1

a0=-1
ans=1
for i in range(M):
    a=int(input())
    n=(a-1)-(a0+1)
    if a-a0==1:
        print(0)
        exit()
    c=0
    for k in range(n // 2 + 1):
        c += combi(n - k, k) % mod
    ans=(ans*c)%mod
    a0=a

a = N+1
n = (a - 1) - (a0 + 1)
c = 0
for k in range(n // 2 + 1):
    c += combi(n - k, k) % mod
ans=(ans*c)%mod

print(ans)

Submission status: Wrong Answer

Solution code:
import math


def combi(a, b):
    ans = math.factorial(a) / (math.factorial(a - b) * math.factorial(b))
    ans=int(ans)
    return ans

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

mod=10**9+7

if N==1:
    print(1)
    exit()

if M==0:
    a=N-1

a0=-1
cnt=[]
for i in range(M):
    a=int(input())
    n=(a-1)-(a0+1)
    if a-a0==1:
        print(0)
        exit()
    c=0
    for k in range(n // 2 + 1):
        c += combi(n - k, k) % mod
    cnt.append(c)
    a0=a

a = N+1
n = (a - 1) - (a0 + 1)
c = 0
for k in range(n // 2 + 1):
    c += combi(n - k, k) % mod
cnt.append(c)

ans=1
for i in range(len(cnt)):
    ans*=cnt[i]
    ans=ans%mod

print(ans)

Submission status: Wrong Answer

Solution code:
import math


def combi(a, b):
    ans = math.factorial(a) / (math.factorial(a - b) * math.factorial(b))
    ans=int(ans)
    return ans

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

mod=10**9+7

if N==1:
    print(1)
    exit()

if M==0:
    a=N-1

a0=-1
cnt=[]
for i in range(M):
    a=int(input())
    n=(a-1)-(a0+1)
    if a-a0==1:
        print(0)
        exit()
    c=0
    for k in range(n // 2 + 1):
        c += combi(n - k, k) % mod
    cnt.append(c)
    a0=a

if not a==N-1:
    a=N-1
    n = a - a0
    c = 0
    for k in range(n // 2 + 1):
        c += combi(n - k, k) % mod
    cnt.append(c)

ans=1
for i in range(len(cnt)):
    ans*=cnt[i]
    ans=ans%mod

print(ans)

Submission status: Wrong Answer

Solution code:
p = 10**9 + 7
n,m = list(map(int, input().split()))
a = set()
a = [a.add(int(input())) for _ in range(m)]

dp = [0 for i in range(n+2)]
dp[0] = 1

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

print(dp[-2]%p)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
A=[int(input()) for _ in range(M)]
n1,n2=1,2
ans=0
for i in range(3,N+1):
    if i in A:
        n1=n2%1000000007
        n2=0
    else:
        tmp=n2
        n2=(n1+n2)%1000000007
        n1=tmp
print(n2)

Submission status: Wrong Answer

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

ans=1


def fb(num):
    """num番目のフィボナッチ数を返す
    """
    a, b = 1, 1
    for i in range(num):
        a, b = a + b, a
    return b
    
#print(fb(0))
lista.append(n)

for i in range(m-1):
  if (lista[i]+1==lista[i+1])&(m>=2):
  	ans=0
else:
		if lista[0]!=1:
			ans=ans*(fb(lista[0]-1))
			for i in range(1,m):
					ans=ans*(fb(lista[i]-lista[i-1]-2))
					
		 
					
		if lista[0]==1:
			for i in range(1,m):
					ans=ans*(fb(lista[i]-lista[i-1]-2))
					
		
		ans= ans*(fb(lista[m]-lista[m-1]-1))
		
print(ans%1000000007)

Submission status: Wrong Answer

Solution code:
import sys,queue,copy
sys.setrecursionlimit(10**8)
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
INF = float('inf')

N,M = inpl()

alist = list()
for _ in range(M):
    alist.append(int(input()))

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

print(dp[N]%1000000007)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
a=[-1]
for i in range(m):
    s=int(input())
    a.append(s)  
a.append(n+1)
if 1 in a:
    a=a[1:]
if n-1 in a:
    a=a[:-1]
b=[]
for i in range(len(a)-1):
    b.append(a[i+1]-a[i]-2)
l=[0,1,2]
for i in range(3,n+1):
    l.append(l[i-2]+l[i-1])
ans=1

for i in range(len(b)):
    if b[i]<0:
        print(0)
        break
    else:
        ans*=l[b[i]]%1000000007
else:
    #print(a,b,l)
    print(ans%1000000007)

Submission status: Wrong Answer

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

fiblist=[1,1]
for j in range(10**5):
    nums=(fiblist[-1]+fiblist[-2])%(10**9+7)
    fiblist.append(nums)
lists.insert(0,0)
lists.append(n)
ans=1
for i in range(m+1):
    if i==0:
        ans=ans*fiblist[lists[1]-lists[0]-1]
        ans=ans%(10**9+7)
    elif i==m:
        ans=ans*fiblist[lists[m+1]-lists[m]-1]
        ans=ans%(10**9+7)
    elif i!=0 and i!=m:
        if lists[i+1]-lists[i]==1:
            ans=0
            break
        else:
            ans=ans*fiblist[lists[i+1]-lists[i]-2]
            ans=ans%(10**9+7)
print(ans)

Submission status: Wrong Answer

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

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

def keisan(a,b):
    count = 0
    n = b - a - 2
    r = 0

    while n >= r:

        count += combination(n,r)
        n -= 1
        r += 1

    return count

result = 1

if M == 0:
    keisan(-1,N+1)
    print(int(result)%1000000007)
    sys.exit()

for i in range(M):

    if i == 0:
        result *= keisan(-1,a[0])
        continue

    #階段の段が連続して壊れている場合は登れない
    if a[i] - a[i-1] == 1:
        result = 0
        break
    else:
        result *= keisan(a[i-1],a[i])


else:
    result *= keisan(a[M-1],N+1)

print(int(result)%1000000007)

Submission status: Wrong Answer

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

dp = [0]*(n+1)
dp[0] = 1
if a:
    if a[0]!=1:
        dp[1] = 1

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

Submission status: Wrong Answer

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

#フィボナッチ数列
def Fib(n):
    a, b = 0, 1
    if n == 1:
        return a
    elif n == 2:
        return b
    else:
        for i in range(n-2):
            a, b = b, a + b
        return b
 
for i in range(M):
  a = int(input())
  A.append(a)
#ans = {0~a1-1 a1+1~a2-1 ... a(M-1)+1~aM-1 の行き方の積}
#各a(i)+1~a(i+1)-1への行き方は1通り
#i ~ i+Nへの行き方 Fib(N+1)通り

#REになっていた理由:
#・Fib(0)が定義されていなかったから
#・フィボナッチ数列を再帰的(=Fib(n-1)+Fib(n-2))で定義していると、
#Nが大きい(100000とか）のときに深く潜りすぎるのでRE

if(N == 1): 
 ans = 1
elif(M == 0): 
 ans = Fib(N+1)
else: 
 ans = 0
 for i in range(M):  
    if(i == 0): #0~ a1-1 // ai+1 = A[i]
      n = (A[i]-1)-0
      #print(0,A[i]-1)
    else:
      n = (A[i]-1)-(A[i-1]+1) 
      #print(A[i-1]+1,A[i]-1)
      
    if(i != 0): #「渡れない箇所が二連続」が存在するなら0通り
     dif = A[i]-A[i-1]
     if(dif == 1):
       ans = 0
       break
          
    if(ans == 0): ans += (Fib(n+1)%(10**9 + 7))
    else: ans = ans*(Fib(n+1)%(10**9 + 7))

 n = N - (A[M-1]+1)#最後にaM + 1 ~ N のルートも考慮する
 ans = ans*(Fib(n+1)%(10**9 + 7))
 #print(A[M-1]+1,N)
            
ans = ans%(10**9 + 7)
print(ans)

Submission status: Wrong Answer

Solution code:
it = [9,27,37,4,1,3,2,0]
min(it)

Submission status: Wrong Answer

Solution code:
#C問題
mod = 10**9+7
N,M = map(int,input().split())

step = []
for i in range(N+2):
    if i <= 1:
        step.append(1)
    elif i == 2:
        step.append(1)
    else:
        step.append(step[i-1]+step[i-2])
    
A = []
for j in range(M):
    A.append(int(input()))

stairs = []
flag = 0
old = 0
for a in A:
    if a-old == 1:
        flag = 1
        break
    else:
        stairs.append(a-old-1)
        old = a
stairs.append(N-old)

if flag == 1:
    print(0)
else:
    #print(stairs)
    ans = 1
    for s in stairs:
        ans*=step[s]
        
    print(ans%mod)

Submission status: Wrong Answer

Solution code:
#C問題
mod = 10**9+7
N,M = map(int,input().split())

step = []
for i in range(N+2):
    if i <= 1:
        step.append(1)
    elif i == 2:
        step.append(1)
    else:
        step.append(step[i-1]+step[i-2])
    
A = []
for j in range(M):
    A.append(int(input()))

stairs = []
flag = 0
old = 0
for a in A:
    if a-old == 1:
        flag = 1
        break
    else:
        stairs.append(a-old-1)
        old = a

if flag == 1:
    print(0)
else:
    #print(stairs)
    ans = 1
    for s in stairs:
        ans*=step[s]
        
    print(ans%mod)

Submission status: Wrong Answer

Solution code:
N, M = map(int,input().split())
a = [0] * (N+1)
for i in range(M):
    a[int(input())] = 0
mod = 1000000007
ans = [0] * (N+1)
ans[0] = 1
for i in range(1,N+1):
     ans[i] = (ans[i-2]*a[i-2] + ans[i-1]*a[i-1]) % mod
print(ans[N])

Submission status: Wrong Answer

Solution code:
N, M = map(int,input().split())
a = [0] * (N+1)
for i in range(M):
    a[i] = int(input())
mod = 1000000007
ans = [0] * (N+1)
ans[0] = 1
for i in range(1,N+1):
     ans[i] = (ans[i-2]*a[i-2] + ans[i-1]*a[i-1]) % mod
print(ans[N])

Submission status: Wrong Answer

Solution code:
def fib(n):
    a, b = 1, 1
    for _ in range(n):
        a, b = b, a + b
    return a
 
from sys import stdin
n,m = [int(x) for x in stdin.readline().rstrip().split()]
a = [-1] + [int(stdin.readline().rstrip()) for _ in range(m)] + [n-1]
print(a)
ans = 1
for i in range(len(a) - 1):
    if a[i] != 0 and a[i + 1] != n and a[i + 1] - a[i] == 1:
        print(0)
        exit()
    ans = ans * fib(a[i + 1] - a[i] - 2) % (10 ** 9 + 7)
print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin
from itertools import accumulate

a,b = [int(x) for x in stdin.readline().rstrip().split()]
li = [int(stdin.readline().rstrip()) for _ in range(b)]

if a == 1:
    print(1)
    exit()

elif a == 2:
    if b == 0:
        print(2)
        exit()
    else:
        print(1) 
        exit()

for k in range(len(li)-1):
    if li[k] +1 == li[k+1]:
        print(0)
        exit()

def stair_cal(x):
    if x == 1:
        return(x)
    elif x == 2:
        return(x)
    elif x == 0:
        return(1)
    lin = [1,2]
    for i in range(2,x):
        lin.append(lin[i-2]+lin[i-1])
    return(lin[-1])

if b == 0:
    print(stair_cal(a)%(10**9+7))
    exit()

li2 = []

li2.append(li[0]-1)

for i in range(1,b):
    li2.append(li[i]-li[i-1]-1)

li2.append(a-li[-1])

point = 1

for e in range(len(li2)):
    point = point*stair_cal(li2[e])%(10**9+7)

print(point)

Submission status: Wrong Answer

Solution code:
s=list(map(int,input().split()))
t = [int(input()) for i in range(s[1])]
list=[]
mod=1000000007
d=1
for k in range(s[0]+10):
  list.append(0)
def fib(x):
  list[0]=list[1]=0
  list[2]=list[3]=1
  for l in range(4,x+3):
    list[l]=list[l-1]+list[l-2]
fib(s[0])
if s[1]==0:
  print(list[s[0]+2])
else:
  for j in range(s[1]+1):
    if j==0:
      d*=list[t[j]+1]
      d=d%mod
      e=t[j]
    elif j==s[1]:
      d*=list[s[0]-t[j-1]+1]
      d=d%mod
    else:
      d*=list[t[j]-t[j-1]]
      d=d%mod
  print(d)

Submission status: Wrong Answer

Solution code:
def fib(n):
    a, b = 1, 1
    for _ in range(n):
        a, b = b, a + b
    return a


n, m = map(int, input().split())
a = [-1] + [int(input()) for i in range(m)] + [n + 1]
ans = 1

for i in range(len(a) - 1):
    if a[i] != 0 and a[i + 1] != n and a[i + 1] - a[i] == 1:
        print(0)
        exit()
    print(fib(a[i + 1] - a[i] - 2))
    ans = ans * fib(a[i + 1] - a[i] - 2) % (10 ** 9 + 7)

print(ans)

Submission status: Wrong Answer

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


def Fib(num):
    a, b = 1, 0
    for _ in range(num):
        a, b = (a + b) % 1000000007, a % 1000000007
    return (a)


def stepcount(x, y):
    if y - x <= 1:
        return 1
    else:
        return Fib(y - x)

if m != 0:
    answer = Fib(outlist[0] - 1)

    for i in range(m - 1):
        answer *= stepcount(outlist[i] + 1, outlist[i + 1] - 1)
        answer = answer % 1000000007

    answer = (answer * stepcount(outlist[m - 1] + 1, n)) % 1000000007

    for i in range(m - 1):
        if outlist[i + 1] - outlist[i] == 1:
            answer = 0
else:
    answer = Fib(n+1)

print(answer)

Submission status: Wrong Answer

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


for i in range(N):
  if i+1 not in a:
    dp[i+1]+=dp[i]
    dp[i+1] %= mod
  if i+2 <= N and i+2 not in a:
    dp[i+2]+=dp[i]
    dp[i+2]%=mod
  
print(dp[-1])

Submission status: Wrong Answer

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

for i in range(N):
  if i+1 not in a:
    dp[i+1]+=dp[i]
    dp[i+1] %= mod
  if i+2 <= N and i+2 not in a:
    dp[i+2]+=dp[i]
    dp[i+2]%=mod
  
print(dp[-1])

Submission status: Wrong Answer

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

dp=[0]*(N+1)

for i in range(N):
  if i+1 not in a:
    dp[i+1]+=dp[i]
  if i+2 < N and i+2 not in a:
    dp[i+2]+=dp[i]
  
print(dp[-1]%1000000007)

Submission status: Wrong Answer

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


MOD = 1000000007

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

dp[0] = 1



next_ng_index = 0

for index in range(N):
    current = index + 1
    if current == A[next_ng_index]:
        next_ng_index += 1
        continue

    pre_stair = current - 1
    dp[current] += dp[pre_stair]

    prepre_stair = current -2
    if prepre_stair >= 0:
        dp[current] += dp[prepre_stair]

    dp[current] %= MOD
    print(dp)

print(dp[-1]%MOD)

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
if 1 not in a:dp[1] = 1

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

print(dp[-1])

Submission status: Wrong Answer

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

dp = [0]*(N+1)
if 1 not in a:dp[1] = 1


for i in range(1,N):
  if i in a: continue
  dp[i+1] = dp[i]+dp[i-1]
  
print(dp[-1])

Submission status: Wrong Answer

Solution code:
import sys
n,m=map(int,input().split())
l=[]
for i in range(m):
    l.append(int(input()))
ans1=0
ans2=0
if 1 in l:
    if 2 in l:
        print(0)
        sys.exit()
    else:
        ans2=1
else:
    ans1=1
    if 2 in l:
        pass
    else:
        ans2=2
S=2
ans3=0
while S<n:
    S+=1
    if S in l:
        ans3=0
        ans1=ans2
        ans2=ans3
    else:
        ans3=(ans1+ans2)%1000000007
        ans1=ans2
        ans2=ans3
print(ans3)

Submission status: Wrong Answer

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

if n == 1:
    print(1)
elif n == 2:
    if a[2] == -1:
        print(1)
    else:
        print(2)
else:
    if a[1] == -1:
        b1 = 0
    else:
        b1 = 1
    if a[2] == -1:
        b2 = 0
    else:
        b2 = b1+1

    b3 = b1 + b2

    for i in range(3,n+1):
        if a[i] == -1:
            b3 = 0
        else:
            b3 = b1+b2
        if b3 > 1000000007:
            b3 = b3 % 1000000007
        b1 = b2
        b2 = b3
        if b1==b2==0:
            break

    print(b3)

Submission status: Wrong Answer

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

if 1 in a:
    b1 = 0
else:
    b1 = 1
if 2 in a:
    b2 = 0
else:
    b2 = b1+1

b3 = 0

for i in range(3,n+1):
    if i in a:
        b3 = 0
    else:
        b3 = b1+b2
    if b3 > 1000000007:
        b3 = b3 % 1000000007
    b1 = b2
    b2 = b3
    if b1==b2==0:
        break

print(b3)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
dp = [0 for i in range(N+1)]
for i in range(M):
    A = int(input())
    dp[A] = -1
dp[0] = 1
for j in range(2, N + 1):
    if dp[j] == -1:
        dp[j] = 0
        continue
    dp[j] = dp[j-2] + dp[j-1]

print(dp[N] % 1000000007)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

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

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

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
use=[0]
ans=1
for i in range(m):
    use.append(int(input()))
use.append(n)
print(use)
if n>=2:        
    lists=[1,1]

    for i in range(n-1):
        lists.append((lists[-1]+lists[-2])%1000000007)

    
    for i in range(m+1):
    
        if use[i+1]-use[i]==1 and i>=1and i<=(m-1):
            ans=0
            break
        if use[i+1]-use[i]>=2 and i>=1:
            ans=(ans*lists[int(use[i+1]-use[i]-2)])%1000000007
        if i==0 and use[1]==1:
            ans=ans
        if i==0 and use[1]>=2:
            ans=(ans*lists[int(use[i+1]-use[i]-2)])%1000000007
        if i==m+1 and n-use[i-1]==1:
            ans=ans
        if i==m+1 and n-use[i-1]>=2:
            ans=(ans*lists[int(use[i]-use[i-1]-1)])%1000000007
      
            
    print(ans)
elif n==1:
    print(1)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
use=[0]
ans=1
for i in range(m):
    use.append(int(input()))
use.append(n)

if n>=2:        
    lists=[1,2]

    for i in range(n-2):
        lists.append((lists[-1]+lists[-2])%1000000007)

    
    for i in range(m+1):
    
        if use[i+1]-use[i]==1 and i>=1:
            ans=0
            break
        else:
            ans=(ans*lists[int(use[i+1]-use[i]-2)])%1000000007
            
            
    print(ans)
elif n==1:
    print(1)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
N,M=map(int,input().split())
l=list(range(N+1))

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

sum=1
start=0
judge=True

for i in range(M):
    a=int(input())
    if (a-start)==1:
        if start==0:
            pass
        else:
            judge=False
            break
    sum*=res[a-start-1]
    start=a+1
sum*=res[N-start]

if judge:    
    print(sum%(10**9+7))
else:
    print(0)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
N,M=map(int,input().split())
l=list(range(N+1))

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

sum=1
start=0
judge=True

for i in range(M):
    a=int(input())
    if (a-start)==1:
        if start==0:
            pass
        else:
            judge=False
            break
    sum*=res[a-start-1]
    print(sum)
    start=a+1
sum*=res[N-start]

if judge:    
    print(sum%(10**9+7))
else:
    print(0)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

N, M = [int(x) for x in input().split()]
a = []

for _ in range(M):
    a.append(int(input()))

MOD = 1000000007

dict = defaultdict(int)
ans = 1
for i in range(M):
    dict[a[i]] = -10 ** 1000
    if i >= 1 and a[i] - a[i - 1] == 1:
        print("0")
        exit()

dict[0] = 1
for i in range(N):
    if dict[i] > 0:
        dict[i + 1] += dict[i]
        dict[i + 2] += dict[i]


print(dict[N] % MOD)

Submission status: Wrong Answer

Solution code:
import sys
N,M = map(int,input().split())
As = [int(input()) for e in range(M)]

if 1 in As and 2 in As:
    print(0)
    sys.exit()

if 1 in As and 2 not in As:
    patterns = [0,1]

if 1 not in As and 2 in As:
    patterns = [1,0]

if 1 not in As and 2 not in As:
    patterns = [1,2]

flags = [0 for _ in range(N)]
for e in As:
    flags[e] = 1
for i in range(3,N+1):
    value = 0
    if not flags[i-2]:
        value += patterns[i-3]
    if not flags[i-1]:
        value += patterns[i-2]
    patterns.append(value%1000000007)
print(patterns[-1]%1000000007)

Submission status: Wrong Answer

Solution code:
import sys
N,M = map(int,input().split())
As = [int(input()) for e in range(M)]

if 1 in As and 2 in As:
    print(0)
    sys.exit()

if 1 in As and 2 not in As:
    patterns = [1,1]

if 1 not in As and 2 in As:
    patterns = [1,1]

if 1 not in As and 2 not in As:
    patterns = [1,2]

flags = [0 for _ in range(N)]
for e in As:
    flags[e] = 1

for i in range(3,N+1):
    value = 0
    if not flags[i-2]:
        value += patterns[i-3]
    else:
        As.remove(i-2)
    if not flags[i-1]:
        value += patterns[i-2]
    patterns.append(value%1000000007)
print(patterns[-1]%1000000007)

Submission status: Wrong Answer

Solution code:
import sys
N,M = map(int,input().split())
As = [int(input()) for e in range(M)]

if 1 in As and 2 in As:
    print(0)
    sys.exit()

if 1 in As and 2 not in As:
    patterns = [1,1]

if 1 not in As and 2 in As:
    patterns = [1,1]

if 1 not in As and 2 not in As:
    patterns = [1,2]

for i in range(3,N+1):
    value = 0
    if i-2 not in As:
        value += patterns[i-3]
    else:
        As.remove(i-2)
    if i-1 not in As:
        value += patterns[i-2]
    patterns.append(value%1000000007)
print(patterns[-1]%1000000007)

Submission status: Wrong Answer

Solution code:
import sys
N,M = map(int,input().split())
As = [int(input()) for e in range(M)]

if 1 in As and 2 in As:
    print(0)
    sys.exit()

if 1 in As and 2 not in As:
    patterns = [1,1]

if 1 not in As and 2 in As:
    patterns = [1,1]

if 1 not in As and 2 not in As:
    patterns = [1,2]

for i in range(3,N+1):
    value = 0
    if i-2 not in As:
        value += patterns[i-3]
    if i-1 not in As:
        value += patterns[i-2]
    patterns.append(value%1000000007)
print(patterns[-1]%1000000007)

Submission status: Wrong Answer

Solution code:
import math
import sys

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

N, M = map(int, input().split())
portion = []
tmp = -1

if M == 0:
    portion.append(N)

for i in range(M):
    a = int(input())
    if a - tmp == 1:
        print(0)
        sys.exit()
    portion.append(a - tmp - 1)
    tmp = a
    if i == M-1:
        portion.append(N - a)

multi_move = 1
for i in range(len(portion)):
    tmp_portion = portion[i] - 1
    arrow2_num = tmp_portion // 2
    if tmp_portion == 0:
        continue
    elif tmp_portion % 2 == 0:
        move = 0
    else:
        move = 1
    for j in range(arrow2_num + 1):
        long_arrow = j
        short_arrow = tmp_portion - j*2
        move += comb(long_arrow + short_arrow, long_arrow)
    multi_move *= move
    multi_move = multi_move % 1000000007
print(multi_move)

Submission status: Wrong Answer

Solution code:
import math
import sys

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

N, M = map(int, input().split())
portion = []
tmp = -1
for i in range(M):
    a = int(input())
    if a - tmp == 1:
        print(0)
        sys.exit()
    portion.append(a - tmp - 1)
    tmp = a
    if i == M-1:
        portion.append(N - a)

multi_move = 1
for i in range(len(portion)):
    tmp_portion = portion[i] - 1
    arrow2_num = tmp_portion // 2
    if tmp_portion == 0:
        continue
    elif tmp_portion % 2 == 0:
        move = 0
    else:
        move = 1
    for j in range(arrow2_num + 1):
        long_arrow = j
        short_arrow = tmp_portion - j*2
        move += comb(long_arrow + short_arrow, long_arrow)
    multi_move *= move
    multi_move = multi_move % 1000000007
print(multi_move)

Submission status: Wrong Answer

Solution code:
import math
import sys

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

N, M = map(int, input().split())
portion = []
tmp = -1
for i in range(M):
    a = int(input())
    if tmp - a == 1:
        print(0)
        sys.exit()
    portion.append(a - tmp - 1)
    tmp = a
    if i == M-1:
        portion.append(N - a)

multi_move = 1
for i in range(len(portion)):
    tmp_portion = portion[i] - 1
    arrow2_num = tmp_portion // 2
    if tmp_portion == 0:
        continue
    elif tmp_portion % 2 == 0:
        move = 0
    else:
        move = 1
    for j in range(arrow2_num + 1):
        long_arrow = j
        short_arrow = tmp_portion - j*2
        move += comb(long_arrow + short_arrow, long_arrow)
    multi_move *= move
    multi_move = multi_move % 1000000007
print(multi_move)