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 _ in range(m)]
if 1 in a and 2 in a:
    print(0)
    exit()
ans = 1
k = 0
if a[-1]!=n:
    a.append(n)

mod = 10**9+7
max = 10**5+1
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル
for i in range( 2, max + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

for i in a:
    if i+1 in a:
        print(0)
        exit()
    else:
        if i-k<=2:
            m = 1
        elif i-k==3:
            m = 2
        else:
            m = 0
            f = i-k-1
            for j in range(f//2,-1,-1):
                m += cmb(f-j,j,mod)
        ans *= m
        ans %= mod
        k = i
print(ans%mod)

Submission status: Runtime Error

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

out=0
for i in range(0,N,1):
  if i in A:
    continue
  if i==N-1:
    out+=1
  for j in range(i,N,2):
    if j in A:
      continue
    if j==N-1:
      out+=1
  
print(out%1000000007)

Submission status: Runtime Error

Solution code:
import sys

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

n,m = list(map(int, input().split()))
memo = [1]*(3)
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
#a = list(set(a))
#a.sort()
dfs(2,a_index,memo[1],memo[0])
#print(memo)
print(memo[2] % (10**9+7))

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)


fiblist = [0] * 100001
fiblist[0] = 1
fiblist[1] = 1

for p in range(2,100001):
    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:
# 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-1)
elif n-p ==3:
    o = o*2
print(o % 1000000007)

Submission status: Runtime Error

Solution code:
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:
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 == a[-1]:
    print(0)
    
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 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 or p==1:
        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)
    p = a[i + 1] - a[i]-1
    ans *= func(p)
    #print(ans)
print(ans%MOD)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100001)

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

fibmemo={1:1,2:1}
for i in range(3,100000):
    fibmemo[i]=fibmemo[i-1]+fibmemo[i-2]
def fib(n):
    return fibmemo[n]

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

Submission status: Runtime Error

Solution code:
import math


memo = [-1 for _ in range(1000000)]
def fact(n):
    if n == 0: return 1
    if memo[n] != -1: return memo[n]
    ret = n * fact(n-1)
    memo[n] = ret
    return ret

fact_mamo = [-1 for _ in range(1000000)]
def c(n, r):
    u = fact_mamo[n]
    if u == -1:
        u = fact(n)
        fact_mamo[n] = u

    d1 = fact_mamo[n-r]
    if d1 == -1:
        d1 = fact(n-r)
        fact_mamo[n-r] = d1

    d2 = fact_mamo[r]
    if d2 == -1:
        d2 = fact(r)
        fact_mamo[r] = d2

    d = d1*d2
    return u//d

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



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

mod = 1000000007
if m == 0:
    print(f(n))
    exit()

ptn = f(a[0]-1)
for i in range(len(a)-1):
    if a[i+1] - a[i] == 1:
        ptn = 0
        break
    ptn = (ptn * f(a[i+1]-1 - a[i]-1)) % mod
ptn = (ptn * f(n - a[len(a)-1]-1)) % mod

print(ptn)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
flag=False
a=[int(input()) for i in range(m)]
for i in range(m-1):#answer 0
    if a[i+1]-a[i]==1:
        flag=True

def fb(num):
    """num番目のフィボナッチ数を返す
    """
    a, b = 1, 0
    for _ in range(num+1):
        a, b = a + b, a
    return b


key=fb(a[0]-1)

if key==0: key=1

for i in range(m-1):
    key*=fb(a[i+1]-a[i]-2)
key*=fb(n-a[len(a)-1]-1)

if m!=0 and flag!=True:
    print(key%1000000007)
elif flag==True:
    print(0)
else: print(fb(n))

Submission status: Runtime Error

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

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

print(fib(N)%1000000007)

Submission status: Runtime Error

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

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:
import sys
sys.setrecursionlimit(500000)
N, M = map(int, input().split())
a = [int(input())for _ in range(M)]
dp = [-1 for _ in range(N + 1)]
dp[0] = 0
dp[1] = 1
def loop(n):
    if n <= 0:
        return 1
    if dp[n] >= 0:
        return dp[n]
    ans = 0
    for i in range(1, 3):
        if n - i in a:
            continue
        ans += loop(n - i)
        ans %= 1000000007

    dp[n] = ans
    return dp[n]

x = a[0]
for i in a:
    if i == x + 1:
        print(0)
        exit()

    x = i
loop(N)
print(dp[N])

Submission status: Runtime Error

Solution code:
def fib_memo(n):
  memo = [0]*(n+1)
  def _fib(n):
    if n <= 1:
      return n
    if memo[n] != 0:
      return memo[n]
    memo[n] = _fib(n-1) + _fib(n-2)
    return memo[n]
  return _fib(n)
  
N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
# A = range(M)
B = range(M)

Ans = reduce(lambda a, b: a*b, B)
# Ans = 10
print(Ans % 1000000007)

Submission status: Runtime Error

Solution code:
import sys

def fibo(n):
    a, b = 0, 1
    if n == 1:
        return 1
    else:
        for i in range(n):
            a0 = a
            a = b
            b = a0 + b
        return b
        
N, M = map(int, input().split())
a = []

for i in range(M):
    a.append(int(input()))
    
for j in range(len(a)-1):
    if a[j+1] - a[j] == 1:
        print(0)
        sys.exit()
    
hole = 0
pattern = 1

for i, k in enumerate(a):
    if i == 0:
        pattern *= fibo(k-1)
    else:
        pattern *= fibo(a[i]-a[i-1]-2)
        
pattern *= fibo(N-a[-1]-1)
print(pattern % 1000000007)

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
def k(n):
    if n==0 or n==1:
        return 1
    else:
        return n*k(n-1)

def c(M,x):
    return k(M-x)/(k(x)*k(M-2*x))

def f(N):
    i=N//2
    count=0
    while i>=0:
        count+=c(N,i)
        i-=1
    return count
p=0
C=[]
for i in range(M):
    a=int(input())
    C.append(f(a-p-1))
    p=a+1
C.append(f(N-p))
if 0 in C:
    print(0)
else:
    m=1
    for j in range(len(C)):
        m=m*C[j]
    print(int(m%1000000007))

Submission status: Runtime Error

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

from operator import mul
from functools import reduce
import itertools

a.append(n)
a.insert(0, 0)
def count_ways(steps, jumps):
    jav_steps = steps - 2
    ls = list(itertools.combinations(range(jav_steps), jumps))
    return len(ls)
    
def count_block(b1, b2):
    steps = b2 - b1
    jump_types = steps//2 + 1
    block_ans = sum([count_ways(steps, jumps) for jumps in range(1, jump_types-1)])    
    return block_ans

ans  = [count_block(a[i], a[i+1]) for i in range(len(a)-1) if a[i+1]!=1]

print(reduce(mul, ans))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
def stairs_count(now, goal, memo):
    if now == goal:
        return 1
    if now > goal:
        return 0

    if memo[now] is not None:
        return memo[now]

    step1 = 0
    step2 = 0

    # step1
    if now + 1 == goal:
        step1 = 1
    else:
        step1 = stairs_count(now+1, goal, memo)

    # step2
    if now + 2 > goal:
        step2 = 0
    elif now + 2 == goal:
        step2 = 1
    else:
        step2 = stairs_count(now+2, goal, memo)

    memo[now] = (step1 + step2) % 1000000007
    return memo[now]


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

root = stairs_count(0, n, memo)
print(root)

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 or p==1:
        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)
    p = a[i + 1] - a[i]-1
    ans *= func(p)
    #print(ans)
print(ans)

Submission status: Runtime Error

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

pre = 0
last = -1
ans_l = []
flag = False
l.append(N+1)

nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]

for i in l:
    if i==1:
        last = 1
        continue
    if i-last==1:
        flag =True
        break
    n = i - last - 3
    r = 0
    tmp = 1
    dif = 1
    while dif>0:
        r += 1
        if n<=0 or n<r:
            break
        tmp += cmb(n, r)
        dif = n-r
        n -= 1
    ans_l.append(tmp)
    # print(i,ans_l)
    last = i
if flag:
    print(0)
else:
    ans = 1
    for i in ans_l:
        ans*=i
    print(ans%1000000007)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
a = list(range(m+2))
a[0] = -1
a[m+1] = n+1
ans = 1
for i in range(m):
  a[i+1] = int(input())
for i in range(m+1):
  if a[i]+1 == a[i+1]:
    ans = 0
  else:
    x = a[i+1]-a[i]-1
    ans = ans*int(1/(5**0.5) * (((1+(5**0.5))/2)**x - ((1-(5**0.5))/2)**x))%1000000007

if m == 0:
    x = a[m+1]-a[i]-1
    ans = int(1/(5**0.5) * (((1+(5**0.5))/2)**x - ((1-(5**0.5))/2)**x))%1000000007

print(ans)

Submission status: Runtime Error

Solution code:
from functools import lru_cache
N, M = map(int, input().split(' '))

@lru_cache(maxsize=None)
def fib(n):
    a, b = 0, 1
    for i in range(0, n):
        a, b = b, a + b
    return a

a_p = int(input())
sum = fib(a_p)
sum %= 1000000007
for i in range(M-1):
    a = int(input())
    diff = a - a_p
    if diff == 1:
        print('0')
        exit()
    sum *= fib((diff-1)%1000000007)
    sum %= 1000000007
    a_p = a

if (N - a_p == 1):
    print('0')
    exit()

sum *= fib(N - a_p)
sum %= 1000000007
print(sum)

Submission status: Runtime Error

Solution code:
import numpy as np
n, m = [int(i) for i in input().split()]
a =[]
d = 1000000007

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

a.append(n+1)
a = np.array(a)
#print(a)

if 1 in a[1:]-a[:-1]:
    print(0)

else:
    dp = [0]*(n+1)
    dp[1]=1
    dp[2]=1
    for i in range(3,len(dp)):
        dp[i]=dp[i-1]+dp[i-2]
        dp[i]=dp[i]%d

    ans = []
    pre = 0
    for i in range(len(a)):
        if i == 0:
            ans.append(a[i]-pre)
        else:
            ans.append(a[i]-pre-1)
        pre = a[i]

    #print(ans)

    if m == 0:
        print(dp[n])
    else:
        x = 1
        for i in ans:
            x = x*dp[i]%d
        print(x)

Submission status: Runtime Error

Solution code:
#coding:utf-8
from math import *
def fib(n):
    return round(( ((1 + sqrt(5))/2)**n - ((1 - sqrt(5))/2)**n ) / sqrt(5))
F = 1001
MD = 1000000007
ls = [0,1]
for f in range(F-2):
    s = sum(ls[-2:])
    ls.append(s)
def fib2(n):
    return ls[n]
old_a = 0
diff = []
N,M = map(int, input().split())
for m in range(M):
    a = int(input())
    if a-old_a==1 and old_a != 0:
        print (0)
        exit()
    diff.append(a-old_a)
    old_a = a
diff.append(N - old_a)
    
#print (diff)
ans = 1
for i,d in enumerate(diff):
    if i!=0 and i!=len(diff)-1:
        d-=1
    ans *= fib(d)
    #ans %= 1000000007
print (ans % MD)
#print (ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)
nCr = {}
def cmb(n, r):
  if r == 0 or r == n: return 1
  if r == 1: return n
  if (n,r) in nCr: return nCr[(n,r)]
  nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
  return nCr[(n,r)]

def calc(x):
  total = 1
  m = x // 2
  for i in range(1, 1+m):
    t = cmb((x-i), i)
    total += t
  # print((x, total))
  return total

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

total = 1
b = int(input())
total *= calc(b-1)

for _ in range(m-1):
  a = int(input())
  t = a - b - 1
  b = a
  if t == 0:
    total = 0
    break
  total *= calc(t)

total *= calc(n-b-1)

print(total % 10000000007)

Submission status: Runtime Error

Solution code:
d = {}

def step(N,M):
	if N == 0:
		return 1
	if N < 0:
		return 0

	if N-1 in d.keys():
		step_1 = d[N-1]
	else:
		step_1 = step(N-1,M)
		d[N-1] = step_1 % 1000000007
	if N-2 in d.keys():
		step_2 = d[N-2]
	else:
		step_2 = step(N-2,M)
		d[N-2] = step_2 % 1000000007
		
	if N - 1 in M and N - 2 in M:
		return 0
	if N - 1 in M:
		return step_2
	if N - 2 in M:
		return step_1
	return (step_1 + step_2) % 1000000007


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

print(step(N, a))

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
 
A = []
for i in range(m):
    A.append(int(input()))
    
dp = [0 for i in range(n + 1)]
dp[0] = 1
 
count = 0
for i in range(n+1):
    count = min(m-1, count)
    if  i !=  A[count]:
        if i >= 2:
            dp[i] += (dp[i-2] + dp[i-1]) % (10 ** 9 + 7)
        elif i == 1:
            dp[i] += dp[i-1] % (10 ** 9 + 7)
    else:
            count += 1
            
print(dp[-1] % (10 ** 9 + 7))

Submission status: Runtime Error

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

Submission status: Runtime Error

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

out=0
for i in range(0,N,1):
  if i in A:
    continue
  if i==N:
    out+=1
  for j in range(i,N,2):
    if j in A:
      continue
    if j==N:
      out+=1
  
print(out%1000000007)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
a=[]
for i in range(m):
    a.append(int(input()))
a.append(n+1)
q=1000000007
def fi(n):
    if n==0:
        return 1
    elif n==1:
        return 1
    elif n==2:
        return 2
    else:
        return fi(n-1)+fi(n-2)
A=[a[0]-1]
temp=0
ans=1
for i in range(1,m+1):
    A.append(a[i]-a[i-1]-2)
    if a[i]-a[i-1]-1==0:
        ans=0
    if temp<a[i]-a[i-1]-2:
        temp=a[i]-a[i-1]-2
Fi=[]
for i in range(temp+1):
    Fi.append(fi(i))
    
if ans!=0:
    for i in range(m+1):
        ans*=Fi[A[i]]
        
Ans=ans%q
print(Ans)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
As = []
for i in range(M):
    As.append(int(input()))
As.sort()
Ds = []
if M==0:
    Ds.append[0]
else:
    for i in range(M):
        if i==0:
            Ds.append(As[0]-1)
        else:
            Ds.append(As[i]-1-As[i-1])
Ds.append(N-As[-1])

def fibo(n):
    if n==1:
        return 1
    elif n==2:
        return 2
    S = [1, 1]
    for i in range(2, n):
        S.append(S[-2]+S[-1])
    return S[-1]

if min(Ds)==0:
    print(0)
else:
    Fs = [fibo(n) for n in Ds]
    pattern = 1
    for f in Fs:
        pattern *= f
    print(pattern % 1000000007)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
bre = []
flag = 0
A = []
for i in range(M):
    bre.append(int(input()))
#print(bre)
A.append(bre[0] - 1)
count = 0
if len(bre) >= 2:
    for i in range(len(bre) - 1):
        a = bre[i + 1] - bre[i]
        A.append(a - 2)
        if a == 1:
            #print(0)
            flag = 1
A.append(N - bre[len(bre) - 1] - 1)

if flag == 0:
    suu = [0, 1, 2]
    for i in range(2, max(A)):
        suu.append(suu[i] + suu[i-1] )
    #print(suu)
    for i in A:
        if count == 0:
            count = suu[i]
        else :
            count *= suu[i]
            count = count % 1000000007
    print(count)

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) % 1000000007
    
    
if __name__ == '__main__':
    N, M = InputToInt()
    result = 1
    oldA = -1
    for i in range(M):
        A = int(input())
        result *= cases(A - oldA - 1)
        result %= 1000000007
        oldA = A
    result *= cases(N - A)
    print(result % 1000000007)

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
a2 = -1
for i in range(m):
  a2 = int(input())
  if a2 == a1:
    continue
  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 -*-

# N : 階段の段数, M : 壊れている段の数
N, M = map(int, input().split())
a = []
for n in range(M):
    a.append(int(input()))


def culcContinueSitu(n):
    # n段連続で使える階段がある場合の登り方を数える
    if n == 1:
        return 1
    elif n == 2:
        return 2
    elif n >= 3:
        # 最初の1段目で飛ばすとき：culcContinueSitu(n-2)を数えれば良い
        # 最初の1段目で飛ばさないとき：culcContinueSitu(n-1)を数えれば良い
        return culcContinueSitu(n-2) + culcContinueSitu(n-1)


if M > 0:
    num_case = 1
    start = 0
    end = N
    for i in range(M):
        if i >= 1 and a[i]-a[i-1] <= 1:
            num_case = 0
            break
        if i >= 1:
            start = a[i-1] + 1
        end = a[i] - 1
        if end == 0:
            continue
        num_case *= culcContinueSitu(end - start)
    if N - a[M-1] > 1 and num_case != 0:
        start = a[M-1] + 1
        end = N
        num_case *= culcContinueSitu(end - start)
else:
    num_case = culcContinueSitu(N)

print(num_case % 1000000007)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
a = list(range(m+2))
a[0] = -1
a[m+1] = n+1
ans = 1
for i in range(m):
  a[i+1] = int(input())
for i in range(m+1):
  if a[i]+1 == a[i+1]:
    ans = 0
  else:
    x = a[i+1]-a[i]-1
    ans = ans * 1/(5**0.5) * (((1+(5**0.5))/2)**x - ((1-(5**0.5))/2)**x)%1000000007

if m == 0:
    x = a[m+1]-a[i]-1
    ans = 1/(5**0.5) * (((1+(5**0.5))/2)**x - ((1-(5**0.5))/2)**x)%1000000007

print(ans)

Submission status: Runtime Error

Solution code:
hoge = input().split()
N = int(hoge[0])
M = int(hoge[1])
broken = []
for i in range(M):
  broken.append(int(input()))

anss = []
safes = []
fibo = [1,2]
safes.append(broken[0]-1)
for i in range(M-1):
  safes.append(broken[i+1] - broken[i] - 1)

safes.append(N-broken[M-1] - 1)

for i in range(len(safes)):
  if safes[i] == 0:
    anss.append(1) # 間が0
  elif safes[i] == 1:
    anss.append(1) # 間が1つ
  elif safes[i] == 2:
    anss.append(2) # 間が2つ
  else:
    for i in range(safes[i] - 2): # 間が3つ以上
      fibo.append(fibo[i] + fibo[i+1])
    anss.append(fibo.pop())
    fibo = [1, 2]

answer = 1
#print(safes)
#print(anss)
for i in range(len(anss)):
  answer = answer * anss[i]
# print(safes)
  
flag = 0
for i in range(M-1):
  if broken[i+1] - broken[i] == 1:
    flag = 1

if flag == 0:
  print(answer%1000000007)
else:
  print(0)

Submission status: Runtime Error

Solution code:
from itertools import permutations

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

patterns = []
for i in range(N, -1, -2):
    pattern = [1] * i
    while sum(pattern) < N:
        pattern.append(2)
    else:
        patterns.extend(set(permutations(pattern)))
import ipdb; ipdb.set_trace()
ans = 0
for pattern in patterns:
    now = 0
    for p in pattern:
        if now + p not in AL:
            now += p
        else:
            break
    else:
        ans += 1
print(ans)

Submission status: Runtime Error

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

pre = 0
last = -1
ans_l = []
flag = False
l.append(N+1)

nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]

for i in l:
    if i==1:
        last = 1
        continue
    if i-last==1:
        flag =True
        break
    n = i - last - 3
    r = 0
    tmp = 1
    dif = 1
    print("n",n)
    while dif>0:
        r += 1
        if n<=0 or n<r:
            break
        print(n,r)
        tmp += cmb(n, r)
        dif = n-r
        print("tmp",tmp,n,r)
        n -= 1
    ans_l.append(tmp)
    # print(i,ans_l)
    last = i
if flag:
    print(0)
else:
    ans = 1
    for i in ans_l:
        ans*=i
    print(ans%1000000007)

Submission status: Runtime Error

Solution code:
from math import factorial
N,M=list(map(int,input().split()))

ans=1
flag=True
if M>0:
    dansa=[int(input()) for _ in range(M)]
    if dansa[0]==0:
        print("0")
    else:
        if len(dansa)>1:
            for i in range(M-1):
                if dansa[i]+1==dansa[i+1]:
                    print("0")
                    flag=False
                    break
    if flag:
        dansa.insert(0,0)
        dansa.append(N)
        for i in range(M+1):
            tmp=dansa[i+1]-dansa[i]-1
            arr=[i for i in range(int(tmp/2)+1)]
            #print("tmp:{}".format(tmp))
            hoge=0
            """
            if tmp%2==0:
                arr=[j*2 for j in range(0,int(tmp/2+1))]

            else:
                arr=[j*2+1 for j in range(0,int((tmp+1)/2))]
            """
            #print(arr)
            #if tmp%2==0:
            for k in arr:
                n=tmp-k
                hoge+=factorial(n) / factorial(k) / factorial(n-k)

            #print(hoge)
            ans=ans*hoge
            #print(ans)
        print(int(ans%1000000007))
        #print(ans)
else:
    tmp=N
    arr=[i for i in range(int(tmp/2)+1)]
    hoge=0
    for k in arr:
                n=tmp-k
                hoge+=factorial(n) / factorial(k) / factorial(n-k)
    ans=hoge
    print(ans)

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 = -1
if len(broken_lst) != 0:
    next_broken = broken_lst.pop(0)
last_broken = broken_lst[0]

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 or i + 2 == last_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)

if last_broken != N - 1:
    counter_arr[-1] += counter_arr[-2]
counter_arr[-1] %= 10**9 + 7

print(counter_arr[-1])

Submission status: Runtime Error

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

roots = 1
OUT = False

def fib(n):
    if n == 0:
        return 0
    if n == 1 or n == 2:
        return 1
    else:
        f = ((1 + 5**0.5) / 2)**n / 5**0.5 + 0.5
        return int(f)

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


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

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


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


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


if OUT:
    roots = 0

print(roots%1000000007)