Problem:


Score : 300 points

Problem Statement

There is a staircase with N steps. Takahashi is now standing at the foot of the stairs, that is, on the 0-th step.
He can climb up one or two steps at a time.

However, the treads of the a_1-th, a_2-th, a_3-th, \ldots, a_M-th steps are broken, so it is dangerous to set foot on those steps.

How many are there to climb up to the top step, that is, the N-th step, without setting foot on the broken steps?
Find the count modulo 1\ 000\ 000\ 007.

Constraints

1 \leq N \leq 10^5

0 \leq M \leq N-1

1 \leq a_1 < a_2 <  ...  < a_M \leq N-1

Input

Input is given from Standard Input in the following format:

N M
a_1
a_2
 .
 .
 .
a_M

Output

Print the number of ways to climb up the stairs under the condition, modulo 1\ 000\ 000\ 007.

Sample Input 1

6 1
3

Sample Output 1

4

There are four ways to climb up the stairs, as follows:

0 \to 1 \to 2 \to 4 \to 5 \to 6

0 \to 1 \to 2 \to 4 \to 6

0 \to 2 \to 4 \to 5 \to 6

0 \to 2 \to 4 \to 6

Sample Input 2

10 2
4
5

Sample Output 2

0

There may be no way to climb up the stairs without setting foot on the broken steps.

Sample Input 3

100 5
1
23
45
67
89

Sample Output 3

608200469

Be sure to print the count modulo 1\ 000\ 000\ 007.



Sample input:
6 1
3


Sample output:
4

Submission status: Runtime Error

Solution code:
import sys
import sympy as sym

def fib(n):
    x = sym.symbols('x',nonnegative=True,integer=True)
    Fib=1/sym.sqrt(5)*(((1+sym.sqrt(5))/2)**(n-1)-((1-sym.sqrt(5))/2)**(n-1)) #一般項の式
    result=Fib.subs(x,n)
    result=result.evalf()
    return int(result)


N, M = map(int, input().split())
a = [-1]
for i in range(M):
    a.append(int(input()))
    
for i in range(M-1):
    if a[i+1] == (a[i] + 1):
        print(0)
        exit()
    
combi = 1

for i in range(len(a)-1):
    dis = a[i+1] - a[i]
    combi *= fib(dis)
    
dis = N+1 - a[-1]
combi *= fib(dis)

print(combi % 1000000007)

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]"):
    if(len(a) >= 2):
        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
    # if(M == 0):
    #     for i in range(2,N+1)
    
    for i in range(2,N+1):
        if(len(a) and a[x] == i-1):
            dp[i] = dp[i-2] % MOD
            # x = min(x+1,M-1)
        elif(len(a) and 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:
def fib(n):
    n += 1
    if n == 0:
        return 1
    else:
        f = ((1 + 5**0.5) / 2)**n / 5**0.5 + 0.5
        return int(f)

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

if M == 0:
    print(fib(N))
    exit()

A = [int(input()) for _ in range(M)]
L = [0] * (M+1)

ans = 1

L[0] = fib(A[0]-1)
L[M] = fib(N-(A[M-1]+1))

for i in range(1,M):
    if A[i]-A[i-1] == 1:
        print(0)
        exit()
    L[i] = fib((A[i]-1)-(A[i-1]+1))

for j in range(M+1):
    ans = (ans * L[j]) % (10**9 + 7)

print(ans)

Submission status: Runtime Error

Solution code:
def step(n, memo={}):
    if n <= 1:
        return 1
    elif n == 2:
        return 2
    elif n in memo:
        return memo[n]
    else:
        memo[n] = (step(n-1,memo)+step(n-2,memo))%1000000007
        return memo[n]

N, M = map(int, input().split())
a = [-1]

for m in range(M):
    a.append(int(input()))
    if a[m+1] - a[m] == 1:
        print(0)
        break
else:
    a.append(N+1)
    ans = 1
    for m in range(M+1):
        ans = (ans*(step(a[m+1]-a[m]-2)))%1000000007
    print(ans)

Submission status: Runtime Error

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

mod=1000000007

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

a_i2=0
a_i1=0
a_i=0

for i in range(n-1):
  if i+2 == a[a_i2]:
      a_i2 += 1
      if a_i2 == m:
        a_i2 -= 1
  else:
    if i+1 == a[a_i1]:
      if i == a[a_i]:
        dp[i+2]=0
        a_i += 1
        if a_i == m:
          a_i -= 1
      else:
        dp[i+2]=dp[i]
      a_i1 += 1
      if a_i1 == m:
        a_i1 -= 1
    else:
      if i == a[a_i]:
        dp[i+2]=dp[i+1]
        a_i += 1
        if a_i == m:
          a_i -= 1
      else:
        dp[i+2]=dp[i+1]+dp[i]

  dp[i+2] = dp[i+2] % mod
  #print(dp)

print(dp[n])

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
import sys
N, M = map(int, input().split())
A = [int(input()) for i in range(M)]
m = 10**9+7
F = [0, 1]
for i in range(2, N+1):
    F.append(F[i-1]+F[i-2])

for i, a in enumerate(A[:-1]):
    if a+1 == A[i+1]:
        print(0)
        sys.exit()

ans = 1
s = 0
for i in range(N):
    if i in A:
        ans *= F[i-s]
        ans %= m
        s = i+1
ans *= F[N-s+1]
ans %= m 
print(ans)

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+100)
fiblist[0] = 1
fiblist[1] = 1

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

#print(d)

if (-1 in d) or (-2 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 math
N,M = [int(x) for x in input().split()]
a = [int(input()) for i in range(M)]

def combinations_count(n, r):
        return math.factorial(n) / (math.factorial(n - r) * math.factorial(r))

def keisan(n,r):
    count = 0
    while n >= r:

        count += combinations_count(n,r)
        n -= 1
        r += 1

    return count
result = 1

for i in range(M):
    if a[i] - a[i-1] == 1:
        result = 0
        break
    elif i == 0:
        result *= keisan(a[i]-1,0)
    else:
        result *= keisan(a[i]-a[i-1]-2,0)

else:
    result *= keisan(N - a[M-1]-1,0)

print(int(result%1000000007))

Submission status: Runtime Error

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

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

if M==0:
  print(step(N))
else:
  b = [0]*(M+1)
  b[0] = step(a[0]-1)
  if M>=2:
    for i in range(M-1):
      if a[i+1]-a[i] == 1:
        b[i+1] = 0
      elif a[i+1]-a[i] == 0:
        b[i+1] = 1
      else:
        b[i+1] = step(a[i+1]-a[i]-2)
  b[M] = step(N-a[M-1]-1)

answer = 1
for i in range(M+1):
  answer = answer*b[i]%1000000007
print(answer)

Submission status: Runtime Error

Solution code:
def calc(_n):
    if _n == 1:
        return 1
    elif _n == 2:
        return 2
    else:
        return calc(_n - 1) + calc(_n -2)


N, M = map(int, raw_input().split())
prev_a = long(-1)
ans = long(1)
for i in range(0, M):
    a = long(input())
    if a == 1:
        prev_a = 1
    elif prev_a + 1 == a:
        ans = 0
        break
    else:
        ans = ans * calc(a - prev_a - 2)
        prev_a = a

if ans == 0:
    print(ans)
else:
    if prev_a + 1 == N:
        ans = 0
    elif prev_a != N:
        ans = ans * calc(N - prev_a - 1)
    print(ans % 1000000007)

Submission status: Runtime Error

Solution code:

import sys
sys.setrecursionlimit(10000)

memo=[0]*10**5
memo[0]=1
memo[1]=1

def fib(n):
  ret=0
  if n==0 or n==1:
    return 1
  if memo[n-1]!=0:
    ret+=memo[n-1]
  else:
    ret+=fib(n-1)
  if memo[n-2]!=0:
    ret+=memo[n-2]
  else:
    ret+=fib(n-2)
  memo[n]=ret
  return ret


n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
a.append(n+1)
prv=0
ans=1
for ai in a:
  if(ai==prv):
    ans=0
    break
  ans*=fib(ai-1-prv)
  while(ans>10**9+7):
    ans%=10**9+7

  prv=ai+1

print(ans)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = []
import sys
flg = 0
for i in range(M):
    a = int(input())
    if a == 1 or a == 2:
        flg = a
    if i != 0:
        if a == A[-1] + 1:
            flg = 3
    A.append(a)
if flg == 3:
    print(0)
    sys.exit()
ary = list(range(3, N + 1))
for a in A:
    try:
        ary.remove(a)
    except:
        pass
def step(n):
    steps = [0 for i in range(n + 1)]
    if flg == 0:
        steps[1] = 1
        steps[2] = 2
    elif flg == 1:
        steps[2] = 1
    else:
        steps[1] = 1
    for i in ary:
        steps[i] = steps[i - 1] + steps[i - 2]
    return steps[n] % 1000000007
print(step(N))

Submission status: Runtime Error

Solution code:
def dfs(x):
  if x == N:
    return 1
  if x > N or x in a:
    return 0
  if memo.get(x):
    return memo[x]
  memo[x] = dfs(x+1) + dfs(x+2)
  return memo[x]

N, M = map(lambda x: int(x), input().split())
a = [int(input()) for i in range(M)]
#print(N)
#print(M)
#print(a)
memo = {}
count = dfs(0)
print(count%1000000007)

Submission status: Runtime Error

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

mod = 10 ** 9 + 7


def Fib(n, memo={}):
    if n == 1:
        return 0
    elif n == 2:
        return 1
    elif n in memo:
        return memo[n] % mod
    else:
        memo[n] = Fib(n - 1, memo) + Fib(n - 2, memo)
        return memo[n] % mod


A = list(int(input()) for i in range(m))


if m > 0:
    ans = Fib(A[0] + 1) % mod
    for i in range(m - 1):
        ans *= Fib(A[i + 1] - A[i])
        ans %= mod
        if A[i] + 1 == A[i + 1]:
            print(0)
            exit()
    ans *= Fib(n - A[-1] + 1)
    ans %= mod
else:
    ans = Fib(n + 1) % mod
print(ans)

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+1)

def fib(step):
    if step < 0:
        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:
N, M = map(int, input().split())
broken = [False for _ in range(10 **5)]
for _ in range(M):
    a = int(input())
    broken[a] = True

INF = 1000000007

memo = [None for _ in range(N + 1)]
if not broken[1]:
    memo[1] = 1
else:
    memo[1] = 0
if not broken[2]:
    memo[2] = 2
else:
    memo[2] = 0
for i in range(3, N + 1):
    if broken[i]:
        memo[i] = 0
        continue
    memo[i] = (memo[i - 2] + memo[i - 1]) % INF

print(memo[N])

Submission status: Runtime Error

Solution code:
def move(now, goal, m):
    global rlt
    if m==goal:
        rlt += 1
        return

    if m>goal: return

    move(m, goal, m+1)
    move(m, goal, m+2)


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

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

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

ans = 0

m = []
now = 0
rlt = 0
for a in A:
    move(now, a-1, now+1)
    move(now, a-1, now+2)
    m.append(rlt)
    rlt = 0

now = A[len(A)-1]+1
move(now, N, now+1)
move(now, N, now+2)
m.append(rlt)

ans = 1

for i in m:
    ans *= i

print(ans%1000000007)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
if N == 1:
    print(1)
    quit()
if M > N//2:
    print(0)
    quit()

A = list(int(input()) for _ in range(M))
idx = 0
P = 10**9 + 7

dp = [0] * (N+1)
dp[0] = 1
dp[1] = 1
a = -1
if len(A):
    if 1 == A[idx]:
        dp[1] = 0
        idx += 1

for i in range(2, N+1):
    if i != A[idx]:
        dp[i] = (dp[i-1] + dp[i-2]) % P
    else:
        dp[i] = 0
        if idx < M-1:
            idx += 1
print(dp[N])

Submission status: Runtime Error

Solution code:
n,m = map(int, input().split())
def f(a):
  return round(((((1+5**0.5)/2)**a)-(((1-5**0.5)/2)**a))/5**0.5)
s = 1
a1 = -1
for i in range(m):
  a2 = int(input())
  a = a2-a1-1
  if a <= 1 and a1 > 0:
    s = 0
    break
  s = s * f(a)
  if s >= 1000000007:
    s = s % 1000000007
  a1 = a2
if s > 0:
  a = n - a2
  s = s * f(a)
  if s >= 1000000007:
    s = s % 1000000007
print(s)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

def fb(num):
    fblist = []
    x, y = 1, 0
    for _ in range(num):
        fblist.append(x)
        x, y = x + y, x
    return fblist



n, m = map(int, input().split())

l = fb(n)

now = 0
p_cnt = []
for i in range(m):
    a = int(input())
    if now == a:
        print(0)
        exit()
    p_cnt.append(l[a - 1 - now])
    now = a + 1

p_cnt.append(l[n - now])

# print(p_cnt);
ans = 1
for j in range(len(p_cnt)):
    # print(ans)
    ans *= p_cnt[j]
    # print(ans)
    
print(ans %  1000000007)

Submission status: Runtime Error

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

li = []
lia = [-1]
ans = 1
mod = 1000000007

for i in range(n):
    if i == 0 or i == 1:
        li.append(1)
    else:
        li.append((li[i-1] + li[i-2]) % mod)

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

lia.append(n+1)

for i in range(len(lia)-1):
    if lia[i+1]-lia[i] != 1:
        ans *= li[lia[i+1]-lia[i]-2]
    else:
        ans = 0
    ans %= mod

print(ans%mod)

Submission status: Runtime Error

Solution code:
N,M = (int(i) for i in input().split())
a = [int(input()) for i in range(M)]
hoge = [0] * N
if 1 not in a:
    hoge[0] = 1
if 2 not in a:
    hoge[1] = 2

for i in range(2,N):
    if i + 1 in a:
        hoge[i] = 0
    elif i in a and (i-1) in a:
        hoge[i] = 0
    elif i in a:
        hoge[i] = hoge[i - 2]
    elif (i-1) in a:
        hoge[i] = hoge[i - 1]
    else:
        hoge[i] = hoge[i-1] + hoge[i-2]
        hoge[i] = hoge[i] % (10**9 + 7)
print(hoge[N-1] % (10**9 + 7))

Submission status: Runtime Error

Solution code:
import sys

def dfs(n:int, heights: int, a_index:int):
    if n < heights:
        return
    
    if m != 0 and a_index <= len(a) -1 and a[a_index] == heights:
        memo[heights] = 0
        a_index += 1
        #print("10",heights)
    else:
        memo[heights] = memo[heights-1] + memo[heights -2]
        #print("13",heights)
    dfs(n,heights+1,a_index)
    return
    

n,m = list(map(int, input().split()))
memo = [1]*(n+1)
a = []
a_index = 0
if m != 0:
    for i in range(m):
        tmp = int(input())
        if i >= 1 and tmp -1 == a[len(a)-1]:
            print(0)
            sys.exit()
        else:
            a.append(tmp)
            #print(i,a)

    if a[0] == 1:
        memo[1] = 0
    a_index += 1

dfs(n,2,a_index)
#print(memo)
print(memo[n] % (10**9+7))

Submission status: Runtime Error

Solution code:
mod=1000000007
def Fib(n):
  a, b = 1, 2
  if n == 1 or n==0:
    return a
  elif n == 2:
    return b
  else:
    for i in range(n-2):
      a, b = b%mod, (a+b)%mod
    return b
n,m=map(int,input().split())
al=[]
zeroflag=0
fa=-1
cnt=0
for iii in range(m):
  a=int(input())
  cnt+=1
  al.append(a)
  if abs(fa-a)==1:
    zeroflag=1
  fa=a

if zeroflag==1:
  print(0)
else:
  ans=1
  for iii in range(m):
    if iii==0:
      ans=Fib(al[iii]-1)
    if iii==m-1:
      break
    if len(al)>1:  
      num=Fib(al[iii+1]-al[iii]-2)
      ans*=num%mod
  ans*=Fib(n-al[-1]-1)%mod
  print(ans%mod)

Submission status: Runtime Error

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

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

    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:
        if dd > 1:
            tmp = 0
            for j in range(round(dd/2) + 1):
                tmp += cmb(dd - j, j)
            ans *= (tmp % 1000000007)

    print(ans % 1000000007)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def Fib(n):    
    if n == 1:
        return 1
    if n == 0:
        return 0
    else:
        return Fib(n-1)+Fib(n-2)

n,m = map(int,input().split())
s =[]
ans = 1
for i in range(m):
    s.append(int(input()))
    if i == 0:
        ans*=Fib(s[0])
    else:
        if s[i]-s[i-1] == 1:
            print(0)
            exit()
        ans *= Fib(s[i]-s[i-1]-1)
if s[-1] != n:
    ans *= Fib(n-s[-1])
    
        
print(ans%1000000007)

Submission status: Runtime Error

Solution code:
F = [1,1]

def fibo(n):
    if n <= len(F):
        return F[n-1]
    while len(F) < n:
        F.append(F[-1] + F[-2])
    return F[n-1]

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

B = [A[0]]
for i in range(M-1):
    B.append(A[i+1] - A[i] - 1)
B.append(N - A[M-1])
ans = 1
if 0 in B:
    ans = 0
else:
    for n in B:
        ans = ans * fibo(n) % MOD
print(ans)

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+5)
fiblist[0] = 1
fiblist[1] = 1

for p in range(2,mm+5):
    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:
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]

sumList = [0] * (N+1)
sumList[0] = 0
sumList[1] = 1
sumList[2] = 2
for i in range(3, N+1) :
    sumList[i] = sumList[i-1] + sumList[i-2]

ans = 0
tmp = 0
if a[0] == 1 :
    ans = 1
else :
    ans = sumList[a[0] - 1]
for i in range(1, M) :
    if a[i] - a[i-1] == 1 :
        ans = 0
    else :
        ans *= sumList[a[i] - 2 - a[i-1]]
ans *= sumList[N - 1 - a[M-1]]
print(ans % 1000000007)

Submission status: Runtime Error

Solution code:
N,M = list(map(int,input().split()))
a = [int(input()) for i in range(M)]
dekai = 1000000007
 
def Fib(n):
	a,b = 0,1
	if n == 1:
		return a
	elif n == 2:
		return b
	else:
		for i in range(n-2):
			a,b = b,a+b
		return b


ans = 1
for i in range(M+1):
	if i == 0:
		ans = (ans*(Fib(a[0]-(-1))%dekai))%dekai
	elif i == M:
		ans = (ans*(Fib(N+1-a[M-1])%dekai))%dekai
	else:
		ans = (ans*(Fib(a[i]-a[i-1])%dekai))%dekai
print(ans)

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]"):
    if(len(a)):
        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
    # if(M == 0):
    #     for i in range(2,N+1)
    
    for i in range(2,N+1):
        if(len(a) and a[x] == i-1):
            dp[i] = dp[i-2] % MOD
            # x = min(x+1,M-1)
        elif(len(a) and 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=[]
for i in range(m):
    a.append(int(input()))

inf=1000000007

def fib(k):
    a, b = 1, 1
    for i in range(k):
        yield a
        a, b = b, a + b
 
l=[i for i in fib(n)]
p=[]
for i in range(n):
    if i+1 in a:
        p.append(1)
    else:
        p.append(0)

ans=1

for i in range(n-1):
   if p[i]==1 and p[i+1]==1:
       print(0)
       exit()
k=[a[0]-1]
for i in range(m-1):
    k.append(a[i+1]-a[i]-2)
k.append(n-a[m-1]-1)
print(k)
#if k[0]==0:
#   k[0]=1
for j in range(len(k)):
    if j==0:
        ans*=l[k[j]]%inf
    elif j==len(k)-1:
        ans*=l[k[j]]%inf
    else:
        ans*=l[k[j]]%inf
print(ans%inf)

Submission status: Runtime Error

Solution code:
n,m = map(int, input().split())
a = [int(input())for i in range(0,m)]
div = 1000000007
pat = [1,1]
for i in range(2,n+1):
    pat.append(pat[i-2]+pat[i-1])
ans = pat[a[0]-1]
for i in range(1,m):
    ans *= pat[a[i] - a[i-1] -2]
ans *= pat[n- a[-1]-1]
print(ans%div)

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
L=[int(input()) for _ in range(M)]
ans=0
dp=[]
def dfs(i):
	global ans
	if i==N:
		ans+=1
		# print(i)
		return True
	if i>N:return False
	if i in L:return True
	if dfs(i+1)==False:return True
	if dfs(i+2)==False:return True

dfs(0)
print(ans%1000000007)

Submission status: Runtime Error

Solution code:
import math

#n = int(input())
n, m = [int(i) for i in input().split()]
#table = [[int(i) for i in input().split()] for n in range(n)]
#list = [int(i) for i in input().split()]
#s = input()
#list = list(s)

s = [int(input()) for i in range(m)] #m行1列入力

MOD = 1000000007

def fib(n):
    f = (((((1 + 5**0.5) / 2)**n) % MOD ) / 5**0.5 + 0.5) % MOD
    return int(f)

kotae = 1

if (m == 0) :
    kotae = (kotae * fib(n)) % MOD
else :
    for i in range(m + 1) :
        if (i == 0) :
            kotae = kotae * fib(s[i]) % MOD
        elif (i == m) :
            kotae = kotae * fib(n - s[i-1]) % MOD
        else :
            kotae = kotae * fib(s[i] - s[i-1] - 1) % MOD


print(kotae)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
li = [int(input()) for i in range(m)]
p = 1000000007
ans = 0

steps = [0]*(n+1)
steps[1] = 1
steps[2] = 2
for i in range(3,n+1):
  steps[i] = (steps[i-1] + steps[i-2])%p

if li[0] == 1:
  ans += 1
else:
  ans += steps[li[0]-1]%p

for i in range(m-1):
  ans *= steps[li[i+1]-li[i]-2]
  ans %= p

if li[m-1] == n-1: 
  print(ans)
else:
  print((ans*steps[n-li[m-1]-1])%p)

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

def combinations_count(n, r):
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def keisan(n,r):
    count = 0
    while n >= r:

        count += combinations_count(n,r)
        n -= 1
        r += 1

    return count
result = 1

for i in range(M):
    if a[i] - a[i-1] == 1:
        result = 0
        break
    elif i == 0:
        result *= keisan(a[i]-1,0)
    else:
        result *= keisan(a[i]-a[i-1]-2,0)

else:
    result *= keisan(N - a[M-1]-1,0)

print(result%1000000007)

Submission status: Runtime Error

Solution code:
def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    n+=2
    return fibonacci_sub2(n-2, 1, 0)

def fibonacci_sub2(n, fibo_minus1, fibo_minus2):
    return fibo_minus1 if n==0 else fibonacci_sub2(n-1, fibo_minus1+fibo_minus2, fibo_minus1)


N,M = map(int, input().split()) #1 2
a = [int(input()) for i in range(M)]
ans = []
nstep = range(N)
preidx = 0

for idx,i in enumerate(a):
    if i - preidx == 1 and idx != 0:
        print(0)
        exit()
    if idx == 0 and i-preidx-1 != 0:
        ans.append([idx,i-preidx-1])
    elif idx > 0:
        ans.append([idx,i-preidx-2])
    preidx = i
else:
    ans.append([idx,N-preidx-1])

fibsum = 1
for idx,val in enumerate(ans):
    fibsum *= fibonacci(val[1])
    fibsum %= 1000000007 
print(fibsum)

Submission status: Runtime Error

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

def combinations_count(n, r):
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def keisan(n,r):
    count = 0
    while n >= r:

        count += combinations_count(n,r)
        n -= 1
        r += 1

    return count
result = 1

for i in range(M):
    if a[i] - a[i-1] == 1:
        result = 0
        break
    elif i == 0:
        result *= keisan(a[i]-1,0)
    else:
        result *= keisan(a[i]-a[i-1]-2,0)

else:
    result *= keisan(N - a[M-1]-1,0)

print(result%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
mod = 1000000007
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)
        if ans0 > mod:
            ans0 -= mod
        i += 1
    ans *= ans0
    ans %= mod
print(ans%mod)

Submission status: Runtime Error

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

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

memo = [0] * (n+1)

in_memo = [False] * (n+1)

memo[0] = 1
in_memo[0] = True

if 1 in a:
    memo[1] = 0
else:
    memo[1] = 1
in_memo[1] = True

def dp(num):
    if not in_memo[num]:
        if num in a:
            memo[num] = 0
        else:
            memo[num] = dp(num-1) + dp(num-2)
        in_memo[num] = True
    return memo[num]

print(dp(100)%1000000007)

Submission status: Runtime Error

Solution code:
def _comb(N,M):
    count=1
    for i in range(0,M):
        count*=N-i
    for i in range(1,M+1):
        count/=i
    return(int(count))

N,M=list(map(int,input().split()))
A=[int(input()) for i in range(M)]
A.append(N)
if not 1 in A:
    A.append(0)
    A.sort()
count=1
for m in range(len(A)-1):

    count*=sum([_comb((A[m+1]-1)-A[m]-i,i) for i in range((A[m+1]-1)-A[m])])
    #print(sum([comb((A[m+1]-1)-A[m]-i,i,exact=True) for i in range((A[m+1]-1)-A[m])]),sum([_comb((A[m+1]-1)-A[m]-i,i) for i in range((A[m+1]-1)-A[m])]),count)
print(count%1000000007)

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
    # if(M == 0):
    #     for i in range(2,N+1)
    
    for i in range(2,N+1):
        if(len(a) and a[x] == i-1):
            dp[i] = dp[i-2] % MOD
            # x = min(x+1,M-1)
        elif(len(a) and 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 = [-1]
for i in range(m):
    ai = int(input())
    a.append(ai)
a.append(n+1)]

def factorial(x):
  if x == 0:
    return 1
  else:
    return x * factorial(x-1)

def C(x,y):
    return factorial(x)//(factorial(x-y)*factorial(y))

def f(x):
    if x == 0:
        return 1
    else:
        ret = 0
        for i in range(x//2+1):
            ret += C(x-i,i)
        return ret

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

ans = 1
if -1 in b:
    print(0)
else:
    for j in b:
        ans *= (f(j)%1000000007)
    print(ans%1000000007)

Submission status: Runtime Error

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

MOD = 10 ** 9 + 7
a = []
flag = True
for i in range(M):
  tmp = int(input())
  if i != 0 and tmp == a[-1] + 1 or tmp == 0 or tmp == N:
    print(0)
    flag = False
    break
  a.append(tmp)

if flag:
  max_dis = 0
  dis = []
  for i in range(len(a)):
    if i == 0:
      dis.append(a[i])
    else:
      dis.append(a[i] - a[i - 1])
    max_dis = max(max_dis, dis[-1])
  max_dis = max(max_dis, N - a[-1])
  
  fib = [1, 1]
  for _ in range(max_dis):
    fib.append(fib[-1] + fib[-2])
  ans = 1
  for d in dis:
    ans = (ans * fib[d - 1]) % MOD
  ans *= fib[N - a[-1] - 1]
  
  print(ans % MOD)

Submission status: Runtime Error

Solution code:

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

counter_arr = [0]*(N+1)

counter_arr[0] = 1
next_broken = broken_lst.pop(0)
last_broken = -1

for i in range(0, N-1):
    flug = 0
    if i+1 == next_broken:
        flug = 1
#        print("p0", i, counter_arr)
    elif i+1 == last_broken:
        pass
#        print("p1",i, counter_arr)
    else:
        counter_arr[i+1] += counter_arr[i]
        counter_arr[i+1] %= 10**9 + 7
#        print("p2",i,  counter_arr)

    if i + 2 == next_broken:
        flug = 1
#        print("p3",i, counter_arr)
    else:
        counter_arr[i+2] += counter_arr[i]
        counter_arr[i+2] %= 10**9 + 7
#        print("p4",i, counter_arr)
    
    if flug == 1:
        last_broken = next_broken
        if len(broken_lst) != 0:
            next_broken = broken_lst.pop(0)

    
counter_arr[-1] += counter_arr[-2]
counter_arr[-1] %= 10**9 + 7

print(counter_arr[-1])

Submission status: Runtime Error

Solution code:
import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

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

sl = []
cnt = -1
for i in range(M):
    a = int(input())
    b = (a - 1) - (cnt + 1)
    if b == -1:
        print(0)
        break
    sl.append(max(b, 1))
    cnt = a
else:
    sl.append(max(N - (a + 1), 1))
    ans = 1
    for s in sl:
        p = 0
        for i in range(s):
            j = s - i
            if (i > j):
                break
            p += combinations_count(j, i)
        ans *= p
    print(ans % 1000000007)