Problem:


Score : 300 points

Problem Statement

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

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

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

Constraints

1 \leq N \leq 10^5

0 \leq M \leq N-1

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

Input

Input is given from Standard Input in the following format:

N M
a_1
a_2
 .
 .
 .
a_M

Output

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

Sample Input 1

6 1
3

Sample Output 1

4

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

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

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

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

0 \to 2 \to 4 \to 6

Sample Input 2

10 2
4
5

Sample Output 2

0

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

Sample Input 3

100 5
1
23
45
67
89

Sample Output 3

608200469

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



Sample input:
6 1
3


Sample output:
4

Submission status: Wrong Answer

Solution code:
import sys
n,m=map(int,input().split())
a=[]
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+2]=step[j]
      step[j+1]=0
      if (10**9)+7<=step[j+2]:
        step[j+2]=step[j+2]%((10**9)+7)
      j+=2
    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
if 1 in a:
  step[1]=0
else:
  step[1]=1
for i in range(m):
  a.append(int(input()))
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
if 1 in a:
  step[1]=0
else:
  step[1]=1
for i in range(m):
  a.append(int(input()))
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+=1
  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+=1
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()))
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]
    step[j+2]=step[j+2]%((10**9)+7)
    j+=2
  else:
    if j+2 in a:
      step[j+1]=step[j]
      step[j+1]=step[j+1]%((10**9)+7)
      j+=1
    else:
      step[j+2]=step[j]+step[j+1]
      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()))
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]
    j+=2
  else:
    if j+2 in a:
      step[j+1]=step[j]
      j+=1
    else:
      step[j+2]=step[j]+step[j+1]
      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()))
for j in range(m-1):
  if a[j+1]-a[j]==1:
    print(0)
    sys.exit()
    
for j in range(n-1):
  if j+1 in a:
    step[j+2]=step[j]
    step[j+2]%((10**9)+7)
  else:
    step[j+2]=2*step[j]+step[j+1]
    step[j+2]%((10**9)+7)
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()))
for j in range(m-1):
  if a[j+1]-a[j]==1:
    print(0)
    sys.exit()
    
for j in range(n-1):
  if j+1 in a:
    step[j+2]+=step[j]
  else:
    step[j+2]+=2*step[j]
print(step[n]%((10**9)+7))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)
def input():
    return sys.stdin.readline().rstrip()

def main():
    N,M=map(int,input().split())
    a=[int(input()) for i in range(M)]
    dp=[1]*(N+1)
    if M!=0:
        dp[1]=0 if a[0]==1 else 1
        for i in a:
            dp[i]=0
        for i in range(1,N):
            if dp[i+1]!=0:
                dp[i+1] = (dp[i]+dp[i-1]) % 1000000007
    print(dp[N])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

MOD = 10 ** 9 + 7
MIN = 100


def org(N, M, dp):
    a = [0] * M

    dp[0] = 1
    dp[1] = 1
    dp[2] = 2
    for i in range(3, max(N+1, MIN)):
        dp[i] = dp[i-1] + dp[i-2]

    ans = 1

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

        if i != 0 and abs(a[i] - a[i-1]) == 1:
            print(0)
            return

        if a[i] == 1:
            ans *= 1
        elif i == 0:
            ans *= dp[a[i] - 1]
            ans %= MOD
            # print(a[i], ans, a[i] - 1)
        else:
            ans *= dp[a[i] - a[i-1] - 2]
            ans %= MOD
            # print(a[i], ans, a[i] - a[i-1] - 2)

    if M == 0:
        ans *= dp[N]
        ans %= MOD
        # print(ans, N - a[M-1] - 1)
        print(ans)
    else:
        ans *= dp[N - a[M-1] - 1]
        ans %= MOD
        # print(ans, N - a[M-1] - 1)
        print(ans)


def good(N, M, dp):
    a = [0] * len(dp)

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

    dp[0] = 0 if a[0] is True else 1
    dp[1] = dp[0] + (0 if a[1] is True else 1)

    if N == 1:
        print(dp[0])
        return
    elif N == 2:
        print(dp[1])
        return

    for i in range(2, N):
        if a[i] is True:
            dp[i] = 0
        else:
            dp[i] = dp[i-1] + dp[i-2]
            dp[i] %= MOD

    print(dp[N-1] % MOD)
    # print(dp)


def main():
    N, M = map(int, input().split())
    dp = [0] * max((N + 1), MIN)

    good(N, M, dp)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

MOD = 10 ** 9 + 7


def main():
    N, M = map(int, input().split())
    memo = [0] * max((N + 1), 10)
    a = [0] * M

    memo[0] = 0
    memo[1] = 1
    memo[2] = 2
    for i in range(3, max(N+1, 10)):
        memo[i] = memo[i-1] + memo[i-2]

    # print(memo)
    ans = 1

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

        if i != 0 and abs(a[i] - a[i-1]) == 1:
            print(0)
            return

        if a[i] == 1:
            ans *= 1
        elif i == 0:
            ans *= memo[a[i] - 1]
            ans %= MOD
            # print(a[i], ans, a[i] - 1)
        else:
            ans *= memo[a[i] - a[i-1] - 2]
            ans %= MOD
            # print(a[i], ans, a[i] - a[i-1] - 2)

    if M == 0:
        ans *= memo[N]
        ans %= MOD
        # print(ans, N - a[M-1] - 1)
        print(ans)
    else:
        ans *= memo[N - a[M-1] - 1]
        ans %= MOD
        # print(ans, N - a[M-1] - 1)
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

MOD = 10 ** 9 + 7


def main():
    N, M = map(int, input().split())
    memo = [0] * (N + 1)
    a = [0] * M

    if N == 1:
        print(1)
        return
    elif N == 2:
        print(2)
        return
    elif N == 3:
        print(3)
        return

    memo[0] = 0
    memo[1] = 1
    memo[2] = 2
    for i in range(3, N+1):
        memo[i] = memo[i-1] + memo[i-2]

    # print(memo)
    ans = 1

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

        if i != 0 and abs(a[i] - a[i-1]) == 1:
            print(0)
            return

        if a[i] == 1:
            ans *= 1
        elif i == 0:
            ans *= memo[a[i] - 1]
            ans %= MOD
            # print(a[i], ans, a[i] - 1)
        else:
            ans *= memo[a[i] - a[i-1] - 2]
            ans %= MOD
            # print(a[i], ans, a[i] - a[i-1] - 2)

    if M == 0:
        ans *= memo[N]
        ans %= MOD
        # print(ans, N - a[M-1] - 1)
        print(ans)
    else:
        ans *= memo[N - a[M-1] - 1]
        ans %= MOD
        # print(ans, N - a[M-1] - 1)
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

break_list.append(-1)
fib = [0] * (N + 1)
if break_list[0] == 1:
    fib[1] = 0
else:
    fib[1] = 1
    
fib[0] = 1
t = 0
for i in range(N - 1):
    if i + 2 == break_list[t]:
        fib[i + 2] = 0
        t = t + 1
    else:
        fib[i + 2] = fib[i] + fib[i + 1]
 
if N == 1:
    print( fib[1] )
else:
    print( fib[i+2] %  1000000007 )

Submission status: Wrong Answer

Solution code:
from math import factorial as fac
N,M = map( int, input().split() )
break_list = []
for i in range(M):
    break_list.append( int( input() ) )
break_list.append( N + 1 )
start = 0
ans = 1
for i in break_list:
    sum_c = 0
    end = i - 1
    if start > end:
        i = -1
        break
    step_1 = end - start
    step_2 = int( ( end - start ) / 2 )
    for j in range(step_2 + 1):
        k = step_1 - 2 * j
        sum_c += int( fac(k + j) / ( fac(j) * fac(k) ) )
    ans *= sum_c
    start = i + 1
    
if i > -1:
    print( ans % 1000000007 )
else:
    print(0)

Submission status: Wrong Answer

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


def calc_patterns(num):
    if 1 == num:
        return 1
    elif 2 == num:
        return 2
    else:
        return num - 2 + calc_patterns(num-1)


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


count = 0
for i in range(1, len(a)):
    if a[i] == (a[i-1] + 1):
        print(0)
        exit(0)
    count += patterns[a[i] - 1 - (a[i-1]+1)]
print(count % 1000000007)

Submission status: Wrong Answer

Solution code:
sum_ = [0]

N,M = input().split()
N,M = int(N),int(M)
m_ = [0,N-1]
for i in range(M):
    m_.append(int(input()))
#m = sorted(m)

m = [1 for i in range(N+1)]
for i in m_:
    m[i] = 0
for i in range(1,N+1):
    if(i==1):
        if(m[i]==1):
            sum_.append(1)
        else:
            sum_.append(0)
    elif(i==2):
        if(m[i]==1):
            sum_.append(1+sum_[1])
        else:
            sum_.append(sum_[1])
    
    else:
        sum_.append(m[i-1]*sum_[i-1]+m[i-2]*sum_[i-2])
#print(sum_)
print(sum_[N]%1000007)

Submission status: Wrong Answer

Solution code:
sum_ = [0]
N = 6
m_ = [3]#[1,23,45,67,89]
m = [1 for i in range(N+1)]
for i in m_:
    m[i] = 0
for i in range(1,N+1):
    if(i==1):
        if(m[i]==1):
            sum_.append(1)
        else:
            sum_.append(0)
    elif(i==2):
        if(m[i]==1):
            sum_.append(1+sum_[1])
        else:
            sum_.append(sum_[1])
    
    else:
        sum_.append(m[i-1]*sum_[i-1]+m[i-2]*sum_[i-2])
#print(sum_)
print(sum_[N]%1000007)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
a=[]
b=[0]*(n+1)
b[0]=1
MOD=(10**9)+7

a.append(int(input()) for i in range(m))
  
if 1 not in a:
  b[1]=1
else:
  b[1]=0
  
for j in range(2,n+1):
  if j in a:
    continue
  else:
    b[j]=(b[j-1]+b[j-2])%MOD
    
print(b[n]%MOD)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
a=[]
b=[0]*(n+1)
b[0]=1
MOD=(10**9)+7

a.append(int(input()) for _ in range(m))
  
if 1 not in a:
  b[1]=1
  
  
for j in range(2,n+1):
  if j in a:
    continue
  else:
    b[j]=(b[j-1]+b[j-2])%MOD
    
print(b[n]%MOD)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
a=[]
b=[0]*(n+1)
b[0]=1
MOD=(10**9)+7

a.append(int(input()) for _ in range(m))
  
if 1 in a:
  b[1]=0
else:
  b[1]=1
  
for j in range(2,n+1):
  if j not in a:
    b[j]=(b[j-1]+b[j-2])%MOD
    
print(b[n]%MOD)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
a=[]
b=[0]*(n+1)
b[1]=1
b[0]=1
MOD=(10**9)+7

a.append(int(input()) for _ in range(m))
  
if 1 in a:
  b[1]=0
else:
  b[1]=1
  
for j in range(2,n+1):
  if j not in a:
    b[j]=(b[j-1]+b[j-2])%MOD
    
print(b[n]%MOD)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
a=[]
b=[0]*(n+1)
b[0]=0
b[1]=1

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

Submission status: Wrong Answer

Solution code:
import scipy
print(0)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
broken=[False]*(n+1)
for i in range(m):
  broken[int(input())]=True
dp=[0]*(n+1)
dp[0]=1
dp[1]=1 if 1 not in broken else 0

for i in range(2,len(dp)):
  if broken[i]:
    dp[i]=0
  else:
    dp[i]=(dp[i-2]+dp[i-1])%1000000007
  
print(dp[-1])

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
dp=[0]*(n+1)
dp[0]=1

for i in range(m):
  dp[int(input())]=-1

if dp[1]!=-1:
  dp[1]==1

for i in range(2,len(dp)):
  if dp[i]==-1:
    continue
  else:
    dp[i]=(max(dp[i-2],0)+max(dp[i-1],0))%1000000007
    if dp[i]==0:
      print(0)
      break
else:  
  print(dp[-1])

Submission status: Wrong Answer

Solution code:
n , m = map(int, input().split())
const = 1000000007
r = [1 for i in range(n+1)]
for i in range(m):
  r[int(input())] = 0
for i in range(3, n+1):
  if r[i] > 0:
    r[i] = (r[i-1] + r[i-2])%const
print(r[n])

Submission status: Wrong Answer

Solution code:
from sys import stdin
import numpy as np

n,m = [int(x) for x in stdin.readline().rstrip().split()]

lin = np.array([0]*(n+1))

if m != 0:
    for i in range(m):
        lin[int(stdin.readline().rstrip())] = -1

dp = np.array([-1]*(n+1))

dp[0] = 1

if lin[1] == -1:
    dp[1] = 0
else:
    dp[1] = 1

for i in range(2,n+1):
    if lin[i] == -1:
        dp[i] = 0
    else:
        dp[i] = dp[i-1] + dp[i-2]

print(int(dp[n]%(10**9+7)))

Submission status: Wrong Answer

Solution code:
from sys import stdin
import numpy as np

n,m = [int(x) for x in stdin.readline().rstrip().split()]

if m != 0:
    lin = [int(stdin.readline().rstrip()) for _ in range(m)]
else:
    lin = [-1]

dp = np.array([-1]*(n+1))

dp[0] = 1

if lin[0] == 1:
    dp[1] = 0
else:
    dp[1] = 1

for i in range(2,n+1):
    if i in lin:
        dp[i] = 0
    else:
        dp[i] = dp[i-1] + dp[i-2]

print(int(dp[n]%(10**9+7)))

Submission status: Wrong Answer

Solution code:
from sys import stdin

n,m = [int(x) for x in stdin.readline().rstrip().split()]

#フィボナッチ数列
def fib(n):
    a, b = 1, 1
    for _ in range(n):
        a, b = b, a + b
    return a

if m == 0:
    print(fib(n))
    exit()

lin = [int(stdin.readline().rstrip()) for _ in range(m)]

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

if lin[0] == 1:
    dp[1] = 0
else:
    dp[1] = 1
for i in range(2,n+1):
    if i in lin:
        dp[i] = 0
    else:
        dp[i] = dp[i-1] + dp[i-2]

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

Submission status: Wrong Answer

Solution code:
import numpy as np


def main(n, m, a):
    dp = np.zeros(n + 1)
    dp[0] = 1
    dp[1] = 1 if 1 not in a else 0

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

    return dp[-1]


if __name__ == '__main__':
    N, M = map(int, input().split())
    A = set()
    for _ in range(M):
        A.add(int(input()))

    print(main(N, M, A))

Submission status: Wrong Answer

Solution code:
import numpy as np


def main(n, m, a):
    dp = np.zeros(n + 1)
    dp[0] = 1
    dp[1] = 1 if 1 not in a else 0

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

    return dp[-1]


if __name__ == '__main__':
    N, M = map(int, input().split())
    A = set()
    for _ in range(M):
        A.add(int(input().strip()))

    print(main(N, M, A))

Submission status: Wrong Answer

Solution code:
def fibonacci(N):
    a = 1
    b = 2
    c = 0

    if N <= 1:
        return 1
    elif N == 2:
        return 2
    else:
        for i in range(N-2):
            c = a+b
            a = b
            b = c
    return c


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

    temp = 1
    for i in range(M+1):
        if M == 0:
            num = fibonacci(N)
            print(num)
            return
        else:
            if i == 0:
                num = fibonacci(A[i]-1)
            else:
                if i <= M-1:
                    if A[i-1] == A[i]-1:
                        print(0)
                        return
                    num = fibonacci(A[i]-A[i-1]-2)
                else:
                    num = fibonacci(N-A[i-1]-1)
        temp *= num
    print(temp%1000000007)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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


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

for i in range(m):
	dp[int(input())] = -1


for i in range(n-1):
	if dp[i+2] != -1:
		if dp[i+1] != -1:
			dp[i+2] += dp[i+1]
		if dp[i] != -1:
			dp[i+2] += dp[i]

print(dp[n]%1000000007)

Submission status: Wrong Answer

Solution code:
#ABC129C - Typical Stairs
N, M = list(map(int,input().split()))
dp = [-1]*(N+1)
dp[0] = 1
for j in range(M):
    a = int(input())
    dp[a] = 0
if dp[1] == 0:
    dp[1] = 0
    dp[2] = 1
elif dp[1] == -1:
    dp[1] = 1
for i in range(2,N+1,1):
    if dp[i] == -1:
        dp[i] = dp[i-1] + dp[i-2]
    #print(dp[i])
print(dp[N] % 1000000007)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
A = set([int(input()) for _ in range(m)])
mod = 1000000007
dp = [0]*(n+1)
dp[0],dp[1] = 1,1
for i in range(2,n+1):
    dp[i] = (dp[i-1] + dp[i-2])%mod
    if i in A:dp[i] = 0
print(dp[n])

Submission status: Wrong Answer

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

import sys
sys.setrecursionlimit(100000)

memo  =[-1]*(N+2)
memo[0] = 1
memo[1] = 1
def stair_count(n):
    for j in range(2,n+1):
        memo[j] = memo[j-1] + memo[j-2]

start = 0
answer = 1
dif = []
for i in a:
    if i == start:
        print(0)
        exit()
    else:
        n = i-1-start
        dif.append(n)
        stair_count(max(dif))
        start = i+1
for i in a:
        answer = (answer * memo[n])

n = N -start
answer = answer * memo[n]
print(answer%1000000007)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline


def fib(n):
    '''f(n)=f(n-1)+f(n-2)'''
    a, b = 0, 1
    for _ in range(n-1):
        a, b = b, a+b
    return b


n, m = map(int, input().split())
mod = 10**9+7
a = [int(input()) for _ in range(m)]
if not a:
    ans = fib(n+1)
else:
    ans = fib(a[0])*fib(n-a[m-1]) % mod
    for i in range(m-1):
        if a[i+1]-a[i] == 1:
            ans = 0
            break
        ans = ans * fib(a[i+1]-a[i]-1) % mod

print(ans)

Submission status: Wrong Answer

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

stairs = []

for i in range(M):
    stairs.append(int(input()))
path = []
path.extend([1, 1])
# caluclate from N-2 step (second last)
if N > 3:
    for n in range(2, N):
        if N - n not in stairs:
            path.append(path[n-2] + path[n-1])
        else:
            path.append(0)
    print((path[-1] + path[-2]) % (10**9+7)) 
elif N < 2:
    count = 0
    for i in range(N):
        count += path[i]
    print(count)

Submission status: Wrong Answer

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

stairs = []

for i in range(M):
    stairs.append(int(input()))
path = []
path.extend([1, 2])
# caluclate from last step
for n in range(3, N):
    if N - n not in stairs:
        path.append(path[n-3] + path[n-2])
    else:
        path.append(0)
        
print((path[-1] + path[-2]) % (10**9+7))

Submission status: Wrong Answer

Solution code:
"""
問題文
    N段の階段があります。高橋君は現在、上り口(0段目)にいます。 高橋君は一歩で1段か2段上ることができます。
    ただし、a1,a2,a3,....aM段目の床は壊れており、その段に足を踏み入れることは危険です。
    壊れている床を踏まないようにしながら、最上段(N段目)にたどりつくまでの移動方法は何通りあるでしょうか？ 
    総数を1,000,000,007で割った余りを求めてください。

制約
    1≦N≦10^5
    0≦M≦N−1
    1≦a1<a2< ... <aM≦N−1
"""
#入力の受け取り
N, M = map(int, input().split())
hoal = [int(input()) for i in range(M)]

#listの初期化
dp = list()
dp = [0]*N

    
dp_check = list()
dp_check = [0]*N

for i in range(M):
    dp_check[hoal[i]-1]=1
    if dp_check[hoal[i]-1]==1 and dp_check[hoal[i]-2]==1:
        print("0")
        exit()

if N==1:
    if M==1:
        dp[0]=0
    else:
        dp[0]=1
else:
    if dp_check[0]==1:
        dp[0]=0
        dp[1]=1
    elif dp_check[1]==1:
        dp[0]=1
        dp[1]=0
    else:
        dp[0] = 1
        dp[1] = 2
    #実際に求める
    #dp[i]<-i段までの移動方法の和
    for i in range(N):
        if i>1 and dp_check[i]==0:
            dp[i]=dp[i-1]+dp[i-2]

        dp[i]=dp[i]%1000000007

    print(dp[N-1])

Submission status: Wrong Answer

Solution code:
"""
問題文
    N段の階段があります。高橋君は現在、上り口(0段目)にいます。 高橋君は一歩で1段か2段上ることができます。
    ただし、a1,a2,a3,....aM段目の床は壊れており、その段に足を踏み入れることは危険です。
    壊れている床を踏まないようにしながら、最上段(N段目)にたどりつくまでの移動方法は何通りあるでしょうか？ 
    総数を1,000,000,007で割った余りを求めてください。

制約
    1≦N≦10^5
    0≦M≦N−1
    1≦a1<a2< ... <aM≦N−1
"""
#入力の受け取り
N, M = map(int, input().split())
hoal = [int(input()) for i in range(M)]

#listの初期化
dp = list()
dp = [0]*N
    
dp_check = list()
dp_check = [0]*N

for i in range(M):
    dp_check[hoal[i]-1]=1
    if dp_check[hoal[i]-1]==1 and dp_check[hoal[i]-2]==1:
        print("0")
        exit()

if N==1:
    if M==1:
        dp[0]=0
    else:
        dp[0]=1
    print(dp[N-1])
else:
    if dp_check[0]==1:
        dp[0]=0
        dp[1]=1
    elif dp_check[1]==1:
        dp[0]=1
        dp[1]=0

    #実際に求める
    #dp[i]<-i段までの移動方法の和
    for i in range(N):
        if i>1 and dp_check[i]==0:
            dp[i]=dp[i-1]+dp[i-2]

        dp[i]=dp[i]%1000000007

    print(dp[N-1])

Submission status: Wrong Answer

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

st = [1]*(n+1)
for i in range(m):
    st[li[i]-1] = 0

if st[0] == 0:
    if st[1] == 0:
        print(0)
elif st[0] == 1:
    if st[1] != 0:
        st[1] = 2
    elif st[1] == 0:
        pass
    
for i in range(2,n+1):
    if st[i] == 0:
        continue
    else:
        st[i] = (st[i-1] + st[i-2])%1000000007

print(st[n-1])

Submission status: Wrong Answer

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

st = [1]*(n+1)
for i in range(m):
    st[li[i]-1] = 0

if st[0] == 0 and st[1] == 0:
    print(0)
    exit()
elif st[0] == 0:
    st[1] = 1
elif st[0] == 1:
    st[1] = 2

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

Submission status: Wrong Answer

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

st = [1]*(n+1)
for i in range(m):
    st[li[i]-1] = 0

if st[0] == 0 and st[1] == 0:
    print(0)
elif st[0] == 0:
    st[1] = 1
elif st[0] == 1:
    st[1] = 2

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
n, m = map(int,input().split())
a = [int(input()) for i in range(m)]
b = [0] * (m+1)
if m > 0:
    b[0] = a[0] - 1
    b[m] = n - a[-1] - 1
for i in range(m-1):
    if a[i] + 1 == a[i+1]:
        print("0")
        quit()
if m >= 2:
    for i in range(m-1, 0, -1):
        b[i] = a[i] - a[i-1] - 2
ans = 1
step = [0] * (n+1)
step[0] = 1
step[1] = 1
for i in range(2, n+1):
    step[i] = (step[i-1] + step[i-2]) % 1000000007
for i in b:
    ans = ans * step[i] % 1000000007
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+1)
dp[0]=1
dp[1]=1
for i in range(2,n+1):
    if i in a:
        dp[i]=0
        continue
    dp[i]=dp[i-1]+dp[i-2]
    dp[i]%=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 i in range(m)]
dp=[-1]*(n+1)
dp[0]=1
dp[1]=1
for i in range(2,n+1):
    if i in a:
        dp[i]=0
        continue
    dp[i]=dp[i-1]+dp[i-2]
print(dp[-1]%(10**9+7))

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
A=[int(input()) for i in range(M)]
m=10**9+7
b=0
def DP():

                    
    a=1
    b=0

    def f(n):
        
        nonlocal a,b
        if n==0:

            if a>=b:
                
                b=0

            else:
                a=0

        if n % 2 == 1:

            b=a+b
        elif n % 2 == 0:

            a=a+b

        return max(a,b)

    return f

dp=DP()

for i in range(1,N+1):
    if (i in A) and (i+1 in  A):
        print(0)
        exit()
    if i in A:
        x=dp(0)
        continue
    else:
        x=dp(i)

print( x % m )

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())	
s=[1 for _ in range(n+2)]
for _ in range(m):
    s[int(input())+1]=0
mod=1000000007
num=[0 for _ in range(n+2)]
num[0]=num[1]=1
for i in range(n):
    if num[2]==2:
        num[2]=1
    num[i+2]=(num[i+1]*s[i+1]+num[i]*s[i])%mod
print(num[n+1])

Submission status: Wrong Answer

Solution code:
def typical_stairs():
    n, m = map(int, input().split())
    dangerous = set(map(int, open(0).read().split()))
    mod = 1000000007
    dp = [0] * (n + 1)
    dp[0] = 1
    if 1 not in dangerous:
        dp[1] = 1
    for i in range(2, n + 1):
        if i not in dangerous:
            dp[i] = dp[i - 2] + dp[i - 1]
    print(dp[-1] % mod)


if __name__ == '__main__':
    typical_stairs()

Submission status: Wrong Answer

Solution code:
def typical_stairs():
    n, m = map(int, input().split())
    dangerous = set(open(0).read().split())
    mod = 1000000007
    dp = [0] * (n + 1)
    dp[0] = 1
    if 1 not in dangerous:
        dp[1] = 1
    for i in range(2, n + 1):
        if i not in dangerous:
            dp[i] = dp[i - 2] + dp[i - 1]
    print(dp[-1] % mod)


if __name__ == '__main__':
    typical_stairs()

Submission status: Wrong Answer

Solution code:
import sys


def typical_stairs():
    n, m = map(int, input().split())
    dangerous = set(sys.stdin.readline())
    mod = 1000000007
    dp = [0] * (n + 1)
    dp[0] = 1
    if 1 not in dangerous:
        dp[1] = 1
    for i in range(2, n + 1):
        if i not in dangerous:
            dp[i] = dp[i - 2] + dp[i - 1]
    print(dp[-1] % mod)


if __name__ == '__main__':
    typical_stairs()

Submission status: Wrong Answer

Solution code:
# 階段の段数
n = 100
# 壊れている階段の数
m = 5
# 壊れている階段
a = [1, 23, 45, 67, 89]

# DPテーブル初期化値
INIT = 0
# DPテーブル(dp[i]：i番目の段に到達する移動方法の総数)
dp = [INIT for i in range(n + 1)]

# 0番目の段に到達するための移動方法は1通り
dp[0] = 1

# dp[1]～dp[n]までループ
for i in range(1, n + 1):
    # 階段が壊れている場合、到達できないので0通り
    if (i in a):
        dp[i] = 0
    # i = 1の場合、0番目の段から1つ飛びで来るパターンしかない
    elif (i <= 1):
        dp[i] = dp[i - 1]
    # それ以外の場合、1つ飛びパターンと2つ飛びパターンの合計
    else:
        dp[i] = dp[i - 1] + dp[i - 2]

# 最終地点のDPテーブルの値を1000000007で割った余りが答えとなる
print(dp[n] % 1000000007)

Submission status: Wrong Answer

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


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

if n == 0:
    print(0)

total = 1
i = 0
for x in a:
    if x == i:
        print(0)
        exit()
    total *= fib(x - i - 1)
    i = x + 1
if a[-1] != n:
    total *= fib(n - (a[-1] + 1))

print(total % 1000000007)

Submission status: Wrong Answer

Solution code:
import math
def fib(number):
    a, b = 0, 1
    for _ in range(number):
        a, b = b, a + b
    return b
N, M = map(int, input().split())
a = []
ans = 1
tmp = 0
for _ in range(M):
    a.append(int(input()))
for i in a:
    number = i-1-tmp
    if i == 1:
        tmp = 2
        continue
    else:
        if number<1:
            print(0)
            exit()
        else:
            ans *= fib(number)
            tmp = i+1
print((ans*fib(N-tmp))%1000000007)

Submission status: Wrong Answer

Solution code:
import math
def fib(number):
    a, b = 0, 1
    for _ in range(number-1):
        a, b = b, a + b
    return a
N, M = map(int, input().split())
a = []
ans = 1
tmp = 0
for _ in range(M):
    a.append(int(input()))
for i in a:
    number = i-tmp
    if i == 1:
        tmp = 2
        continue
    else:
        if number<1:
            print(0)
            exit()
        else:
            ans *= fib(number+2)
            tmp = i
print((ans*fib(N-tmp+2))%1000000007)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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