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:
def fib(number):
    if(number<=2):
        return 1
    elif(number==3):
        return 2
    else:
        return fib(number-1) + fib(number-2)

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

frag = True
before = -100
for _ in range(m):
    tmp = int(input())
    if(tmp - before == 1):
        frag = False
    before = tmp
    a.append(tmp)


warukazu = 1000000007
if(frag):
    before = 0
    ans = 0
    for i in range(m):
        if(i==0):
            ans = fib(a[i]-before)
        else:
            ans = ans * fib(a[i]-before-1)
        before = a[i]
    ans = ans * fib(n - before)
    ans = ans % warukazu
    print(ans)
else:
    print(0)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
way = [1 for _ in range(n+1)]
b1 = 1
b2 = 1
count = 1
ai = int(input())
if ai == 1:
  b2 = 0
  ai = int(input())
  count += 1
for i in range(2,n+1):
  if i == ai:
    b1 = b2
    b2 = 0
    if count < m:
      ai = int(input())
      count+=1
  else:
    tmp = b2
    b2 = (b1 + tmp)%1000000007
    b1 = tmp
print(b2)

Submission status: Runtime Error

Solution code:
import sys
n, m = map(int, input().split())
kaidan = [1] * (n+1)
for _ in range(m):
    a = int(input())
    kaidan[a] = -1

def fib(n):    
    if n == 1:
        return 0
    elif n == 2:
        return 1
    else:
        return fib(n-1)+fib(n-2)

ans = 1
renzoku = 0
koshou = 0
for i in range(n+2):
    if i == n+1:
        temp = fib(renzoku+1)
        ans = ans * temp
    elif kaidan[i] == 1:
        renzoku += 1
        koshou = 0
    else:
        koshou += 1
        if koshou == 2:
            print(0)
            sys.exit()
        else:
            temp = fib(renzoku+1)
            ans = ans * temp
        renzoku = 0

print(ans%1000000007)

Submission status: Runtime Error

Solution code:
from collections import deque
N, M = map(int, input().split())
A = list(int(input()) for _ in range(M))
A = deque(A)
P = 10**9 + 7

dp = [0] * (N+1)
dp[0] = 1
dp[1] = 1
a = A.popleft()
if 1 == a:
    dp[1] = 0
    a = A.popleft()

for i in range(2, N+1):
    if i != a:
        dp[i] = (dp[i-1] + dp[i-2]) % P
    else:
        dp[i] = 0
        if len(A):
            a = A.popleft()
print(dp[N])

Submission status: Runtime Error

Solution code:
import math

mod = 1000000007

def feb(n):
    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:
        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()))
a = []
for _ in range(M):
    a.append(int(input()))
dif = [a[0]-1]
dif.extend([(a[i]-1)-(a[i-1]+1) for i in range(1,len(a))])
dif.extend([N-a[-1]-1])
max_dif = max(dif)
Fiblist = {-1:0,0:1,1:1,2:2}
for n in range(3,max_dif+1):
    Fiblist[n]=Fiblist[n-1]+Fiblist[n-2]
ans = 1
for part in dif:
    ans= ans*Fiblist[part]%1000000007
print(ans)

Submission status: Runtime Error

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

broken_step = []
for _ in range(M):
    broken_step.append(int(input()))
    
mod = 1000000007

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

def step_memo(N):
    if N == 0:
        return 1
    if N == 1:
        return 1

    a = 1
    b = 1
    
    if N-1 in broken_step:
        a = 0
    if N-2 in broken_step:
        b = 0
    if N in broken_step:
        a = 0
        b = 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 = [int(input()) for _ in range(M)]
DIV = 10**9+7

def main():
    B = [0]*(M+1)
    for i in range(M+1):
        if i==0:
            B[i] = A[i]-1
        elif i==M:
            B[i] = N-A[i-1]-1
        else:
            B[i] = A[i] - A[i-1] - 2
    min_B = min(B)
    if min_B<0:
        return 0
    
    max_B = max(B)
    F = [1]*(max_B+1)
    for i,f in enumerate(F):
        if i<2:
            pass
        else:
            F[i] = F[i-2] + F[i-1]
    ans = 1
    for b in B:
        ans *= F[b]
        ans %=DIV
    return ans

print(main())

Submission status: Runtime Error

Solution code:
law = 10 ** 9 + 7

fibo_memo = {}
def fibo(N):
    if (N <= 3):
        return N

    if (N in fibo_memo):
        return fibo_memo[N]

    val = fibo(N - 1) + fibo(N - 2)
    fibo_memo[N] = val
    return val

def main():
    N, M = map(int, input().split())

    ans = 1
    b = 0
    for _ in range(M):
        a = int(input())

        if (a > 1):
            ans = ans * fibo(a - b - 1) % law
        b = a

    ans = ans * fibo(N - b - 1) % law

    return ans


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

Submission status: Runtime Error

Solution code:
import sys
from math import factorial

def combination(n,r):
    nCr = int(factorial(n) / factorial(r) / factorial(n - r))
    return(nCr)

n, m = [int(i) for i in input().split()]
a = [-1]
for i in range(m):
    a.append(int(input()))
    if a[-1] - a[-2] == 1:
        print(0)
        sys.exit()
a.append(n+1)
# print(a)

ans = 1
for i in range(len(a)-1):
    # print('i',i,ans)
    a_begin = a[i]
    a_end = a[i+1]
    # print(a_begin,a_end)
    num_stair = a_end - a_begin - 2
    max_num_two_up = num_stair // 2
    # print(num_stair,max_num_two_up)
    ans_tmp = 0
    for j in range(max_num_two_up+1):
        ans_tmp += combination(num_stair-j,j)
    ans *= ans_tmp

ans = ans % 1000000007
print(ans)

Submission status: Runtime Error

Solution code:
N_M = list(map(int, input().split()))
N = N_M[0]
M = N_M[1]
for i in range(M):
    dis[i] = list(int(input()))

dp = [0 for i in range(N+2)]
dp[0] = 1
if 1 in dis:
    dp[1] = 0
else :
    dp[1] = 1

for i in range(N):
    if i+2 in dis:
        dp[i+2]=0
    else:
        if i in dis :
            dp[i+2]=dp[i+1]
        if i+1 in dis :
            dp[i+2]=dp[i]
        else :
            dp[i+2]=dp[i]+dp[i+1]

print(dp[N])

Submission status: Runtime Error

Solution code:
from functools import lru_cache

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

MOD = pow(10, 9) + 7

isOk = True
for i in range(M-1):
    if a[i] + 1 == a[i+1]:
        isOk = False
    
@lru_cache(maxsize = None)
def func(n):
    if n <= 0:
        return 1
    cnt = 0
    if n >= 2:
        cnt += func(n-2) % MOD
    if n >= 1:
        cnt += func(n-1) % MOD
    return cnt

if not isOk:
    print(0)
else:
    ans = 1
    s = 0
    for i in range(M+1):
        if i >= M:
            e = N
        else:
            e = a[i] - 1

        ans = ans * func(e-s) % MOD

        if i >= M:
            break

        s = a[i] + 1

    print(ans)

Submission status: Runtime Error

Solution code:

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

s = [0] * (N+1)

for i in range(M):
    ai = int(input())
    s[ai] = -1

print(s)

s[0] = 1

if N == 1:
    print(1)
else:
    if s[1] == 0:
        s[1] = 1

    for i in range(2,N+1):
        if s[i] >= 0:
            s[i] += (max(0,s[i-1]) + max(0,s[i-2]))
        print(s)

    print(s[N] % 1000000007)

Submission status: Runtime Error

Solution code:
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

n,m = map(int,input().split(' '))
a0 = -1
b = []
for q in range(m):
    a1 = int(input())
    if a1 == a0:
        continue
    else:
        b.append(a1-a0-2)
        a0 = a1
b.append(n-a1-1)
ans = 1
for b0 in b:
    if b0 == -1:
        ans = 0
        break
    i = 0
    ans0 = 0
    while i <= b0//2:
        ans0 += cmb(b0-i,i)
        i += 1
    ans *= ans0
mod = 1000000007
print(ans%mod)

Submission status: Runtime Error

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

a=[1,1]
for i in range(2,10000):
    a.append((a[i-1]+a[i-2])%1000000007)

bad=[]
for i in range(m):
    bad.append(int(input()))
num=[]
before=0
bad_flag=0

if m!=0:
    for i in range(len(bad)):
        nxt=bad[i]-before-1
        if nxt==-1:
            bad_flag=1
            break
        num.append(nxt)
        before=bad[i]+1
    num.append(n-bad[len(bad)-1]-1)
else:
    num.append(n)
if bad_flag:
    print(0)
else:
    ans=0
    last=1
    for i in num:
        ans=a[i]*last
        last=ans%1000000007
    print(last)

Submission status: Runtime Error

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

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

x = [0] * (N+1)
x[0] = 1
ai = 0
if ai >= M or 1 != a[ai]:
    x[1] = x[0]
else:
    ai += 1
for i in range(2, (N+1)):
    if ai >= M or i != a[ai]:
        x[i] = (x[i-1] + x[i-2]) % base
    else:
        ai += 1
print(x[N])

Submission status: Runtime Error

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

fib = [0]*n
fib[0] = 1
fib[1] = 1
for x in range(2, n):
    fib[x] = fib[x-1] + fib[x-2]

mod = 10**9+7
ans = 1
prev_a = -1
for i in range(m):
    a = int(input())
    if a - 1 == prev_a:
        ans = 0
        break
    else:
        ans = (ans * fib[a - prev_a - 2]) % mod
    prev_a = a

ans = (ans * fib[n - a - 1]) % mod
print(ans)

Submission status: Runtime Error

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



ans = 1
o = 0
for i in range(m):
    a = int(input())
    if a == o:
        ans = 0
        break
    if a > o + 1:
        ans = (ans * list[a - o - 2]) % 1000000007
    o = a + 1

if a + 1 < n:
    ans = (ans * list[n - a - 2]) % 1000000007
print(ans)

Submission status: Runtime Error

Solution code:
LARGE = 1000000007


def step(a, i):
    if i == len(a):
        return 1
    elif i > len(a):
        return 0

    elif a[i] == 0:
        return 0

    return step(a, i + 1) + step(a, i + 2)


def solve():
    n, m = [int(x) for x in input().split()]
    a = [1] * n
    for _ in range(m):
        a[int(input())] = 0

    # print(n, m)
    # print(a)

    ans = step(a, 0)
    print(ans % LARGE)


if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
from sys import stdin

N, M = [int(x) for x in stdin.readline().rstrip().split()]
a = [int(stdin.readline().rstrip()) for _ in range(M)]
fib = [1, 1]
for k in range(N):
    fib.append((fib[-1] + fib[-2]) % 1000000007)
ans = fib[a[0] - 1]
for l in range(M - 1):
    if a[l + 1] - a[l] == 1:
        print(0)
        exit()
    ans = ans * fib[a[l + 1] - a[l] - 2]
ans = ans * fib[N - a[-1] - 1]
print(ans % 1000000007)

Submission status: Runtime Error

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

a = []
for i in range(m):
    a.append(int(input()))

d = [a[0]-1]
for j in range(1,m):
    d.append(a[j]-a[j-1]-2)

d.append(n-a[m-1]-1)

mm = max(d)

fiblist = [0] * (mm+1)
fiblist[0] = 1
fiblist[1] = 1

for p in range(2,mm+1):
    fiblist[p] = (fiblist[p-1]+fiblist[p-2]) % 1000000007

#print(d)

if -1 in d:
    print(0)
else:
    ans = 1
    for k in range(m+1):
        ans = (ans * fiblist[d[k]]) % 1000000007

    print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
import math
import sys
sys.setrecursionlimit(10000000)

def main():
    N, M = map(int, input().split())
    A = [0] * (N + 1)
    for i in range(M):
        bre = int(input())
        A[bre] = -1
    a_2 = 1
    a_1 = 1 if A[1] != -1 else -1
    # print(A)
    for i in range(N):
        if (A[i] == -1) & (A[i + 1] == -1):
            print(0)
            sys.exit()
    # print(a_1, a_2)
    A[0] = 1
    A[1] = 1 if A[1] != -1 else -1
    for i in range(2, N + 1):
        if A[i] == -1:
            a_2 = a_1
            a_1 = -1
            continue
        elif a_1 == -1:
            a = a_2
        elif a_2 == -1:
            a = a_1
        else:
            a = a_1 +a_2
        a_2 = a_1
        a_1 = a
        # print(a_2, a_1)
    print(a % 1000000007)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n, m = map(int,input().split())
dangerList = [int(input()) for i in range(m)]
answerList = [0] * (n+2)
answerList[0] = 1
nextDanger = dangerList.pop(0)
for i in range(n):
  if i == nextDanger:
    if len(dangerList) > 0:
    	nextDanger = dangerList.pop(0)
  else:
    answerList[i+1] = (answerList[i+1] + answerList[i]) % 1000000007
    answerList[i+2] = (answerList[i+2] + answerList[i]) % 1000000007
print(answerList[n])

Submission status: Runtime Error

Solution code:
def up_stairs(N, a, now):
  
  if now == N:
    return 1
  if now > N:
    return 0
  if (now in a):
    return 0
  
  return up_stairs(N, a, now + 1) + up_stairs(N, a, now + 2)


N,M = (int(x) for x in input().split())

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

print(int(up_stairs(N, a, 0) % 1000000007))

Submission status: Runtime Error

Solution code:
lis = [1,1,2]
def num(n):
    if len(lis) >= n+1:
        return lis[n]
    else:
        res = num(n-2) + num(n-1)
        lis.append(res)
        return res

N,M = map(int,input().split())
count = 1
pre = 0
for i in range(M+1):
    if i == M:
        cur = N+1
    else:
        cur = int(input())
    number = cur-1-pre
    if number >= 0:
        count = count * num(number) % 1000000007
    else:
        count = 0
        break
    pre = cur + 1
print(count%1000000007)

Submission status: Runtime Error

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

stepsum=[1]   #k段目までの組み合わせ
if a[0]==1:   #1段目がNGなら
    stepsum.append(0)
else:
    stepsum.append(1)
    
for i in range(2,N+1):
    stepsum.append(((stepsum[i-1]+stepsum[i-2])*(not(i in a)))%1000000007)

ans=stepsum[N]%1000000007
print(ans)

Submission status: Runtime Error

Solution code:
N, M = list(map(int, input().split()))
a = []
for _ in range(M):
    a.append(int(input()))
dif = [a[0]-1]
dif.extend([(a[i]-1)-(a[i-1]+1) for i in range(1,len(a))])
dif.extend([N-a[-1]-1])
max_dif = max(dif)
Fiblist = {-1:0,0:1,1:1,2:2}
for n in range(3,max_dif+1):
    Fiblist[n]=Fiblist[n-1]+Fiblist[n-2]
ans = 1
for part in dif:
    ans*=Fiblist[part]
print(ans%1000000007)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

X = (1+np.sqrt(5))/2
Y = (1-np.sqrt(5))/2
Z = np.sqrt(5)

def InputToInt():
    A = input().split()
    for i in range(len(A)):
        A[i] = int(A[i])
    return A

def cases(N):
    if N == 0:
        print('0')
        sys.exit()
    return int((np.power(X, N)-np.power(Y, N))/Z+0.1)
    
    
if __name__ == '__main__':
    N, M = InputToInt()
    result = 1
    oldA = -1
    for i in range(M):
        A = int(input())
        result *= cases(A - oldA - 1)
        oldA = A
    result *= cases(N - A)
    print(result % 1000000007)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
def solve(N, M, A):
    MOD = 10**9 + 7
    A = set(A)
    if N == 1:
        return 1

    dp = [0] * (N+1)
    dp[0] = 1
    dp[1] = 1 if 1 not in A else 0
    for i in range(2, N+1):
        if i in A:
            dp[i] = 0
        else:
            dp[i] = (dp[i-2] + dp[i-1]) % MOD
    return dp[-1]


N, M = map(int, input).split())
A = [int(input()) for _ in range(M)]
ans = solve(N, M, A)
print(ans)

Submission status: Runtime Error

Solution code:
N, M = map(int,input().split())
a = []
dev = 100000007

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

ans = 0

def dfs(step):
    global ans
    if step == N:
        ans = (ans+1)%dev
        return
    elif step > N:
        return
    
    for ds in (1,2):
        ns = step + ds
        if ns in a:
            continue
        else:
            dfs(ns)

dfs(0)
print(ans)

Submission status: Runtime Error

Solution code:
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

def main():
    N, M = map(int, input().split())
    A = [-1] + [int(input()) for i in range(M)] + [N + 1]

    count = 0
    d = [0] * (len(A) - 1)
    for i in range(len(A) - 1):
        if A[i+1] - A[i] == 1:
            print(0)
            exit(0)
        d[i] = A[i+1] - 1 - (A[i] + 1)

    ans = 1
    for dd in d:
        tmp = 0
        for j in range(round(dd/2) + 1):
            tmp += cmb(dd - j, j)
        ans *= tmp

    print(ans%1000000007)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
DIV = 10**9+7

B = [0]*(M+1)
for i in range(M+1):
    if i==0:
        B[i] = A[i]-1
    elif i==M:
        B[i] = N-A[i-1]-1
    else:
        B[i] = A[i] - A[i-1] - 2
max_B = max(B)
F = [1]*(max_B+1)
for i,f in enumerate(F):
    if i<2:
        pass
    else:
        F[i] = F[i-2] + F[i-1]
ans = 1
for b in B:
    ans *= F[b]
    ans %=DIV

print(ans)

Submission status: Runtime Error

Solution code:
#ABC129-C
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return list(input())
n,m=IL()
D=[True]*n
for i in range(m):
    D[I()-1]=False
A=[0]*n
if D[0]:
    A[0]=1
    if D[1]:
        A[1]=2
    else:
        A[1]=0
else:
    A[0]=0
    if D[1]:
        A[1]=1
    else:
        A[1]=0
for i in range(2,n):
    if D[i]:
        A[i]=A[i-1]+A[i-2]
    else:
        A[i]=0
print(A[n-1]%1000000007)

Submission status: Runtime Error

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

dif = [a[0]-1]
dif.extend([(a[i]-1)-(a[i-1]+1) for i in range(1,len(a))])
dif.extend([N-a[-1]-1])
max_dif = max(dif)
print(dif, max_dif)

Fiblist = {-1:0,0:1,1:1,2:2}
for n in range(3,max_dif+1):
    Fiblist[n]=Fiblist[n-1]+Fiblist[n-2]
print(Fiblist)
ans = 1
for part in dif:
    ans*=Fiblist[part]
print(ans%1000000007)

Submission status: Runtime Error

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

broken_step = []
for _ in range(M):
    broken_step.append(int(input()))
    
mod = 1000000007

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

def step_memo(N):
    if N == 0:
        return 1
    if N == 1:
        return 1

    a = 1
    b = 1
    
    if N-1 in broken_step:
        a = 0
    elif N-2 in broken_step:
        b = 0
    elif N in broken_step:
        a = 0
        b = 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 = list(int(input()) for _ in range(M))

MOD = pow(10, 9) + 7

isOk = True
for i in range(M-1):
    if a[i] + 1 == a[i+1]:
        isOk = False
    

def func(n):
    if n <= 0:
        return 1
    cnt = 0
    if n >= 2:
        cnt += func(n-2) % MOD
    if n >= 1:
        cnt += func(n-1) % MOD
    return cnt

if not isOk:
    print(0)
else:
    ans = 1
    s = 0
    for i in range(M+1):
        if i >= M:
            e = N
        else:
            e = a[i] - 1

        ans = ans * func(e-s) % MOD

        if i >= M:
            break

        s = a[i] + 1

    print(ans)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
a=[]
for i in range(m):
    a.append(int(input()))
count=[0]*(n+2)
count[1]=2
count[0]=1
i=0
s=a.pop(0)
if s==1:
    count[1]=1
    count[0]=0
    if a:
        s=a.pop(0)
if s==2:
    count[1]=0
    if a:
        s=a.pop(0)

while i<n:        
    if (i+2==s-1):
        i=i+1
        if a:
            s=a.pop(0)
    else:
        count[i+2]=(count[i]+count[i+1])%1000000007
        i=i+1
#print(count)
print(count[n-1])

Submission status: Runtime Error

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

for i in range(n):
  if i == a[-1] - 1:
    if len(a) < m:
      a.append(int(input()))
    r.append(0)
  elif i == 0:
    r.append(1)
  else:
    r.append((r[i] + r[i-1]) % mod)
print(r[-1])

Submission status: Runtime Error

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

a=[1,1]
for i in range(2,10000):
    a.append((a[i-1]+a[i-2])%1000000007)
bad=[]
for i in range(m):
    bad.append(int(input()))
num=[]
before=0
bad_flag=0
# print(bad)
for i in range(len(bad)):
    nxt=bad[i]-before-1
    if nxt==-1:
        bad_flag=1
        break
    num.append(nxt)
    before=bad[i]+1
num.append(n-bad[len(bad)-1]-1)
if bad_flag:
    print(0)
else:
    ans=0
    last=1
    for i in num:
        # print(num,a[i])
        ans=a[i]*last
        last=ans%1000000007
    print(last)

Submission status: Runtime Error

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

stepsum=[1]   #k段目までの組み合わせ
if a[0]==1:   #1段目がNGなら
    stepsum.append(0)
else:
    stepsum.append(1)
    
for i in range(2,N+1):
    stepsum.append((stepsum[i-1]+stepsum[i-2])*(not(i in a)))

ans=stepsum[N]%1000000007
print(ans)

Submission status: Runtime Error

Solution code:
modulo=10**9+7
n, m=map(int, input().split())
a_list=[]
for i in range(m):
    a=int(input())
    a_list.append(a)
dp=[0 for i in range(n+1)]#0~n
dp[0]=1
if a_list[0]==1:
    dp[1]=0
else:
    dp[1]=1

for i in range(2, n+1):
    if not i in a_list:
        dp[i]=(dp[i-2]+dp[i-1])%modulo
print(dp[n]%modulo)

Submission status: Runtime Error

Solution code:
MOD=10**9+7
N,M=map(int,input().split())
a=[]

for i in range(M):
  a.append(int(input()))
s=[1]
b=0 if 1 in a else 1
s.append(b)
p,q=-1,-1
j=-1
for i in range(2,N+1):
  while j<M-1:
    if a[j+1]<=i:
      j+=1
    else:
      break
  v=s[i-2]+s[i-1]
  if a[j]==i:
    v=0
  s.append(v%MOD)
print(s[N])

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
from functools import lru_cache

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

PRIME = 10 ** 9 + 7
N, M = list(map(int, input().split()))
broken_stairs = []
for _ in range(M):
    broken_stairs.append(int(input()))

prev_broken = -1
cannot = False
ans = 1
for a in broken_stairs:
    if a - prev_broken == 1:
        cannot = True
        break
    ans *= fib(a - prev_broken - 2)
    ans %= PRIME
    prev_broken = a

ans *= fib(N - prev_broken - 1)
ans %= PRIME

if cannot:
    print(0)
else:
    print(ans)

Submission status: Runtime Error

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

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

memo = {}


def step(now):
    if now in a:
        return 0
    # print(now)
    if now == n:
        return 1
    if now > n:
        return 0
    if now in memo.keys():
        return memo[now]
    memo[now] = step(now+1)+step(now+2)
    return memo[now]


print(step(0) % 1000000007)
# print(memo)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
lis = [int(input()) for i in range(m)]
dp = [0 for i in range(n+2)]
dp[0] = 1
cou = 0
co = 0
for i in range(n):
  if i+1 != lis[cou]:
    dp[i+1] += dp[i]
    dp[i+1] %= 10 ** 9+7
  else:
    cou +=1
  if i+2 !=  lis[co]:
    dp[i+2] += dp[i]
    dp[i+2] %= 10 ** 9 + 7
  else:
    co += 1
print(dp[n])

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)
    
print(count(n)%1000000007)

Submission status: Runtime Error

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

fib_l = [-1] * n

def fib(step):
    if step < -1:
        return 0
    if fib_l[step] != -1:
        return fib_l[step]
    if 0 <= step <= 1:
        return 1
    else:
        t = fib(step-1) + fib(step-2)
        fib_l[step] = t
        return t

ret = 1
for i in range(m+1):
    ret *= fib(a[i+1] - a[i] - 2)
print(ret % 1000000007)

Submission status: Runtime Error

Solution code:
mod = 1000000007

n, m = list(map(int, input().split()))
nums = [int(input()) for _ in range(m)]
 
dp = [1] + [0 for _ in range(n)]

if nums[0] == 1:
	del nums[0]
else:
	dp[1] = 1
	

for i in range(2, n + 1):
	#print(i, dp, nums)
	if len(nums) ==  0:
		dp[i] = (dp[i - 1] + dp[i - 2]) % mod
	else:
		for j in range(len(nums)):
			if nums[j] > i:
				dp[i] = (dp[i - 1] + dp[i - 2]) % mod
				break
			elif nums[j] == i:
				del nums[:(j + 1)]
				break
#print(nums)
#print(dp)
print(dp[-1])

Submission status: Runtime Error

Solution code:
mod = 1000000007

N, M = [int(i) for i in input().split()]
A = [int(input()) for _ in range(M)] + [N + 1]

for i in range(len(A) - 1):
    if A[i] + 1 == A[i + 1]:
        print(0)
        quit()

memo = {0: 1, 1: 1, 2: 2, 3: 3}

def fib(n):
    if n not in memo:
        memo[n] = fib(n - 1) + fib(n - 2)
    return memo[n]

ans = 1
pre = -1
lo = 0
for a in A:
    f = fib(a - 1 - lo)
    ans = (ans * f) % mod

    lo = a + 1
    pre = a

print(ans)

Submission status: Runtime Error

Solution code:
import sys
N, M = map(int, input().split())
MOD = 10 ** 9 + 7
NMAX = 10 ** 5
sys.setrecursionlimit(NMAX+1)

memo = [None for _ in range(NMAX+1)]
def fibo(n):
    if memo[n]:
        return memo[n]
    if n == 0:
        return 0
    elif n < 3:
        return 1
    else:
        return fibo(n-1) + fibo(n-2)

nc = 1
b = 0
for i in range(M):
    a = int(input())
    nc = (nc * fibo(a - b)) % MOD
    b = a + 1

nc = (nc * fibo(N + 1 - b)) % MOD

print(nc)

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]"):
    i = 2
    arr = [1, 1]
    seek = 0
    while a[seek]==1:
        arr[1] = 0
        seek+=1
    while i<=N:
        if seek < len(a) and i == a[seek]:
            arr[0], arr[1] = arr[1], 0
            seek+=1
        else:
            arr[0], arr[1] = arr[1], (arr[0]+arr[1])%MOD
        i+=1
    print(arr[1])

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 heapq import heappush, heappop, heapify, heapreplace
from collections import defaultdict


class Solution:
    def main(self):
        N, M =map(int, input().split())
        self.memo = {}
        for _ in range(M):
            a = int(input())
            self.memo[a] = 0
        res = self.rec(N)
        print(res)

    def rec(self, n):
        if n < 0:
            return 0
        elif n == 0:
            return 1
        elif n in self.memo:
            return self.memo[n]
        else:
            val = (self.rec(n-1) + self.rec(n-2)) %1000000007
            self.memo[n] = val
            return val


if __name__ == '__main__':
    Solution().main()

Submission status: Runtime Error

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

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]

    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:
N, M = map(int,input().split())
A = [int(input()) for k in range(M)]
dp = [0 for k in range(N+1)]
MOD = 10**9+7

dp[0] = 1
dp[1] = 1
dp[2] = 1

t = 0
if A[0] == 1:
    t += 1
    dp[1] = 0

for k in range(2,N+1):
    if t < len(A):
        if A[t] == k:
            dp[k] = 0
            t += 1
        else:
            dp[k] = dp[k-1] + dp[k-2]
            dp[k] %= MOD
    else:
        dp[k] = dp[k-1] + dp[k-2]
        dp[k] %= MOD
print(dp[N])

Submission status: Runtime Error

Solution code:
from math import factorial
n,m,*a=map(int,open(0).read().split())
s=0
c=[0]*(1+len(a))
p=1
for j,e in enumerate(a+[n+1]):
  d=e-1-s
  m=d//2
  for i in range(m+1):
    l=d-i*2
    c[j]+=factorial(l+i)/factorial(l)/factorial(i)
  s=e+1
  p*=c[j]
print(int(p%1000000007))