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:
#!/usr/bin/python3
# -*- coding: utf-8 -*-

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

k = ((a[0]-1) - 0) - 1
tmp = 1 # noskip
for i in range(k//2+1):
    #print(i)
    tmp += k - 2*i
way.append(tmp)

for i in range(1, M):
    if a[i] - a[i-1] == 1:
        print(0)
        exit()
    else:
        k = ((a[i]-1) - (a[i-1]+1)) - 1
        tmp = 1 # noskip
        for i in range(k//2+1):
            tmp += k - 2*i
        way.append(tmp)

k = (N - (a[M-1]+1)) - 1
tmp = 1 # noskip
for i in range(k//2+1):
    tmp += k - 2*i
way.append(tmp)

#print(way)
res = 1
for tmp in way:
    res *= tmp
res = res % 1000000007
print(res)

Submission status: Runtime Error

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-

import math

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

k = ((a[0]-1) - 0) - 1
tmp = 1 # noskip
for i in range(math.ceil(k/2)):
    #print(i)
    tmp += k - 2*i
way.append(tmp)

for i in range(1, M):
    if a[i] - a[i-1] == 1:
        print(0)
        exit()
    else:
        k = ((a[i]-1) - (a[i-1]+1)) - 1
        tmp = 1 # noskip
        for i in range(math.ceil(k/2)):
            tmp += k - 2*i
        way.append(tmp)

k = (N - (a[M-1]+1)) - 1
tmp = 1 # noskip
for i in range(math.ceil(k/2)):
    tmp += k - 2*i
way.append(tmp)

#print(way)
res = 1
for tmp in way:
    res *= tmp
res = res % 1000000007
print(res)

Submission status: Runtime Error

Solution code:
# 2019-11-14 10:01:24(JST)
import sys
# import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
from functools import reduce
# import operator as op
# from scipy.misc import comb # float
# import numpy as np 

mod = 10 ** 9 + 7
def main():
    n, m, *broken_treads = [int(x) for x in sys.stdin.read().split()]
    safe = sorted((set(range(1, n+1)) - set(broken_treads)))

    p = [0] * (n + 1) # p[i] は連続するi段の、1~i段目までの登り方の総パターン
    p[1] = 1
    for i in range(2, n+1):
        p[i] = p[i-1] + p[i-2]

    count = 1 # 最初に0th stepを踏んでいるので1
    sections = []
    for i in range(1, n+1):
        if i in safe:
            count += 1
        else:
            if count >= 1:
                sections.append(p[count])
                count = 0
            else: # countが0だったら一つ前も壊れている
                print(0)
                sys.exit()
    
    if count >= 1:    # if the last is not broken.
        sections.append(p[count])

    ans = reduce(lambda x, y: x * y % mod, sections)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

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

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

Submission status: Runtime Error

Solution code:
# DP
N, M = map(int, input().split())
broken = list(map(int, input().split()))

MOD = 10**9+7
dp = [0 for i in range(N+2)]
dp[N] = 1

for i in reversed(range(N)):
    if i in broken:
        continue
    dp[i] = dp[i+1] + dp[i+2]
    dp[i] %= MOD

print(dp[0])

Submission status: Runtime Error

Solution code:
import numpy as np
N , M = map(int, input().split())
a = list()
for n in range(M):
	a.append(int(input()))
dp = np.zeros(N+1)
dp[0] = 1
dp[1] = 0 if a[0] == 1 else 1
for n in range(2,N+1):
	if n in a:
		dp[n] = 0
	else:
		dp[n] = (int(dp[n-1])+int(dp[n-2]))%(10**9+7)
print(int(dp[N]))

Submission status: Runtime Error

Solution code:
import numpy as np
N , M = map(int, input().split())
a = list()
for n in range(M):
    a.append(int(input()))
dp = np.zeros(N+1)
dp[0] = 1
dp[1] = 0 if a[0] == 1 else 1
for n in range(2,N+1):
    if n in a:
        dp[n] = 0
    else:
        dp[n] = (int(dp[n-1])+int(dp[n-2]))%(10**9+7)
print(int(dp[N]))

Submission status: Runtime Error

Solution code:
import numpy as np
import math
N , M = map(int, input().split())
a = list()
for n in range(M):
    a.append(int(input()))
dp = np.zeros(N+1)
dp[0] = 1
dp[1] = 0 if a[0] == 1 else 1
for n in range(2,N+1):
    if n in a:
        dp[n] = 0
    else:
        dp[n] = (int(dp[n-1])+int(dp[n-2]))%(math.pow(10,9)+7)
print(int(dp[N]))

Submission status: Runtime Error

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


arr = [0] * (N + 1)
arr[1] = 1 if a[1] else 0
arr[2] = arr[1] + 1 if a[2] else 0

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

print(arr[N] % 1000000007)

Submission status: Runtime Error

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


memo = {}

def find(n):
    if n == 0:
        return 1
    if n == 1:
        return 1
    if n in memo:
        return memo[n]
    memo[n] = (find(n - 1) if a[n - 1] else 0) + (find(n - 2) if a[n - 2] else 0)
    return memo[n]


print(find(N) % 1000000007)

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
a=[int(input()) for i in range(M)]
dp=[1]*(N+2)
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])

Submission status: Runtime Error

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+2)
    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: Runtime Error

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

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)
    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]
    print(dp[N]%1000000007)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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] * M

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

    dp[0] = 0 if 0 in a else 1
    dp[1] = dp[0] + (0 if 1 in a 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: Runtime Error

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] * N

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

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)

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


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

    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)

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


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

MOD = 1_000_000_007


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

    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)

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


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

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

Submission status: Runtime Error

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

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

Submission status: Runtime Error

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

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

Submission status: Runtime Error

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

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

Submission status: Runtime Error

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

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
#%%
import sys
def input():
    return sys.stdin.readline().rstrip()

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

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

    divider = 1000000007
    dp[0], dp[1] = 1, 1
    for i in range(2,N+1):
        dp[i]=(dp[i-1]+dp[i-2])%divider

    p = 0
    ans = 1
    for a in a_list:
        r = dp[a-1-p] if a-1 >= p else 0
        ans = (ans*r)%divider 
        p = a + 1
    else:
        if a < N:
            r = dp[N-p]%divider
            ans = (ans*r)%divider

    print(ans)
        

# %%
if __name__ == '__main__':
    main()

# %%
# from atcoder_test import doTest
# doTest("abc129","c",main)

Submission status: Runtime Error

Solution code:
#%%
import sys
def input():
    return sys.stdin.readline().rstrip()

def comb(N):
    if N<0:
        return 0
    if N==0 or N==1:
        return 1

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

    for j in range(1,N+1):
        for i in [1,2]:
            if j == i:
                dp[i][j] = 1
            else:
                dp[i][j] = dp[1][j-i] + dp[2][j-i]
    return dp[1][N]+dp[2][N]

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

    divider = 1000000007
    p = 0
    ans = 1

    for a in a_list:
        r = comb(a-1-p)%divider
        ans = ans%divider 
        ans = (ans*r)%divider 
        p = a + 1
    else:
        if a < N:
            r = comb(N-p)%divider
            ans = ans%divider
            ans = (ans*r)%divider

    print(ans)
        

# %%
if __name__ == '__main__':
    main()

# %%
# from atcoder_test import doTest
# doTest("abc129","c",main)

Submission status: Runtime Error

Solution code:
#%%
import sys
def input():
    return sys.stdin.readline().rstrip()

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

    def comb(N):
        if N<0:
            return 0
        if N==0:
            return 1

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

        for j in range(1,N+1):
            for i in [1,2]:
                if j == i:
                    dp[i][j] = 1
                else:
                    dp[i][j] = dp[1][j-i] + dp[2][j-i]
        return dp[1][N]+dp[2][N]

    divider = 1000000007
    p = 0
    ans = 1

    for a in a_list:
        r = comb(a-1-p)%divider
        ans = ans%divider 
        ans = (ans*r)%divider 
        p = a + 1
    else:
        if a < N:
            r = comb(N-p)%divider
            ans = ans%divider
            ans = (ans*r)%divider

    print(ans)
        

# %%
if __name__ == '__main__':
    main()

# %%
# from atcoder_test import doTest
# doTest("abc129","c",main)

Submission status: Runtime Error

Solution code:
#%%
import sys
def input():
    return sys.stdin.readline().rstrip()

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

    def comb(N):
        if N<0:
            return 0
        if N==0:
            return 1

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

        for j in range(1,N+1):
            for i in [1,2]:
                if j == i:
                    dp[i][j] = 1
                else:
                    dp[i][j] = dp[1][j-i] + dp[2][j-i]
        return dp[1][N]+dp[2][N]

    divider = 1000000007
    p = 0
    ans = 1

    for a in a_list:
        r = comb(a-1-p)%divider
        ans = (ans*r)%divider 
        p = a + 1
    else:
        if a < N:
            r = comb(N-p)%divider
            ans = (ans*r)%divider

    print(ans)
        

# %%
if __name__ == '__main__':
    main()

# %%
# from atcoder_test import doTest
# doTest("abc129","c",main)

Submission status: Runtime Error

Solution code:
#%%
import sys
def input():
    return sys.stdin.readline().rstrip()

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

    def comb(N):
        if N<0:
            return 0
        if N==0:
            return 1
        dp=[[0 for _ in range(N+1)] for _ in range(3)]
        for j in range(1,N+1):
            dp[0][j] = 1
            for i in [1,2]:
                if j == i:
                    dp[i][j] = dp[i-1][j]
                else:
                    dp[i][j] = dp[1][j-i] + dp[2][j-i]
        return dp[1][N]+dp[2][N]
    p = 0
    divider = 1000000007
    ans = 1
    for a in a_list:
        r = comb(a-1-p)%divider
        ans = ans * r
        p = a + 1
    else:
        if a < N:
            r = comb(N-p)%divider
            ans = ans * r
    ans = ans%divider
    print(ans)
        

# %%
if __name__ == '__main__':
    main()

# %%
# from atcoder_test import doTest
# doTest("abc129","c",main)

Submission status: Runtime Error

Solution code:
#%%
import sys
def input():
    return sys.stdin.readline().rstrip()

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

    def comb(N):
        if N<0:
            return 0
        if N==0:
            return 1
        import numpy as np
        dp=np.zeros((3, N+1), dtype=np.int64)
        for j in range(1,N+1):
            dp[0][j] = 1
            for i in [1,2]:
                if j == i:
                    dp[i][j] = dp[i-1][j]
                else:
                    dp[i][j] = dp[1][j-i] + dp[2][j-i]
        return dp[1][N]+dp[2][N]
    p = 0
    divider = 1000000007
    ans = 1
    for a in a_list:
        r = comb(a-1-p)%divider
        ans = ans * r
        p = a + 1
    else:
        if a < N:
            r = comb(N-p)%divider
            ans = ans * r
    ans = ans%divider
    print(ans)
        

# %%
if __name__ == '__main__':
    main()

# %%
# from atcoder_test import doTest
# doTest("abc129","c",main)

Submission status: Runtime Error

Solution code:
N,M = map( int, input().split() )
break_list = []
for i in range(M):
    break_list.append( int( input() ) )
   
fib = [0] * (N + 1)
if 1 in break_list:
    fib[1] = 0
else:
    fib[1] = 1
    
fib[0] = 1
for i in range(N - 1):
	if i + 2 in break_list:
    	fib[i + 2] = 0
    else:
        fib[i + 2] = fib[i] + fib[i + 1]

if N == 1:
  print( fib[1] )
else:
  print( fib[i+2] %  1000000007 )

Submission status: Runtime Error

Solution code:
N,M = map( int, input().split() )
break_list = []
for i in range(M):
    break_list.append( int( input() ) )
   
fib = [0] * (N + 1)
if 1 in break_list:
    fib[1] = 0
else:
    fib[1] = 1
    
if 0 in break_list:
    print(0)
else:
    fib[0] = 1
    for i in range(N - 1):
        if i + 2 in break_list:
            fib[i + 2] = 0
        else:
            fib[i + 2] = fib[i] + fib[i + 1]

    print( fib[i+2] %  1000000007 )

Submission status: Runtime Error

Solution code:
N,M = map( int, input().split() )
break_list = []
for i in range(M):
    break_list.append( int( input() ) )
k = 1    
fib = [0] * (N + 1)
if 1 in break_list:
    fib[1] = 0
else:
    fib[1] = 1
    
if 0 in break_list:
    k = -1
    
fib[0] = 1
for i in range(N - 1):
    if i + 2 in break_list:
        fib[i + 2] = 0
    else:
        fib[i + 2] = fib[i] + fib[i + 1]
    
if k > -1:
    print( fib[i+2] %  1000000007 )

else:
    print(0)

Submission status: Runtime Error

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
t = 1
for i in break_list:
    sum_c = 0
    end = i - 1
    if start > end:
        t = -1
    step_1 = end - start
    step_2 = int( ( end - start ) / 2 )
    for j in range(step_2 + 1):
        k = step_1 - 2 * j
        sum_c += fac(k + j) // ( fac(j) * fac(k) )
    ans *= sum_c
    start = i + 1
    
if t == 1:
    print( ans % 1000000007 )
else:
    print(0)

Submission status: Runtime Error

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
k = 1
for i in break_list:
    sum_c = 0
    end = i - 1
    if start > end:
        k = -1
    step_1 = end - start
    step_2 = int( ( end - start ) / 2 )
    for j in range(step_2 + 1):
        k = step_1 - 2 * j
        sum_c += fac(k + j) // ( fac(j) * fac(k) )
    ans *= sum_c
    start = i + 1
    
if k == 1:
    print( ans % 1000000007 )
else:
    print(0)

Submission status: Runtime Error

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

for i in range(m):
    a.append(int(input().strip()))

broken = [False] * (n + 1)

for i in range(m):
    broken[a[i]] = True

dp = []
dp.append(1)

if (broken[1]):
    dp.append(0)
else:
    dp.append(1)

for i in range(2, n + 1, 1):
    if (broken[i]):
        dp.append(0)
    else:
        dp.append((dp[i - 1] + dp[i - 2]) % 1_000_000_007)

print(dp[n])

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
a = [int(input()) for i in range(m)]
s = [1] + [0 for i in range(1,n+1)]
p = 1000000007
if n==1:
    print(1)
else:
    ind = 0
    if a[0] != 1:
        s[1] = 1
    else:
        ind += 1
    for i in range(2,n+1):
        if ind < m:
            if a[ind] != i:
                s[i] = (s[i-1] + s[i-2]) % p
            else:
                ind += 1
        else:
            s[i] = (s[i-1] + s[i-2]) % p
    print(s[-1])

Submission status: Runtime Error

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

# オブジェクトがハッシュ可能であるか判定する.
def hashable(x):
    try:
        hash(x)
        return True
    except TypeError:
        return False

# 関数を Memoize するデコレータ.
def memoize(callable):
    cache = {}
    def wrapper(*args, **kwargs):
        key = args + tuple(kwargs.items())
        if not hashable(key):
            return callable(*args, **kwargs)
        if key not in cache:
            cache[key] = callable(*args, **kwargs)
        return cache[key]
    return wrapper

# from functools import lru_cache
# @lru_cache(maxsize=None)
@memoize
def fibo(n):
    if n in A:
        return 0
    elif n == 0 or n == 1:
        return 1
    return fibo(n-2) + fibo(n-1)

print(fibo(N) % 1000000007)

Submission status: Runtime Error

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

from functools import lru_cache
@lru_cache(maxsize=None)
def fibo(n):
    if n in A:
        return 0
    elif n == 0 or n == 1:
        return 1
    return fibo(n-2) + fibo(n-1)

print(fibo(N) % 1000000007)

Submission status: Runtime Error

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

from functools import lru_cache
@lru_cache(maxsize=None)
def fibo(n):
    if n in A:
        return 0
    elif n == 0 or n == 1:
        return 1
    return fibo(n-1) + fibo(n-2)

print(fibo(N) % 1000000007)

Submission status: Runtime Error

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

from functools import lru_cache
@lru_cache(maxsize=None)
def fibo(n):
    if n in A:
        return 0
    elif n == 0 or n == 1:
        return 1
    return fibo(n-1) + fibo(n-2)

print(fibo(N) % 1_000_000_007)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
a = []
for i in range(M):
  a.append(int(input()))
dp = []
dp.append(1)
if a:
  cantuse = a.pop(0)
  if cantuse == 1:
    dp.append(0)
    cantuse = a.pop(0)
  else:
    dp.append(1)
else:
  cantuse = -1
  dp.append(1)

for i in range(N-1):
  if (i+2) == cantuse:
    dp.append(0)
    if a:
      cantuse = a.pop(0)
  else:
    dp.append(dp[-1]+dp[-2])
print(dp[-1]%1000000007)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
a = []
for i in range(M):
  a.append(int(input()))
dp = []
dp.append(1)
if a:
  cantuse = a.pop(0)
  if cantuse == 1:
    dp.append(0)
  cantuse = a.pop(0)
else:
  cantuse = -1
  dp.append(1)

for i in range(N-1):
  if (i+2) == cantuse:
    dp.append(0)
    if a:
      cantuse = a.pop(0)
  else:
    dp.append(dp[-1]+dp[-2])
print(dp[-1]%1000000007)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
a = []
for i in range(M):
  a.append(int(input()))
dp = []
if a:
  cantuse = a.pop(0)
dp.append(1)
if cantuse == 1:
  dp.append(0)
  cantuse = a.pop(0)
else:
  dp.append(1)

for i in range(N-1):
  if (i+2) == cantuse:
    dp.append(0)
    if a:
      cantuse = a.pop(0)
  else:
    dp.append(dp[-1]+dp[-2])
print(dp[-1]%1000000007)

Submission status: Runtime Error

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

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

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

Submission status: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
a = [-1]

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

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

#print(a)

b = []
for i in range(M+1):
    b.append(a[i+1] - a[i] - 2)

#print(b)

def func(n):
    if n == -1:
        retval = 0
    elif n >= 0 and n <= 1:
        retval = 1
    else:
        retval = func(n-2) + func(n-1)
    return retval % (10**9 + 7)

result = 1

for i in range(M+1):
    result = result * func(b[i])
    result = result % (10**9 + 7)

print(result)

Submission status: Runtime Error

Solution code:
a = [-1]

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

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

#print(a)

b = []
for i in range(M+1):
    b.append(a[i+1] - a[i] - 2)

#print(b)

def func(n):
    if n == -2:
        retval = 0
    elif n >= -1 and n <= 1:
        retval = 1
    else:
        retval = func(n-2) + func(n-1)
    return retval % (10**9 + 7)

result = 1

for i in range(M+1):
    result = result * func(b[i])
    result = result % (10**9 + 7)

print(result)

Submission status: Runtime Error

Solution code:
from math import factrial
def comb(n, r):
    return factorial(n) // (factorial(n - r) * factorial(r))

t=list(map(int, input().split()))
N=int(t[0])
M=int(t[1])
a=[-1]
for i in range(M):
        a.append(int(input()))
a.append(N+1)
d=1
for i in range(M+1):
        b=a[i+1]-a[i]-1
        c=0
        if (b==0):c=0
        else:
                for j in range(int((b-1)/2)+1):
                        c = c + int(comb((b-1-j),j))
                        c = c%1000000007
        d = d*c
        d = d%1000000007
print(d)