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 operator
from functools import reduce
from scipy.misc import comb


def ncr(n, r):
    return comb(n, r, exact=True)


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

    num_pattern %= 1000000007

# last step
dry_step = num_stair - last_wet

num_pattern *= step2patterns(dry_step - 1)

print(num_pattern % 1000000007)
exit(0)

Submission status: Time Limit Exceeded

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)
else:
  k = [0, 1]    
  for i in range(1, N+1): #インデックスは-1
    if i in a:
      k.append(0)
    else:
      sum = k[i-1] + k[i]
      k.append(sum)
      
  print(k[-1]%1000000007)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
al=[int(input()) for i in range(m)]
mod=1000000007
ansl=[0,1]
for i in range(1,n+1):
    if i in al:
        ansl.append(0)
    else:
        ansl.append((ansl[-2]+ansl[-1])%mod)
print(ansl[-1]%mod)

Submission status: Time Limit Exceeded

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

h = []
a = 1
b = 0
mod = 10 ** 9 + 7

for i in range(m):
    h += [int(input()),]

for i in range(1,n+1):
    if i in h:
        a,b = 0,a
    else:
        a,b = a + b,a
        a %= mod
        

print(a % mod)

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)
    comb = combination(num_stair,0)
    #print(comb)
    ans_tmp = comb
    for j in range(1, max_num_two_up+1):
        comb = comb * (num_stair - (j-1) - (j-1)) * (num_stair - (j-1) - (j-1) - 1) // j // (num_stair - (j-1))
        ans_tmp += comb
        #print(comb)
    ans *= ans_tmp

ans = ans % 1000000007
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
ans=-1
dp=[0 for i in range(n+1)]
dp[1]=1
if n==1 and m==1:
  ans=0
if n==2 and m==1:
  br=int(input())
  if br==1:
    ans=1
  elif br==2:
    ans=0
if n==2 and m==2:
  ans=0
if n>=2:
  dp[2]=2


q=1000000007
a=[]
if n>=3:
  for i in range(m):
    b=int(input())
    a.append(b)
    if b-a[i-1]==1:
      ans=0
      break
    if b==1:
      dp[1]=0
      dp[2]=1
    if b==2:
      dp[2]=0

  for i in range(3,n+1):
    if i in a:
      continue
    else:
      dp[i]=(dp[i-1]+dp[i-2])
      """print("dp[i]",i,dp[i])"""
if ans==0 or ans==1:
  dp[n]=ans
while(dp[n]>q):
  dp[n]=dp[n]%q
print(dp[n])

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 step2patterns(num_step):
    pats = 0
    for j in range(0, (num_step//2)+1):
        pats += ncr(num_step-j, j)
    return pats


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

last_wet = -1
num_pattern = 1

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)

# last step
dry_step = num_stair - last_wet

num_pattern *= step2patterns(dry_step - 1)

print(num_pattern % 1000000007)
exit(0)

Submission status: Time Limit Exceeded

Solution code:
N, M  = map(int, input().split())
a  = []
for _ in range(M):
  a.append(int(input()))
sdic  = {}
ans = 0
sdic[N] = 1
sdic[N+1] = 0
for n in reversed(range(N)):
  if n in a:
    sdic[n] = 0
    continue
  t = sdic[n+1] + sdic[n+2]
  if t == 0:
    print(0)
    quit()
  sdic[n] = t
  
print(sdic[0]%1000000007)

Submission status: Time Limit Exceeded

Solution code:
# ABC129C - Typical Stairs
import sys
input = sys.stdin.readline

n, m = list(map(int, input().rstrip().split()))
lst = list(map(int, [input().rstrip() for _ in range(m)]))
MOD = 10 ** 9 + 7

if 0 in lst:
    a, b = 0, 1
if 1 in lst:
    a, b = 1, 0
else:
    a, b = 1, 1

for i in range(2, n + 1):
    if a == 0 and b == 0:
        print(0)
        break
    if i in lst:
        a = b
        b = 0
    else:
        tmp = b
        b = (a + b) % MOD
        a = tmp
else:
    print(b)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split(" "))
a=[]
mod = 10 ** 9 + 7
ans = 1
for i in range(m):
    a.append(int(input()))
    if a[i]-1 == a[i-1]:
        ans = 0
if ans == 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+3 in a) and not(j+3 > n):
            temp = ans
            ans += t
            t = temp
        else:
            t = ans
            ans *= 2

print(ans % mod)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
N, M = [int(_) for _ in stdin.readline().rstrip().split()]
A = [int(stdin.readline().rstrip()) for _ in range(M)]

def solve(n):
    dp = []
    for i in range(n+1):
        if i in A:
            dp.append(0)
        else:
            dp.append(1)
    for i in range(2, n+1):
        if dp[i] == 0:
            continue
        dp[i] = dp[i-1]+dp[i-2]
    return dp[n] % 1000000007

print(solve(N))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def solve():
	N, M = map(int, input().split())
	A = [int(input()) for _ 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)

solve()

Submission status: Time Limit Exceeded

Solution code:
import operator
from functools import reduce
from scipy.misc import comb


def ncr(n, r):
    return comb(n, r, exact=True)


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

# last step
dry_step = num_stair - last_wet

num_pattern *= step2patterns(dry_step - 1)

print(num_pattern % 1000000007)
exit(0)

Submission status: Time Limit Exceeded

Solution code:
import math

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

if M == 0:
    a = [-1 , N+1]
else :
    a = [-1] * (M+2)

    for i in range(1,M+1) :
        a[i] = int(input())

flag = True # 可能かどうか
for i in range(0,M+1) :
    if a[i] + 1 == a[i+1] :
        flag = False
        break

fact = [0] * (N+2)

if flag :
    a[M+1] = N + 1

    ans = 1

    for i in range(M+1) :
        length = a[i+1] - a[i] - 2 # 上がる長さ
        max2step = math.floor(length / 2) # 2段の回数
        count = 1
        for j in range(1,max2step+1) :
            if fact[j] != 0 :
                step2 = fact[j]
            else :
                step2 = math.factorial(j)
                fact[j] = step2
            if fact[length-2*j] != 0 :
                step1 = fact[length-2*j]
            else :
                step1 = math.factorial(length-2*j)
                fact[length-2*j] = step1
            if fact[length - j] != 0 :
                step3 = fact[length-j]
            else :
                step3 = math.factorial(length - j)
                fact[length - j] = step3
            count += step3 // step1 // step2
        ans *= count

    print(ans % 1000000007)
else :
    print(0)

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

Submission status: Time Limit Exceeded

Solution code:
import operator
from functools import reduce
from scipy.misc import comb


def ncr(n, r):
    return comb(n, r, exact=True)


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:
import sys
sys.setrecursionlimit(1000000)

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

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

def count(now,s,e):
    if now > e:
        return 0
    if now == e:
        return 1
    cnt=0
    cnt+=count(now+1,s,e)
    cnt+=count(now+2,s,e)
    return cnt


c_mod=1000000007
start=0
end=0
ans=1
before=100000
for a in a_list:
    if abs(before-a)==1:
        print(0)
        exit()
    # 各部分の移動方法
    end=a-1
    ans=ans*count(start,start,end)%c_mod
    start=a+1
    before=a
if end<n:
    end=n
    ans=ans*count(start,start,end)%c_mod
print(ans)

Submission status: Time Limit Exceeded

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

pat = [1]
zero = False
for i in range(1, n + 1):
    if i - 1 in a and i - 2 in a:
        zero = True
        break
    if i in a:
        pat.append(0)
        continue
    cnt = 0
    if i - 1 not in a:
        cnt = (cnt + pat[i - 1]) % mod
    if i - 2 >= 0 and i - 2 not in a:
        cnt = (cnt + pat[i - 2]) % mod
    pat.append(cnt)

if zero:
    print(0)
else:
    print(pat[n])

Submission status: Time Limit Exceeded

Solution code:
from math import factorial

N, M = map(int, input().split())
search_starts = [0]
search_ends = []
for _ in range(M):
    a_i = int(input())
    search_ends.append(a_i-1)
    search_starts.append(a_i+1)
search_ends.append(N)

all_patterns = 1
for start, end in zip(search_starts, search_ends):
    passdiff = end - start
    num_2 = passdiff // 2
    residue = passdiff % 2

    tmp_patterns_for_range = 0
    for num2to1 in range(num_2+1):
        add_n_1 = num2to1 * 2
        tmp_num2 = num_2 - num2to1
        tmp_n_pattern = \
            factorial(tmp_num2 + add_n_1 + residue) // factorial(tmp_num2) // factorial(add_n_1 + residue)
        tmp_patterns_for_range += tmp_n_pattern
    all_patterns *= tmp_patterns_for_range

print(all_patterns%1000000007)

Submission status: Time Limit Exceeded

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

pat = [1]
zero = False
for i in range(1, n + 1):
    if i - 1 in a and i - 2 in a:
        zero = True
        break
    if i in a:
        pat.append(0)
        continue
    cnt = 0
    if i - 1 not in a:
        cnt = (cnt + pat[i - 1]) % mod
    if i - 2 >= 0 and i - 2 not in a:
        cnt = (cnt + pat[i - 2]) % mod
    pat.append(cnt % mod)

if zero:
    print(0)
else:
    print(pat[n])

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


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 += int(comb(num_ptn_1_2,r,exact=True))
        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:
from math import factorial
import sys
n,m =map(int,input().split())

modn=1000000007

prev=-1
cnt=1
for i in range(m+1):
    next=0

    if i==m:
        next=n+1
    else:
        next=int(input())

    steps=next-prev
    if steps<2:
        print(0)
        sys.exit()
    elif steps==2 or steps==3:
        None
    else:
        max=steps-2

        min=max//2+(1 if steps%2==1 else 0)
        sum=0
        for i in range(min,max+1):
            sum+=factorial(i) // (factorial(i*2 - max) * factorial(max-i))
        cnt*=sum%modn
    
    prev=next

print(cnt%modn)

Submission status: Time Limit Exceeded

Solution code:
#ABC129C-TypicalStairs.py

#import list
from sys import stdin
from functools import lru_cache

input = stdin.readline

#constant
#N = int(input())
N, M = list(map(int,input().split()))
A = [int(input()) for _ in range(M)]+[N+1]

#variable

#function
@lru_cache(maxsize=None)
def partition(two_steps,total_steps):
    if two_steps == 0:
        return 1
    elif two_steps == 1:
        return total_steps-1
    else:
        result = 0
        for i in range(total_steps-(2*(two_steps-1))):
            result += partition(two_steps-1,total_steps-(i+2))
        return result

@lru_cache(maxsize=None)
def sectorSum(total_steps):
    if total_steps == 0:
        return 0
    result = 0
    max_two_steps = total_steps//2
    for two_steps in range(max_two_steps+1):
        result += partition(two_steps,total_steps)
    return result
#class

#main function
def main():
    totalResult = 1
    position = 0
    i = 0
    while position < N:
        a = A.pop(0)
        if position+1 == a:
            position = a+1
            if position == A[0]:
                totalResult = 0
                break
        else:
            totalResult = totalResult*sectorSum(a-1-position)
            position = a+1
    print(totalResult%1000000007)




if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
o = [int(input()) for _ in range(m)]
#print(o)
mod = (10**9)+7
dp = [1]+[0]*(n)
flag1 = False

for i in range(n):
  if i+1 not in o:
    dp[i+1] = dp[i] + dp[i-1]
  else:
    dp[i+1] = 0
  #print(i,dp)
#print(dp)
print(dp[-1]%mod)

Submission status: Time Limit Exceeded

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

# memo = [-1 for _ in range(n)]
step_now = 0
step_1   = 0
step_2   = 0
DIV_NUM = 1000000007
if 1 in a_list:
    step_now = 0
else:
    step_now = 1
for i in range(1, n):
    if i == 1:
        step_1 = step_now
        if i+1 in a_list:
            step_now = 0
        else:
#             memo[i] = (memo[0] + 1) % DIV_NUM
            step_now = step_1 + 1
    else:
        step_2 = step_1
        step_1 = step_now
        if i+1 in a_list:
            step_now = 0
        else:
#             memo[i] = (memo[i-1] + memo[i-2]) % DIV_NUM
            step_now = (step_1 + step_2) % DIV_NUM
    if step_now ==  step_1 == step_2 == 0:
        break

print(step_now)

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)))%((10**9)+7)
    ans=(ans*tmp)%((10**9)+7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

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

if M == 0:
    a = [-1 , N+1]
else :
    a = [-1] * (M+2)

    for i in range(1,M+1) :
        a[i] = int(input())

flag = True # 可能かどうか
for i in range(0,M+1) :
    if a[i] + 1 == a[i+1] :
        flag = False
        break

if flag :
    a[M+1] = N + 1

    ans = 1

    for i in range(M+1) :
        length = a[i+1] - a[i] - 2 # 上がる長さ
        max2step = math.floor(length / 2) # 2段の回数
        count = 1
        for j in range(1,max2step+1) :
            step2 = math.factorial(j)
            step1 = math.factorial(length-2*j)
            count += math.factorial(length - j) // step1 // step2
        ans *= count

    print(int(ans % 1000000007))
else :
    print(0)

Submission status: Time Limit Exceeded

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

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:
    
    num_goup = [1]
    for s in range(1, N + 1):
        if s in A:
            num_goup.append(0)
            continue
    
        if s == 1:
            num_goup.append(1)
            continue
    
        if num_goup[-1] == 0:
            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:
#ABC129C-TypicalStairs.py

#import list
from sys import stdin

input = stdin.readline

#constant
#N = int(input())
N, M = list(map(int,input().split()))
A = [int(input()) for _ in range(M)]+[N+1]

#variable

#function
def partition(two_steps,total_steps):
    if two_steps == 0:
        return 1
    elif two_steps == 1:
        return total_steps-1
    else:
        result = 0
        for i in range(total_steps-(2*(two_steps-1))):
            result += partition(two_steps-1,total_steps-(i+2))
        return result

def sectorSum(total_steps):
    if total_steps == 0:
        return 0
    result = 0
    max_two_steps = total_steps//2
    for two_steps in range(max_two_steps+1):
        result += partition(two_steps,total_steps)
    return result
#class

#main function
def main():
    totalResult = 1
    position = 0
    i = 0
    while position < N:
        a = A.pop(0)
        if position+1 == a:
            position = a+1
            if position == A[0]:
                totalResult = 0
                break
        else:
            totalResult = totalResult*sectorSum(a-1-position)
            position = a+1
    print(totalResult%1000000007)




if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

pat = [1]
zero = False
for i in range(1, n + 1):
    if i - 1 in a and i - 2 in a:
        zero = True
        break
    if i in a:
        pat.append(0)
        continue
    cnt = 0
    if i - 1 not in a:
        cnt += pat[i - 1] % mod
    if i - 2 >= 0 and i - 2 not in a:
        cnt += pat[i - 2] % mod
    pat.append(cnt % mod)

if zero:
    print(0)
else:
    print(pat[n])

Submission status: Time Limit Exceeded

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

# memo = [-1 for _ in range(n)]
step_now = 0
step_1   = 0
step_2   = 0
DIV_NUM = 1000000007
if 1 in a_list:
    step_now = 0
else:
    step_now = 1
for i in range(1, n):
    if i == 1:
        step_1 = step_now
        if i+1 in a_list:
            step_now = 0
        else:
#             memo[i] = (memo[0] + 1) % DIV_NUM
            step_now = step_1 + 1
    else:
        step_2 = step_1
        step_1 = step_now % DIV_NUM
        if i+1 in a_list:
            step_now = 0
        else:
#             memo[i] = (memo[i-1] + memo[i-2]) % DIV_NUM
            step_now = (step_1 + step_2) % DIV_NUM
    if step_now ==  step_1 == step_2 == 0:
        break

print(step_now)

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 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 math

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

if M == 0:
    a = [-1 , N+1]
else :
    a = [-1] * (M+2)

    for i in range(1,M+1) :
        a[i] = int(input())

flag = True # 可能かどうか
for i in range(0,M+1) :
    if a[i] + 1 == a[i+1] :
        flag = False
        break

if flag :
    a[M+1] = N + 1

    ans = 1

    for i in range(M+1) :
        length = a[i+1] - a[i] - 2 # 上がる長さ
        max2step = math.floor(length / 2) # 2段の回数
        count = 1
        for j in range(1,max2step+1) :
            if length - 2 * j < 0 :
                break
            step2 = math.factorial(j)
            step1 = math.factorial(int(length-2*j))
            count += math.factorial(length - j) // step1 // step2
        ans *= count

    print(int(ans % 1000000007))
else :
    print(0)

Submission status: Time Limit Exceeded

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

s = list(map(int, input().split()))
N = s[0]
M = s[1]
flag = 0

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


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

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


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

Submission status: Time Limit Exceeded

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

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 or ra == 1:
        continue
    else:
        aaa = 1
        for n in range(1, ra // 2 + 1):
            length = ra - (2 * n) + n
            aaa += math.factorial(length) // (math.factorial(length - n) * math.factorial(n))
        ans *= aaa

print(ans % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
import math

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

    d1 = fact_mamo[n-r]
    if d1 == -1:
        d1 = math.factorial(n-r)
        fact_mamo[n-r] = d1

    d2 = fact_mamo[r]
    if d2 == -1:
        d2 = math.factorial(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: 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
p_dict = dict()
for a in a_list:
    p = 0
    end_step = a - 1
    diff = end_step - start_step
    if diff in p_dict.keys():
        p = p_dict[diff]
    else:
        for x in range(diff // 2 + 1):
            p += math.factorial(diff - x) // math.factorial(x) // math.factorial(diff - 2 * x)
        p_dict[diff] = p
    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

prev=-1
cnt=1
for i in range(m+1):
    next=0

    if i==m:
        next=n+1
    else:
        next=int(input())

    steps=next-prev
    if steps<2:
        cnt= 0
    elif steps==2 or steps==3:
        None
    else:
        max=steps-2

        min=max//2+(1 if steps%2==1 else 0)
        sum=0
        for i in range(min,max+1):
            sum+=factorial(i) // (factorial(i*2 - max) * factorial(max-i))
        cnt*=sum%modn
    
    prev=next

print(cnt%modn)