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:
#d=["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]
#import numpy as np
#n=int(input())
#import fractions
#import math
#lis=list(input().split())
#lis=list(map(float,input().split()))
#n=int(input())
#S=input()

import itertools

lis=list(map(int,input().split()))
alist=[-1]
ans=1
for i in range(lis[1]):
    alist.append(int(input()))
alist.append(lis[0]+1)

for i in range(lis[1]+1):
    l=alist[i+1]-alist[i]-2
    tmp=0
    t=int((l+l%2)/2)
    h=int((l-l%2)/2)
    for j in range(h+1):
        tmp+=len(list(itertools.combinations(range(t+j),h-j)))
    ans=(ans*tmp)%((10**9)+7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# n=int(input())
# a,b=map(int, input().split())
# c=list(map(int, input().split()))
# s=[list(map(int,list(input()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき

# a=100
# b=0.987654321
# print('{0:06d}-{1:6f}'.format(a,b))  # 0埋めのときの出力
# 000100-0.987654

import numpy as np
import math
import copy
import itertools
from math import factorial

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

div_num  = 1000000007

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

dmg = [int(input()) for _ in range(M)]

for i in range(M - 1):
    # 連番なら終了
    if dmg[i] + 1 == (dmg[i + 1]):
        print(0)
        exit()

comb_list = []
start = 0
for i in range(len(dmg) + 1):
    if i == len(dmg):
        interval = N - start
    else:
        interval = (dmg[i] - 1) - start
    j = 0
    comb_sum = 0
    while True:
        if (2 * j) > interval:
            break
        num_ptn_1_2 = j + (interval - (2 * j))
        r = j
        #comb_sum += int(factorial(num_ptn_1_2) / factorial(r) / factorial(num_ptn_1_2 - r))
        comb_sum += cmb(num_ptn_1_2,r)
        j += 1
    if i < len(dmg):
        # 壊れた階段の次を始点にする
        start = dmg[i] + 1
    comb_list.append(comb_sum)

result = 1

for elem in comb_list:
    result *= elem

print(result % div_num)

Submission status: Time Limit Exceeded

Solution code:
import math
import functools
import operator


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

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
    
def sum_comb(gap):
    if gap < 0:
        return 0
    elif gap < 2:
        return 1
    else:
        return sum([combinations_count(gap-i, i) for i in range((gap//2+1))])

combs = []
now = 0
for step in break_steps:
    gap = step - 1 - now
    combs.append(sum_comb(gap))
    now = step + 1
gap = n - now
combs.append(sum_comb(gap))
print(functools.reduce(operator.mul, combs) % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
import operator
from functools import reduce


def ncr(n, r):
    r = min(r, n-r)
    numer = reduce(operator.mul, range(n, n-r, -1), 1)
    denom = reduce(operator.mul, range(1, r+1), 1)
    return numer // denom


def calc_step2patterns(num_step):
    pats = 0
    for j in range(0, (num_step//2)+1):
        pats += ncr(num_step-j, j)
    return pats


def step2patterns(num_step, step_dict):
    try:
        return step_dict[num_step]
    except KeyError:
        ret = calc_step2patterns(num_step)
        step_dict[num_step] = ret
        return ret


num_stair, num_wet = map(int, input().split(' '))

last_wet = -1
num_pattern = 1
d = {}

for i in range(0, num_wet):
    wet = int(input())
    dry_step = wet - last_wet - 1
    last_wet = wet

    if dry_step <= 0:
        print('0')
        exit(0)

    elif dry_step == 1 or dry_step == 2:
        continue

    else:
        num_pattern *= step2patterns(dry_step - 1, d)

# last step
dry_step = num_stair - last_wet

num_pattern *= step2patterns(dry_step - 1, d)

print(num_pattern % 1000000007)
exit(0)

Submission status: Time Limit Exceeded

Solution code:
#d=["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]
#import numpy as np
#n=int(input())
#import fractions
#import math
#lis=list(input().split())
#lis=list(map(float,input().split()))
#n=int(input())
#S=input()

import itertools

lis=list(map(int,input().split()))
alist=[-1]
ans=1
for i in range(lis[1]):
    alist.append(int(input()))
alist.append(lis[0]+1)

for i in range(lis[1]+1):
    l=alist[i+1]-alist[i]-2
    tmp=0
    t=int((l+l%2)/2)
    h=int((l-l%2)/2)
    for j in range(h+1):
        tmp+=len(list(itertools.combinations(range(t+j),h-j)))
    ans=ans*tmp
ans=ans%((10**9)+7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7
N,M = map(int,input().split())
a = [int(input()) for _ in range(M)]
if M>N//2+2:
  print(0)
  exit()
x = 0
y = 1
for i in range(N):
  if i+1 in a:
    z = 0
  else:
    z = x + y
  x = y
  y = z
print(z%MOD)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(50000)
N,M=map(int,input().split())
L=[int(input()) for _ in range(M)]
ans=0

def dfs(i):
	global ans
	if i==N:
		ans+=1
		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: Time Limit Exceeded

Solution code:
#import numpy as np
#from numpy import*
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph) # dijkstra# floyd_warshall
#from scipy.sparse import csr_matrix

from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)
#input=sys.stdin.readline  #危険！基本オフにしろ！

def main():
    n,m,*a=map(int,open(0).read().split())
    dp=[0]*(n+1)
    dp[0]=1
    mod=10**9+7
    for i in range(1,n+1):
        if i in a:
            continue
        dp[i]=dp[i-1]%mod
        if i>1:
            dp[i]+=dp[i-2]%mod
    print(dp[n]%mod)
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
n,m = list(map(int,input().split()))
a = [int(input()) for i in range(m)]

inf=float("inf")

fib_memo = [-inf for i in range(n+1)]
fib_memo[0] = 1
if 1 in a:
    fib_memo[1]=0
else:
    fib_memo[1]=1

if 1 in [a[i] - a[i-1] for i in range(1,m)]:
    print(0)
    import sys
    sys.exit()
else:
    cur_fib_i = 2
    while cur_fib_i <= n:
        if cur_fib_i in a:
            fib_memo[cur_fib_i]=0
        else:
            fib_memo[cur_fib_i] = fib_memo[cur_fib_i-1] + fib_memo[cur_fib_i-2]
        cur_fib_i += 1
print(fib_memo[n]%1000000007)
#print(fib_memo)

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

def pattcount(num):
    if(num == 0): return 1
    if(num < 0): return 0
    result = 1
    ranmax = num // 2 + 1
    for i in range(1, ranmax):
        result += cmb(num-i, i)
    
    return result
    

if __name__ == '__main__':
    n,m = list(map(int, input().split()))

    pattern = 1
    step = 0
    for i in range(m):
        a = int(input())
        pattern *= pattcount(a - 1 - step)
        step = a + 1

    pattern *= pattcount(n - step)

    print(pattern % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
#from numpy import*
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph) # dijkstra# floyd_warshall
#from scipy.sparse import csr_matrix

from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)
#input=sys.stdin.readline  #危険！基本オフにしろ！

def main():
    n,m,*a=map(int,open(0).read().split())
    dp=defaultdict(int)
    dp[0]=1
    mod=10**9+7
    for i in range(1,n+1):
        if i in a:
            continue
        dp[i]=dp[i-1]%mod
        if i>1:
            dp[i]+=dp[i-2]%mod
    print(dp[n]%mod)
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
n, m = map(int, input().split())
a = [0] + [int(input()) for _ in range(m)] + [n]


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


ans = 1
for i in range(m + 1):
    if i == 0 and i == m:
        ra = a[i+1] - a[i]
    elif i == 0 or i == m:
        ra = a[i+1] - a[i] - 1
    else:
        ra = a[i+1] - a[i] - 2
    if ra < 0:
        if i == 0 or i == m:
            continue
        else:
            ans = 0
            break
    elif ra == 0:
        continue
    elif ra == 1:
        continue
    else:
        aaa = 1
        for n in range(1, ra // 2 + 1):
            length = ra - (2 * n) + n
            aaa += combinations_count(length, n)
        ans *= aaa

print(ans % 1000000007)

Submission status: Time Limit Exceeded

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

n,m=map(int,input().split())
a=[int(input()) for i in range(m)]
F = [1]*(n+3)
for i in range(2,n+1):
    F[i]=(F[i-1]%(10**9+7)+F[i-2]%(10**9+7))%(10**9+7)


if n==1:
    print(1)
elif n==2:
    if m==1:
        print(1)
    elif m==0:
        print(2)
else:
    for i in range(m):
        if a[i]+1 in a or a[i]-1 in a:
            print(0)
            exit()
    if m==0:
        print(F[n])
    else:
        x=F[min(a)-1]
        a.append(n+1)
        for i in range(1,len(a)):
            x=(x*F[a[i]-a[i-1]-2])%(10**9+7)
        print(x)

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import factorial

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

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

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

ans = ans % 1000000007
print(ans)

Submission status: 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 a in a_list[1:]:
    sub = a - cur - 2
    cur = a
    if sub <= 1:
        if sub == -1:
            print(0)
            sys.exit()
        continue
    if sub in memo.keys():
        ans *= memo[sub]
        continue
    count = sum(fact(sub - j) // fact(j) // fact(sub - j*2) for j in range(sub // 2 + 1))
    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 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:
        A.remove(i)
        
print(dp[-1] % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

Solution code:
def solve(n,m,a):
    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)
    return dp[-1]
def main():
    n,m = map(int,input().split())
    a = [int(input())-1 for i in range(m)]
    print(solve(n,m,a))
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
N, M = map(int, input().split())
a = []
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 % 1000000007

if M >= 1:
	a.append(int(input()))
	num = a[0]
	ans = get_count(num - 1)
	
	if M > 1:
		for i in range(1, M):
			a.append(int(input()))
			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:
n, m = map(int, input().split())
a_s = [int(input()) for _ in range(m)]

dp = [1]

for i in range(1, n + 1):
    if i in a_s:
        dp.append(0)
    else:
        dpim2 = 0 if i-2 < 0 else dp[i-2]
        dp.append((dp[i-1] + dpim2) % 1000000007)

print(dp[-1])

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()))

for s1, s2 in zip(A[1:], A[:-1]):
    if s1 - s2 == 1:
        print(0)
        break

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

Submission status: Time Limit Exceeded

Solution code:
import math
import functools
import operator


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

def combinations_count(n, r):
    if n -r >= 0:
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
    else:
        return 0
    
def sum_comb(gap):
    if gap < 0:
        return 0
    elif gap < 2:
        return 1
    else:
        return sum([combinations_count(gap-i, i) for i in range(gap)])

combs = []
now = 0
for step in break_steps:
    gap = step - 1 - now
    combs.append(sum_comb(gap))
    now = step + 1
gap = n - now
combs.append(sum_comb(gap))
print(functools.reduce(operator.mul, combs) % 1000000007)

Submission status: Time Limit Exceeded

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

n,m=map(int,input().split())
a=[int(input()) for i in range(m)]
F = [1,1]
for i in range(1,n):
    F.append((F[i]%(10**9+7)+F[i-1]%(10**9+7))%(10**9+7))


if n==1:
    print(1)
elif n==2:
    if m==1:
        print(1)
    elif m==0:
        print(2)
else:
    for i in range(m):
        if a[i]+1 in a or a[i]-1 in a:
            print(0)
            exit()
    if m==0:
        print(F[n])
    else:
        x=F[min(a)-1]
        a.append(n+1)
        for i in range(1,len(a)):
            x=(x*F[a[i]-a[i-1]-2])%(10**9+7)
        print(x)

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 = step_end + 2

print(sum_move % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import itertools as itr

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

def calc_routes(dan):
    tmp = 1
    for i in range(int(dan/2)):
        i += 1
        n = dan - i
        tmp += len(list(itr.combinations(range(n), i)))

    return tmp

routes = 1
prev = 0
for x in a:
    if x == prev:
        routes = 0
        break
    else:
        dan = (x-1) - prev
        routes = (routes * calc_routes(dan)) % 1000000007
        prev = x+1

routes = (routes * calc_routes(N-prev)) % 1000000007
print(int(routes))

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
  


  
  
N, M = map(int,input().split())
A = []
for i in range(M):
  a = int(input())
  A.append(a)
  
flag = False
for i in A:
  if i+1 in A:
    flag = True
    
    
if flag :
  print(0)
elif not flag:
  A.append(N+1)
  A.sort()
  a_struct = []
  cut = 0
  for i in A:
    x = []
    for j in range(cut, i):
      x.append(j)
    a_struct.append(len(x)-1)
    cut = i+1


  sum_ = 1  

  for i in a_struct:
    sho = int(i/2)
    amari = i%2
    ccc = 0
    for j in range(sho+1):
      count = 0
      if j == 0:
        ccc += 1
        continue
      counter_1 =i-2*j 
      ccc += cmb(counter_1+j, j)
    sum_ *= ccc
    
    
  print(sum_%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 i >= 2:
            dp[i] += (dp[i-2] + dp[i-1]) % (10 ** 9 + 7)
        elif i == 1:
            dp[i] += dp[i-1] % (10 ** 9 + 7)
            
print(dp[-1] % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

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

def stairs(n):
    if(n<=0):
        return 1
    comb = 0
    for i in range(int(n/2)+1):
        comb += combinations_count(n-i,i)
    return comb

def main():
    N,M = map(int,input().split(" "))
    broken_l = []
    for _ in range(M):
        broken_l.append(int(input()))

    broken_l.append(-1)
    broken_l.append(N+1)
    broken_l.sort()
    ans = 1
    for i in range(len(broken_l)-1):
        step = broken_l[i+1] - broken_l[i]
        if(step == 1 and broken_l[i+1]!=1):
            print(0)
            exit(0)
        else:
            ans *= stairs(step-2)

    print(ans%(1000000007))

if __name__ == '__main__':
    main()

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)  # 整数列に変換

fibs = []
for i in range (max(gaps)):
    fibs.append(fib(i))


if 0 in gaps:
    print(0)
else:
    patterns = 1
    for i in range(len(gaps)):
        patterns *= fibs[gaps[i]-1]
    print(patterns % 1000000007)

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 % 1000000007

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:
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])
			result_list[i-2] = 0
	print(result_list[n-1]%1000000007)

Submission status: Time Limit Exceeded

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


if n==1:
    print(1)
elif n==2:
    if m==1:
        print(1)
    elif m==0:
        print(2)
else:
    for i in range(m):
        if a[i]+1 in a or a[i]-1 in a:
            print(0)
            exit()
    if m==0:
        print(F[n])
    else:
        x=F[min(a)-1]
        a.append(n+1)
        for i in range(1,len(a)):
            x=(x*F[a[i]-a[i-1]-2])%(10**9+7)
        print(x)

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 = sum(fact(sub - j) // fact(j) // fact(sub - j*2) for j in range(sub // 2 + 1))
    memo[sub] = count
    ans *= count
print(ans % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
import sys

mod = 10**9 + 7


def extgcd(a, b):
    r = [1, 0, a]
    w = [0, 1, b]
    while w[2] != 1:
        q = r[2] // w[2]
        r2 = w
        w2 = [r[0] - q * w[0], r[1] - q * w[1], r[2] - q * w[2]]
        r = r2
        w = w2
    return [w[0], w[1]]


def mod_inv(a, m):
    x = extgcd(a, m)[0]
    return (m + x % m) % m


def Cmb(n, k):
    res = 1
    for i in range(1, n + 1):
        res = res * i % mod
    for i in range(1, k + 1):
        res = res * mod_inv(i, mod) % mod
    for i in range(1, n - k + 1):
        res = res * mod_inv(i, mod) % mod
    return res


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:
N,W = input().split()
aArr = list()
ans = 0
tmp = int(N)
for i in range(int(W)):
    inputInt = int(input())
    aArr.append(inputInt)
    if inputInt - tmp == 1:
        print(ans)
        exit()
    tmp = inputInt
tmp = 0
intArr = list()
for i in range(int(N)+1):
    if(i in aArr):
        intArr.append(0)
    elif i < 2:
        intArr.append(1)
    else:
        intArr.append(intArr[i-2] + intArr[i-1])
print(intArr[int(N)] % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
n,m = list(map(int,input().split()))
a = [int(input()) for i in range(m)]

inf=float("inf")

fib_memo = [1]
if 1 in a:
    fib_memo.append(0)
else:
    fib_memo.append(1)

if 1 in [a[i] - a[i-1] for i in range(1,m)]:
    print(0)
    import sys
    sys.exit()
else:
    cur_fib_i = 2
    while cur_fib_i <= n:
        if cur_fib_i in a:
            fib_memo.append(0)
        else:
            fib_memo.append(fib_memo[cur_fib_i-1] + fib_memo[cur_fib_i-2])
        cur_fib_i += 1
print(fib_memo[n]%1000000007)
#print(fib_memo)

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
for i in A:
  if i+1 in A:
    flag = True
    
    
if flag :
  print(0)
elif not flag:
  A.append(N+1)
  A.sort()
  a_struct = []
  cut = 0
  for i in A:
    x = []
    for j in range(cut, i):
      x.append(j)
    a_struct.append(len(x)-1)
    cut = i+1


  sum_ = 1  

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

Submission status: Time Limit Exceeded

Solution code:
nn, m = map(int, input().split())
a = []
sum = []
for i in range(m):
    a.append(int(input()))
def count(n):
    if n < 0:
        return 0
    if n == 0:
        return 1
    if n in a:
        return 0
    if n == 1:
        return 1
    return sum[n - 1] + sum[n - 2]

for i in range(nn + 1):
    sum.append(count(i))
print(sum[nn] % 1000000007)

Submission status: Time Limit Exceeded

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

def stairs(n):
    if(n<0):
        return 1
    comb = 0
    for i in range(int(n/2)+1):
        comb += combinations_count(n-i,i)
    return comb

def main():
    N,M = map(int,input().split(" "))
    broken_l = []
    for _ in range(M):
        broken_l.append(int(input()))

    broken_l.append(-1)
    broken_l.append(N+1)
    broken_l.sort()
    ans = 1
    for i in range(len(broken_l)-1):
        step = broken_l[i+1] - broken_l[i]
        if(step == 1 and broken_l[i+1]!=1):
            print(0)
            exit(0)
        else:
            ans *= stairs(step-2)

    print(ans%(1000000007))

if __name__ == '__main__':
    main()

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]
  if b[i] == 0: continue

ans = b[N]
ans %= 1000000007

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math

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

pre_a = None
for _ in range(M):
    a = int(input())
    if pre_a is not None and a - pre_a < 2:
        print(0)
        sys.exit()
    pre_a = a
    a_list.append(a)

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

answer %= 1000000007
print(answer)

Submission status: Time Limit Exceeded

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

modn=1000000007

def c(n, r):
    return factorial(n) // (factorial(n - r) * 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

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)