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:
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:
            ret = ret * get_pattern((a[j]-1) - (a[j-1]+1))　# a[j-1]+1マスからa[j]-1マスへ移動する全パターン
            ret = ret * get_pattern(N - (a[j] + 1)) 　# a[j]+1マスからNマスへの移動パターン
        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())

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)
    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)
        count %= MOD
print(count)

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]
        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:
n , m = map(int, input().split())
a = []
p = 0
max_wid = 0
for i in range(m):
    b = int(input())
    a.append(b)
    if i > 0:
        max_wid = max(max_wid, b)
max_wid = max(max_wid, n - a[m-1])
fib = [1, 1]
for i in range(max_wid):
    l = len(fib)
    fib.append(fib[l-2] + fib[l-1])
 
ans = 1
if a[0] == 0:
    ans *= 0
else:
    ans *= fib[a[0]-1]
 
for i in range(m-1):
    if a[i+1] == a[i] + 1:
        ans *= 0
    else:
        ans *= fib[a[i+1]-a[i]-2]
        
 
ans *= fib[n - a[m-1]-1]
ans %= 1000000007
print(ans)

Submission status: Runtime Error

Solution code:
    import math
    def cmb(n, r):
        return math.factorial(n)// ( math.factorial(n-r) * math.factorial(r) )
     
     
     
    N,M = input().split()
     
    N = int(N)
    M = int(M)
     
    a = []
    ans = 1
     
    for i in range(M):
        newa = int(input())
        a.append(newa)
     
    if (M != 0):
        for k in range(M-1):
            if (a[k+1] - a[k] == 1):
                ans = 0
                
        
        
        for i in range(M + 1):
        
     
            if (i == 0):
                dan = a[i] - 1
            elif (i == M):
                dan = N - a[i - 1] - 1
            else:
                dan = a[i] - a[i - 1] - 2
     
            abletwo = (dan - (dan % 2)) // 2
            now = 0
     
            if (dan != 0):
     
                for j in range(abletwo + 1):
     
                    now += cmb (dan - j , j )
     
            else:
                now = 1
            
            ans *= now
     
    else:
        ans = 0
        abletwo = (N - (N % 2)) // 2
     
        for j in range(abletwo + 1):
     
            ans += cmb (N - j , j )
     
    ans = 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
#print(new_list)1

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)
        count %= MOD
print(count)

Submission status: Runtime Error

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

step=[0]*n
for _ in range(m):
    a=int(input())
    step[a-1]=-1

if step[0]!=-1:
    step[0]=1
if step[1]!=-1:
    step[1]=1
for i in range(2,n):
    if step[i]==-1:
        continue
    if step[i-1]!=-1:
        step[i]+=step[i-1]
    if step[i-2]!=-1:
        step[i]+=step[i-2]
print(step[n-1]%c_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:
        print(n)
    else:
        print(endFib(n))
    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:
mod = 10**9+7

def stairs(n):
    if n ==0:
        return 1
    if n ==1:
        return 1
    else:
        return stairs(n-1)+stairs(n-2)
def main():
    n,m=map(int,input().split(' '))
    a = [-1]
    a_dis=[]
    ans = 1
    for i in range(m):
        a.append(int(input()))
    for i in range(m):
        a_dis.append(a[i+1]-a[i]-2)
    a_dis.append(n-a[-1]-1)
    for i in a_dis:
        if i <0:
            ans = 0
            break
        tmp = stairs(i)%mod
        ans *=tmp
        ans %= mod
        tmp = 0
    print(ans)

main()

Submission status: Runtime Error

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

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

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

for x in a:
    dp[x] = -float('inf')

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

Submission status: Runtime Error

Solution code:
def fib(n):
    if n == 1 or n == 2:
        return 1
    else:
        return (fib(n - 1) + fib(n - 2)) % (10 ** 9 + 7)


def counter(n):
    if n == 0:
        return 0
    else:
#        f = round(phi**(n) / math.sqrt(5)) % (10**9+7)
        return fib(n)


N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
if M == 0:
    print(counter(N+1))
    exit()
a.append(N+1)
ans = counter(a[0])
for i in range(1,M+1):
    ans = (ans * counter(a[i]-a[i-1]-1)) % (10**9+7)
print(ans)

Submission status: Runtime Error

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

step=[0]*n
for _ in range(m):
    a=int(input())
    step[a-1]=-1

if step[0]!=-1:
    step[0]=1
if step[1]!=-1:
    step[1]=1
for i in range(n):
    if step[i]==-1:
        continue
    if step[i-1]!=-1:
        step[i]+=step[i-1]
    if step[i-2]!=-1:
        step[i]+=step[i-2]
print(step[n-1]%c_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()

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
#print(new_list)1

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)
        count %= MOD
print(count)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
  
broken_step = []
for _ in range(M):
    broken_step.append(int(input()))
      
import sys
sys.setrecursionlimit(10000000)

mod = 1000000007

memo = [-1] * (N+1)

if N == 0 and N not in broken_step:
    memo[N] = 1
elif N == 0 and N in broken_step:
    memo[N] = 0

if N == 1 and N not in broken_step:
    memo[N] = 1
    
elif N == 1 and N in broken_step:
    memo[N] = 0

def step_memo(N):
    
    if N in broken_step:
        return 0
        
    if memo[N] != -1:
        return memo[N]
    
    memo[N] =  (a * step_memo(N-1) + b * step_memo(N-2)) % mod
    return (a * step_memo(N-1) + b * step_memo(N-2)) % mod

print(step_memo(N))

Submission status: Runtime Error

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

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

val = [0,1]
j = 0
for i in range(1, N + 1):
    ans = val[0] + val[1]
    val[0] = val[1]
    val[1] = ans
    if i == a[j]:
        val[1] = 0
        if len(a) - 1 != j:
            j += 1

print(ans%(10**9+7))

Submission status: Runtime Error

Solution code:

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:
    print(endFib(n))
    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:
N, M = map(int, input().split())

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

val = [0,1]
j = 0
for i in range(1, N + 1):
    ans = val[0] + val[1]
    val[0] = val[1]
    val[1] = ans
    if i == a[j]:
        val[1] = 0
        if len(a) - 1 > j:
            j += 1

print(ans%(10**9+7))

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]
    if p == 1:
        ans*=0
    else:
        ans *= Fib(p+1)
    print(ans)

ans*=Fib(a[0]+1)*Fib(n-a[-1]+1)

print(ans%MOD)

Submission status: Runtime Error

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

for i in range(m):
  b=int(input())
  a.append(b)
    
def count(x):
    if x==-1:
        return 0
    elif x==0:
        return 1
    elif x in a:
        return 0
    else:
        return (count(x-2)+count(x-1))%1000000007
    
print(count(n))

Submission status: Runtime Error

Solution code:
def mulmod(x,y,p):
    return x*y % p

def fib_memo(n):
    memo = [0]*(n+1)

    def _fib(n):
        if n <= 1:
            return n
        if memo[n] != 0:
            return memo[n]
        memo[n] = _fib(n-1) + _fib(n-2)
        return memo[n]

    return _fib(n)

n,m = map(int,input().split())
a =[]
pos = 0
result = 1
last = -1
for i in range(m):
    x = int(input())
    if (last+1) == x:
        print(0)
        exit(0)
    last = x
    a.append(x)

for i in a:
    result = mulmod(fib_memo(i-pos),result,1000000007)
    pos = i+1

result = mulmod(fib_memo(n-pos+1),result,1000000007)

print(result)

Submission status: Runtime Error

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

gap=[0]*m
gap[0]=a[0]-1
for i in range(3,n+1):
    lst[i]=lst[i-1]+lst[i-2]
    
    
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)
#print(gap)

Submission status: Runtime Error

Solution code:
md = 1000000007
dp=[]
def countways(n,broken,ix):
	global dp,md
	if(dp[ix]!=-1):
		return dp[ix]

	ways = 0
	if((ix+1)<=n and broken[ix+1]==0):
		ways+=countways(n,broken,ix+1)
	if((ix+2)<=n and broken[ix+2]==0):
		ways+=countways(n,broken,ix+2)
	dp[ix]=(ways%md)
	return dp[ix]

n,m = list(map(int,input().split()))
dp = [-1 for i in range(n+1)]
dp[n] = 1
broken = [0 for i in range(n+1)]
for i in range(m):
	broken[int(input())]=1
# print(brok	en)
print(countways(n,broken,0)%md)

Submission status: Runtime Error

Solution code:
import resource
import sys


# Will segfault without this line.
resource.setrlimit(resource.RLIMIT_STACK, [0x10000000, resource.RLIM_INFINITY])
sys.setrecursionlimit(0x100000)

mod = int(1e9+7)

def dfs(i,dp,bad):
    if i == 0:
      return 1
    if i in dp:
      return dp[i]
    dp[i] = 0
    for d in (1,2):
      x = i-d;
      if 0 <= x and x not in bad:
        dp[i] += dfs(x,dp,bad)
        dp[i] %= mod
    return dp[i]

n,m = [int(a) for a in input().split()]
bad = set()
for _ in range(m):
  a = int(input())
  bad.add(a)
print(dfs(n,dict(),bad))

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, M
    if dp[x] >= 0:
        return dp[x]

    if x < 0:
        return 0

    res = 0
    zeroflg = True
    try:
        if x-2 >= 0 and a[x-2] != 1:
            res += solve(x-2) % Mod
            zeroflg = False
    except:
        pass
    try:
        if x-1 >= 0 and 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+10)
dp[0] = 1
dp[1] = 1

print(solve(N) % Mod)

Submission status: Runtime Error

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

if 1 in ls:
    steps=[1,0]
else:
    steps=[1,1]

for this_step in range(2,n+1):
    if this_step in ls:
        ap=0
    else:
        ap=steps[-1]+steps[-2]
    steps.append(ap)
    print(steps)

print(steps[-1]%1000000007)

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]
    if p == 1:
        ans*=0
    else:
        ans *= Fib(p+2)
    #print(ans)

ans*=Fib(a[0]+2)*Fib(n-a[-1]+2)

print(ans%MOD)

Submission status: Runtime Error

Solution code:
from collections import deque


def Fibonacci(n): 
    if n<0: 
        print("Incorrect input") 
    # First Fibonacci number is 0 
    elif n==1: 
        return 1
    # Second Fibonacci number is 1 
    elif n==2: 
        return 2
    else: 
        return Fibonacci(n-1)+Fibonacci(n-2) 
        

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

A = deque()

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

pos = 0
diff = []
la = None

for a in A:
    if la and a - la == 1:
        print(0)
        exit()
    d = (a) - pos
    diff.append(d)
    pos = a
    la = a

# 最後の階段
diff.append(N - pos)
diff = list(filter(lambda x: False if x <= 0 else True, diff))
F = [Fibonacci(d) for d in diff]

_sum = 1
for f in F:
    _sum *= f

print(_sum // 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,M
    if dp[x]>=0:
        return dp[x]

    if x<0:
        return 0

    res=0
    zeroflg=True
    if  x-1>=0 and a[x-1]!=1:
        res+=solve(x-1)%Mod
        zeroflg=False
    if x-2>=0 and a[x-2]!=1:
        res+=solve(x-2)%Mod
        zeroflg=False
    
    if zeroflg:
        return 0
    dp[x]=res
    return res

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

print(solve(N)%Mod)

Submission status: Runtime Error

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

def main(N, M, a_list):
    fib_memo = {}
    fib_memo[0] = 1
    fib_memo[1] = 1
    def fib(n):
        if n not in fib_memo:
            fib_memo[n] = fib(n-1) + fib(n-2)
        return fib_memo[n]

    mul = 1
    old_a = 0

    for a in a_list:
        if a != 1 and old_a == a - 1:
            print(0)
            return

        mul *= (fib(a - old_a - 1) % 1000000007)
        old_a = a
        

    mul *= (fib(N - a_list[-1] -1) % 1000000007)
    print(mul % 1000000007)




if __name__ == "__main__":
    N, M = [int(x) for x in input().split()]
    a_list = []
    for _ in range(M):
        a_list.append(int(input()))

    main(N, M, a_list)

Submission status: Runtime Error

Solution code:
NM= list(map(int, input().split()))
A = [int(input()) for i in range(NM[1])]

roots = 1
OUT = False

def fib(n):
    if n == 0:
        return 0
    if n == 1 or n == 2:
        return 1
    else:
        f = fib(n-1)+fib(n-2)
        return int(f)



for j in range(len(A)):
    #keynum 1 ブロックに1つ，飛ぶしかないのでスルー keynum 0 ブロックに0，問答無用で全体0通り
    keynum = 1

    if j == 0:
        keynum = A[j]
    else:
        keynum = A[j] - (A[j-1]+1)


    if keynum == 0:
        roots = 0
        OUT = True
        break
    elif keynum == 1 or keynum == 2:
        continue
    else:
        roots *= fib(keynum)


lastkeynum = NM[0]+1 - (A[-1]+1)
# print(lastkeynum)
if lastkeynum == 0:
    roots = 0
elif lastkeynum == 1 or lastkeynum == 2:
    roots = roots
else:
    roots *= fib(lastkeynum)


if OUT:
    roots = 0

print(int(roots%1000000007))
# print(int(fib(94)%1000000007))


# #解答例
# n,m=map(int,input().split())
# A=set(int(input()) for i in range(m))
# dp=[0]*(n+1)
# dp[0]=1
# for i in range(1,n+1):
#     # print("i {}, dp {}".format(i,dp[i-2]))
#     dp[i]=(dp[i-1]+dp[i-2])%(10**9+7)
#     if i in A:dp[i]=0
# print(dp[n])

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(11000)

mod = int(1e9+7)

def dfs(i,dp,bad):
    if i == 0:
      return 1
    if i in dp:
      return dp[i]
    dp[i] = 0
    for d in (1,2):
      x = i-d;
      if 0 <= x and x not in bad:
        dp[i] += dfs(x,dp,bad)
        dp[i] %= mod
    return dp[i]

n,m = [int(a) for a in input().split()]
bad = set()
for _ in range(m):
  a = int(input())
  bad.add(a)
print(dfs(n,dict(),bad))

Submission status: Runtime Error

Solution code:
from math import factorial
n, m = map(int, input().split())
broken = [-1]
x = 0
y = 0
for i in range(m):
    b = int(input())
    broken.append(b)
    if x == 1:
        if b == broken[i-1] + 1:
            print(0)
            y = 1
            break
    x = 1
broken.append(n+1)
anslist = []
for i in range(m+1):
    d = broken[i+1] - broken[i] - 1
    if d == 1 or d == 0:
        continue
    dd = d - 1
    if dd == 1:
        pass
    else:
        mskip = dd // 2
        d_way = 0
        for j in range(1, mskip+1):
            d_way += factorial(dd-j*2+ j) /(factorial(dd-j*2) * factorial(j))
    d_way += 1 
    anslist.append(int(d_way))
if d_way != 0:
    ans = 1
    for i in range(len(anslist)):
        ans *= anslist[i]
if y == 0:
    if ans == 0:
        print(1)
    else:
        print(int(ans%1000000007))

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]
        else:
            memo[n] = inner(n-1)+inner(n-2)
            return memo[n]
    return inner(n)% mod

print(fib(N)% mod)

Submission status: Runtime Error

Solution code:
import sys

mod = int(1e9+7)

def dfs(i,dp,bad):
    if i == 0:
      return 1
    if i in dp:
      return dp[i]
    dp[i] = 0
    for d in (1,2):
      x = i-d;
      if 0 <= x and x not in bad:
        dp[i] += dfs(x,dp,bad)
        dp[i] %= mod
    return dp[i]

n,m = [int(a) for a in input().split()]
bad = set()
for _ in range(m):
  a = int(input())
  bad.add(a)
print(dfs(n,dict(),bad))

Submission status: Runtime Error

Solution code:
n,m = map(int, input().split())
listA = [int(input()) for i in range(m)]
listB = [0]*(n+1)
for k in range(m):
    listB[listA[k]] = 1
if(listB[1]==1 and listB[2]==1):
    a,b = 0,0
elif(listB[1]==1):
    a,b = 0,1
elif(listB[2]==1):
    a,b = 1,0
else:
    a,b = 1,2

for j in range(1, n-1):
    if(listB[j+2]!=0):
        a,b = b,0
    if(listB[j+2]==0):
        a,b = b,a+b

print(b%1000000007)

Submission status: Runtime Error

Solution code:
def fib2(n):
    if n <= 1:
        return n
    result = [1, 0, 0, 1]
    matrix = [1, 1, 1, 0]
    while n > 0:
        if n % 2:
            result = mul(matrix, result)
        matrix = mul(matrix, matrix)
        n //= 2
    return result[2]

def mul(a, b):
    return [a[0]*b[0] + a[1]*b[2],
            a[0]*b[1] + a[1]*b[3],
            a[2]*b[0] + a[3]*b[2],
            a[2]*b[1] + a[3]*b[3]]

inp = input()
n = int(inp.split()[0])
m = int(inp.split()[1])
a = []
for i in range(m):
  a.append(int(input()))
  
mul_list = []
nochance = False
for j in range(m+1):
  if j == 0:
    ss = a[0]
    if ss <= 0:
      p = 1
    else:
      p = fib2(ss)
    mul_list.append(p)
  elif j == m:
    step = n - a[-1]
    p = fib2(step)
    mul_list.append(p)
  else:
    step = a[j] - a[j-1] - 1
    if step == 0:
      nochance = True
      break
    p = fib2(step)
    mul_list.append(p)
    

if nochance:
  print(0)
else:
  ans = 1
  for b in mul_list:
    ans *= b
  print(ans%1000000007)

Submission status: Runtime Error

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

n,m=map(int,input().split())
a=[int(input()) for i in range(m)]
ans = fib(a[0]-1)%1000000007
for i in range(m-1):
  if a[i+1]-a[i]==1:
    ans=0
    break
  ans = ans*fib(a[i+1]-a[i]-2)%1000000007
ans = ans*fib(n-a[m-1]-1)%1000000007
print(ans)

Submission status: Runtime Error

Solution code:
import sys

mod = int(1e9+7)

def dfs(i,dp,bad):
    if i == 0:
      return 1
    if i in dp:
      return dp[i]
    dp[i] = 0
    for d in (1,2):
      x = i-d;
      if 0 <= x and x not in bad:
        dp[i] += dfs(x)
        dp[i] %= mod
    return dp[i]

n,m = (int(a) for a in input().split())
bad = set()
for _ in range(m):
  a = int(input())
  bas.add(a)
print(dfs(n,dict(),bad))

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,M
    if dp[x]>=0:
        return dp[x]

    if x<0:
        return 0

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

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

print(solve(N)%Mod)

Submission status: Runtime Error

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

# フィボナッチ数列の関数
def fibonacci(n):
    f = ((1 + 5**0.5) / 2)**n / 5**0.5 + 0.5
    return int(f)

# 段の切れ目ごとの場合の数を算出
R = len(a) - 1
for i in range(R):
    x = a[i + 1] - a[i] -1
    pattern.append(fibonacci(x))

# 段の切れ目ごとの場合の数の積
for i in range(len(pattern)):
    ans = ans * pattern[i] % 1000000007

# 1段目まで、最終弾までの数
s1 = fibonacci(a[0])
s2 = fibonacci(N - a[-1])

# かける
ans = ans * s1 * s2 % 1000000007

# 2弾続けて壊れている場合はNG
for i in range(M - 1):
    if a[i] + 1 == a[i + 1]:
        ans = 0

print(ans)

Submission status: Runtime Error

Solution code:
from math import factorial
import sys
N,M=map(int,input().split())
ANS1=1
ANS2=1
ANS3=1
A=int(input())
list1=[A]
DAN=A
B=DAN-DAN//2
for k in range(B):
  a = factorial(B) / factorial(k+1) / factorial(B - (k+1))
  ANS1+=a
for i in range(1,M):
  ans2=1
  A=int(input())
  list1+=[A]
  DAN=A-list1[i-1]-1
  B=DAN-DAN//2
  if A==list1[i-1] or A==list1[i-1]+1 and M!=1:
    print(0)
    sys.exit()
  for k in range(B):
    a = factorial(B) / factorial(k+1) / factorial(B - (k+1))
    ANS2+=a
  ANS3*=ANS2
DAN=N-A-1
B=DAN-DAN//2
for t in range(B):
  a = factorial(B) / factorial(t+1) / factorial(B - (t+1))
  ANS3+=a
ANS=ANS1*ANS2*ANS3  
print(int(ANS)%1000000007)

Submission status: Runtime Error

Solution code:
from math import factorial
n, m = map(int, input().split())
broken = [-1]
x = 0
y = 0
for i in range(m):
    b = int(input())
    broken.append(b)
    if x == 1:
        if b == broken[i-1] + 1:
            print(0)
            y = 1
            break
    x = 1
broken.append(n+1)
anslist = []
for i in range(m+1):
    d = broken[i+1] - broken[i] - 1
    if d == 1:
        continue
    dd = d - 1
    mskip = dd // 2
    d_way = 0
    for j in range(1, mskip+1):
        d_way += factorial(dd-j*2+ j) /(factorial(dd-j*2) * factorial(j))
    d_way += 1 
    anslist.append(int(d_way))
if d_way != 0:
    ans = 1
    for i in range(len(anslist)):
        ans *= anslist[i]
if y == 0:
    if ans == 0:
        print(1)
    else:
        print(int(ans%1000000007))

Submission status: Runtime Error

Solution code:
from functools import lru_cache
 
 
N, M = map(int, input().split())
# 壊れている床番号
a = []
for _ in range(M):
    a.append(int(input()))
# ルートの総数
root = 0
# 今いる階段の段数
now = 0
 
 
def isSafe(now):
    """
    1, 2段先共になければ0
    1段先だけあれば1
    2段先だけあれば2
    1, 2段先共にあれば3
    """
    now_1 = not (now-1) in a
    now_2 = not (now-2) in a
    if now<=1:
        return 0
    elif now==2:
        return int(now_1)
    else:
        return int(now_1 + now_2*2)
 
 
@lru_cache(maxsize=1000)
def step(N):
    # N段を登る移動方法数
    if N <= 1:
        if not (1 in a):
            return 1   
        else:
            return 0
    elif N==2:
        if not (2 in a):
            return step(1) + 1
        else:
            return step(1)
    elif isSafe(N)==1:
        return step(N-1)
    elif isSafe(N)==2:
        return step(N-2)
    elif isSafe(N)==3:
        return step(N-1)+step(N-2)
    else:
        return 0
 
print(step(N)%1000000007)

Submission status: Runtime Error

Solution code:
import sys
inputs = sys.stdin.readline
def main():
	ans = 1
	a = 0
	b = 0
	flg2 = 0
	N, M = map(int,inputs().split())
	A =[0]*(M+1)
	for i in range(M):
		a = int(inputs())
		A[i] = a-1-b
		b = a + 1
	A[M] = N - b
	A.sort()
	if A [0] < 0:
		flg2 = 1
	p = 1
	q = 1
	t = 0
	flg = 0
	while (A[t]<2):
		t = t+1
		if t > M:
			flg2 = 1
	for k in range(2,N+1):
		r = p + q
		p = q
		q = r
		while (A[t] == k):
			ans = ans*r%1000000007
			t += 1
			if t == M+1:
				flg = 1
				break
		if flg == 1:
			break
	if flg2 == 0:
		print(ans%1000000007)
	else:
		print(0)
main()