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:
n,m = map(int,input().split())

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

dp = [0]*(n+1)
dp[0] = 1
if not 1 in list1: 
	dp[1] = 1 #i+2まで考えるため、初期設定はi = 1まで必要
for i in range(n-1):
	if i not in list1:
		dp[i+2] += dp[i]
	if i+1 not in list1:
		dp[i+2] += dp[i+1]

print(dp[n]%1000000007)

Submission status: Time Limit Exceeded

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

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

dp = [0]*(n+1)
dp[0] = 1
if not 1 in list1: 
	dp[1] = 1 #i+2まで考えるため、初期設定はi = 1まで必要
for i in range(n-1):
	if (i in list1)and (i+1 in list1):
		break
	if i in list1 :
		dp[i+2] = dp[i+1]
	elif i+1 in list1:
		dp[i+2] = dp[i]
	else:
		dp[i+2] = dp[i] + dp[i + 1]

print(dp[n]%1000000007)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
A = [int(input()) for _ in range(m)]
mod = 1000000007
dp = [0]*(n+1)
dp[0],dp[1] = 1,1
for i in range(2,n+1):
    if i in A:
        continue
    elif i-1 in A and i-2 in A:
        dp[n] = 0
        break
    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]

print(dp[n]%mod)

Submission status: Time Limit Exceeded

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


from operator import mul
from functools import reduce

def comb(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 stair_count(start,end):
    #print(start,end)
    aida = end - start
    total = 0
    i = aida
    #print("aida/2={}".format(aida/2))
    kazu = 0
    while i >= kazu:
        total += comb(i,kazu)
        kazu += 1
        i -= 1
    return total

start = 0
answer = 1
for i in a:
    #print("i={}".format(i))
        if i == start:
            print(0)
            exit()
        else:
            answer = (answer * stair_count(start, i-1))
            start = i+1
answer = (answer * stair_count(start, N))
    #print("answer={}".format(answer))
print(answer%1000000007)

Submission status: Time Limit Exceeded

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


from operator import mul
from functools import reduce

def comb(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 stair_count(start,end):
    #print(start,end)
    aida = end - start
    total = 0
    i = aida
    #print("aida/2={}".format(aida/2))
    kazu = 0
    while i >= kazu:
        total += comb(i,kazu)
        kazu += 1
        i -= 1
    return total

start = 0
answer = 1
for i in a:
    #print("i={}".format(i))
        if i == start:
            print(0)
            exit()
        else:
            answer = (answer * stair_count(start, i-1))
            start = i+1
answer = (answer * stair_count(start, N))
    #print("answer={}".format(answer))
print(answer%1000000007)

Submission status: Time Limit Exceeded

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


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

def stair_count(start,end):
    #print(start,end)
    aida = end - start
    total = 1
    i = aida-1
    #print("aida/2={}".format(aida/2))
    kazu = 1
    while (aida%2==0 and i >= (aida/2)) or (aida%2!=0 and i>(aida/2)):
        total += comb(i,kazu)
        kazu += 1
        i -= 1
    return total

start = 0
answer = 1
for i in a:
    #print("i={}".format(i))
        if i == start:
            print(0)
            exit()
        else:
            answer = (answer * stair_count(start, i-1))
            start = i+1
answer = (answer * stair_count(start, N))
    #print("answer={}".format(answer))
print(answer%1000000007)

Submission status: Time Limit Exceeded

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


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

def stair_count(start,end):
    #print(start,end)
    aida = end - start
    total = 1
    i = aida-1
    #print("aida/2={}".format(aida/2))
    kazu = 1
    while (aida%2==0 and i >= (aida/2)) or (aida%2!=0 and i>(aida/2)):
        total += comb(i,kazu)
        kazu += 1
        i -= 1
    return total

start = 0
answer = 1
for i in range(1,N):
    #print("i={}".format(i))
    if i in a:
        if i == start:
            print(0)
            exit()
        else:
            answer = (answer * stair_count(start, i-1))
            start = i+1
    elif i == N-1:
        answer = (answer * stair_count(start, N))
    else:
        continue
    #print("answer={}".format(answer))
print(answer%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=[1]
if 1 in a:
  dp.append(0)
else:
  dp.append(1)
for i in range(2,n+1):
  if i in a:
    dp.append(0)
  else:
    dp.append(dp[-2]+dp[-1])
print(dp[n]%1000000007)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
A=[int(input()) for _ 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:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10 ** 7)

MOD = 1000000007  # type: int


def solve(N: int, M: int, a: "List[int]"):
    lst = [0 for i in range(N + 2)]
    lst[1] = 1
    for i in range(2, N + 2):
        if i - 1 in a:
            lst[i] = 0
        else:
            lst[i] = lst[i - 1] + lst[i - 2]
            lst[i] %= MOD

    print(lst[N + 1])
    # print(lst)
    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools
# (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(M)]  # type: "List[int]"
    solve(N, M, a)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math

def move(n):
	twonum = n // 2
	com = 0
	for i in range(twonum + 1):
		up = n - i
		com += math.factorial(up) // (math.factorial(up - i) * math.factorial(i))
	return com

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

s = 1
for i in range(M+1):
	step = a[i+1] - a[i] - 1
	if step > 1000000007:
		step = step % 1000000007
	m = move(step)
	s = s * m
	a[i+1] += 1

print(s % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
MOD = 1000000007

fact = [0 for i in range(100001)] # fact[i] = i! mod MOD
inv_fact = [0 for i in range(100001)] # inv_fact[i] = i!のmod MODでの逆元
 
# aのn乗をPで割った余りを求めるよ
def mod_pow(a, n, P):
	if n == 0: # aの0乗は1（それはそう）
		return 1
	if n%2 == 0: # aの4乗は（aの2乗）の2乗、みたいなノリ
		x = mod_pow(a, n/2, P)
		return (x*x)%P
	# aの5乗はa×（aの4乗）、みたいなノリ
	return (a*mod_pow(a, n-1, P))%P
 
# nCk mod MODを求める！！
def comb(n, k):
	if n < k:
		return 0
	ans = fact[n]
	ans = (ans * inv_fact[k])%MOD
	ans = (ans * inv_fact[n-k])%MOD
	return ans

def move(n):
	twonum = n // 2
	com = 0
	for i in range(twonum + 1):
		up = n - i
		com += comb(up, i)
	return com

# fact,inv_factを初期化
fact[0] = inv_fact[0] = 1
for i in range(100000):
	# (i+1)!ってi!に(i+1)をかけたものだよね
	fact[i+1] = (fact[i]*(i+1))%MOD
	# (i+1)!の逆元って、i!の逆元に(i+1)の逆元をかけたものだよね
	inv_fact[i+1] = (inv_fact[i]*mod_pow(i+1, MOD-2, MOD))%MOD

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

s = 1
for i in range(M+1):
	step = a[i+1] - a[i] - 1
	if step > MOD:
		step = step % MOD
	m = move(step)
	s = (s * m) % MOD
	a[i+1] += 1

print(s)

Submission status: Time Limit Exceeded

Solution code:
import math

memo = dict()
def move(n):
    if n in memo:
        return memo[n]
    twonum = n // 2
    com = 0
    for i in range(twonum + 1):
        up = n - i
        com += math.factorial(up) // (math.factorial(up - i) * math.factorial(i))
    memo[n] = com
    return com

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

s = 1
for i in range(M+1):
	step = a[i+1] - a[i] - 1
	m = move(step)
	s = s * m
	a[i+1] += 1

print(s % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
import math

def move(n):
	twonum = n // 2
	com = 0
	for i in range(twonum + 1):
		up = n - i
		com += math.factorial(up) // (math.factorial(up - i) * math.factorial(i))
	return com

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

s = 1
for i in range(M+1):
	step = a[i+1] - a[i] - 1
	m = move(step)
	s = s * m % 1000000007
	a[i+1] += 1

print(s)

Submission status: Time Limit Exceeded

Solution code:
import math

def move(n):
	twonum = n // 2
	com = 0
	for i in range(twonum + 1):
		up = n - i
		com += math.factorial(up) // (math.factorial(up - i) * math.factorial(i))
	return com

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

s = 1
for i in range(M+1):
	step = a[i+1] - a[i] - 1
	m = move(step)
	s = s * m
	a[i+1] += 1

print(s % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
A=list(int(input()) for i in range(m))+[-1]
dp=[0]*(n+1)
dp[0]=1
for i in range(1,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())
A = []
for a in range(M):
	A.append(int(input()))
	
DP = [0] * (N + 1)	
DP[0] = 1

mod = (10 ** 9) + 7

for i in range(1,N+1):
	if i in A:
		DP[i] = 0
	else:
		DP[i] = DP[i-1] + DP[i-2]

print(DP[N] % (mod))

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
dp[1] = 1
for i in a:
    dp[i] = 0
for i in range(2, n+1):
    if i not in a:
        dp[i] = (dp[i-1] + dp[i-2]) % 1000000007
print(dp[n])

Submission status: Time Limit Exceeded

Solution code:
def main():
  N,M = map(int,input().split())
  a = [int(input()) for i in range(M)]
  m = 10**9+7

  dp = [0]*(N+1)
  dp[0] = 1
  if 1 not in a:
    dp[1] = 1
  for i in range(2,N+1):
    if i not in a:
      dp[i] = dp[i-1] + dp[i-2]
      dp[i] %= m
  print(dp[-1])

if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

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

dp = [0]*(N+1)
dp[0] = 1
if 1 not in a:
	dp[1] = 1
for i in range(2,N+1):
    if i not in a:
    	dp[i] = dp[i-1] + dp[i-2]
    	dp[i] %= m
print(dp[-1])

Submission status: Time Limit Exceeded

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

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):
    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())
a = [int(input()) for i in range(m)]

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

for i in range( 1, 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:
N,M=map(int,input().split())
A=[int(input()) for i in range(M)]
m=10**9+7
b=0
ans=[0,1]
for i in range(1,N+1):
    if (i in A) and (i+1 in A):
        print(0)
        exit()
    if i in A:
        ans.append(0)
    else:
        ans.append(ans[-1]+ans[-2])

print(ans[-1] % m)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

dp = [INIT for i in range(n + 1)]
dp[0] = 1

for i in range(1, n + 1):
    if (i in a):
        dp[i] = 0
    elif (i <= 1):
        dp[i] = dp[i - 1]
    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())

# 壊れている階段
a = []
for i in range(m):
    a.append(int(input()))

# DPテーブル初期化値
INIT = 0
# DPテーブル(dp[i]：i番目の段に到達する移動方法の総数)
dp = [INIT for i in range(n + 1)]

# 0番目の段に到達するための移動方法は1通り
dp[0] = 1

# dp[1]～dp[n]までループ
for i in range(1, n + 1):
    # 階段が壊れている場合、到達できないので0通り
    if (i in a):
        dp[i] = 0
    # i = 1の場合、0番目の段から1つ飛びで来るパターンしかない
    elif (i <= 1):
        dp[i] = dp[i - 1]
    # それ以外の場合、1つ飛びパターンと2つ飛びパターンの合計
    else:
        dp[i] = dp[i - 1] + dp[i - 2]

# 最終地点のDPテーブルの値を1000000007で割った余りが答えとなる
print(dp[n] % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
l=[0]*m
for i in range(m):
    l[i]=int(input())
#print(l)
dp=[0]*(n+1)
dp[0]=1
for j in range(1,n+1):
    if j not in l:
        dp[j]=-1
#print(dp)
if dp[1]==-1:dp[1]=1
for i in range(2,n+1):
    if dp[i]==-1:
        dp[i]=(dp[i-1]+dp[i-2])%1000000007
print(dp[-1]%1000000007)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
l=[]
for _ in range(m):
    l.append(int(input()))
#print(l)
dp=[0]*(n+1)
dp[0]=1
if 1 not in l:
    dp[1]=1

for i in range(2,n+1):
    if i in l:
        dp[i]=0
    else:
        dp[i]=dp[i-1]+dp[i-2]
print(dp[-1]%1000000007)

Submission status: Time Limit Exceeded

Solution code:
import sys
imput=sys.stdin.readline
n,m=map(int,input().split())
l=[]
for _ in range(m):
    l.append(int(input()))
#print(l)
dp=[0]*(n+1)
dp[0]=1
if 1 not in l:
    dp[1]=1
 
for i in range(2,n+1):
    if i in l:
        dp[i]=0
    else:
        dp[i]=(dp[i-1]+dp[i-2])%(1000000007)
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
imput=sys.stdin.readline
n,m=map(int,input().split())
l=[]
for _ in range(m):
    l.append(int(input()))
#print(l)
dp=[0]*(n+1)
dp[0]=1
if 1 not in l:
    dp[1]=1
 
for i in range(2,n+1):
    if i in l:
        dp[i]=0
    else:
        dp[i]=(dp[i-1]+dp[i-2])%(10**9+7)
print(dp[-1]%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import sys
imput=sys.stdin.readline
n,m=map(int,input().split())
l=[int(input()) for i in range(m)]
#print(l)
dp=[0]*(n+1)
dp[0]=1
if 1 not in l:
    dp[1]=1
else:dp[1]=0 
for i in range(2,n+1):
    if i in l:
        dp[i]=0
    else:
        dp[i]=(dp[i-1]+dp[i-2])
print(dp[-1]%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import sys
imput=sys.stdin.readline
n,m=map(int,input().split())
l=[int(input()) for i in range(m)]
#print(l)
dp=[0]*(n+1)
dp[0]=1
if 1 not in l:
    dp[1]=1
else:dp[1]=0 
for i in range(2,n+1):
    if i in l:
        dp[i]=0
    else:
        dp[i]=(dp[i-1]%(10**9+7)+dp[i-2]%(10**9+7))%(10**9+7)
print(dp[-1]%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import sys
imput=sys.stdin.readline
n,m=map(int,input().split())
l=[int(input()) for i in range(m)]
#print(l)
dp=[0]*(n+1)
dp[0]=1
if 1 not in l:
    dp[1]=1
else:dp[1]=0 
for i in range(2,n+1):
    if i in l:
        dp[i]=0
    else:
        dp[i]=(dp[i-1]+dp[i-2])%(10**9+7)
print(dp[-1]%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import sys
imput=sys.stdin.readline
n,m=map(int,input().split())
l=[int(input()) for i in range(m)]
dp=[0]*(n+1)
dp[0]=1
if 1 not in l:
    dp[1]=1
else:dp[1]=0 
for i in range(2,n+1):
    if i in l:
        dp[i]=0
    else:
        dp[i]=pow(dp[i-1]+dp[i-2],1,10**9+7)
print(dp[-1]%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int,input().split())
data = []
for i in range(M):
    data.append(int(input()))
dp = [0] * (N + 1)
dp[0] = 1
dp[1] = 1
if 1 in data:
    dp[1] = 0
mod = 10**9 + 7
for i in range(2,N + 1):
    if not i in data:
        dp[i] = dp[i - 1] + dp[i - 2]
print(dp[N] % mod)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int,input().split())
data = []
for i in range(M):
    data.append(int(input()))
dp = [0] * (N + 2)
dp[0] = 1
mod = 10**9 + 7
for i in range(N):
    if not i + 1 in data:
        dp[i + 1] += dp[i]
    if not i + 2 in data:
        dp[i + 2] += dp[i]
print(dp[N] % mod)

Submission status: Time Limit Exceeded

Solution code:
n,m=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 in a:
        b[i]=0 
    else:
        b[i]=b[i-1]+b[i-2]
print(b[-1]%1000000007)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(20000000)

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


def forward(steps):
    global cnt
    if steps > n:
        return
    if steps == n:
        cnt += 1
        return
    elif steps in A:
        return

    forward(steps + 1)
    forward(steps + 2)


forward(0)
print(cnt % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
BASE =  1000000007

class Route(object):
    def __init__(self):
        self.counter = [1]

    def getCounter(self, idx):
        if idx == -1:
            return 0
        try:
            return self.counter[idx]
        except IndexError:
            return 0

    def getList(self):
        return self.counter

    def append(self, elem):
        self.counter.append(elem)

if __name__ == '__main__':
    N, M = [int(i) for i in input().split()]
    not_available = []
    for i in range(M):
        not_available.append(int(input()))
    route_counter = Route()
    for idx in range(1, N + 1):
        if idx in not_available:
            route_counter.append(0)
            continue
        route_counter.append(route_counter.getCounter(idx - 1) + route_counter.getCounter(idx - 2))
    print(route_counter.getCounter(N) % BASE)

Submission status: Time Limit Exceeded

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

mod=10**9+7

if N==1:
    print(1)
    exit()

f=[0]*(N+1)

if 0 in a:
    f[0]=0
else:
    f[0]=1

if 1 in a:
    f[1]=0
else:
    f[1]=f[0]+1

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

    f[i]=f[i]%mod

print(f[N-1])

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
a = [ int(input()) for _ in range(m) ]
dp = [0]*n
for i in range(n):
  if not i+1 in a:
    if i == 0:
      dp[i] = 1
    elif i == 1:
      dp[i] = 1 + dp[i-1]
    else:
      dp[i] = dp[i-2] + dp[i-1]
  if dp[i] >= 1000000007:
    dp[i] %= 1000000007
print(dp[n-1]%1000000007)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

dp = [0 for i in range(n+2)]
dp[0] = 1

for i in range(n):
    if i+2 not in a:
        dp[i+2] = dp[i]%p
    if i+1 not in a:
        dp[i+1] += dp[i]%p

print(dp[-2]%p)

Submission status: Time Limit Exceeded

Solution code:
##
p = 10**9 + 7
n,m = list(map(int, input().split()))
a = [int(input()) for _ in range(m)]

dp = [0 for i in range(n+2)]
dp[0] = 1

for i in range(n):
    if i+2 not in a:
        dp[i+2] += dp[i]
    if i+1 not in a:
        dp[i+1] += dp[i]

print(dp[-2]%p)

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
A=[int(input()) for _ in range(M)]
n1,n2=0,1
for i in range(1,N+1):
    if i in A:
        n1=n2
        n2=0
    else:
        tmp=n2
        n2=(n1+n2)%1000000007
        n1=tmp
print(n2)

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()))
    if A[i] - 1 == A[i - 1] and i > 0:
        print("0")
        exit()
dp = [0] * (N + 1)
dp[0] = 1
for i in range(1 , N + 1):
    if i in A:
        continue
    else:
        if i == 1:
            dp[1] = 1
        else:
            dp[i] = dp[i - 1] + dp[i - 2]
            dp[i] %= mod
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
import sys,queue,copy
sys.setrecursionlimit(10**8)
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
INF = float('inf')

N,M = inpl()

alist = list()
for _ in range(M):
    alist.append(int(input()))

dp = [0]*(N+1)
dp[0] = 1
if 1 not in alist:
    dp[1] = 1
for i in range(2,N+1):
    if i <= N and i not in alist:
        dp[i] += dp[i-1] + dp[i-2]

print(dp[N]%1000000007)

Submission status: Time Limit Exceeded

Solution code:
import sys,queue,copy
sys.setrecursionlimit(10**8)
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
INF = float('inf')

N,M = inpl()

alist = list()
for _ in range(M):
    alist.append(int(input()))

dp = [0]*(N+1)

for i in range(N+1):
    if i <= N and i not in alist:
        if i == 0 :
            dp[i] = 1
        elif i < 2:
            dp[i] += dp[i-1]
        elif i <= N:
            dp[i] += dp[i-1]
            dp[i] += dp[i-2]


print(dp[N]%1000000007)

Submission status: Time Limit Exceeded

Solution code:
p=10**9+7
N,M=map(int,input().split())
a=[]
for i in range(M):
    a.append(int(input()))
x=[0 for i in range(N+1)]
x[0]=1
if 1 in a:
    x[1]=0
else:
    x[1]=x[0]
for i in range(2,N+1):
    x[i]=((x[i-1] if i-1 not in a else 0)+(x[i-2] if i-2 not in a else 0))%p

print(x[N])

Submission status: Time Limit Exceeded

Solution code:
def main():

    N, M = map(int, input().split())
    A = [int(input()) for _ in range(M)]
    stairs = [0] * N
    for i in range(N):
        if (i + 1) in A:
            stairs[i] = 0
        elif i == 0:
            stairs[i] = 1
        elif i == 1:
            stairs[i] = 1 + stairs[i - 1]
        else:
            stairs[i] = (stairs[i - 1] + stairs[i - 2]) % (10 ** 9 + 7)
    print(stairs[N - 1])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

#コンビネーションnCrを求める
def combination(n, r):
        return math.factorial(n)//(math.factorial(n - r) * math.factorial(r))

def keisan(a,b):
    count = 0
    n = b - a - 2
    r = 0

    while n >= r:

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

    return count

result = 1

if M == 0:
    result *= keisan(-1,N+1)
    print(int(result)%1000000007)
    sys.exit()

for i in range(M):

    if i == 0:
        result *= keisan(-1,a[0])
        continue

    #階段の段が連続して壊れている場合は登れない
    if a[i] - a[i-1] == 1:
        result = 0
        break
    else:
        result *= keisan(a[i-1],a[i])


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

print(int(result)%1000000007)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
n, m = map(int, input().split())
a = []
ans = [0 for _ in range(n)]
for i in range(m):
    a.append(int(input()))
for i in range(m-1):
    if a[i+1]-a[i] == 1:
        print(0)
        sys.exit()
for i in range(n):
    if i+1 in a:
        ans[i] = 0
    else:
        if i == 0:
            ans[i] = 1
        elif i == 1:
            ans[i] = 1+ans[i-1]
        else:
            ans[i] = ans[i-1]+ans[i-2]
print(ans[-1]%(10**9+7))

Submission status: Time Limit Exceeded

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

#通過できない階段をaに格納\n",
a = [int(input()) for _ in range(m)]
count = [0 for _ in range(n+1)]
count[0] = 1
for i in range(1,n+1):
    if i in a:
        continue
    count[i] = (count[i-1]+count[i-2])%(10**9+7)
print(count[-1])

Submission status: Time Limit Exceeded

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

#通過できない階段をaに格納\n",
a = [int(input()) for _ in range(m)]
count = [0 for _ in range(n+1)]
count[0] = 1
for i in range(1,n+1):
    if i not in a:
        count[i] = (count[i-1]+count[i-2])%(10**9+7)
print(count[-1])

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
dp = [0] * (N+2)
dp[1] = 1
e = 1e9 + 7
for i in range(2, N+2):
    if i-1 not in A:
        dp[i] = (dp[i-1] + dp[i-2]) % e
print(int(dp[-1]))

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
dp = [0] * (N+1)
dp[0] = 1
e = 1e9 + 7
for i in range(1, N+1):
    if i not in A:
        if i == 1:
            dp[i] = 1
            continue
        else:
            dp[i] = (dp[i-1] + dp[i-2]) % e
print(int(dp[N]))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

def dp(n):
  lst=[None]*(n+1)
  if len(lst)==1:
    lst[0]=1
  else:
    if 1 not in broken:
      lst[0],lst[1]=1,1
    else:
      lst[0],lst[1]=1,0
  if n<=1:
    return lst[n]
  else:
    for i in range(2,n+1):
      if i not in broken:
        lst[i]=lst[i-1]+lst[i-2]
      else:
        lst[i]=0
    return lst[n]
  
def count(A,B):
  ans=0
  if A==B or B-A==1:
    return 1
  elif B<A:
    return 0
  if (A%2==0 and B%2==0) or (A%2==1 and B%2==1):
    for i in range((B-A)//2+1):
      n=B-A-2*i+i
      ans+=math.factorial(n)//math.factorial(i)//math.factorial(n-i)
    return ans
  else:
    return count(A+1,B)+count(A+2,B)

if M!=0:
  V=1
  for i in range(M):
    if i==0:
      V*=count(0,broken[i]-1)
    else:
      V*=count(broken[i-1]+1,broken[i]-1)
  V*=count(broken[-1]+1,N)
  print(V%(10**9+7))
else:
  print(dp(N)%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
broken=[]
for i in range(M):
  broken.append(int(input()))
def dp(n):
  lst=[None]*(n+1)
  if len(lst)==1:
    lst[0]=1
  else:
    if 1 not in broken:
      lst[0],lst[1]=1,1
    else:
      lst[0],lst[1]=1,0
  if n<=1:
    return lst[n]
  else:
    for i in range(2,n+1):
      if i not in broken:
        lst[i]=lst[i-1]+lst[i-2]
      else:
        lst[i]=0
    return lst[n]
print(dp(N)%(10**9+7))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
mod=10**9+7

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

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

for i in range(1,n+1):
    if i in a:
        continue
    x=dp[i-1]
    if i>1:
        x+=dp[i-2]
    dp[i]=x%mod
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
import math
N,M=map(int,input().split())
broken=[]
for i in range(M):
  broken.append(int(input()))
def count(A,B):
  ans=0
  if A==B or B-A==1:
    return 1
  elif B<A:
    return 0
  if (A%2==0 and B%2==0) or (A%2==1 and B%2==1):
    for i in range((B-A)//2+1):
      n=B-A-2*i+i
      ans+=math.factorial(n)//math.factorial(i)//math.factorial(n-i)
    return ans
  else:
    return count(A+1,B)+count(A+2,B)
if M!=0:
  V=1
  for i in range(M):
    if i==0:
      V*=count(0,broken[i]-1)
    else:
      V*=count(broken[i-1]+1,broken[i]-1)
  V*=count(broken[-1]+1,N)
  print(V%(10**9+7))
else:
  print(count(0,N)%(10**9+7))

Submission status: Time Limit Exceeded

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


MOD = 1000000007

dp = [0 for _ in range(N + 1)]

dp[0] = 1

for index in range(N):
    current = index + 1
    if current in A:
        continue

    pre_stair = current - 1
    dp[current] += dp[pre_stair]

    prepre_stair = current -2
    if prepre_stair >= 0:
        dp[current] += dp[prepre_stair]

    dp[current] %= MOD

print(dp[-1]%MOD)