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:
N,M = map(int, input().split())
a = [int(input()) for i in range(M)]

flag = 0
if m > 2:
    for i in range(M-1):
        if a[i+1] - a[i] == 1:
            flag += 1

if flag >= 1:
    print(0)


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

    ans = fib(a[0]-1)
    for i in range(M-1):
        ans = (ans * fib(a[i+1]-a[i]-2))%(10**9+7)

    ans = (ans * fib(N-a[-1]-1))%(10**9+7)

    print(ans)

Submission status: Runtime Error

Solution code:
mod = 1000000007


def feb(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    k = (n + 1) / 2 if n % 2 else n / 2
    fib_k = feb(k)%mod
    fib_k_1 = feb(k - 1)%mod
    return fib_k**2 + fib_k_1**2 if n % 2 else (2 * fib_k_1 + fib_k) * fib_k

    # if n==0:
    #     return 0
    # if n==1:
    #     return 1
    # else:
    #     return feb(n-1)+feb(n-2)
    # root = math.sqrt(5)
    # return int((1/root)*(((1+root)/2)**n - ((1-root)/2)**n))

def calculate(n, b):
    diff = [b[i+1] - b[i] - 1 for i in range(len(b)-1)]
    diff.insert(0, b[0])
    diff.append(n - b[-1])
    sum = 1
    for d in diff:
        if d == 0:
            return 0
        sum *= feb(d)%mod
        sum = sum%mod
    return sum


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

print(calculate(n, b))

Submission status: Runtime Error

Solution code:
from itertools import permutations
n,m = map(int,input().split())
lst = [int(input()) for i in range(m)]
slst = []
cnt = 1

for i in range(m):
  if len(slst) == 0:
    slst.append(list(range(0,lst[i])))
  else:
    slst.append(list(range(lst[i-1]+1,lst[1])))
slst.append(list(range(lst[-1]+1,n+1)))
#print(slst)
for i in slst:
  if len(i) == 1:
    cnt*=1
  elif len(i) == 2:
    cnt*= 2
  elif len(i) == 3:
    cnt*= 3
  elif len(i) == 4:
    cnt*= 4
  elif len(i) == 5:
    cnt*= 7
  elif len(i) == 6:
    cnt*= 12
print(cnt)
"""
  for j in range(len(i)//2+1):
    tmp = [[2]*j+[1]*(len(i)-2*j)]
    plst = list(permutations(tmp))
    print(plst)
"""

Submission status: Runtime Error

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

MOD = 1000000007  # type: int

def solve(N: int, M: int, a: "List[int]"):
    l = [a[i+1]-a[i] for i in range(M-1)]
    if(len(l) and min(l)<=1):
        print(0)
        exit()

    dp = [1] * (N+1)
    dp[1] = 1
    dp[2] = 2
    x = 0
    
    for i in range(2,N+1):
        if(a[x] == i-1):
            dp[i] = dp[i-2] % MOD
            # x = min(x+1,M-1)
        elif(a[x] == i-2):
            dp[i] = dp[i-1] % MOD
            x = min(x+1,M-1)
        else:
            dp[i] = (dp[i-1] + dp[i-2]) % MOD
    
    print(dp[N])
    
    return


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

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

ans = 0
def up(now):
    global ans
    if now == n:
        ans += 1
        return
    elif now > n:
        return
    
    if now+1 in a and now+2 in a:
        print(0)
        exit(0)
        #return
    elif now+1 in a:
        up(now+2)
    elif now+2 in a:
        up(now+1)
    else:
        up(now+1)
        up(now+2)
        
if __name__ == '__main__':
    up(0)
    print(ans % 1000000007)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
ali = [int(input()) for _ in range(m)]
dif = []
cap = 0
for num in ali:
  dif.append(num-cap)
  cap = num
dif.append(n-cap+1)
dif[0] += 1
ref = [0,0,1,1]
a,b = 1,1
if m <= 10000:
  nnn = 1000
else:
  nnn = 100000
for i in range(nnn):
  a,b = b,a+b 
  ref.append(b)
ans = 1
for num in dif:
  ans *= (ref[num] % 1000000007)
print(ans % 1000000007)

Submission status: Runtime Error

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



if n == 1:
    print(1)

elif n == 2:
    if m == 0:
        print(2)
    elif m == 1:
        if a[0] == 2:
            print(0)
        else:
            print(1)
        
    
elif n == a[-1]:
    print(0)
    
else:
    if m == 0:
        t = -1
    else:
        c = 0
        t = a[c]-1
    x, y = 0, 1
    for i in range(n):
        if x == 0 and y == 0:
            break
        elif i == t:
            x, y = y, 0
            if a[c]-1 == a[-1]-1:
                continue
            else:
                c += 1
                t = a[c]-1
        else:
            x, y = y, x + y
    print(y%1000000007)

Submission status: Runtime Error

Solution code:
import numpy as np

n, m = map(int, input().split())
a = [int(input()) for i in range(m)]
div = 1000000007
arr = [1 ,2]
for i in range(2, n):
    arr.append(int(arr[i - 2] + arr[i - 1]))
ans = []

for i in range(m):
    if i == 0:
        if a[i] > 1:
            ans.append(a[i] - 1)
        else:
            ans.append(1)
    elif i < m:
        ans.append(a[i] - a[i-1] - 1)
ans.append(n - a[-1] - 1)

if m == 0:
    print(ans[-1])
else:
    b = 1
    for i in ans:
        if i == 0:
            b *= 0
        else:
            b *= arr[i-1]
    print(b % div)

Submission status: Runtime Error

Solution code:

broken_step = []

line = [int(s) for s in input().split()]

N, M = line[0], line[1]

for i in range(M):
    step_num = int(input().split()[0])-1
    broken_step.append(step_num)
    
    
dp = list(range(N))
if 0 in broken_step and 1 not in broken_step:
    dp[0] = 0
    dp[1] = 1
elif 0 not in broken_step and 1 not in broken_step:
    dp[0] = 1
    dp[1] = 2
elif 0 in broken_step and 1 in broken_step:
    dp[0] = 0
    dp[1] = 0
else:
    dp[0] = 1
    dp[1] = 0
    

for i in range(N-2):
    dp[i+2] = dp[i]+dp[i+1] if i+2 not in broken_step else 0
    
print(dp[N-1]%1000000007)

Submission status: Runtime Error

Solution code:
def comb(start, end):
  dist = end - start
  if dist%2 == 0:
    step = dist/2
    return 2**step
  else:
    step = int(dist/2)
    return (2**step) *(step + 1)

N, M = map(int, input().split())
startpoint = 1
result = 1

for i in range(M):
  ai = int(input())
  if ai == 1:
    startpoint = 2
    continue
  if ai <= startpoint:
    result = 0
    break
  endpoint = ai - 1
  result *= comb(startpoint, endpoint)
  startpoint = ai + 1
  print(result)
  
result *= comb(startpoint, N)
print(int(result % 1000000007))

Submission status: Runtime Error

Solution code:
N, M=map(int, input().split())
a=[int(input()) for _ in range(M)]
tmp=[1,1,2]
for i in range(N):
    tmp.append(tmp[-1]+tmp[-2])
def func(x):
    if x==-1:
        return 0
    elif x==-2:
        return 1
    else:
        return tmp[x]

s=func(a[0]-1)
for i in range(0, M-1):
    s*=func(a[i+1]-a[i]-2)
s*=func(N-a[M-1]-1)
print(s%1000000007)

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 = []

for a in A:
    d = (a - 1) - pos
    diff.append(d)
    pos = a + 1

# 最後の階段
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)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
a=[]
for i in range(m):
	a.append(int(input()))
if m>1:
	for i in range(m-1):
		if a[i]+1==a[i+1]:
			print(0)
			exit()
list1=[1,1]
for i in range(n):
	nu=list1[i]+list1[i+1]
	list1.append(nu)
ans=[]
x=a[0]
if x==1:
	ans.append(1)
else:
	ans.append(list1[x-1])
if m>1:
	for i in range(0,m-1):
		x=a[i+1]-a[i]-1
		ans.append(list1[x-1])
x=n-a[-1]
ans.append(list1[x-1])
import functools
import operator
result = functools.reduce(operator.mul, ans)
p,mod=divmod(result, 1000000007)
print(mod)

Submission status: Runtime Error

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


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


M=1000000007

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

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

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

print(solve(N)%M)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
mod = 10 ** 9 + 7
pat = [0] * (n + 1)
pat[0] = 1
pat[1] = 1
for i in range(m):
    pat[i] = -1

pat = [1]
for i in range(2, n + 1):
    if pat[i] < 0:
        continue
    if pat[i - 1] > 0:
        pat[i] = (pat[i] + pat[i - 1]) % mod
    if pat[i - 2] > 0:
        pat[i] = (pat[i] + pat[i - 2]) % mod

print(pat[n])

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

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

for i in range(len(a_null)-1):
    if a_null[i] + 1 == a_null[i+1]:
        print(0)
        sys.exit()
a = np.zeros(N+1)
for i in a_null:
    a[a_null] = 1

zero_index = np.where(a == 0)[0]
zero_renban = []
zero = 0
for i in range(len(zero_index)-1):
    if zero_index[i] + 1 == zero_index[i+1]:
        zero += 1
        if i +1 == len(zero_index)-1:
            zero_renban.append(zero+1)
    else:
        zero_renban.append(zero+1)
        zero = 0

memo = np.zeros(10**6)
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]

ans = 1
for i in zero_renban:
    ans *= fib(i)

print(int(ans%1000000007))

Submission status: Runtime Error

Solution code:
N, M=map(int, input().split())
a=[int(input()) for _ in range(M)]
tmp=[1,1,2]
for i in range(N):
    tmp.append(tmp[-1]+tmp[-2])
def func(x):
    if x==-1:
        return 0
    else:
        return tmp[x]

s=func(a[0]-1)
for i in range(0, M-1):
    s*=func(a[i+1]-a[i]-2)
s*=func(N-a[M-1]-1)
print(s%1000000007)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

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

for i in range(len(a_null)-1):
    if a_null[i] + 1 == a_null[i+1]:
        print(0)
        sys.exit()
a = np.zeros(N+1)
for i in a_null:
    a[a_null] = 1

zero_index = np.where(a == 0)[0]
zero_renban = []
zero = 0
for i in range(len(zero_index)-1):
    if zero_index[i] + 1 == zero_index[i+1]:
        zero += 1
        if i +1 == len(zero_index)-1:
            zero_renban.append(zero)
    else:
        zero_renban.append(zero)
        zero = 0

zero_renban = np.array(zero_renban, dtype = 'int64')
zero_renban = np.delete(zero_renban, np.where(zero_renban == 0)[0])

memo = np.zeros(10**6)
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]

ans = 1
for i in zero_renban:
    ans *= fib(i)

print(int(ans%1000000007))

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
mod = 10 ** 9 + 7
a = []
pat = [0] * (n + 1)
pat[0] = 1
pat[1] = 1
for i in range(m):
    a.append(int(input()))
    pat[a] = -1

pat = [1]
for i in range(2, n + 1):
    if pat[i] < 0:
        continue
    if pat[i - 1] > 0:
        pat[i] = (pat[i] + pat[i - 1]) % mod
    if pat[i - 2] > 0:
        pat[i] = (pat[i] + pat[i - 2]) % mod

print(pat[n])

Submission status: Runtime Error

Solution code:
mod = 1000000007

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

# def feb(n):
#     if n == 0:
#         return 0
#     if n == 1:
#         return 1
#     k = (n + 1) / 2 if n % 2 else n / 2
#     fib_k = feb(k)
#     fib_k_1 = feb(k - 1)
#     return fib_k**2 + fib_k_1**2 if n % 2 else (2 * fib_k_1 + fib_k) * fib_k

    # if n==0:
    #     return 0
    # if n==1:
    #     return 1
    # else:
    #     return feb(n-1)+feb(n-2)
    # root = math.sqrt(5)
    # return int((1/root)*(((1+root)/2)**n - ((1-root)/2)**n))

def calculate(n, b):
    diff = [b[i+1] - b[i] - 1 for i in range(len(b)-1)]
    diff.insert(0, b[0])
    diff.append(n - b[-1])
    sum = 1
    for d in diff:
        if d == 0:
            return 0
        sum *= feb(d)%mod
        sum = sum%mod
    return sum


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

print(calculate(n, b))

Submission status: Runtime Error

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

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

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

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

print (ans)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

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

for i in range(len(a_null)-1):
    if a_null[i] + 1 == a_null[i+1]:
        print(0)
        sys.exit()
a = np.zeros(N+1)
for i in a_null:
    a[a_null] = 1

zero_index = np.where(a == 0)[0]
zero_renban = []
zero = 0
for i in range(len(zero_index)-1):
    if zero_index[i] + 1 == zero_index[i+1]:
        zero += 1
        if i +1 == len(zero_index)-1:
            zero_renban.append(zero+1)
    else:
        zero_renban.append(zero+1)
        zero = 0

zero_renban = np.array(zero_renban, dtype = 'int64')
zero_renban = np.delete(zero_renban, np.where(zero_renban == 0)[0])

memo = np.zeros(10**6)
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]

ans = 1
for i in zero_renban:
    ans *= int(fib(i))

print(int(ans%1000000007))

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
for i in range(m):
    t = int(input())
    if t < 3:
        p = t
        pass
    elif t == 3:
        p = t
        o = 2
        pass
    elif t-p == 1:
        print(0)
        exit()
    elif t-p-1 == 1:
        p = t
        pass
    elif t-1-p == 2:
        p = t
        pass
    elif t-1-p > 2:
        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:
s = list(map(int, input().split()))
n,m = s[0],s[1]
a = [int(input()) for i in range(m)]



if n == 1:
    print(1)

# elif n == 2 and a[-1] ==1:
#     print(1)
    
elif n == a[-1]:
    print(0)
    
else:
    if m == 0:
        t = -1
    else:
        c = 0
        t = a[c]-1
    x, y = 0, 1
    for i in range(n):
        if x == 0 and y == 0:
            break
        elif i == t:
            x, y = y, 0
            if a[c]-1 == a[-1]-1:
                continue
            else:
                c += 1
                t = a[c]-1
        else:
            x, y = y, x + y
    print(y%1000000007)

Submission status: Runtime Error

Solution code:
import functools

@functools.lru_cache(None)
def Fib(n):
    if n == 1:
        return 0
    elif n == 2:
        return 1
    else:
        return Fib(n-1)+Fib(n-2)

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

#出来ない判定
for i in range(m-1):
    if (a[i+1] - a[i]) == 1:
        print(0)
        exit()

#壊れてる床前後で組み合わせ
allnum = 1
i = 0
for b in range(m):
    allnum = (allnum * Fib(a[b]-1 - i + 2))%MOD
    i = a[b]+1

allnum = (allnum * Fib(n - i + 2))%MOD

print(allnum)

Submission status: Runtime Error

Solution code:
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__":
    mm = 1000000007
    ans = main()
    print(ans)

Submission status: Runtime Error

Solution code:
import bisect
def f(x,a):
  global N,M
  if M==0:
    return False
  b = bisect.bisect_left(a,x)
  return True if x==a[min(b,N)] else False
MOD = 10**9+7
N,M = map(int,input().split())
a = [int(input()) for _ in range(M)]
a.sort()
x = 0
y = 1
for i in range(N):
  if f(i,a) and f(i+1,a):
    print(0)
    exit()
  elif f(i+1,a):
    z = 0
  else:
    z = x + y
  x = y
  y = z
print(z%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

n, m = MAP()

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

a.insert(0,0)
a.append(n)

def func(p):
    if p == 0 :
        return 0
    else:
        q = int(p / 2)
        #print('q:',q)
        ret = 0
        for i in range(q + 1):
            #print('i',i,[i,p-i*2])
            if i ==0:
                ret += 1
            else:
                ret += int(math.factorial(p - i * 2 + 1) / math.factorial(i) / math.factorial(p - i * 2))
            #print(ret)

        return ret

#print(func(0))
#print(a)
ans=1
for i in range(len(a)-1):
    #print(i)
    if i+1 == 1 or i+1 == n - 1:
        ans *= 1
    else:
        p = a[i + 1] - a[i]-1
        ans *= func(p)
        #print(ans)
print(ans%MOD)

Submission status: Runtime Error

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

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

wa = (10**9) + 7

def Fib(n):
    if n==0:
        return 0 #F0
    elif n==1:
        return 1 #F1
    elif n==2:
        return 1
    else:
        fibo_minus1 = 1 #Fn-1
        fibo_minus2 = 0 #Fn-2
        for i in range(2,n):
            fibo = fibo_minus1 + fibo_minus2 #Fn = Fn-1 + Fn-2
            fibo_minus2 = fibo_minus1 # Fn-2の値を更新
            fibo_minus1 = fibo # Fn-1の値を更新
        return fibo





ans = 1



if M!= 1:
    length = a[0]
    ans *= Fib(length+1)

    for i in range(0,M-1):
        length = a[i+1]-a[i]-1
        # print(length)
        if length == 0:
            ans *= 0
        else:
            ans *= Fib(length+1)
        # print(ans)


    
if M==1:
    length = a[0]
    ans *= Fib(length+1)




length = N-a[-1]


ans *= Fib(length+1)

print(ans%wa)

Submission status: Runtime Error

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


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


M=(1000000007)

def solve(x):
    if x in dp:
        return dp[x]

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

dp={}
dp[0]=1
dp[1]=1

print(solve(N)%M)

Submission status: Runtime Error

Solution code:
import bisect
def f(x,a):
  global N,M
  if M==0:
    return False
  b = bisect.bisect_left(a,x)
  return True if x==a[mi  n(b,N)] else False
MOD = 10**9+7
N,M = map(int,input().split())
a = [int(input()) for _ in range(M)]
a.sort()
x = 0
y = 1
for i in range(N):
  if f(i,a) and f(i+1,a):
    print(0)
    exit()
  elif f(i+1,a):
    z = 0
  else:
    z = x + y
  x = y
  y = z
print(z%MOD)

Submission status: Runtime Error

Solution code:
import functools
import operator

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

N,M = map(int,input().split())
A = [int(input()) for i in range(M)]
if A[0] == 1:
    A.pop(0)
    A.insert(0, 1)
    A.append(N+1)
    sabun = [A[i+1]-A[i]-1 for i in range(M)]
else:
    A.insert(0, -1)
    A.append(N+1)
    sabun = [A[i+1]-A[i]-1 for i in range(M+1)]
# print(sabun)
if min(sabun) == 0:
    print("0")
else:
    f = [i for i in fib(max(sabun))]
    f.insert(0, 1)
    # print(f)
    ans = [f[i-1] for i in sabun]
    # print(ans)
    result = functools.reduce(operator.mul, ans)
    print(int(result%1000000007))

Submission status: Runtime Error

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

pattern=[0]*(n+1)
pattern[0]=1
pattern[1]=1
pattern[2]=2

for i in range(3, n+1):
    pattern[i]=2*pattern[i-2]+pattern[i-3]

judge=False
for i in range(m-1):
    if a[i+1]-a[i]==1:
        judge=True
ans=1
med=1
num=1

if judge:
    print("0")
else:
    for i in range(n):
        if i+1 in a:
            num=0
            ans*=med
        else:
            med=pattern[num]
            num+=1

ans*=med

if not judge:
    print(ans%1000000007)

Submission status: Runtime Error

Solution code:
import math
N, M = (int(i) for i in input().split())

list_a = list()
for i in range(M):
  list_a.append(int(input()))


curr = 0

list_pat = list()
for i in range(M+1):
  if i==M:
   dist=N
  else:
   dist=list_a[i]-1
  if dist-curr<=1:
   if dist==N:
    break
   else:
    if list_a[i]==1:
     curr=2
    else:
     list_pat.append(0)
#     print('break!')
     break
  else:
   diff_dist = dist-curr
#   print('diff_dist' + str(diff_dist))
   if diff_dist == 0:
    list_pat.append(1)
#    print('a')
   else:
    max_num_2 = diff_dist//2
    if max_num_2 == 0:
     list_pat.append(1)
#     print('b')
    else:
     list_pat_this = list()
     for num_2 in range(max_num_2+1):
      num_1 = diff_dist-num_2*2
#      print('num_1:'+str(num_1))
#      print('num_2:'+str(num_2))
      list_pat_this.append(math.factorial(num_1+num_2)/math.factorial(num_1)/math.factorial(num_2))
#     print(list_pat_this)
     list_pat.append(int(sum(list_pat_this)))
     if dist!=N: 
      curr = list_a[i]+1

#print(list_pat)
pat=1
for pat_this in list_pat:
 pat=pat*pat_this

print(pat%1000000007)

Submission status: Runtime Error

Solution code:

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

l=[0]*(N+1)
l[0]=1

for i in range(N):
    c=l[i]%1000000007
    if i<=N-2:
        if i not in a:
            l[i+1]+=c
    elif i not in a:
        l[i+1]+=c
        l[i+2]+=c

print(l[N]%1000000007)

Submission status: Runtime Error

Solution code:
import copy
n,m = map(int,input().split())
a = [int(input()) for i in range(m)]
if n == 1:
    if m == 1:
        print(0)
    else:
        print(1)
else:
    if 1 == a[0]:
        if 2 in a:
            a1 = 0
            a2 = 0
        else:
            a1 = 0
            a2 = 1
    else:
        if 2 in a:
            a1 = 1
            a2 = 0
        else:
            a1 = 1
            a2 = 2
    if n == 2:
        print(a2)
    else:
        for i in range(3,n+1):
            if i in a:
                a1 = copy.copy(a2)
                a2 = 0
            else:
                an = a1 + a2
                a1 = copy.copy(a2)
                a2 = copy.copy(an)
        print(a2 % 1000000007)

Submission status: Runtime Error

Solution code:
# 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
for i in range(m):
    t = int(input())
    if t < 3:
        p = t
        pass
    elif t == 3:
        p = t
        o = 2
        pass
    elif t-p == 1:
        print(0)
        exit()
    elif t-p-1 == 1:
        p = t
        pass
    elif t-1-p == 2:
        p = t
        pass
    elif t-1-p > 2:
        o = o*endFib(t-2-p)
        p = t
if n-p > 3:
    o = o * endFib(n-p-2)
elif n-p ==3:
    o = o*2
print(o % 1000000007)

Submission status: Runtime Error

Solution code:
import bisect
def f(x,a):
  global N,M
  if M==0:
    return False
  b = bisect.bisect_left(a,x)
  return True if x==a[mi
  n(b,N)] else False
MOD = 10**9+7
N,M = map(int,input().split())
a = [int(input()) for _ in range(M)]
a.sort()
x = 0
y = 1
for i in range(N):
  if f(i,a) and f(i+1,a):
    print(0)
    exit()
  elif f(i+1,a):
    z = 0
  else:
    z = x + y
  x = y
  y = z
print(z%MOD)

Submission status: Runtime Error

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

MOD = 1000000007  # type: int

def is_ok(i,a):
    ii = bisect.bisect_left(a,i)
    if ii >= len(a):
        return True
    return i != a[ii]


def solve(N: int, M: int, a: "List[int]"):
    dp = [0]*N
    dp[0] = 1 if is_ok(1,a) else 0
    if is_ok(2,a):
        if is_ok(1,a):
            dp[1] = 2
        else:
            dp[1] = 1

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

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


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

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from math import factorial
def c(n):
    c = 0
    if n != 0:
        for i in range(n):
            if n - i < i:
                pass
            else:
                x = n - i
                r = i
                c += factorial(x) / factorial(r) / factorial(x - r)
    return c
N, M = map(int,input().split())
ans = 1
pre_a = 0
for j in range(M+1):
    if j != M:
        a = int(input())

    else:
        a = N
    n = a - pre_a - 1
    if a == 1:
        ans *= 1
    else:
        ans *= c(n)
    pre_a = a
print(ans%1000000007)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
n, m = map(int, input().split())
BIGNUM = 10 ** 9 + 7

last_ana = int(input())
blocks = [last_ana]

for _ in range(1, m):
    ana = int(input())
    blocks.append(ana - last_ana - 1)
    last_ana = ana

blocks.append(n - last_ana)

if 0 in blocks:
    ans = 0
else:
    b_max = max(blocks)

    c = [1, 1]
    for i in range(2, b_max):
        ctmp = c[i - 1] + c[i - 2]
        c.append(ctmp)

    ans = 1
    for num in blocks:
        ans = ans * c[num - 1]

print(ans % BIGNUM)

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
a=[0]*(N+1)
b=[0]*(M+2)
c=[0]*(M+2)
a[0]=0
a[1]=1
a[2]=1
for i in range(3,N+1):
    a[i]=a[i-1]+a[i-2]
b[0]=-1
b[M+1]=N+1
way=1
for i in range(1,M+1):
    b[i]=int(input())
    c[i]=b[i]-b[i-1]-1
    way=(way*a[c[i]])%1000000007
c[M+1]=b[M+1]-b[M]-1
way=(way*a[c[M+1]])%1000000007
print(way)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
n, m = map(int, input().split())
BIGNUM = 10 ** 9 + 7

last_ana = int(input())
blocks = [last_ana]

for _ in range(1, m):
    ana = int(input())
    blocks.append(ana - last_ana - 1)
    last_ana = ana

blocks.append(n - last_ana)

if 0 in blocks:
    ans = 0
else:
    b_max = max(blocks)

    c = [1, 1]
    for i in range(2, b_max):
        ctmp = c[i - 1] + c[i - 2]
        c.append(ctmp % BIGNUM)

    ans = 1
    for num in blocks:
        ans = ans * c[num - 1]

print(ans % BIGNUM)

Submission status: Runtime Error

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


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


M=(1000000007)

def solve(x):
    if x in dp:
        return dp[x]

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

dp={}
dp[0]=1
dp[1]=1
if a[1]:
    a[1]=1

print(solve(N)%M)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
MOD = 10**9 + 7

q = [1,2]
append = q.append
for i in range(10**5+10):
    if i >= 2:
        t = q[i-1]+q[i-2]
        t%= MOD
        append(t)
ans = 1
a_pre = 0
for i in range(m+1):
    if i == m:
        if a_now == n-1:
            print(0)
            exit()
        else:
            ans *= q[n-a_now-2]
            ans %=MOD
            break
    if i>0:
        a_pre = a_now
    a_now = int(input())
    if i == 0:
        if a_now != 1:
            ans*=q[a_now-2]
            ans%=MOD
    if i>0:
        if a_pre + 1 == a_now:
            print(0)
            exit()
        else:
            if a_now-a_pre-3!=-1:
                ans*=q[a_now-a_pre-3]
            ans %=MOD

print(ans)

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:
		print(0)
		flg2 = 1
	p = 1
	q = 1
	t = 0
	flg = 0
	while (A[t]<2):
		t = t+1
	if t > M:
		print(0)
		flg2 = 1
	for k in range(2,N):
		r = p + q
		p = q
		q = r
		while (A[t] == k):
			ans = ans*r
			t += 1
			if t == M+1:
				flg = 1
				break
		if flg == 1:
			break
	if flg2 == 0:
		print(ans%1000000007)
main()