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

dp = [0] * (n+1)
# 0段目と1段目は1通り（但し、１段目が壊れていない場合）（0 段目は「なにもしない」という から1 通り）
dp[:2] = 1, 1 if 1 not in a else 0 

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

print(dp[-1] % (10**9+7))

Submission status: Time Limit Exceeded

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

dp = [0] * (n+1)
# 0段目と1段目は1通り（但し、１段目が壊れていない場合）（0 段目は「なにもしない」という から1 通り）
dp[:2] = 1, 1 if 1 not in a else 0 

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

print(dp[-1] % (10**9+7))

Submission status: Time Limit Exceeded

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

dp = []
# 0段目と1段目は1通り（但し、１段目が壊れていない場合）（0 段目は「なにもしない」という から1 通り）
dp[:2] = 1, 1 if 1 not in a else 0 

for i in range(2, n + 1):
    if i in a:
        dp.append(0)
    else:
        dp.append(dp[i - 1] + dp[i - 2])

print(dp[-1] % (10 **9+7))

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

MOD= 1000000007

c=[0]*(n+1)
c[0]=1
if 1 in a:
    c[1]=0
else:
    c[1]=1

for i in range(2,n+1):
    if i in a:
        continue
    else:
        c[i] = (c[i - 1] + c[i - 2]) % MOD

print(c[n])

Submission status: Time Limit Exceeded

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

ans=0
MOD= 1000000007

c=[0]*(n+1)
c[0]=1
if 1 in a:
    c[1]=0
else:
    c[1]=1

for i in range(2,n+1):
    if i in a:
        continue
    else:
        c[i] = (c[i - 1] + c[i - 2]) % MOD

print(c[n]%MOD)

Submission status: Time Limit Exceeded

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

ans=0
MOD= 1000000007

c=[0]*(n+1)
c[0]=1
if 1 in a:
    c[1]=0
else:
    c[1]=1

for i in range(2,n+1):
    c[i]+=(c[i-1]+c[i-2])%MOD
    if i in a:
        c[i]=0

print(c[n]%MOD)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
	modu = 1000000007
	n, m = map(int, input().split())
	a = [False]*n
	for _ in range(m):
		a[int(input())] = True
	dp = [0]*(n+1)
	dp[0], dp[1] = 1, 1
	for i in range(2, n+1):
		if i in a:
			continue
		multi = []
		if not a[i-1]:
			multi.append(dp[i-1])
		if not a[i-2]:
			multi.append(dp[i-2])
		dp[i] = sum(multi) % modu
	print(dp[-1])
resolve()

Submission status: Time Limit Exceeded

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

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

if 1 in l:
    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]
    dp[i] %= mod
print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
def main():
  import sys
  input = sys.stdin.readline

  N,M = map(int,input().split())
  A = tuple([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 not in A:
      dp[i] = (dp[i-1] + dp[i-2])%1000000007
    else:
      continue
  print(dp[N])

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  import sys
  input = sys.stdin.readline

  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 not in A:
      dp[i] = (dp[i-1] + dp[i-2])%1000000007
    else:
      dp[i] = 0
  print(dp[N])

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  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 not in A:
      dp[i] = (dp[i-1] + dp[i-2])%1000000007
    else:
      dp[i] = 0
  print(dp[N])

if __name__ == "__main__":
  main()

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
if 1 in A:
  dp[1] = 0
else:
  dp[1] = 1

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

print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
def resolve():
	modu = 1000000007
	n, m = map(int, input().split())
	a = []
	for _ in range(m):
		a.append(int(input()))
	dp = [0]*(n+1)
	dp[0], dp[1] = 1, 1
	for i in range(2, n+1):
		if i in a:
			continue
		multi = []
		if i-1 not in a:
			multi.append(dp[i-1])
		if i-2 not in a:
			multi.append(dp[i-2])
		dp[i] = sum(multi) % modu
	print(dp[-1])
resolve()

Submission status: Time Limit Exceeded

Solution code:
# 初期入力
N,M = (int(x) for x in input().split())
A = [int(input()) for i in range(M)]


#
mod_9 = 10**9 +7
dp =[0]*(N +1)
dp[0] = 1
if 1 not in A:
    dp[1] =1
for i in range(N-1):
    if i+2 in A:
        dp[i+2] = 0
    else:
        dp[i+2] = dp[i+1] + dp[i] 
        dp[i+2] %= mod_9
kotae =dp[N] # % mod_9
print(kotae )

Submission status: Time Limit Exceeded

Solution code:
# 初期入力
N,M = (int(x) for x in input().split())
A = [int(input()) for i in range(M)]


#
mod_9 = 10**9 +7
dp =[0]*(N +1)
dp[0] = 1
if 1 not in A:
    dp[1] =1
for i in range(N-1):
    if i+2 not in A:
        dp[i+2] = dp[i+1] + dp[i] 
        dp[i+2] %= mod_9
kotae =dp[N] # % mod_9
print(kotae )

Submission status: Time Limit Exceeded

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

mod = 1000000007

result = [-1]*(N+1)

result[0] = 1
result[1] = 1

for a in a_list:
    result[a] = 0

for i in range(2, N+1):
    if i not in a_list:
        result[i] = (result[i-1]+result[i-2])%mod
        if result[i] == 0:
            result[-1] = 0
            break
    
print(result[-1])

Submission status: Time Limit Exceeded

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

mod = 1000000007

result = []

for i in range(N+1):
    if i in a_list:
        result += [0]
    elif i == 0 or i == 1:
        result += [1]
    else:
        result += [(result[i-1]+result[i-2]) % mod]
        
print(result[-1])

Submission status: Time Limit Exceeded

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

if any([abs(A[i+1] - A[i] == 1) for i in range(len(A)-1)]):
  print(0)
  exit()

mod = pow(10, 9) + 7
dp = [0] * (N+1+2)
dp[0] = 1
if 1 not in A:
  dp[1] = 1
  
for i in range(2, N+1):
  if i not in A:
    if i-1 not in A:
      dp[i] = (dp[i] + dp[i-1]) % mod
    if i-2 not in A:
      dp[i] = (dp[i] + dp[i-2]) % mod
print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
#3問目
NM = input().split()
N,M = int(NM[0]), int(NM[1])
A = []
dp = [0] * (N+1)
dp[0] = 1
dp[1] = 1
MOD = 1000000007
for _ in range(M):
    A.append(int(input()))
    
if(1 in A):
    dp[1] = 0

for i in range(2, N+1):
    #貰うdp
    if(i in A):
        dp[i] = 0
    else:
        dp[i] = dp[i-1] + dp[i-2]
    dp[i] %=MOD
    
print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
#3問目
NM = input().split()
N,M = int(NM[0]), int(NM[1])
A = []
dp = [0] * (N+1)
dp[0] = 1
dp[1] = 1
MOD = 1000000007
for _ in range(M):
    A.append(int(input()))
    
if(1 in A):
    dp[1] = 0

for i in range(2, N+1):
    #貰うdp
    if(i in A):
        dp[i] = 0
    else:
        dp[i] = dp[i-1] + dp[i-2]
    dp[i] = dp[i] % MOD
    
print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
#3問目
NM = input().split()
N,M = int(NM[0]), int(NM[1])
A = []
dp = [int(0) for _ in range(N+1)]
dp[0] = 1
dp[1] = 1
MOD = 1000000007
for _ in range(M):
    A.append(int(input()))
    
if(1 in A):
    dp[1] = 0

for i in range(2, N+1):
    #貰うdp
    if(i in A):
        dp[i] = 0
    else:
        dp[i] = dp[i-1] + dp[i-2]
    dp[i] = dp[i] % MOD
    
print(dp[N])

Submission status: Time Limit Exceeded

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

#dp[i]:i段目までの上がり方

div = 1000000007

dp = [0] * (N+1)
dp[0] = 1
if not 1 in a:
    dp[1] = 1

def stairs():
    for i in range(N-1):
        if dp[i+1] == 0 and dp[i] == 0:
            break
        if not i+2 in a:
            dp[i+2] = (dp[i+1] + dp[i]) % div
    print(dp[N])

stairs()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

#dp[i]:i段目までの上がり方

div = 1000000007

dp = [0] * (N+1)
dp[0] = 1
if not 1 in a:
    dp[1] = 1

def stairs():
    for i in range(N-1):
        if not i+2 in a:
            dp[i+2] = (dp[i+1] + dp[i]) % div
    print(dp[N])

stairs()

Submission status: Time Limit Exceeded

Solution code:
mod = pow(10,9)+7
N,M = map(int,input().split())
A = [int(input()) for i in range(M)]+[mod]
DP = [1]
for i in range(1,N+1):
    if i==A[0]:
        DP.append(0)
        A = A[1:]
    else:
        a = DP[i-1]
        b = DP[i-2] if i>1 else 0
        DP.append(a+b)
print(DP[N]%mod)

Submission status: Time Limit Exceeded

Solution code:
mod = pow(10,9)+7
N,M = map(int,input().split())
A = [int(input()) for i in range(M)]+[mod]
DP = [1]
for i in range(1,N+1):
    if i==A[0]:
        DP.append(0)
        A = A[1:]
    else:
        a = DP[i-1]
        b = DP[i-2] if i>1 else 0
        DP.append((a+b)%mod)
print(DP[N]%mod)

Submission status: Time Limit Exceeded

Solution code:
mod = pow(10,9)+7
N,M = map(int,input().split())
A = [int(input()) for i in range(M)]+[mod]
DP = [1]
for i in range(1,N+1):
    if i==A[0]:
        DP.append(0)
        A = A[1:]
    else:
        a = DP[i-1]
        b = DP[i-2] if i>1 else 0
        DP.append((a+b)%mod)
print(DP[N]%mod)

Submission status: Time Limit Exceeded

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

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

for i in range(N):
    if i + 1 not in A:
        dp[i + 1] += dp[i]
    if i + 2 <= N and i + 2 not in A:
        dp[i + 2] += dp[i]

print(dp[N] % mod)
# print(dp)

Submission status: Time Limit Exceeded

Solution code:
MOD = 1000000007

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

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

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

for i in range(2, n + 1):
    if i in a:
        continue
    f[i] = f[i - 1] + f[i - 2]
    if f[i] >= MOD:
        f[i] -= MOD

print(f[-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

div = 1000000007

n, m, *a = map(int, read().split())

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

if 1 not in a:
    f[1] = 1
 
for i in range(2, n + 1):
    if i in a:
        continue
    f[i] = (f[i - 1] + f[i - 2]) % div
 
print(f[-1])

Submission status: Time Limit Exceeded

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

dp = [0] * (n+1)
dp[0] = 1
for i in range(n):
    if i+1 not in a_ls and i not in a_ls:
        if dp[i + 1] == 0:
            dp[i+1] = dp[i]
        else:
            dp[i+1] = (dp[i+1] + dp[i]) % 1000000007
    if i+2 <= n and i+2 not in a_ls and i not in a_ls:
        if dp[i + 2] == 0:
            dp[i+2] = dp[i]
        else:
            dp[i+2] = (dp[i+2] + dp[i]) % 1000000007
print(dp[-1])

Submission status: Time Limit Exceeded

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

dp = [0] * (n+1)
dp[0] = 1
for i in range(n):
    if i+1 not in a_ls and i not in a_ls:
        if dp[i + 1] == 0:
            dp[i+1] = dp[i]
        else:
            dp[i+1] = dp[i+1] + dp[i]
    if i+2 <= n and i+2 not in a_ls and i not in a_ls:
        if dp[i + 2] == 0:
            dp[i+2] = dp[i]
        else:
            dp[i+2] = dp[i+2] + dp[i]
print(dp[-1] % 1000000007)

Submission status: Time Limit Exceeded

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

div = 1000000007

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

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

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

for i in range(2, n + 1):
    if i in a:
        continue
    f[i] = (f[i - 1] + f[i - 2]) % div

print(f[-1])

Submission status: Time Limit Exceeded

Solution code:
import itertools
import math
import string
import collections
from collections import Counter
from collections import deque
import sys
sys.setrecursionlimit(2*10**5)
INF = 2**60


def readints():
    return list(map(int, input().split()))


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


def has_duplicates2(seq):
    seen = []
    for item in seq:
        if not(item in seen):
            seen.append(item)
    return len(seq) != len(seen)


def divisor(n):
    divisor = []
    for i in range(1, n+1):
        if n % i == 0:
            divisor.append(i)
    return divisor


# coordinates
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]


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

safe = [True]*(N+1)
for i in range(M):
    safe[(a[i])] = False


def func(i):
    global safe

    if not(safe[i]):
        return 0
    if memo[i] != 0:
        return memo[i]
    if i == 0:
        return 1
    if i == 1:
        return 1
    ret = 0
    if i >= 2:
        ret += func(i-1)+func(i-2)
        memo[i] = ret
        return ret


print(func(N) % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import math
import string
import collections
from collections import Counter
from collections import deque
import sys
sys.setrecursionlimit(2*10**5)
INF = 2**60


def readints():
    return list(map(int, input().split()))


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


def has_duplicates2(seq):
    seen = []
    for item in seq:
        if not(item in seen):
            seen.append(item)
    return len(seq) != len(seen)


def divisor(n):
    divisor = []
    for i in range(1, n+1):
        if n % i == 0:
            divisor.append(i)
    return divisor


# coordinates
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]


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

safe = [True]*(N+1)
for i in range(M):
    safe[(a[i])] = False


def func(i):
    global safe
    if memo[i] != 0:
        return memo[i]

    if not(safe[i]):
        return 0
    if i == 0:
        return 1
    if i == 1:
        return 1
    ret = 0
    if i >= 2:
        ret += func(i-1)+func(i-2)
        memo[i] = ret
        return ret


print(func(N) % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import queue
    n,m = map(int,input().split())
    A = []
    for _ in range(m):
        a = int(input())
        A.append(a)
    mod = 10**9+7
    q = queue.Queue()
    q.put(1)
    if 1 in A:
        q.put(0)
    else:
        q.put(1)
    for i in range(2,n+1):
        if i in A:
            q.get()
            q.put(0)
        else:
            a = q.get()
            b = q.get()
            q.put(b)
            q.put((a+b)%mod)

    q.get()
    print(q.get())

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

    print(ans[1]%mod)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():

    div = 1000000007

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

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

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

    for i in range(2, n + 1):
        if i in a:
            continue
        f[i] = (f[i - 1] + f[i - 2]) % div

    print(f[-1])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
div = 1000000007

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

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

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

for i in range(2, n + 1):
    if i in a:
        continue
    f[i] = (f[i - 1] + f[i - 2]) % div

print(f[-1])

Submission status: Time Limit Exceeded

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

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

for i in range(1, n + 1):
    if i in a:
        continue
    f[i] = (f[i - 1] + f[i - 2]) % 1000000007

print(f[n])

Submission status: Time Limit Exceeded

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

dp = [0]*(N+1) # 初期条件
dp[0] = 1
dp[1] = 0 if 1 in H else 1
for i in range(2,N+1):
  if i in H:
    dp[i] = 0
  else:
    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())
H = []
for i in range(M):
  H.append(int(input()))

dp = [0]*(N+1) # 初期条件
dp[0] = 1
dp[1] = 0 if 1 in H else 1
for i in range(2,N+1):
      if i in H:
        dp[i] = 0
      else:
        dp[i] = (dp[i-1]+dp[i-2])%1000000007

print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, M = map(int, input().split())
    broken = [int(input()) for _ in range(M)]
    div = 1000000007

    comb_list = [0] * (N + 1)
    comb_list[0] = 1
    if 1 not in broken:
        comb_list[1] = 1

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

    print(comb_list[-1])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

comb_list = [0] * (N + 1)
comb_list[0] = 1
if 1 not in broken:
    comb_list[1] = 1

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

print(comb_list[-1])

Submission status: Time Limit Exceeded

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

comb_list = [0] * (N + 1)
comb_list[0] = 1  # 0段目にたどり着くには1通りの方法
if 1 not in broken:  # 1段目が壊れてなければ1段目にたどり着くには1通り
    comb_list[1] = 1


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

print(comb_list[-1])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
a = [int(input()) for _ in range(m)]
dp=[0 for _ in range(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]
print(dp[n]%1000000007)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
#import fractions
#import math
#import collections
#from collections import deque
#from bisect import bisect_left
#N = int(input())
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = list(map(int,input().split()))
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
N,M = map(int,input().split())
A = [int(input()) for _ in range(M)]  
ans = [0] * (N+3)
ans[0] = 1
for i in range(N):
    if i not in A:
        ans[i+1] += ans[i]
        ans[i+1] = ans[i+1] % 1000000007
        ans[i+2] += ans[i]
        ans[i+2] = ans[i+2] % 1000000007
    else:
        ans[i] = 0
print(ans[N])

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
#import fractions
#import math
#import collections
#from collections import deque
#from bisect import bisect_left
#N = int(input())
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = list(map(int,input().split()))
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
N,M = map(int,input().split())
A = [int(input()) for _ in range(M)]  
ans = [0] * (N+3)
ans[0] = 1
for i in range(N):
    if (i+1) not in A:
        ans[i+1] += ans[i]
        ans[i+1] = ans[i+1] % 1000000007
    if (i+2) not in A:
        ans[i+2] += ans[i]
        ans[i+2] = ans[i+2] % 1000000007
print(ans[N])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

holes = [ int(input()) for _ in range(m) ]


DIV = 10**9+7

dp = [0 for _ in range(n+1)]
dp[0] = 1
if 1 not in holes:
    dp[1] = 1

for i in range(2, n+1):
    if i not in holes:
        dp[i] = (dp[i-1] + dp[i-2]) % DIV

print(dp[n])

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
dp=[0]*(n+1)
f=[]
dp[0]=1

for i in range(m):
    t=int(input())
    f.append(t)

for i in range(1,n+1):
    if i in f:
        continue
    else:
        if dp[i-1] != 0:
            dp[i] += dp[i-1]
        if i > 1:
            if dp[i-2] != 0:
                dp[i] += dp[i-2]

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

Submission status: Time Limit Exceeded

Solution code:
#an+2 = an+1 + an
n,m = map(int,input().split())
a=[]
for i in range(m):
    a.append(int(input()))
ans = [0]*3
for floor in range(1,n+1):
    if floor in a:
        ans = [ans[1],ans[2], 0]
    elif floor == 1:
        ans = [0,0,1]
    elif floor == 2:
        ans = [ans[1],ans[2],ans[2]+1]
    else:
        ans = [ans[1],ans[2],ans[1]+ans[2]]
print(ans[2]%1000000007)

Submission status: Time Limit Exceeded

Solution code:
#an+2 = an+1 + an
n,m = map(int,input().split())
a=[]
for i in range(m):
    a.append(int(input()))
ans = []
for floor in range(1,n+1):
    if floor in a:
        ans.append(0)
    elif floor == 1:
        ans.append(1)
    elif floor == 2:
        ans.append(ans[0] + 1)
    else:
        ans.append(ans[floor-2] + ans[floor-3])
print(ans[n-1]%1000000007)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import math
import string
import collections
from collections import Counter
from collections import deque
import sys
sys.setrecursionlimit(2*10**5)


def readints():
    return list(map(int, input().split()))


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


def has_duplicates2(seq):
    seen = []
    for item in seq:
        if not(item in seen):
            seen.append(item)
    return len(seq) != len(seen)


def divisor(n):
    divisor = []
    for i in range(1, n+1):
        if n % i == 0:
            divisor.append(i)
    return divisor


# coordinates
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]

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

safe = [True]*(N+1)
for i in range(M):
    safe[(a[i])] = False


def func(i):
    global safe

    if not(safe[i]):
        return 0
    if i == 0:
        return 1
    if i == 1:
        return 1
    if i >= 2:
        return func(i-1)+func(i-2)


print(func(N) % 1000000007)

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
A = list()
for i in range(M):
  A.append(int(input()))
ans = list()
for i in range(N+1):
  if(i in A):
    ans.append(0)
  elif(i == 0 or i == 1):
    ans.append(1)
  else:
    ans.append((ans[i-1]+ans[i-2])%1000000007)
print(ans[N])

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
now=0
MOD=10**9+7
p=[1,0]#0 humu  1 humazu
A=[int(input()) for i in range(M)]+[-1]
while now<N:
  if now==A[0]-1:
    p=[0,p[0]]
    A=A[1:]
  else:
    p=[(p[0]+p[1])%MOD, p[0]%MOD]
  now+=1
print(p[0]%MOD)

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
now=0
MOD=10**9+7
p=[1,0]#0 humu  1 humazu
A=[int(input()) for i in range(M)]+[-1]
while now<N:
  if now==A[0]-1:
    p=[0,p[0]]
    A=A[1:]
  else:
    p=[p[0]+p[1], p[0]]
  now+=1
print(p[0]%MOD)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

import sys
import math
import collections
import itertools
INF = 10 ** 13
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def gcd(x, y) : return y if x % y == 0 else gcd(y, x % y)
def lcm(x, y) : return (x * y) // gcd(x, y)
def I() : return int(input())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def LS() : return input().split()
def RS(N) : return [input() for _ in range(N)]
def LRS(N) : return [input().split() for _ in range(N)]
def PL(L) : print(*L, sep="\n")

N, M = LI()
A = RI(M)

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

for i in range(N):
    if i in A:
        continue

    dp[i+1] = ((dp[i] % MOD) + (dp[i+1] % MOD)) % MOD
    dp[i+2] = ((dp[i] % MOD) + (dp[i+2] % MOD)) % MOD

print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

import sys
import math
import collections
import itertools
INF = 10 ** 13
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def gcd(x, y) : return y if x % y == 0 else gcd(y, x % y)
def lcm(x, y) : return (x * y) // gcd(x, y)
def I() : return int(input())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def LS() : return input().split()
def RS(N) : return [input() for _ in range(N)]
def LRS(N) : return [input().split() for _ in range(N)]
def PL(L) : print(*L, sep="\n")

N, M = LI()
A = RI(M)

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

for i in range(N):
    if i in A:
        continue

    dp[i+1] = (dp[i] + dp[i+1]) % MOD
    dp[i+2] = (dp[i] + dp[i+2]) % MOD

print(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
dp = [0]*(n+1)
dp[0] = 1
dp[1] = 0 if 1 in a else 1
for i in range(2, n+1):
    dp[i] = (dp[i-1]+dp[i-2])%mod if i not in a else 0 #かけたところは0にしとこう、ってことか…
print(dp[n])

Submission status: Time Limit Exceeded

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

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

def fibo(x):
    if x >= 0 and fibo_l[x] is not None:
        if fibo_l[x] == 0:
            fibo_l[x] = fibo(x-1) % 1000000007 + fibo(x-2) % 1000000007
        return fibo_l[x]
    else: return 0

print(fibo(n) % 1000000007)