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: Time Limit Exceeded

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

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

def get_count(num):
	count = 0
	for i in range(num // 2 + 1):
		count += c_count(num - i, i)
	return count

if M >= 1:
	num = a[0]
	ans = get_count(num - 1)
	
	if M > 1:
		for i in range(1, M):
			if a[i] == a[i-1] + 1:
				print(0)
				sys.exit()
			ans *= get_count(a[i] - a[i-1] - 2)
	ans *= get_count(N - a[-1] - 1)
	print(ans % 1000000007)
else:
	print(get_count(N))

Submission status: Time Limit Exceeded

Solution code:
import math

MOD = 10 ** 9 + 7

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

c = {}
def nCr(n, r):
    if (n, r) in c:
        return c[(n, r)]
    a = math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
    c[(n, r)] = a
    return a

d = {}
def step(n):
    if n in d:
        return d[n]
    a = 0
    for k in range(n // 2 + 1):
        a += nCr(n - k, k)
    d[n] = a
    return a

ans = 1
for i in range(M + 1):
    n = a[i + 1] - a[i] - 2
    if n < 0:
        ans = 0
    else:
        ans *= step(n)
print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
n, m = map(int, input().split())
a = []
cr = 0
for i in range(m):
    a.append(int(input()))
s =[]
if 1 in a[:2]:
    s.append(0)
else:
    s.append(1)
if 2 in a[:3]:
    s.append(0)
else:
    s.append(1+s[0])
for i in range(2,n):
    if i+1 in a[cr:]:
        cr += 1
        s.append(0)
    elif i in a[cr:]:
        s.append(s[i-2]% 1000000007)
    elif i-1 in a[cr:]:
        s.append(s[i-1]% 1000000007)
    else:
        s.append((s[i-1] + s[i-2])% 1000000007)
print(s[n-1] % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
N,M = [ int(x) for x in input().split() ]
a = [ int( input() ) for _ in range(M) ]
b = [ 0 for _ in range(N+1) ]

b[0] = 1
for i in range(N):
  for j in range(i+1, min(N+1,i+3)):
    if not j in a: b[j] += b[i]

ans = b[N]
ans %= 1000000007

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import numpy as np
s = list(map(int, input().split()))
N = s[0]
M = s[1]

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


broken = np.array([int(input()) for i in range(M)])
broken = np.append(-1,broken)
broken = np.append(broken,N+1)
#  -1段目とN+1段目が壊れていると表記して一貫した計算が可能に

gaps = np.array([])  # 壊れている段の間にある壊れていない段数
for i in range(M+1):
    gaps = np.append(gaps, broken[i+1]-broken[i]-1)

gaps = np.array(gaps, np.int)  # 整数列に変換
if 0 in gaps:
    print(0)
else:
    patterns = 1
    for i in range(len(gaps)):
        patterns *= fib(gaps[i]-1)
    print(patterns % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
import math
import sys

n, m = map(int, input().split())
a_list = [None] * (m + 2)
a_list[0] = -1
for i in range(m):
    a_list[i+1] = int(input())
a_list[-1] = n + 1

fact_memo = dict()
def fact(n):
    if n in fact_memo.keys():
        return fact_memo[n]
    f = math.factorial(n)
    fact_memo[n] = f
    return f

memo = dict()
ans = 1
cur = a_list[0]
for i, a in enumerate(a_list):
    if i == 0:
        continue
    sub = a - cur - 1
    cur = a
    if sub <= 2:
        if sub == 0:
            print(0)
            sys.exit()
        continue
    sub -= 1
    if sub in memo.keys():
        ans *= memo[sub]
        continue
    count = 0
    for j in range(sub // 2 + 1):
        count += fact(sub - j) // fact(j) // fact(sub - j * 2)
    memo[sub] = count
    ans *= count
print(ans % 1000000007)

Submission status: Time Limit Exceeded

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

x = [0]*(N+1)
y = [1]*(N+1)
for i in range(N+1):
    if i in a:
        y[i] = 0
x[0] = 1
if y[1] == 0:
    x[1] = 0
else:
    x[1] = 1

for i in range(2, N+1):
    if y[i] == 0:
        x[i] = 0
    else:
        x[i] = (x[i-1] + x[i-2]) % 1000000007
print(x[N])

Submission status: Time Limit Exceeded

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]*1000001
    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)
    x = 1
    for i in ans:
        x = x*dp[i]%d
    print(x)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    (N, M) = list(map(int, input().split(" ")))
    As = [int(input()) for i in range(M)]

    cnts = [False] * (N+1)
    for i in range(N+1):
        c = 0
        if i in As:
            c = 0
        elif i == 0:
            c = 1
        elif i == 1:
            c = 1
        elif i == 2:
            c = 2 if 1 not in As else 1
        else:
            c = (cnts[i-2] + cnts[i-1])%1000000007
        cnts[i] = c

    print(cnts[N])

if '__main__' == __name__:
    resolve()

Submission status: Time Limit Exceeded

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

x = [0]*(N+1)

ans = 0
x[0] = 1
if 1 in a:
    x[1] = 0
else:
    x[1] = 1

for i in range(2, N+1):
    if i in a:
        x[i] = 0
    else:
        x[i] = (x[i-1] + x[i-2]) % 1000000007
print(x[N])

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(1000000)

N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
a.append(N+1)
sum_move = 1
fact = [-1] * (N+1)
fact[0] = 1


def factorial(num, fact):
    if fact[num] > 0:
        return fact[num]
    else:
        fact[num] = factorial(num-1, fact) * num
        return fact[num]


step_begin = 0
for i in range(M+1):
    tmp_sum = 0
    step_end = a[i] - 1
    step_num = step_end - step_begin
    for j in range(step_num//2 + 1):
        tmp_sum += factorial(step_num - j, fact) \
            // factorial(j, fact) // factorial(step_num - 2 * j, fact)
    if tmp_sum != 0:
        sum_move *= tmp_sum
    else:
        sum_move = 0
        break
    step_begin = a[i] + 1

print(sum_move % 1000000007)

Submission status: Time Limit Exceeded

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

for i in range(n+1):
    if not i in A:
        if (dp[i-2] >= 1) and (i-2 >= 0):
            dp[i] += dp[i-2] % (10 ** 9 + 7)
        if (dp[i-1] >= 1) and (i-1 >= 0):
            dp[i] += dp[i-1] % (10 ** 9 + 7)
            
print(dp[-1] % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import factorial

mod = 10**9 + 7


def Cmb(n, k):
    return factorial(n) // (factorial(n - k) * factorial(k))


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

if 1 in [a[i + 1] - a[i] for i in range(l - 1)]:
    print(0)
    sys.exit()

b = [-1] + a + [n + 1]
c = []
for bi, bi2 in zip(b[:-1], b[1:]):
    c.append((bi2 - 1) - (bi + 1))  # width 2 を取れる数


def count(n):
    ret = 0
    for i in range(n // 2 + 1):
        ret += Cmb(n - i, i) % mod
    return ret


ans = 1
for ci in c:
    ans *= count(ci) % mod
    ans %= mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

MOD = 10 ** 9 + 7

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

c = {}
def nCr(n, r):
    if (n, r) in c:
        return c[(n, r)]
    a = math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
    c[(n, r)] = a
    return a

d = {}
def step(n):
    if n in d:
        return d[n]
    a = 0
    for k in range(n // 2 + 1):
        a += nCr(n - k, k)
    d[n] = a
    return a

ans = 1
for i in range(M + 1):
    n = a[i + 1] - a[i] - 2
    if n < 0:
        ans = 0
    else:
        ans *= step(n)
        ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

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

for i in range(n+1):
    if not i in A:
        if (dp[i-2] >= 1) and (i-2 >= 0):
            dp[i] += dp[i-2]
        if (dp[i-1] >= 1) and (i-1 >= 0):
            dp[i] += dp[i-1]
        dp[i] = dp[i] % (10 ** 9 + 7)
        
print(dp[-1] % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

Solution code:
import math
import sys

n, m = map(int, input().split())
a_list = [-1]
for _ in range(m):
    a_list.append(int(input()))
a_list.append(n + 1)

fact_memo = dict()
def fact(n):
    if n in fact_memo.keys():
        return fact_memo[n]
    f = math.factorial(n)
    fact_memo[n] = f
    return f

memo = dict()
ans = 1
cur = a_list[0]
for i, a in enumerate(a_list):
    if i == 0:
        continue
    sub = a - cur - 1
    cur = a
    if sub <= 2:
        if sub == 0:
            print(0)
            sys.exit()
        continue
    sub -= 1
    if sub in memo.keys():
        ans *= memo[sub]
        continue
    count = 0
    for j in range(sub // 2 + 1):
        count += fact(sub - j) // fact(j) // fact(sub - j * 2)
    memo[sub] = count
    ans *= count
print(ans % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
import math

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

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

a_list.append(N + 1)
start_step = 0
end_step = 0
answer = 1
for a in a_list:
    p = 0
    end_step = a - 1
    diff = end_step - start_step
    for x in range(diff // 2 + 1):
        p += math.factorial(diff - x) // math.factorial(x) // math.factorial(diff - 2 * x)
    answer *= p
    start_step = a + 1

for i in range(len(a_list) - 1):
    if a_list[i + 1] - a_list[i] < 2:
        answer = 0
        break

answer %= 1000000007
print(answer)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
a_list=[]
result_list=[]
for i in range(m):
	a_list.append(int(input()))
if n ==1:
	print(1)
elif n ==2 and 1 not in a_list:
	print(2)
elif n==2 and 1 in a_list:
	print(1)
else:
	if 1 in a_list:
		result_list.append(0)
	else:
		result_list.append(1)
	if 2 in a_list:
		result_list.append(0)
	elif 2 not in a_list and 1 in a_list:
		result_list.append(1)
	else:
		result_list.append(2)
	for i in range(2,n):
		if i+1 in a_list:
			result_list.append(0)
		else:
			result_list.append(result_list[i-1]+result_list[i-2])
	print(result_list[n-1]%1000000007)

Submission status: Time Limit Exceeded

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

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

if 1 not in a:
    b[1] = 1

for i in range(2,N+1):
    if i not in a:
        for j in range(1,3):
            if b[i-j] != 0:
                b[i]+= b[i-j]

print(b[N]%1000000007)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split(" "))
a=[]
ans = 1
for i in range(m):
    a.append(int(input()))
    if a[i]-1 == a[i-1]:
        ans = 0
if ans == 1:
    t = 1
    for j in range(n,-1,-1):
        if j in a:
            ans *= 1
        elif j+1 in a or j+2 in a:
            ans *= 1
        elif j+2 > n:
            ans *= 1
        elif not(j+2 in a) and not(j+3 in a) and not(j+3 > n):
            t2 = ans
            ans += t
            t = t2
        else:
            t = ans
            ans *= 2

print(ans % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
from sys import exit
import math
n,m =map(int,input().split())

modn=1000000007

if n==m:
    print(0)
    exit()

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

def step(steps):
    if steps<2:
        return 0
    if steps==2 or steps==3:
        return 1
    max=steps-2

    min=max//2+(1 if steps%2==1 else 0)
    sum=0
    for i in range(min,max+1):
        sum+=c(i,max-i)
    return sum

a=[]
prev=-1
cnt=1
for i in range(m):
    next=int(input())

    cnt*=step(next-prev)%modn
    
    prev=next

cnt*=step(n-prev+1)%modn
print(cnt%modn)

Submission status: Time Limit Exceeded

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())
A = []
for i in range(M):
  a = int(input())
  A.append(a)
  
flag = False
A.append(N+1)
A.sort()
a_struct = []
cut = 0
#0~2, #4~6
for i in A:
  x = []
  for j in range(cut, i):
    x.append(j)
  a_struct.append(len(x)-1)
  cut = i+1

#print(x)
#print(a_struct)
sum_ = 1  

for i in a_struct:
  if i == -1:
    flag = True
  sho = int(i/2)
  amari = i%2
  ccc = 0
  for j in range(sho+1):
    count = 0
    if j == 0:
      ccc += 1
      #print('j')
      continue
    counter_1 =i-2*j 
    counter_2 = j
    count = cmb(counter_1+counter_2, counter_1)

    #print('count ', count)
    ccc += count
  sum_ *= ccc
    
#print(a_struct)
if flag:
  print(0)
elif not flag:
  print(sum_%1000000007)
#2 2

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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 memo.get(now) != None:
        return memo[now]
    # print(now)
    memo[now] = step(now+1)+step(now+2)
    return memo[now]


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

Submission status: Time Limit Exceeded

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 culcC(num):
    if num  < 2:
        return 1
    ret = 1
    minus2 = 1
    while(True):
        ret += cmb(num - minus2,minus2 if minus2 >0 else 1)
        minus2 += 1
        if num - 2 * minus2 < 0:
            break
    return ret
            
n,m = map(int,input().split())
aa = [int(input()) for i in range(m)]

if n == 1:
    print(1)
elif m == 0:
    print(culcC(n) % 1000000007)
else:
    ans = 1
    stand = 0
    for i,a in enumerate(aa):
#        連続穴
        if stand == a:
            ans = 0
            break
        step_num = a - stand - 1
        ans *= culcC(step_num)
        stand = a + 1
        
    # 最後のaからnまでで計算
    ans *= culcC(n - aa[-1] - 1)
    
    print(ans % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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

memo = {}


def step(now):
    if (memo.get(now) != None):
        return memo.get(now)
    if (now in a):
        return 0
    # print(now)
    if (now == 0):
        return 1
    if (now < 0):
        return 0
    # print(now)
    memo.update({now: step(now-1)+step(now-2)})
    return memo.get(now)


print(step(n) % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
from functools import lru_cache
import sys
sys.setrecursionlimit(10 ** 9)

@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: Time Limit Exceeded

Solution code:
import math

def c(n, r):
    u = math.factorial(n)
    d = math.factorial(n-r) * math.factorial(r)
    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: Time Limit Exceeded

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

def convi(li):
    m=max(li)
    a=[1,1]
    if m>2:
        for i in range(2,m+1):
            a.append(a[i-2]+a[i-1])
            
    ans=1    
    for j in li:
        ans=ans*a[j-1]%1000000007
    return ans

def count(li,n):
    t=1
    ans=1
    li2=[]
    for i in range(1,n+1):
        if i in li:
            if i+1 in li:
                return(0)
            else:
                li2.append(t)
                t=0
        else:
            t+=1
    if t>0:        
        li2.append(t)   
    if 0 in li2:
    	li2.remove(0)
        

        
    return convi(li2)

                

print(count(li,n)%1000000007)

Submission status: Time Limit Exceeded

Solution code:
import math
import sys

n, m = map(int, input().split())
a_list = [-1]
for _ in range(m):
    a_list.append(int(input()))
a_list.append(n + 1)

memo = dict()
ans = 1
cur = a_list[0]
for i, a in enumerate(a_list):
    if i == 0:
        continue
    sub = a - cur - 1
    cur = a
    if sub <= 2:
        if sub == 0:
            print(0)
            sys.exit()
        continue
    sub -= 1
    if sub in memo.keys():
        ans *= memo[sub]
        continue
    count = 0
    for j in range(sub // 2 + 1):
        count += math.factorial(sub - j) // math.factorial(j) // math.factorial(sub - j * 2)
    memo[sub] = count
    ans *= count
print(ans % 1000000007)

Submission status: Time Limit Exceeded

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

for i in range(n+1):
    if not i in A:
        if (dp[i-2] >= 1) and (i-2 >= 0):
            dp[i] += dp[i-2]
        if (dp[i-1] >= 1) and (i-1 >= 0):
            dp[i] += dp[i-1]
            
print(dp[-1] % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

Solution code:
import math

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

ans = 1
a_pre = -1
for mi in range(m):
    a = int(input())
    if a == a_pre:
        break
    elif a == a_pre + 1:
        ans = 0
        break
    k = a - a_pre - 2
    max_2 = k//2
    cnt = 0
    for i in range(max_2+1):
        cnt += math.factorial(k-i) // (math.factorial(k-2*i) * math.factorial(i)) % 1000000007
    ans = ans * cnt % 1000000007
    if ans == 0:
        break
    a_pre = a

a = n + 1
if a == a_pre:
    pass
elif a == a_pre + 1:
    ans = 0
else:
    k = a - a_pre - 2
    max_2 = k//2
    cnt = 0
    for i in range(max_2+1):
        cnt += math.factorial(k-i) // (math.factorial(k-2*i) * math.factorial(i)) % 1000000007
    ans = ans * cnt % 1000000007

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n,m=(int(i) for i in input().split())
a = [int(input()) for i in range(m)]
#print(n,m,a)

d=[0 for i in range(100000+10)]
p=1000000007
#n=100
#a=[1, 23, 45, 67, 89]

d[0]=1
if a.count(1) == 0:
    d[1]=1
else:
    d[1]=0
    
if a.count(2) == 0:
    d[2]=d[1]+d[0]
else:
    d[2]=0
    
for i in range(2,n+1):
    if a.count(i) == 0:
        d[i]=d[i-1]+d[i-2]
        d[i]=d[i]%p
    else:
        d[i]=0
#print(d)

print(d[n]%p)

Submission status: Time Limit Exceeded

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

def dp(n,ls):
    dp_table=[[0 for i in range(n+1)]]
    dp_table[0][0]=1
    sum=0
    count=1
    edge=0
    while True:
        row=[0]*count
        previous=dp_table[-1]
        for i in range(count,n+1):
            if i in ls:
                row.append(0)
            elif i==0:
                row.append(0)
            elif i==1:
                row.append(previous[0])
            else:
                row.append(previous[i-1]+previous[i-2])
            if i==edge+2:
                edge=i
                row=row+([0]*(n-edge))
                break
        sum+=row[-1]
        if row.count(0)==n+1:
            return sum
        dp_table.append(row)
        count+=1

print(dp(n,ls)%1000000007)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
N, M = map(int, input().split())
A = []
for _ in range(M):
    A.append(int(input()))

num_goup = [1]
for s in range(1, N + 1):
    if s in A:
        if num_goup[-1] == 0:
            break
        num_goup.append(0)
        continue
    
    if s == 1:
        num_goup.append(1)
        continue
    
    if num_goup[-1] == 0:
        if num_goup[-2] == 0:
            num_goup.append(0)
            break
        else:
            num_goup.append(num_goup[-2])
    else:
        if num_goup[-2] == 0:
            num_goup.append(num_goup[-1])
        else:
            num_goup.append(num_goup[-1] + num_goup[-2])
    
print(num_goup[-1] % 1000000007)

Submission status: Time Limit Exceeded

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())
a=[-1]
ans=1
flg=0
for i in range(m):
    a.append(int(input()))
a.append(n+1)

for i in range(len(a)-1):
    k=a[i+1]-a[i]-2
    b=0
    tmp=0
    if k==-1 and i!=0:
        flg=1
        break
    while k-2*b>=0:
        c=k-2*b
        tmp+=cmb(c+b,c)
        b+=1
    if tmp!=0:
        ans*=tmp
        
ans=ans%(10**9+7)

if flg==0:
    print(ans)
else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
n, m = map(int, input().split())
a = []
for i in range(m):
    a.append(int(input()))
s =[]
if 1 in a:
    s.append(0)
else:
    s.append(1)
if 2 in a:
    s.append(0)
else:
    s.append(1+s[0])
for i in range(2,n):
    if i+1 in a:
        s.append(0)
    elif i in a:
        s.append(s[i-2]% 1000000007)
    elif i-1 in a:
        s.append(s[i-1]% 1000000007)
    else:
        s.append((s[i-1] + s[i-2])% 1000000007)
print(s[n-1] % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000000) 

def resolve():
    (N, M) = list(map(int, input().split(" ")))
    As = [int(input()) for i in range(M)]
    # mems = [False] * (N+1)

    cnts = [False] * (N+1)
    for i in range(N+1):
        c = 0
        if i in As:
            c = 0
        elif i == 0:
            c = 1
        elif i == 1:
            c = 1
        elif i == 2:
            c = 2 if 1 not in As else 1
        else:
            c = cnts[i-2] + cnts[i-1]
        cnts[i] = c
        # print("cnt[{}] = {}".format(str(i), str(c)))

    print(cnts[N]%1000000007)
    # for i in range(N-1):
    #     if i in As and i+1 in As:
    #         return 0 

    # def rec(target):
    #     if target in As:
    #         return 0
        
    #     if target == 1:
    #         return 1
        
    #     if target == 2:
    #         return 2 if 1 not in As else 1

    #     if not mems[target]:
    #         one = rec(target-1)
    #         two = rec(target-2)
    #         mems[target] = one + two
        
    #     return mems[target]
    # print(rec(N)%1000000007)

if '__main__' == __name__:
    resolve()

Submission status: Time Limit Exceeded

Solution code:
from math import factorial
import math
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(dd//2 + 1):
                tmp += cmb(dd - j, j)
            ans *= tmp

    print(ans % 1000000007)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math

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

ans = 1
for mi in range(1, m+2):
    if a[mi] == a[mi-1]:
        break
    elif a[mi] == a[mi-1] + 1:
        ans = 0
        break
    k = a[mi] - a[mi-1] - 2
    max_2 = k//2
    cnt = 0
    for i in range(max_2+1):
        cnt += math.factorial(k-i) // (math.factorial(k-2*i) * math.factorial(i)) % 1000000007
    ans = ans * cnt % 1000000007
    if ans == 0:
        break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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

memo = {}


def step(now):
    if (memo.get(now) != None):
        return memo[now]
    if (now in a):
        return 0
    # print(now)
    if (now == 0):
        return 1
    if (now < 0):
        return 0
    # print(now)
    memo[now] = step(now-1)+step(now-2)
    return memo[now]


print(step(n) % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
a = [int(input())-1 for i in range(m)]
dp = [0]*n
if n==1:
    if 0 in a:
        print(0)
        exit()
    else:
        print(1)
        exit()
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 in a:
        continue
    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]
        if dp[i]>10**9+7:
            dp[i]-=(10**9+7)
print(dp[n-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000000)

def dfs(x):
  if x == N:
    return 1
  if x > N or x in a:
    return 0
  if memo[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 = [False]*(N+1)
count = dfs(0)
print(count%1000000007)

Submission status: Time Limit Exceeded

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

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


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

dp = [0] * (N + 1)

if N == 1 and M != 1:
    print(1)
    exit()
elif N == 1 and M == 1:
    print(0)
    exit()

if 1 in a and 2 in a:
    print(0)
    exit()

if 1 in a:
    dp[1] = 0
    dp[2] = 1
elif 2 in a:
    dp[1] = 1
    dp[2] = 0
else:
    dp[1] = 1
    dp[2] = 2

for i in range(3,N+1):
    if i in a:
        dp[i] = 0
    else:
        dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007

print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
import math
import sys

n, m = map(int, input().split())
a_list = [-1]
for _ in range(m):
    a_list.append(int(input()))
a_list.append(n + 1)

memo = dict()
ans = 1
for i in range(1, len(a_list)):
    sub = a_list[i] - a_list[i-1] - 1
    if sub == 0:
        print(0)
        sys.exit()
    if sub <= 2:
        continue
    sub -= 1
    if sub in memo.keys():
        ans *= memo[sub]
        continue
    count = 0
    for j in range(sub // 2 + 1):
        count += math.factorial(sub - j) // math.factorial(j) // math.factorial(sub - j * 2)
    memo[sub] = count
    ans *= count
print(ans % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
[N,M] = list(map(int,input().split()))
a = [int(input()) for i in range(M)]
DP = [0]*(N+1)
DP[0] = 1
if 1 in a:
    DP[1] = 0
else:
    DP[1] = 1
for i in range(2,N+1):
    if i in a:
        DP[i] = 0
    else:
        DP[i] = DP[i-1] + DP[i-2]
print(DP[N]%(1000000007))

Submission status: Time Limit Exceeded

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

def convi(li):
    m=max(li)
    a=[1,1]
    if m>2:
        for i in range(2,m+1):
            a.append(a[i-2]+a[i-1])
            
    ans=1    
    for j in li:
        ans*=a[j-1]
    return ans

def count(li,n):
    t=1
    ans=1
    li2=[]
    for i in range(1,n+1):
        if i in li:
            if i+1 in li:
                return(0)
            else:
                li2.append(t)
                t=0
        else:
            t+=1
    if t>0:        
        li2.append(t)   
    if 0 in li2:
    	li2.remove(0)
        

        
    return convi(li2)

                

print(count(li,n)%1000000007)