Problem:


Score : 300 points

Problem Statement

There is a staircase with N steps. Takahashi is now standing at the foot of the stairs, that is, on the 0-th step.
He can climb up one or two steps at a time.

However, the treads of the a_1-th, a_2-th, a_3-th, \ldots, a_M-th steps are broken, so it is dangerous to set foot on those steps.

How many are there to climb up to the top step, that is, the N-th step, without setting foot on the broken steps?
Find the count modulo 1\ 000\ 000\ 007.

Constraints

1 \leq N \leq 10^5

0 \leq M \leq N-1

1 \leq a_1 < a_2 <  ...  < a_M \leq N-1

Input

Input is given from Standard Input in the following format:

N M
a_1
a_2
 .
 .
 .
a_M

Output

Print the number of ways to climb up the stairs under the condition, modulo 1\ 000\ 000\ 007.

Sample Input 1

6 1
3

Sample Output 1

4

There are four ways to climb up the stairs, as follows:

0 \to 1 \to 2 \to 4 \to 5 \to 6

0 \to 1 \to 2 \to 4 \to 6

0 \to 2 \to 4 \to 5 \to 6

0 \to 2 \to 4 \to 6

Sample Input 2

10 2
4
5

Sample Output 2

0

There may be no way to climb up the stairs without setting foot on the broken steps.

Sample Input 3

100 5
1
23
45
67
89

Sample Output 3

608200469

Be sure to print the count modulo 1\ 000\ 000\ 007.



Sample input:
6 1
3


Sample output:
4

Submission status: Time Limit Exceeded

Solution code:
import sys
n, m = map(int, input().split())
a = [int(sys.stdin.readline()) for _ in range(m)]
mod = 1000000007
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = dp[0] if not 1 in a else 0
for i in range(2, n + 1):
    if not i in a:
        dp[i] = (dp[i - 1] + dp[i - 2]) % mod
    else:
        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)]

wa = (10**9) + 7

#dpを使う

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

print(dp[N]%wa)

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:
n,m=map(int,input().split())
a=[]
for i in range(m):
	a.append(int(input()))

num=[1,1,2]


mod=1000000007

count=0
jud=1
ans=1
for i in range(n+1):
	
	if i>2:
		num.append(1)
		num[i]=(num[i-1]+num[i-2])%mod

	if(jud==0 and i in a):
		print("0")
		break
	elif i in a:
		
		ans=(ans%mod)*(num[count-1]%mod)
		count=0
		jud=0
	elif(i==n):
		count+=1
		ans=(ans%mod)*(num[count-1]%mod)
		
		print(ans%mod)
	else:
		jud=1
		count+=1

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

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split(" "))
a=[-100] * m
ans = 1
for i in range(m):
    a[i] = 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 % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
n, m = list(map(int, input().split() ))
broken = [int(input()) for _ in range(m)]

mod = 10**9+7

num_way = [0] * (n+1)
num_way[0] = 1
if 1 in broken:
	num_way[1] = 0
else:
	num_way[1] = 1

for i in range(2, (n+1)):
	if i in broken:
		num_way[i] = 0
	else:
		num_way[i] = (num_way[i-1] + num_way[i-2]) % mod

print (num_way[n])

Submission status: Time Limit Exceeded

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

dp = [0] * (n+1)
for j in range(n+1):
    if j in a:
        dp[j] = 0
    elif j == 1 or j == 0:
        dp[j] = 1
    else:
        dp[j] = (dp[j-1] + dp[j-2]) % mod

print(dp[n])

Submission status: Time Limit Exceeded

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

dp = [0] * (n+1)
for j in range(n+1):
    if j in a:
        dp[j] = 0
    elif j > 1:
        dp[j] = (dp[j-1] + dp[j-2]) % mod
    else:
        dp[j] = 1

print(dp[n])

Submission status: Time Limit Exceeded

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

for _ in range(M):
  a.append(input())

S = [0] * (N+1)
S[0] = 1
for n in range(1, N+1):
    if str(n) in a:
        S[n] = 0
    elif n==1:
        S[n] = 1
    else:
        S[n] = (S[n-1] + S[n-2])%1000000007

print(S[n])

Submission status: Time Limit Exceeded

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

for _ in range(M):
  a.append(input())

S = [0] * (N+1)
S[0] = 1
for n in range(1, N+1):
    if str(n) in a:
        S[n] = 0
    elif n==1:
        S[n] = 1
    else:
        S[n] = S[n-1] + S[n-2]

print(S[n] % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
N, M = tuple(map(int, input().split()))
mod = 10**9+7
broken = [int(input()) for _ in range(M)]
dp = [0]* (N+1)


dp[0] = 1

for i in range(1, N+1):
    if (i in broken):
        continue
    if (i == 1):
        dp[i] = 1
        continue
    dp[i] = (dp[i-1] + dp[i-2]) % mod

print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
N, M = tuple(map(int, input().split()))
mod = 10**9+7
broken = []
dp = [0]* (N+1)

for i in range(M):
    broken.append(int(input()))

dp[0] = 1

for i in range(1, N+1):
    if (i in broken):
        continue
    if (i == 1):
        dp[i] = 1
        continue
    dp[i] = (dp[i-1] + dp[i-2]) % mod

print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
N, M = tuple(map(int, input().split()))
mod = 10**9+7
broken = []
dp = []

for i in range(M):
    broken.append(int(input()))

for i in range(N+1):
    dp.append(0)

dp[0] = 1

for i in range(1, N+1):
    if (i in broken):
        continue
    if (i == 1):
        dp[i] = 1
        continue
    dp[i] = (dp[i-1] + dp[i-2]) % mod

print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
N, M = tuple(map(int, input().split()))
mod = 10**9+7
broken = []
dp = []

for i in range(M):
    broken.append(int(input()))

for i in range(N+2):
    dp.append(0)

dp[N] = 1

for i in reversed(range(N)):
    if (i in broken):
        continue
    dp[i] = (dp[i+1] + dp[i+2]) % mod

print(dp[0])

Submission status: Time Limit Exceeded

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


s = [0] * (n + 1)
s[0] = 1
for i in range(n):
    j = i + 1
    while(j <= min(n, i + 2)):
        if j not in a:
            s[j] += s[i]
            s[j] = int(s[j] % 1000000007)
        j += 1

print(s[n])

Submission status: Time Limit Exceeded

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

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

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

print(l[-1])

Submission status: Time Limit Exceeded

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

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

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

print(l[-1])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

for _ in range(M):
  a.append(input())

S = [0] * (N+1)
for n in range(N+1):
    if str(n) in a:
        S[n] = 0
    elif n<=1:
        S[n] = 1
    else:
        S[n] = S[n-1] + S[n-2]

print(S[n] % 1000000007)

Submission status: Time Limit Exceeded

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

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

for i in range(2, n+1):
  if i in a:
    if l[i-1] == 0:
      print(0)
      exit()
    else:
      l.append(0)
  else:
    l.append((l[i-2] + l[i-1]) % mod)
print(l[-1])

Submission status: Time Limit Exceeded

Solution code:

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

# DP
dp = [0] * (N + 1)
dp[0] = 1
dp[1] = 1 if 1 not in AL else 0
divisor = 10 ** 9 + 7

for i in range(2, N + 1):
    if i in AL:
        continue
    dp[i] = (dp[i-1] + dp[i-2]) % divisor
print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
def main(N, M, a_list):
    div = 10**9 + 7
    
    dp = {}
    dp[0] = 1
    if 1 in a_list:
        dp[1] = 0
    else:
        dp[1] = 1

    for i in range(N):
        if i+2 in a_list:
            dp[i+2] = 0
        else:
            dp[i+2] = (dp[i+1] + dp[i])
    
    print(dp[N] % div)


if __name__ == "__main__":
    N, M = [int(x) for x in input().split()]
    a_list = []
    for _ in range(M):
        a_list.append(int(input()))

    main(N, M, a_list)

Submission status: Time Limit Exceeded

Solution code:
def main(N, M, a_list):
    div = 10**9 + 7
    
    dp = {}
    dp[0] = 1
    if 1 in a_list:
        dp[1] = 0
    else:
        dp[1] = 1

    for i in range(N):
        if i+2 in a_list:
            dp[i+2] = 0
        else:
            dp[i+2] = (dp[i+1] + dp[i]) % div
    
    print(dp[N] % div)


if __name__ == "__main__":
    N, M = [int(x) for x in input().split()]
    a_list = []
    for _ in range(M):
        a_list.append(int(input()))

    main(N, M, a_list)

Submission status: Time Limit Exceeded

Solution code:
N, M = list(map(int, input().split()))
alist = []
for m in range(M) :
    alist.append(int(input()))
    
a2 = 0
a1 = 1
for n in range(N) :
    a0 = (a1 + a2)*int((n+1) not in alist)%1000000007
    a2, a1 = a1, a0
else :
    print(a0)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
import sys
sys.setrecursionlimit(10**6)

def main(N, M, a_list):
    div = 10**9 + 7
    @lru_cache(maxsize=None)
    def fib(n):
        if n in a_list:
            return 0
        else:
            if n == -1:
                return 0
            elif n == 0 or n == 1:
                return 1
            else:
                return fib(n-2) % div + fib(n-1) % div
    
    
    print(fib(N) % div )


if __name__ == "__main__":
    N, M = [int(x) for x in input().split()]
    a_list = []
    for _ in range(M):
        a_list.append(int(input()))

    main(N, M, a_list)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
import sys
sys.setrecursionlimit(10**6)

def main(N, M, a_list):
    div = 10**9 + 7
    @lru_cache(maxsize=None)
    def fib(n):
        if n in a_list:
            return 0
        else:
            if n == -1:
                return 0
            elif n == 0 or n == 1:
                return 1
            else:
                return fib(n-1) % div + fib(n-2) % div
    
    
    print(fib(N) % div )


if __name__ == "__main__":
    N, M = [int(x) for x in input().split()]
    a_list = []
    for _ in range(M):
        a_list.append(int(input()))

    main(N, M, a_list)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(200000)

N, M = list(map(int, input().split()))
alist = []
for m in range(M) :
    alist.append(int(input()))

def stairs(n, a1, a2) :
    a0 = (a1 + a2)*int(n not in alist)%1000000007
    if n == N :
        return a0
    else :
        return stairs(n+1, a0, a1)
      
print(stairs(1, 1, 0))

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7

n,m = (int(x) for x in input().split())
a = [0]*m
for i in range(m):
    a[i] = int(input())

#動的計画法？　加算の仕方はフィボナッチ数列みたいな考え方
total = [0]*(n+1)
total[0] += 1
#床が抜けているところは０で埋める
if 1 not in a:
    total[1] += 1
for i in range(2,n+1):
    if i not in a:
        total[i] += total[i-1] + total[i-2]

print(total[-1] % MOD)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7

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

#動的計画法？　加算の仕方はフィボナッチ数列みたいな考え方
total = [1]
if 1 not in a:
    total.append(1)
else:
    total.append(0)
#床が抜けているところは０をtotalにpushする
for i in range(2,n+1):
    if i not in a:
        total.append(total[i-1]+total[i-2])
    else:
        total.append(0)

print(total[-1] % 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)
if 0 in a:
    dp[0] =0
else:
    dp[0]=1

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

for i in range(2,n+1):

    if dp[i-1]==dp[i-2]==0:break

    dp[i] = (dp[i-2]+dp[i-1])

    if i in a:
        dp[i] = 0

print(dp[-1]%1000000007)

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

dp =[0]*(n+1)


for i in range(n+1):
    if i<=1:
        dp[i]=1
    else:
        if dp[i-1]==dp[i-2]==0:break
        dp[i] = (dp[i-2]+dp[i-1])
    if i in a:
        dp[i] = 0

print(dp[-1]%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)


for i in range(n+1):
    if i<=1:
        dp[i]=1
    else:
        dp[i] = (dp[i-2]+dp[i-1])
    if i in a:
        dp[i] = 0

print(dp[-1]%1000000007)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

tmp = deque([0])

res = 0
while True:
    if tmp:
        now = tmp.popleft()
        
        if now + 1 <= N:
            
            if now + 1 == N:
                res += 1
                
            elif now + 1 in A:
                pass
            
            else:
                tmp.append(now + 1)
                
            
        if now + 2 <= N:
            
            if now + 2 == N:
                res += 1
                
            elif now + 2 in A:
                pass
            
            else:
                tmp.append(now + 2)
            
    else:
        break
            
print(res%(10 ** 9 + 7))

Submission status: Time Limit Exceeded

Solution code:
import queue




N,M = map(int,input().split(" "))
A = queue.Queue()

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

oneBreak = False
for m in range(M):
    inp = int(input())
    if inp == 1:
        oneBreak = True
    else:
        A.put(inp)


DP = [0] * (N+1)

DP[0] = 1

if(oneBreak):
    DP[1] = 0
else:
    DP[1] = 1
#壊れている階段の時は判定をスキップ（DPテーブルは0のまま）

if(M != 0):
    nowA = A.get()
    for n in range(2,N + 1):
        if(nowA == n):
            if(not A.empty()):
                nowA = A.get()
            else:
                nowA = -1
        else:
            DP[n]  = (DP[n-1] + DP[n-2])

else:
    for n in range(2,N+1):
        DP[n] = DP[n-1] + DP[n-2]


print(DP[n]%1000000007)

Submission status: Time Limit Exceeded

Solution code:
import functools
import operator

n, m = list(map(int, input().split()))
a = [input() for i in range(m)]
total_act = 0
total_act2 = 1
total = []
for i in range(n + 1):
    if str(i) not in a:
        total_act3 = total_act2 + total_act
        total_act2 = total_act
        total_act = total_act3
    else:
        total.append(total_act)
        total_act = 0
        total_act2 = 1
total.append(total_act)
result = functools.reduce(operator.mul, total)
print(result % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
n, m = list(map(int, input().split()))
a = [input() for i in range(m)]
total_act = 0
total_act2 = 1
total = 1
for i in range(n + 1):
    if str(i) not in a:
        total_act3 = total_act2 + total_act
        total_act2 = total_act
        total_act = total_act3
    else:
        total *= total_act
        total_act = 0
        total_act2 = 1
total *= total_act
print(total % 1000000007)

Submission status: Time Limit Exceeded

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

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

memo = [0]*(n+1)
memo[0]=1
if not(1 in a):
    memo[1]=1

for i in range(2,n+1):
    #print(i)
    if i in a:
        continue
    #print(memo[i-1],memo[i-2])
    memo[i]=memo[i-2]+memo[i-1]
            

#print(memo)
print(memo[n]% 1000000007)

Submission status: Time Limit Exceeded

Solution code:
n, m = list(map(int, input().split()))
a = [input() for i in range(m)]
total_act = 0
total_act2 = 1
total = 1
for i in range(n + 1):
    if str(i) in a:
        total = (total_act * total) % 1000000007
        total_act = 0
        total_act2 = 1
    else:
        total_act3 = total_act2 + total_act
        total_act2 = total_act
        total_act = total_act3
total = (total_act * total) % 1000000007
print(total)

Submission status: Time Limit Exceeded

Solution code:
n, m = list(map(int, input().split()))
a = [input() for i in range(m)]
total_act = 0
total_act2 = 1
total = 1
for i in range(n + 1):
    if str(i) in a:
        total *= total_act
        total_act = 0
        total_act2 = 1
    else:
        total_act3 = total_act2 + total_act
        total_act2 = total_act
        total_act = total_act3
total *= total_act
print(total%1000000007)

Submission status: Time Limit Exceeded

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

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

memo = [0]*(n+1)
memo[0]=1
if not(1 in a):
    memo[1]=1

for i in range(2,n+1):
    #print(i)
    if i in a:
        continue
    #print(memo[i-1],memo[i-2])
    memo[i]=memo[i-2]+memo[i-1]
            

#print(memo)
print(memo[n]% 1000000007)

Submission status: Time Limit Exceeded

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

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

memo = {0:1}

for i in range(n):
    for j in range(i+1,min(i+2,n)+1):
        if j in a:
            continue
        if memo.get(i) is None:
            memo[i]=0
        if memo.get(j) is None:
            memo[j]=memo[i]
        else:
            memo[j]+=memo[i]
            


print(memo[n] % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6) 
N, M = map(int, input().split())
is_stairs = [1] * (N)

for i in range(M):
    a = int(input())
    is_stairs[a-1] = 0

memo = [0] * (N)
def routes(n):
    if n == 1:
        if is_stairs[0]:
            return 1
        else:
            return 0
    elif n == 2:
        if is_stairs[0] and is_stairs[1]:
            return 2
        elif not is_stairs[0] and is_stairs[1]:
            return 1
        else:
            return 0
    else:
        if memo[n-1]:
            return memo[n-1] % 1000000007
        else:
            if is_stairs[n-1]:
                memo[n-1] = routes(n-1) + routes(n-2)
                return memo[n-1] % 1000000007
            else:
                return 0

total = routes(N)
print(total)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6) 
N, M = map(int, input().split())
is_stairs = [1] * (N)

for i in range(M):
    a = int(input())
    is_stairs[a-1] = 0

memo = [0] * (N)
def routes(n):
    if n == 1:
        if is_stairs[0]:
            return 1
        else:
            return 0
    elif n == 2:
        if is_stairs[0] and is_stairs[1]:
            return 2
        elif not is_stairs[0] and is_stairs[1]:
            return 1
        else:
            return 0
    else:
        if memo[n-1]:
            return memo[n-1]
        else:
            if is_stairs[n-1]:
                memo[n-1] = routes(n-1) + routes(n-2)
                return memo[n-1]
            else:
                return 0

total = routes(N)
print(total % 1000000007)

Submission status: Time Limit Exceeded

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

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

a_list = []

for index in range(m):
    a_list.append(int(input()))

ans_list = []

ans_list = [0] * (n + 1)

for index in range(n + 1):
    if index == 0:
        ans_list[index] += 1
        continue
    if index == 1 and (index not in a_list):
        ans_list[index] += ans_list[index - 1]
        continue

    if index not in a_list:
        if (index - 1) not in a_list:
            ans_list[index] += ans_list[index - 1]
            ans_list[index] %= 1000000007
        if (index - 2) not in a_list:
            ans_list[index] += ans_list[index - 2]
            ans_list[index] %= 1000000007

print(ans_list[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
dp[1]=0 if 1 in a else 1
mod=10**9+7

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

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=[1]*(N+1)
dp[0]=1
dp[1]=1

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

print(dp[N])

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

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

step0 = 1
step1 = 0 if (1 in a) else 1

ans = [step0, step1]
for i in range(2, N+1):
    ans.append(0 if i in a else ans[-1] + ans[-2])
print(ans[-1] % 1000000007)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

step0 = 1
step1 = 0 if (1 in a) else 1

ans = [step0, step1]
for i in range(2, N+1):
    if i in a:
        now = 0
    else:
        now = ans[-1] + ans[-2]
    ans.append(now)
print(ans[-1] % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, M = map(int, input().split())
a_l = []
for _ in range(M):
    a_in = int(input())
    a_l.append(a_in)
a = np.array(a_l)

step0 = 1

if 1 in a:
    step1 = 0
else:
    step1 = 1

ans = [step0, step1]
for i in range(2, N+1):
    if i in a:
        now = 0
    else:
        now = ans[-1] + ans[-2]
    ans.append(now)
print(ans[-1] % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
import sys
n,m=map(int,input().split())
a=list(map(int,sys.stdin))
dp=[0]*(n+1)
dp[0]=1
if 1 not in a:dp[1]=1
for i in range(2,n+1):
    if i in a:continue
    if dp[i-1]==dp[i-2]==0:break
    dp[i]=(dp[i-1]+dp[i-2])%1000000007
print(dp[-1])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

if m > 0:
    aaa = [int(input()) for i in range(m)]
else:
    aaa = set()

dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1 if 1 not in aaa else 0
MOD = 10 ** 9 + 7
 
for i in range(2, n + 1):
    if i in aaa:
        continue
    dp[i] = (dp[i - 2] + dp[i - 1]) % MOD
print(dp[n])

Submission status: Time Limit Exceeded

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

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

dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1 if 1 not in aaa else 0
MOD = 10 ** 9 + 7
 
for i in range(2, n + 1):
    if i in aaa:
        continue
    dp[i] = (dp[i - 2] + dp[i - 1]) % MOD
print(dp[n])

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

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

dp = [1] * (n+1)
for j in range(n+1):
    if j in a:
        dp[j] = 0
    elif j > 1:
        dp[j] = dp[j-1] + dp[j-2]

print(dp[n]%mod)

Submission status: Time Limit Exceeded

Solution code:
OK = "O"
BRO = "B"
MOD = 1000000007

N,M=map(int, input().split())
Broken=[int(input()) for i in range(M)]
K = "".join(list(BRO if i in Broken else OK for i in range(N+1)))

dp=[0 for i in range(N+1)]
dp[0]=1
for i in range(N):
  for j in range(i+1,min(i+2+1,N+1)):
    if K[j]==OK:
      dp[j]+=dp[i]
      dp[j]%=MOD
      
print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
MOD = 1000000007
N = 100001

fibo = [1, 1] + [0] * N
for i in range(2, N):
    fibo[i] = (fibo[i - 1] + fibo[i - 2]) % MOD

n, m = list(map(int, input().split(" ")))
a_list = [int(input()) for _ in range(m)]
ngs = [i in a_list for i in range(n)]
ngs.append(False)
for i in range(n):
    if ngs[i] and ngs[i + 1]:
        print(0)
        exit()
cnts = []
cnt = 0

for ng in ngs:
    if ng:
        cnts.append(cnt)
        cnt = 0
        continue
    cnt += 1
cnts.append(cnt)
ans = 1
for c in cnts:
    if c != 0:
        ans *= fibo[c - 1]
# print(ngs)
# print(cnts)
print(ans % MOD)

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

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

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

Submission status: Time Limit Exceeded

Solution code:
def typical_stairs(N: int, M: int, A: list)->int:
    MOD = 10**9 + 7

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

    for i in range(N):
        if i+1 in A:
            dp[i+1] = 0
        else:
            dp[i+1] = dp[i]
            if i > 0:
                dp[i+1] += dp[i-1]
                dp[i+1] %= MOD

    # print(dp)
    return dp[N]


if __name__ == "__main__":
    M = 0

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

    ans = typical_stairs(N, M, A)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
 
n, m = [int(i) for i in input().split()]
a = [-1]
for mi in range(m):
    a.append(int(input()))
a.append(n+1)
 
ans = 1
for mi in range(1, m+2):
    if a[mi] == a[mi-1]:
        break
    elif a[mi] == a[mi-1] + 1:
        ans = 0
        break
    k = a[mi] - a[mi-1] - 2
    max_2 = k//2
    cnt = 0
    for i in range(max_2+1):
        cnt += math.factorial(k-i) // (math.factorial(k-2*i) * math.factorial(i)) % 1000000007
    ans = ans * cnt % 1000000007
    if ans == 0:
        break
 
print(ans)