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: Runtime Error

Solution code:
import math
def calc_pattern(stairs):
    if stairs<=4:
        return stairs
    d=stairs//2+1
    l=[(math.factorial(i+(stairs-i*2))/math.factorial(i)/math.factorial(stairs-i*2))%1000000007  for i in range(d)]
    return (sum(l))%1000000007
"""
for stairs in range(1,11):
    print(stairs, calc_pattern(stairs))
"""
N,M=map(int,input().split())
A=[-1]
A.extend([int(input()) for m in range(M)])
A.append(N+1)
#print(A)
s=1
for m in range(M+1):
    if A[m+1]==1 or A[m]==N-1:
        continue
    if A[m]+1==A[m+1]:
        print(0)
        exit()
    else:
        #print("{} ~ {}".format(A[m]+1, A[m+1]-1))
        #print(calc_pattern(A[m+1]-1 - (A[m]+1)))
        s*=calc_pattern(A[m+1]-1 - (A[m]+1))
        s%=1000000007
        #print(s)
print(int(s))
# 0~A[0]-1, A[0]+1~A[1]-1
# A の先頭に-1を入れれば、A[i]+1~A[i+1]-1 で統一できそう

Submission status: Runtime Error

Solution code:
import math
def calc_pattern(stairs):
    if stairs<=4:
        return stairs
    d=stairs//2+1
    l=[(math.factorial(i+(stairs-i*2))/math.factorial(i)/math.factorial(stairs-i*2))%1000000007  for i in range(d)]
    return (sum(l))%1000000007
N,M=map(int,input().split())
A=[-1]
A.extend([int(input()) for m in range(M)])
A.append(N+1)
s=1
for m in range(M+1):
    if A[m+1]==1 or A[m]==N-1:
        continue
    if A[m]+1==A[m+1]:
        print(0)
        exit()
    else:
		s*=calc_pattern(A[m+1]-1 - (A[m]+1))
        s%=1000000007
print(int(s))

Submission status: Runtime Error

Solution code:
import math
def calc_pattern(stairs):
    if stairs<=4:
        return stairs
    d=stairs//2+1
    l=[(math.factorial(i+(stairs-i*2))/math.factorial(i)/math.factorial(stairs-i*2))%1000000007  for i in range(d)]
    return (sum(l))%1000000007

N,M=map(int,input().split())
A=[-1]
A.extend([int(input()) for m in range(M)])
A.append(N+1)

s=1
for m in range(M+1):
    if A[m+1]==1 or A[m+1]==N-1:
        continue
    if A[m]+1==A[m+1]:
        print(0)
        exit()
    else:
        s*=calc_pattern(A[m+1]-1 - (A[m]+1))
        s%=1000000007
print(int(s))

Submission status: Runtime Error

Solution code:
import math
def calc_pattern(stairs):
    d=stairs//2
    l=[(math.factorial(i+(d-i)*2)/math.factorial(i)/math.factorial((d-i)*2))%1000000007  for i in range(d+1)]
    return (sum(l))%1000000007

#stairs=10
#print(calc_pattern(stairs))

# if A[i]+1==A[i+1]: print(0) exit()
N,M=map(int,input().split())
#A=[int(input()) for n in range(M)]
A=[-1]
A.extend([int(input()) for m in range(M)])
A.append(N+1)
#print(A)
# now=0, for a in A:
# 0~A[0]-1, A[0]+1~A[1]-1
# A の先頭に-1を入れれば、A[i]+1~A[i+1]-1 で統一できそう
s=1
for m in range(M+1):
    if A[m]+1==A[m+1]:
        print(0)
        exit()
    else:
        #print("{} ~ {}".format(A[m]+1, A[m+1]-1))
        #print(calc_pattern(A[m+1]-1 - (A[m]+1)))
        s=(s * calc_pattern(A[m+1]-1 - (A[m]+1)))%1000000007
print(int(s))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**9)
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)]
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: Runtime Error

Solution code:
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())
a = [int(input()) for _ in range(m)]
ans = fib(a[0])*fib(n-a[m-1])
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) % (10**9+7)

print(ans)

Submission status: Runtime Error

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

stairs = []

for i in range(M):
    stairs.append(int(input()))
path = []
index = 1
if stairs[-1] == N-1:
    path.extend([1, 0])
    index += 1
else:
    path.extend([1, 1])
# caluclate from N-2 step (second last)

if N >= 2:
    for n in range(2, N):
        if N - n != stairs[-index]:
#             print(n, N - n, index, stairs[-index])
            path.append(path[n-2] + path[n-1])
        else:
            path.append(0)
            index += 1
    print((path[-1] + path[-2]) % (10**9+7)) 
#     print(path)
elif N < 2:
    print(1)

Submission status: Runtime Error

Solution code:
N, M = map(int,input().split())
a = [] 
for i in range(M):
    a.append(int(input()))
a.sort()
diff = [a[i+1]-a[i] for i in range(M-1)] if M!=1 else []
if diff and min(diff)==1 :
    print(0)
else:
    if not(diff):
        stairs = [a[0]-1,N-a[0]-1]
    else :
        stairs = [a[0]-1]+[diff[i]-2 for i in range(M-1)]+[N-a[-1]-1]
    
    t = [1,1]
    for i in range(max(stairs)-1):
        t.append(t[-1]+t[-2])
    ans = 1
    for i in stairs:
        ans *= t[i]
    print(ans%1000000007)

Submission status: Runtime Error

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[0] = 1
dp[1] = 2
    
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 hoal[0]==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
        
    #実際に求める
    #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: Runtime Error

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[0] = 1
dp[1] = 2


if 1 in hoal:
    dp[0] = 0
    dp[1] = 1
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()

#実際に求める
#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: Runtime Error

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[0] = 1
dp[1] = 2


if 1 in hoal:
    dp[0] = 0
    dp[1] = 1

if 2 in hoal:
    dp[1] = 0
    
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()

#実際に求める
#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)

Submission status: Runtime Error

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[0] = 1
dp[1] = 2
if 1 in hoal:
    dp[0] = 0
    dp[1] = 1
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()
        
#実際に求める
#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: Runtime Error

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[0] = 1
dp[1] = 2
if 1 in hoal:
    dp[0] = 0
    dp[1] = 1
dp_check = list()
dp_check = [0]*N

for i in range(M):
    dp_check[hoal[i]-1]=1

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

#実際に求める
#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: Runtime Error

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[0] = 1
dp[1] = 2
if 1 in hoal:
    dp[0] = 0
    dp[1] = 1
dp_check = list()
dp_check = [0]*N

for i in range(M):
    dp_check[hoal[i]-1]=1

for i in range(N):
    if dp_check[i]==1 and dp_check[i+1]==1:
        print("0")
        exit()

#実際に求める
#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: Runtime Error

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[0] = 1
dp[1] = 2
if 1 in hoal:
    dp[0] = 0
    dp[1] = 1

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

print(dp[N-1])

Submission status: Runtime Error

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[0] = 1
dp[1] = 2
if 1 in hoal:
    dp[0] = 0
    dp[1] = 1

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

print(dp[N-1])

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys

sys.setrecursionlimit(10 ** 7)


MOD = 1000000007  # type: int


def solve(N: int, M: int, a: "List[int]"):
    ways_to_stairs = {}
    stairs = []
    for i in range(N + 1):
        stairs.append(True)
    for i in a:
        stairs[i] = False

    routes_to_stairs = {0: 1}
    if 1 not in a:
        routes_to_stairs[1] = 1

    for i in range(N + 1):
        if i <= 1:
            continue
        if stairs[i]:
            ways = 0
            if stairs[i - 1]:
                ways += routes_to_stairs[i - 1]
            if stairs[i - 2]:
                ways += routes_to_stairs[i - 2]
        routes_to_stairs[i] = ways

    print(routes_to_stairs[N] % MOD)
    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(M)]  # type: "List[int]"
    solve(N, M, a)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int


def solve(N: int, M: int, a: "List[int]"):
    ways_to_stairs = {}
    stairs = []
    for i in range(N + 1):
        stairs.append(True)
    for i in a:
        stairs[i] = False

    routes_to_stairs = {0: 1}
    if 1 not in a:
        routes_to_stairs[1] = 1

    for i in range(N + 1):
        if i <= 1:
            continue
        if stairs[i]:
            ways = 0
            if stairs[i - 1]:
                ways += routes_to_stairs[i - 1]
            if stairs[i - 2]:
                ways += routes_to_stairs[i - 2]
        routes_to_stairs[i] = ways

    print(routes_to_stairs[N] % MOD)
    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(M)]  # type: "List[int]"
    solve(N, M, a)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n,m,*a=map(int,open(0).read().split())
b=[-1]*(n+1)
a+=[0,0]
for i in a:
    b[i]=0

if a[0]==1 and a[1]==2:
    b[1],b[2]=0,0
elif a[0]==1:
    b[2]=1
elif a[0]==2:
    b[1]=1
else:    
    b[1],b[2]=1,2
for i in range(3,n+1):
    if b[i]==-1:
        b[i]=(b[i-1]+b[i-2])%1000000007
print(b[-1])

Submission status: Runtime Error

Solution code:
n,m,*a=map(int,open(0).read().split())
b=[-1]*(n+1)
if m!=0:
    for i in a:
        b[i]=0
    if m>=2:    
        if a[0]==1 and a[1]==2:
            b[1],b[2]=0,0
    elif a[0]==1:
        b[2]=1
    elif a[0]==2:
        b[1]=1
    else:    
        b[1],b[2]=1,2
else:    
    b[1],b[2]=1,2  
for i in range(3,n+1):
    if b[i]==-1:
        b[i]=(b[i-1]+b[i-2])%1000000007
print(b[-1])

Submission status: Runtime Error

Solution code:
n,m,*a=map(int,open(0).read().split())
b=[-1]*(n+1)
if m!=0:
    for i in a:
        b[i]=0
    if a[0]==1 and a[1]==2:
        b[1],b[2]=0,0
    elif a[0]==1:
        b[2]=1
    elif a[0]==2:
        b[1]=1
    else:    
        b[1],b[2]=1,2
else:    
    b[1],b[2]=1,2  
for i in range(3,n+1):
    if b[i]==-1:
        b[i]=(b[i-1]+b[i-2])%1000000007
print(b[-1])

Submission status: Runtime Error

Solution code:
n,m,*a=map(int,open(0).read().split())
b=[-1]*(n+1)
if m!=0:
    for i in a:
        b[i]=0
    if a[0]==1 and a[1]==2:
        continue
    elif a[0]==1:
        b[2]=1
    elif a[0]==2:
        b[1]=1
    else:    
        b[1],b[2]=1,2
else:    
        b[1],b[2]=1,2        
for i in range(3,n+1):
    if b[i]==-1:
        b[i]=(b[i-1]+b[i-2])%1000000007
print(b[-1])

Submission status: Runtime Error

Solution code:
n,m,*a=map(int,open(0).read().split())
b=[-1]*(n+1)
if m!=0:
    for i in a:
        b[i]=0
    if a[0]==1:
        b[2]=1
    elif a[0]==2:
        b[1]=1
    else:    
        b[1],b[2]=1,2
else:    
        b[1],b[2]=1,2        
for i in range(3,n+1):
    if b[i]==-1:
        b[i]=(b[i-1]+b[i-2])%1000000007
print(b[-1])

Submission status: Runtime Error

Solution code:
n,m,*a=map(int,open(0).read().split())
b=[-1]*(n+1)
for i in a:
    b[i]=0
if a[0]==1:
    b[2]=1
elif a[0]==2:
    b[1]=1
else:    
    b[1],b[2]=1,2
for i in range(3,n+1):
    if b[i]==-1:
        b[i]=(b[i-1]+b[i-2])%1000000007
print(b[-1])

Submission status: Runtime Error

Solution code:
n,m,*a=map(int,open(0).read().split())
b=[-1]*(n+1)
for i in a:
    b[i]=0
if a[0]==1:
    b[2]=1
elif a[0]==2:
    b[1]=1
else:    
    b[1],b[2]=1,2
for i in range(3,n+1):
    if b[i]!=0:
        b[i]=(b[i-1]+b[i-2])%1000000007
print(b[-1])

Submission status: Runtime Error

Solution code:
n,m,*a=map(int,open(0).read().split())
b=[0]*(n+1)
if a[0]==1:
    b[2]=1
elif a[0]==2:
    b[1]=1
else:    
    b[1],b[2]=1,2
for i in range(3,n+1):
    if not i in a:
        b[i]=(b[i-1]+b[i-2])%1000000007
print(b[-1])

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
A=list(int(input()) for i in range(m))
dp=[0]*(n+1)
dp[0]=1
j=0
for i in range(1,n+1):
    if i==A[j]:
        dp[i]=0
        j +=1
    else:
        dp[i]=(dp[i-1]+dp[i-2])

print(dp[n]%1000000007)

Submission status: Runtime Error

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

mod = (10 ** 9) + 7

for i in range(1,N+1):
	if i in A:
		DP[i] = 0
	else:
		DP[i] = DP[i-1] + DP[i-2]

print(DP[n] % (mod))

Submission status: Runtime Error

Solution code:
n, m = map(int,input().split())
a = [int(input()) for i in range(m)]
b = [0] * (m+1)
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: Runtime Error

Solution code:
n, m = map(int,input().split())
a = [int(input()) for i in range(m)]
b = [0] * (m+1)
b[0] = a[0] - 1
b[m] = n - a[-1] - 1
if m >= 2:
    for i in range(m-1, 0, -1):
        b[i] = a[i] - a[i-1] - 2
for i in range(m-1):
    if a[i] + 1 == a[i+1]:
        print("0")
        quit()
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: Runtime Error

Solution code:
N, M = list(map(int, input().split()))
A = set(int(input()) for i in range(M))
x = [0] * (n+1)
x[0] = 1

for i in range(1, n+1): 
  if x[i] in A:
    x[i] = 0
  else:
    x[i] = (x[i-1] + x[i-2])%(10**9+7)
return x[n]

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
a=[0]*m
for i in range(m):
	a[i]=int(input())
	
def pattern(n):
	if n==0:
		return 1
	if n==1:
		return 1
	return pattern(n-1)+pattern(n-2)%1000000007

def renzoku(m):
	total=0
	for i in range(m-1):
		if a[i]==a[i+1]-1:
			total=1
			break;
	return total
	
if renzoku(m):
	print(0)
	
elif m==0:
	print(pattern(n))
	
else:
	total=pattern(n-a[m-1]-1)*pattern(a[0]-1)%1000000007
	for i in range(m-1):
		total*=pattern(a[i+1]-a[i]-2)
	print(total%1000000007)

Submission status: Runtime Error

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

def renzoku(m):
	total=0
	for i in range(m-1):
		if a[i]==a[i+1]-1:
			total=1
			break;
	return total
	
if renzoku(m):
	print(0)
	
elif m==0:
	print(pattern(n))
	
else:
	total=pattern(n-a[m-1]-1)*pattern(a[0]-1)%1000000007
	for i in range(m-1):
		total*=pattern(a[i+1]-a[i]-2)
	print(total%1000000007)

Submission status: Runtime Error

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

def renzoku(m):
	total=0
	for i in range(m-1):
		if a[i]==a[i+1]-1:
			total=1
			break;
	return total
	
if renzoku(m):
	print(0)
	
elif m==0:
	print(pattern(n))
	
else:
	total=pattern(n-a[m-1]-1)*pattern(a[0]-1)
	for i in range(m-1):
		total*=pattern(a[i+1]-a[i]-2)
	print(total%1000000007)

Submission status: Runtime Error

Solution code:
dp = [0] * (n+1)
dp[0] = 1

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

print(dp[n])

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
def typical_stairs():
    n, m, *dangerous = map(int, open(0).read().split())
    dangerous = set(*dangerous)
    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]) % mod
    print(dp[-1])


if __name__ == '__main__':
    typical_stairs()

Submission status: Runtime Error

Solution code:
def typical_stairs():
    n, m, dangerous = map(int, open(0).read().split())
    dangerous = set(dangerous)
    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]) % mod
    print(dp[-1])


if __name__ == '__main__':
    typical_stairs()

Submission status: Runtime Error

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


def typical_stairs():
    n, m = map(int, input().split())
    dangerous = set(int(input()))
    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]) % mod
    print(dp[-1])


if __name__ == '__main__':
    typical_stairs()

Submission status: Runtime Error

Solution code:
def typical_stairs():
    n, m = map(int, input().split())
    dangerous = set(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: Runtime Error

Solution code:
def typical_stairs():
    n, m = map(int, input().split())
    dangerous = list(int(input()) for _ in range(m))
    mod = 1000000007
    dp = [0] * (n + 1)
    dp[0] = 1
    if not dangerous[0] == 1:
        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: Runtime Error

Solution code:
def typical_stairs():
    n, m = map(int, input().split())
    dangerous = list(int(input()) for _ in range(m))
    mod = 1000000007
    dp = [0] * (n + 1)
    dp[0] = 1
    if not dangerous[0] == 1:
        dp[1] = 1
    else:
        dp[1] = 0
    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: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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


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


if n == 0:
    print(0)
elif n == 1:
    print(1)
if m == 0:
    print(fib(n))

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: Runtime Error

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

Submission status: Runtime Error

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


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


if n == 0:
    print(0)
elif n == 1:
    print(1)

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: Runtime Error

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


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


if n == 0:
    print(0)
elif n == 1:
    print(1)

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

print(total % 1000000007)

Submission status: Runtime Error

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

total = 1


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


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

print(total % 1000000007)

Submission status: Runtime Error

Solution code:
import math
def fib(number):
    a, b = 0, 1
    if number == 1:
        return a
    elif number == 0:
        return b
    else:
        for _ in range(number-2):
            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 number<1:
        print(0)
        exit()
    else:
        ans *= fib(number)
        tmp = i
print(number)

Submission status: Runtime Error

Solution code:
import sys
imput=sys.stdin.readline
n,m=map(int,input().split())
l=[0]*m
for i in range(m):
    l[i]=int(input())
#print(l)
dp=[0]*(n+1)
dp[0]=1
if l[0]!=1:
    dp[1]=1
for i in range(2,n+1):
    if i in l:
        dp[i]=0
    else:
        dp[i]=dp[i-1]+dp[i-2]
print(dp[-1]%1000000007)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
def calc_Stairs_Patterns(num):
    if num >= 2:
        return calc_Stairs_Patterns(num - 1) + calc_Stairs_Patterns(num - 2)
    elif num == -1:
        print(0)
        exit()
    else:
        return 1
N, M = map(int,input().split())
data = []
for i in range(M):
    data.append(int(input()))
ans = 1
stair = 0
for i in data:
    ans *= calc_Stairs_Patterns(i  - 1 - stair)
    stair = i + 1
ans *= calc_Stairs_Patterns(N - stair)
print(ans % 1000000007)

Submission status: Runtime Error

Solution code:
#bin/usr/env python3

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

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

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

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: Runtime Error

Solution code:
n,m=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+1):
    if i in a:
        b[i]=0 #0の代入で2連続以上の場合もカバー
    else:
        b[i]=b[i-1]+b[i-2]
print(b[-1]%1000000007)

Submission status: Runtime Error

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

n, m = map(int, input().split())
A = [int(input()) for _ in range(m)]
cnt = 0


def forward(steps):
    global cnt
    if steps > n:
        return
    if steps == n:
        cnt += 1
        return
    elif steps in A:
        return

    forward(steps + 1)
    forward(steps + 2)


forward(0)
print(cnt % 1000000007)

Submission status: Runtime Error

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

n, m = map(int, input().split())
A = [int(input()) for _ in range(m)]
cnt = 0


def forward(steps):
    global cnt
    if steps > n:
        return
    if steps == n:
        cnt += 1
        return
    elif steps in A:
        return

    forward(steps + 1)
    forward(steps + 2)


forward(0)
print(cnt % 1000000007)