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 sys
N, M = map(int, input().split())

a_list = [0] * M

for m in range(M):
    a_list[m] = int(input())

for m in range(M - 1):
    if a_list[m] + 1 == a_list[m + 1]:
        print(0)
        sys.exit()
    else:
        continue

range_list = [i for i in range(1, N + 1)]
new_list = [0] * (M + 1)

new_list[0] = [0] + range_list[0: a_list[0] - 1]
new_list[M] = range_list[a_list[M - 1]:]

if M - 1 >= 1:
    for m in range(1, M):
        new_list[m] = range_list[a_list[m - 1]: a_list[m] - 1]

MOD = 1000000007

def fib(n):
    dp_list = [0] * n
    dp_list[0] = 1
    if n == 1:
        return 1
    dp_list[1] = 2
    
    for i in range(2, n):
        dp_list[i] = dp_list[i - 1] + dp_list[i - 2]
    return dp_list[n - 1]
print(new_list)
count = 1
for item in new_list:
    if not item or len(item) == 1:
        continue
    else:
        count *= (fib(len(item) - 1) % MOD)
        count %= MOD
        #print(count)
print(count)

Submission status: Runtime Error

Solution code:
import sys
    sys.setrecursionlimit(1000000)

def acinput():
    return list(map(int, input().split(" ")))


N, M = acinput()
a = [0]*(N+1)
for i in range(M):
    a[int(input())] = 1


Mod = 1000000007


def solve(x):
    global dp, Mod
    if dp[x] >= 0:
        return dp[x]

    if x < 0:
        return 0

    res = 0
    zeroflg = True

    if  a[x-2] != 1:
        res += solve(x-2) 
        zeroflg = False

    if a[x-1] != 1:
        res += solve(x-1)
        zeroflg = False

    if zeroflg:
        return 0
    dp[x] = res% Mod
    return res


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

print(solve(N) % Mod)


'''
5 1
1
'''

Submission status: Runtime Error

Solution code:
from sys import stdin
import sys
import numpy as np
from math import factorial
# [【Python】組み合わせ\(nCr\) 計算の高速化 \- Qiita](https://qiita.com/derodero24/items/91b6468e66923a87f39f#%E6%97%A2%E5%AD%98%E3%83%84%E3%83%BC%E3%83%AB%E3%82%92%E7%94%A8%E3%81%84%E3%81%9F%E6%89%8B%E6%B3%95%EF%BC%93%E8%A9%95%E4%BE%A1-)


def get_pattern(num):
    ret = 0

    if num == 1:
        ret = 1
    else:
        for i in range(int(num / 2) + 1):
            n = num - i
            r = i
            tmp = factorial(n) / factorial(r) / factorial(n - r)
            ret = ret + tmp

    return int(ret)


if __name__ == '__main__':
    N, M = [int(x) for x in stdin.readline().rstrip().split()]
    a = [int(input()) for i in range(M)]

    ret = 1

    for j in range(M):

        if j == 0:
            # 0マス目からa[j]-1マスまで移動するパターン数
            ret = ret * get_pattern(a[j]-1)
        elif a[j] - a[j-1] == 1:
            # 危険個所が連続していてパターン最後まで移動できるパターンなし
            ret = 0
            break
        else:
            # a[j-1]+1マスからa[j]-1マスまで移動するパターン数
            ret = ret * get_pattern((a[j]-1) - (a[j-1]+1))

        if j == M - 1:
            # a[j]+1マスからNマスへの移動パターン
            ret = ret * get_pattern(N - (a[j] + 1))

    if M == 0:
        ret = get_pattern(N)

    print(ret % 1000000007)

Submission status: Runtime Error

Solution code:
from math import factorial
from copy import copy

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

all_patterns = 1
start, end = None, None
for m_i in range(M + 1):
    if m_i < M:
        a_i = int(input())
    if m_i == 0:
        start = 0
        end = a_i - 1
        next_start = a_i + 1
    elif m_i == M:
        start = copy(next_start)
        end = N
    else:
        start = copy(next_start)
        end = a_i - 1
        next_start = a_i + 1
    passdiff = end - start
    num_2 = passdiff // 2
    residue = passdiff % 2

    tmp_patterns_for_range = 0
    for num2to1 in range(num_2 + 1):
        add_n_1 = num2to1 * 2
        tmp_num2 = num_2 - num2to1
        tmp_n_pattern = \
            factorial(tmp_num2 + add_n_1 + residue) \
            // factorial(tmp_num2) \
            // factorial(add_n_1 + residue)
        tmp_patterns_for_range += tmp_n_pattern
    all_patterns *= tmp_patterns_for_range

print(all_patterns % 1000000007)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
oks = [True] * (N+1)
a = [int(input()) for _ in range(M)]
for i in a:
    oks[i] = False
dp = [0] * (N+1)
if oks[1]:
    dp[1] = 1
if oks[2]:
    dp[2] = 2
for i in range(3, N+1):
    if oks[i]:
        dp[i] = int((dp[i-1] + dp[i-2]) % (1e9+7))


print(dp[N])

Submission status: Runtime Error

Solution code:
#ABC129C-TypicalStairs.py

#import list
from sys import stdin
from functools import lru_cache

input = stdin.readline

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

#variable

#function
#@lru_cache(maxsize=None)
def rootCount(position):
    if position < 0:
        return 0
    elif position == 0:
        return 1
    elif position in A:
        return 0
    else:
        return rootCount(position-1)+rootCount(position-2)
#class

#main function
def main():
    print(rootCount(N)%1000000007)




if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(1000000)

MAX_N = 100010
memo = [-1] * MAX_N

def f(n, na_set):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    elif n == 2:
        if len(na_set & set([1])) == 1:
            return 1
        return 2
    # すでに探索済みならメモを参照する
    elif memo[n] != -1:
        return memo[n]
    else:
        is_next_damaged = False
        is_2next_damaged = False

        if len(na_set & set([n-1])) == 1:
            is_next_damaged = True
        if len(na_set & set([n-2])) == 1:
            is_2next_damaged = True
        if is_next_damaged == True and is_2next_damaged == False:
            res = f(n-2, a_list)
        if is_next_damaged == False and is_2next_damaged == True:
            res = f(n-1, a_list)
        if is_next_damaged == False and is_2next_damaged == False:
            res = f(n-1, a_list) + f(n-2, a_list)

    # メモ
    memo[n] = res
    return res

if __name__ == '__main__':
    N, M = map(int, input().split())
    a_list = [int(input()) for i in range(M)]
    na_set = set([N-a for a in a_list])
    
    divided_by = 1000000007

    answer = -1

    # まず移動方法がない場合を考える。
    min_diff = sys.maxsize
    for i in range(1, len(a_list)):
        min_diff = min(min_diff, a_list[i] - a_list[i - 1])

    if min_diff == 1:
        answer = 0
    else:
        # 何らかなの移動方法が必ず存在する場合
        answer = f(N, na_set)%divided_by

    print(answer)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
#ABC129C-TypicalStairs.py

#import list
from sys import stdin
from functools import lru_cache

input = stdin.readline

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

#variable

#function
@lru_cache(maxsize=None)
def rootCount(position):
    if position < 0:
        return 0
    elif position == 0:
        return 1
    elif position in A:
        return 0
    else:
        return rootCount(position-1)+rootCount(position-2)
#class

#main function
def main():
    print(rootCount(N)%1000000007)




if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
i=0
nn=[]
j=-1

while i!=m:
    a=int(input())
    nn.append(a-j-1)
    if a-j==1:
        if j!=0:
            break
    j=a
    i=i+1
nn.append(n-a)

t=1
if a-j==1:
    t=0
    print(0)
else:
    #print(nn)
    pass
i=0
j=1
ans=1
while i!=len(nn):
    x=nn[i]
    ans_sub=1
    if x==3:
        ans_sub=2
        i=i+1
        ans_sub = int(ans_sub)
        ans = (ans * (ans_sub % 1000000007)) % 1000000007
    else:

        while (x-(1+2*j))>0:
            y=x-(1+(2*j))
            #print(y)
            #print(pow(j+1,y))
            nnt=((pow(j+1,y)-(j+1))/y)+(j+1)
            ans_sub=ans_sub+nnt
            j=j+1
            #print(nnt)
        i=i+1
        j=1
        ans_sub=int(ans_sub)
        ans=(ans*(ans_sub%1000000007))%1000000007
if t==1:
    print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)
from functools import lru_cache


@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)


def main():
    N, M = map(int, input().split())
    a = [-1] + [int(input()) for _ in range(M)]
    n = []
    for i in range(1, len(a)):
        if a[i - 1] + 1 == a[i]:
            return 0
        n.append(a[i] - a[i - 1] - 1)
    n.append(N - a[-1])
    ret = [fib(i) for i in n]
    ans = 1
    for i in ret:
        ans *= i
    return ans % 1000000007


if __name__ == "__main__":
    ans = main()
    print(ans)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
oks = [True] * (N+1)
a = [int(input()) for _ in range(M)]
for i in a:
    oks[i] = False
dp = [0] * (N+1)
if oks[1]:
    dp[1] = 1
if oks[2]:
    dp[2] = 1
for i in range(3, N+1):
    if oks[i]:
        dp[i] = int((dp[i-1] + dp[i-2]) % (1e9+7))


print(dp[N])

Submission status: Runtime Error

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

a_list = [0] * M

for m in range(M):
    a_list[m] = int(input())

for m in range(M - 1):
    if a_list[m] + 1 == a_list[m + 1]:
        print(0)
        sys.exit()
    else:
        continue

range_list = [i for i in range(1, N + 1)]
new_list = [0] * (M + 1)

new_list[0] = [0] + range_list[0: a_list[0] - 1]
new_list[M] = range_list[a_list[M - 1]:]

if M - 1 >= 1:
    for m in range(1, M):
        new_list[m] = range_list[a_list[m - 1]: a_list[m] - 1]

MOD = 1000000007

def fib(n):
    dp_list = [0] * n
    dp_list[0] = 1
    dp_list[1] = 2
    
    for i in range(2, n):
        dp_list[i] = dp_list[i - 1] + dp_list[i - 2]
    return dp_list[n - 1]

count = 1
for item in new_list:
    if not item or len(item) == 1:
        continue
    else:
        count *= (fib(len(item) - 1) % MOD)
        count %= MOD
        #print(count)
print(count)

Submission status: Runtime Error

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

def stair(x):
    if x == 0:
        return 0
    elif x == 1:
        return 1
    else:
        return stair(x - 1) + stair(x - 2)

if m == 0:
    s = stair(n + 1)
else:
    s = stair(A[0]) * stair(n - A[m - 1])
    for i in range(m - 1):
        a = A[i + 1] - A[i] - 1
        s = (s * stair(a) % 1000000007)



print(s%1000000007)

Submission status: Runtime Error

Solution code:
n,m = map(int, input().split())
bl = set([int(input())-1 for _ in range(m)])
l = [i for i in range(n)]

mod = 1000000007
al = [0]*n
if 0 in l and 1 in l:
    al[0] = 1
    al[1] = 2
elif 0 in l:
    al[0] =1
elif 1 in l:
    al[1] = 1
else:
    print(0)
    exit()

    
li = [i for i in l if i>=2]

for i in li:
    if i not in bl
        al[i] = (al[i-1] + al[i-2])%mod
        if al[i] == 0:
            print(0)
            exit()

print(al[-1])

Submission status: Runtime Error

Solution code:
from sys import stdin
import sys
import numpy as np
from math import factorial
# [【Python】組み合わせ\(nCr\) 計算の高速化 \- Qiita](https://qiita.com/derodero24/items/91b6468e66923a87f39f#%E6%97%A2%E5%AD%98%E3%83%84%E3%83%BC%E3%83%AB%E3%82%92%E7%94%A8%E3%81%84%E3%81%9F%E6%89%8B%E6%B3%95%EF%BC%93%E8%A9%95%E4%BE%A1-)


def get_pattern(num):
    ret = 0

    if num == 1:
        ret = 1
    else:
        for i in range(int(num / 2) + 1):
            n = num - i
            r = i
            tmp = factorial(n) / factorial(r) / factorial(n - r)
            ret = ret + tmp

    return int(ret)


if __name__ == '__main__':
    N, M = [int(x) for x in stdin.readline().rstrip().split()]
    a = [int(input()) for i in range(M)]

    ret = 1
    for j in range(M):

        if j == 0:
            # 0マス目からa[j]-1マスまでの移動するパターン数
            ret = ret * get_pattern(a[j]-1)
        elif a[j] - a[j-1] == 1:
            # 危険個所が連続していてパターン最後まで移動できパターンなし
            ret = 0
            break
        else:
            # a[j-1]+1マスからa[j]-1マスまで移動するパターン数
            ret = ret * get_pattern((a[j]-1) - (a[j-1]+1))

        if j == M - 1:
            # a[j]+1マスからNマスへの移動パターン
            ret = ret * get_pattern(N - (a[j] + 1))

    print(ret % 1000000007)

Submission status: Runtime Error

Solution code:
def exec_ncr(max_step, record_dict):
    for i in range(2, max_step):
        record_dict[i] = record_dict[i-1] + record_dict[i-2]


num_stair, num_wet = map(int, input().split(' '))

last_wet = -1
num_pattern = 1
d = {0: 1, 1: 1}
exec_ncr(100000, d)

for i in range(0, num_wet):
    wet = int(input())
    dry_step = wet - last_wet - 1
    last_wet = wet

    if dry_step <= 0:
        print('0')
        exit(0)

    elif dry_step == 1 or dry_step == 2:
        continue

    else:
        num_pattern *= d[dry_step-1]

# last step
dry_step = num_stair - last_wet

num_pattern *= d[dry_step-1]

print(num_pattern % 1000000007)
exit(0)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(1000000)

N, M = map(int, input().split())
oks = [True] * (N+1)
a = [int(input()) for _ in range(M)]
for i in a:
    oks[i] = False
dp = [0] * (N+1)
if oks[1]:
    dp[1] = 1
if oks[2]:
    print("a")
    dp[2] = 1
for i in range(3, N+1):
    if oks[i]:
        dp[i] = int((dp[i-1] + dp[i-2]) % (1e9+7))


print(dp[N])

Submission status: Runtime Error

Solution code:
from functools import lru_cache
@lru_cache(maxsize=1000)
def fib(n):
    if n < 2:
        return n
    else:
        return fib(n - 1) + fib(n - 2)

n,m = map(int,input().split())
a = []
a.append(0)
for i in range(m):
    b = int(input())
    b -= 1
    a.append(b)
a.append(n)
b = []

for i in range(1,n):
    b.append(fib(i))

c = []
if a[1] == 0:
    c.append(1)
else:
    c.append(b[a[1] - a[0] ])
i = 1
while i <= m:
    if a[i + 1] - a[i] - 2 >= 0:
        c.append(b[a[i + 1] - a[i]  - 2])
        i += 1
    #elif a[i + 1] - a[i] - 2 == 0:
        #c.append(1)
    else:
        c.append(0)
        break
#print(c)
d = c[0] 
i = 1
#print(d)
while i < len(c):
    d = d * c[i]
    i += 1
e = 1000000007
print(d % e)
#print(b[0])

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)

def intinput(): return map(int,sys.stdin.readline().split())

fib={0:0,1:1,2:1}
for i in range(3,100003):
    fib[i]=fib[i-1]+fib[i-2]
  #  fib.append(fib[i-1]+fib[i-2])

n,m=intinput()
mod=10**9+7
a=[int(sys.stdin.readline()) for _ in range(m)]
l=[a[0]]
for i in range(len(a)-1):
    l.append(a[i+1]-a[i]-1)
l.append(n-a[-1])
k=1
for i in l:
    k=fib[i]*k%mod
print(k%mod)

Submission status: Runtime Error

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

a_list = [0] * M

for m in range(M):
    a_list[m] = int(input())

for m in range(M - 1):
    if a_list[m] + 1 == a_list[m + 1]:
        print(0)
        sys.exit()
    else:
        continue

range_list = [i for i in range(1, N + 1)]
new_list = [0] * (M + 1)

new_list[0] = range_list[0: a_list[0] - 1]
new_list[M] = range_list[a_list[M - 1]:]

if M - 1 >= 1:
    for m in range(1, M):
        new_list[m] = range_list[a_list[m - 1]: a_list[m] - 1]

MOD = 1000000007

def fib(n):
    dp_list = [0] * n
    dp_list[0] = 1
    dp_list[1] = 2
    
    for i in range(2, n):
        dp_list[i] = dp_list[i - 1] + dp_list[i - 2]
    return dp_list[n - 1]

count = 1
for item in new_list:
    if not item:
        continue
    else:
        count *= (fib(len(item) - 1) % MOD)
        count %= MOD
print(count)

Submission status: Runtime Error

Solution code:
def acinput():
    return list(map(int, input().split(" ")))


N, M = acinput()
a = [0]*(N+100)
for i in range(M):
    a[int(input())] = 1


Mod = 1000000007


def solve(x):
    global dp, Mod
    if dp[x] >= 0:
        return dp[x]

    if x < 0:
        return 0

    res = 0
    zeroflg = True

    if  a[x-2] != 1:
        res += solve(x-2) 
        zeroflg = False

    if a[x-1] != 1:
        res += solve(x-1)
        zeroflg = False


    if zeroflg:
        return 0
    dp[x] = res% Mod
    return res


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

print(solve(N) % Mod)


'''
5 1
1
'''

Submission status: Runtime Error

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

for i in range(1,n):
    b.append(fib(i))

c = []
if a[1] == 0:
    c.append(1)
else:
    c.append(b[a[1] - a[0] ])
i = 1
while i <= m:
    if a[i + 1] - a[i] - 2 >= 0:
        c.append(b[a[i + 1] - a[i]  - 2])
        i += 1
    #elif a[i + 1] - a[i] - 2 == 0:
        #c.append(1)
    else:
        c.append(0)
        break
#print(c)
d = c[0] 
i = 1
#print(d)
while i < len(c):
    d = d * c[i]
    i += 1
e = 1000000007
print(d % e)
#print(b[0])

Submission status: Runtime Error

Solution code:
def acinput():
    return list(map(int, input().split(" ")))


N, M = acinput()
a = [0]*(N+100)
for i in range(M):
    a[int(input())] = 1


Mod = 1000000007


def solve(x):
    global dp, Mod
    if dp[x] >= 0:
        return dp[x]

    if x < 0:
        return 0

    res = 0
    zeroflg = True
    try:
        if  a[x-2] != 1:
            res += solve(x-2) 
            zeroflg = False
    except:
        pass
    try:
        if a[x-1] != 1:
            res += solve(x-1)
            zeroflg = False
    except:
        pass

    if zeroflg:
        return 0
    dp[x] = res% Mod
    return res


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

print(solve(N) % Mod)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# c ABC129
# input


def endFib(n, a1=1, a2=0):
    if (n < 1):
        return a1
    else:
        return endFib(n-1, a1 + a2, a1)


n, m = map(int, input().split())
o = 1
p = 0
if m == 0:
    if n < 3:
        o = n
    else:
        o = endFib(n)
    print(o % 1000000007)
    exit()
ft = int(input())
if ft < 3:
    p = ft
elif ft == 3:
    o = 2
    p = ft
elif ft > 3:
    o = endFib(ft-1)
    p = ft

for i in range(m-1):
    t = int(input())
    if t-p == 1:
        print(0)
        exit()
    elif t-p-1 == 1:
        p = t
    elif t-1-p == 2:
        p = t
    elif t-1-p == 3:
        o = o*2
        p = t
    elif t-1-p > 3:
        o = o*endFib(t-2-p)
        p = t
if n-p > 3:
    o = o * endFib(n-p-1)
elif n-p == 3:
    o = o*2
print(o % 1000000007)

Submission status: Runtime Error

Solution code:
def acinput():
    return list(map(int, input().split(" ")))


N, M = acinput()
a = [0]*(N+100)
for i in range(M):
    a[int(input())] = 1


Mod = 1000000007


def solve(x):
    global dp, Mod
    if dp[x] >= 0:
        return dp[x]

    if x < 0:
        return 0

    res = 0
    zeroflg = True
    try:
        if  a[x-2] != 1:
            res += (solve(x-2) % Mod)
            zeroflg = False
    except:
        pass
    try:
        if a[x-1] != 1:
            res += (solve(x-1) % Mod)
            zeroflg = False
    except:
        pass

    if zeroflg:
        return 0
    dp[x] = res
    return res


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

print(solve(N) % Mod)

Submission status: Runtime Error

Solution code:
from sys import stdin
import sys
import numpy as np
from math import factorial
# [【Python】組み合わせ\(nCr\) 計算の高速化 \- Qiita](https://qiita.com/derodero24/items/91b6468e66923a87f39f#%E6%97%A2%E5%AD%98%E3%83%84%E3%83%BC%E3%83%AB%E3%82%92%E7%94%A8%E3%81%84%E3%81%9F%E6%89%8B%E6%B3%95%EF%BC%93%E8%A9%95%E4%BE%A1-)


def get_pattern(num):
    ret = 0

    if num == 1:
        ret = 1
    else:
        for i in range(int(num / 2) + 1):
            n = num - i
            r = i
            tmp = factorial(n) / factorial(r) / factorial(n - r)
            ret = ret + tmp

    return int(ret)


if __name__ == '__main__':
    N, M = [int(x) for x in stdin.readline().rstrip().split()]
    a = [int(input()) for i in range(M)]

    ret = 1
    for j in range(M):
        if j == 0:
            ret = ret * get_pattern(a[j]-1)  # 0マス目からa[j]-1マスまでの移動パターン
        elif a[j] - a[j-1] == 1:
            ret = 0
            break
        elif j == M - 1:
            # a[j-1]+1マスからa[j]-1マスへ移動する全パターン
            ret = ret * get_pattern((a[j]-1) - (a[j-1]+1))
            # a[j]+1マスからNマスへの移動パターン
            ret = ret * get_pattern(N - (a[j] + 1))
        else:
            ret = ret * get_pattern((a[j]-1) - (a[j-1]+1))

    print(ret % 1000000007)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(200000)

n, m = list(map(int, input().split()))
b = [-1]
ans = 1

def dfs(top, bot, dp):
    if top == bot:
        return 1
    elif top < bot:
        return 0
    else:
        if (top,bot) in dp:
            return dp[(top,bot)]
        dp[(top,bot)] = dfs(top - 1, bot, dp) + dfs(top - 2, bot, dp)
    
for i in range(m):
    broken = int(input())
    b.append(broken)

b.append(n + 1)
##print (b)

dp = dict()

for i in range(len(b) - 1):
    if b[i + 1] == b[i] + 1:
        ans = 0
        break
    else:
##        print (b[i + 1] - 1, b[i] + 1)
        ans *= dfs(b[i + 1] - 1, b[i] + 1, dp)
        ans %= 1000000007

print (ans)

Submission status: Runtime Error

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

a_list = [0] * M

for m in range(M):
    a_list[m] = int(input())

for m in range(M - 1):
    if a_list[m] + 1 == a_list[m + 1]:
        print(0)
        sys.exit()
    else:
        continue

range_list = [i for i in range(1, N + 1)]
new_list = [0] * (M + 1)

a = 0
if a_list[0] == 1:
    new_list[0] = []
else:
    new_list[0] = [0] + range_list[0: a_list[0] - 1]
new_list[M] = range_list[a_list[M - 1]:]

if M - 1 >= 1:
    for m in range(1, M):
        new_list[m] = range_list[a_list[m - 1]: a_list[m] - 1]

MOD = 1000000007

def fib(n):
    dp_list = [0] * n
    dp_list[0] = 1
    dp_list[1] = 2
    
    for i in range(2, n):
        dp_list[i] = dp_list[i - 1] + dp_list[i - 2]
    return dp_list[n - 1]

count = 1
for item in new_list:
    if not item:
        continue
    else:
        count *= (fib(len(item) - 1) & MOD)
        count %= MOD
print(count)

Submission status: Runtime Error

Solution code:
import sys
n = [int(i) for i in input().split()]
a = []
for i in range(n[1]):
    a.append(int(input()))

a.append(n[0]+1)
a = sorted(list(set(a)))


def k(i):
    if i <= 1:
        return 1
    elif i == 2:
        return 2
    else:
        return k(i-2)+k(i-1)


for i in range(1, len(a)):
    if a[i]-a[i-1] == 1:
        print(0)
        sys.exit()
j = -1
ans = 1
for i in a:
    ii = i-j-2
    ans = ans*k(ii)
    j = i
if len(a) == 1:
    ans = k(n[0])
print(ans % 1000000007)

Submission status: Runtime Error

Solution code:
from sys import stdin
import sys
import numpy as np
from math import factorial
# [【Python】組み合わせ\(nCr\) 計算の高速化 \- Qiita](https://qiita.com/derodero24/items/91b6468e66923a87f39f#%E6%97%A2%E5%AD%98%E3%83%84%E3%83%BC%E3%83%AB%E3%82%92%E7%94%A8%E3%81%84%E3%81%9F%E6%89%8B%E6%B3%95%EF%BC%93%E8%A9%95%E4%BE%A1-)


def get_pattern(num):
    ret = 0

    if num == 1:
        ret = 1
    else:
        for i in range(int(num / 2) + 1):
            n = num - i
            r = i
            tmp = factorial(n) / factorial(r) / factorial(n - r)
            ret = ret + tmp

    return int(ret)


if __name__ == '__main__':
    N, M = [int(x) for x in stdin.readline().rstrip().split()]
    a = [int(input()) for i in range(M)]

    ret = 1
    for j in range(M):
        if j == 0:
            ret = ret * get_pattern(a[j]-1)  # 0マス目からa[j]-1マスまでの移動パターン
        elif j == M - 1:
            # a[j-1]+1マスからa[j]-1マスへ移動する全パターン
            ret = ret * get_pattern((a[j]-1) - (a[j-1]+1))
            # a[j]+1マスからNマスへの移動パターン
            ret = ret * get_pattern(N - (a[j] + 1))
        else:
            if a[j] - a[j-1] == 1:
                ret = 0
                break
            else:
                ret = ret * get_pattern((a[j]-1) - (a[j-1]+1))

    print(ret % 1000000007)

Submission status: Runtime Error

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

import math
a_1 = -1
nm_of_cs = 1
for m in range(M+1):
  a_0 = a_1
  if m < M:
    a_1 = int(input())
  else:
    a_1 = N+1
  if a_0 + 1 == a_1:
    nm_of_cs = 0
    break
  d_01 = (a_1 - 1) - (a_0 + 1)
  if d_01 % 2 == 0:
    nm_of_cs *= 2**(d_01 // 2)
  else :
    cs = 0
    for i in range(d_01//2 + 1):
      cs += math.factorial(d_01-i)/(math.factorial(i) + math.factorial(d_01-i*2))
    nm_of_cs *= cs

ans = nm_of_cs % 1000000007
print(ans)

Submission status: Runtime Error

Solution code:
from sys import stdin
import sys
import numpy as np
from math import factorial
# [【Python】組み合わせ\(nCr\) 計算の高速化 \- Qiita](https://qiita.com/derodero24/items/91b6468e66923a87f39f#%E6%97%A2%E5%AD%98%E3%83%84%E3%83%BC%E3%83%AB%E3%82%92%E7%94%A8%E3%81%84%E3%81%9F%E6%89%8B%E6%B3%95%EF%BC%93%E8%A9%95%E4%BE%A1-)


def get_pattern(num):
    ret = 0

    print(num)
    if num == 1:
        ret = 1
    else:
        for i in range(int(num / 2) + 1):
            n = num - i
            r = i
            tmp = factorial(n) / factorial(r) / factorial(n - r)
            ret = ret + tmp

    return int(ret)


if __name__ == '__main__':
    N, M = [int(x) for x in stdin.readline().rstrip().split()]
    a = [int(input()) for i in range(M)]

    ret = 1
    for j in range(M):
        if j == 0:
            ret = ret * get_pattern(a[j]-1)  # 0マス目からa[j]-1マスまでの移動パターン
        elif j == M - 1:
            # a[j-1]+1マスからa[j]-1マスへ移動する全パターン
            ret = ret * get_pattern((a[j]-1) - (a[j-1]+1))
            # a[j]+1マスからNマスへの移動パターン
            ret = ret * get_pattern(N - (a[j] + 1))
        else:
            if a[j] - a[j-1] == 1:
                ret = 0
                break
            else:
                ret = ret * get_pattern((a[j]-1) - (a[j-1]+1))

        print("---" + str(ret))
        print("---" + str(j))

    print("--ans--")
    print(ret % 1000000007)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
mod=10**9+7
a=[int(input()) for i in range(m)]
lst=[0]*(n+1)
lst[0]=1;lst[1]=1;lst[2]=2
for i in range(3,n+1):
    lst[i]=lst[i-1]+lst[i-2]
    
if m!=0:
    gap=[0]*m
    gap[0]=a[0]-1

    for i in range(1,m):
        gap[i]=a[i]-a[i-1]-2
    gap.append(n-a[-1]-1)
    

    ans=1
    for i in range(len(gap)):
        ans*=lst[gap[i]]
        #print('*',lst[gap[i]])
        ans=ans%(10**9+7)
    
    b=a[0]
    for i in range(1,len(a)):
        if b+1==a[i]:
            ans=0
        b=a[i]
    mod=10**9+7
    print(ans)
else:
    print(lst[n]%mod)
#print(gap)

Submission status: Runtime Error

Solution code:
import sys
import re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from copy import copy
import numpy as np
from numpy.fft import fft, ifft
from fractions import gcd
import math


def input(): return sys.stdin.readline().strip()


def INT(): return int(input())


def MAP(): return map(int, input().split())


def LIST(): return list(map(int, input().split()))


sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7


def Fib(n):
    a, b = 0, 1
    if n == 1:
        return a
    elif n == 2:
        return b
    else:
        for _ in range(n-2):
            a, b = b, a + b
        return b


n, m = MAP()

a = [INT() for _ in range(m)]

ans=1
for i in range(m - 1):
    p = a[i + 1] - a[i]-1
    if p == 0:
        ans *= 0
    elif p == 1 or p == 2:
        ans *= 1
    elif p == 3:
        ans *= 2
    else:
        ans *= Fib(p+1)
    #print(ans)

if a[0] == 1 or a[0] == 2:
    ans *= 1
elif a[0] == 3:
    ans *= 2
else:
    ans *= Fib(a[0] + 1)
    
if n-a[-1] == 1 or n-a[-1] == 2:
    ans *= 1
elif n-a[-1] == 3:
    ans *= 2
else:
    ans *= Fib(n-a[-1] + 1)
    

print(ans%MOD)

Submission status: Runtime Error

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

mod = 1000000007

def fib(n):
    memo=["EMPTY"]*(n+1)
    def inner(n):
        if n in lack:
            return 0
        elif n == 0:
            return 1
        elif n == 1:
            return 1
        elif memo[n] != "EMPTY":
            return memo[n] % mod
        else:
            memo[n] = inner(n-1)+inner(n-2)
            return memo[n] % mod
    return inner(n)

print(fib(N)% mod)

Submission status: Runtime Error

Solution code:
import sys
import re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from copy import copy
import numpy as np
from numpy.fft import fft, ifft
from fractions import gcd
import math


def input(): return sys.stdin.readline().strip()


def INT(): return int(input())


def MAP(): return map(int, input().split())


def LIST(): return list(map(int, input().split()))


sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7


def Fib(n):
    a, b = 0, 1
    if n == 1:
        return a
    elif n == 2:
        return b
    else:
        for _ in range(n-2):
            a, b = b, a + b
        return b


n, m = MAP()

a = [INT() for _ in range(m)]

ans=1
for i in range(m - 1):
    p = a[i + 1] - a[i]-1
    if p == 0:
        ans *= 0
    elif p == 1 or p == 2:
        ans *= 1
    elif p == 3:
        ans *= 2
    else:
        ans *= Fib(p+1)
    print(ans)

if a[0] == 1 or a[0] == 2:
    ans *= 1
elif a[0] == 3:
    ans *= 2
else:
    ans *= Fib(a[0] + 1)
    
if n-a[-1] == 1 or n-a[-1] == 2:
    ans *= 1
elif n-a[-1] == 3:
    ans *= 2
else:
    ans *= Fib(n-a[-1] + 1)
    

print(ans%MOD)