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:
MOD = 10**9 + 7
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
    dp[i] = dp[i - 1]
    if i > 1:
        dp[i] = dp[i - 1] + dp[i - 2]
# print(dp)
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
INF = -1
dp = [INF]*(n+1)
if n == 1:
    if 1 in a:
        print(0)
    else:
        print(1)
    exit()

dp[0] = dp[1] = 1

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

for i in range(2, n+1):
    if i in a:
        dp[i] = INF
        continue
    if dp[i-1] == INF and dp[i-2] == INF:
        break
    elif dp[i-1] == INF or dp[i-2] == INF:
        dp[i] = max(dp[i-1], dp[i-2])
    else:
        dp[i] = dp[i-1]+dp[i-2]
    dp[i] %= MOD


print(dp[n] if dp[n] != INF else 0)

Submission status: Time Limit Exceeded

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

dp[0] = dp[1] = 1

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

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


print(dp[n] if dp[n] != INF else 0)

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 in a:
        continue
    else:
        dp[i] = dp[i - 1] + dp[i - 2]
        dp[i] %= 1000000007

print(dp[-1])

Submission status: Time Limit Exceeded

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

a = []

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

    # 隣接してる場合は、0出力で終了
    if a[i] == a[i - 1] + 1:
        print(0)
        exit(0)

dp = [0] * (N + 1)

dp[0] = 1

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

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

print(dp[-1])

Submission status: Time Limit Exceeded

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

a = []

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

    # 隣接してる場合は、0出力で終了
    if a[i] == a[i - 1] + 1:
        print(0)
        exit(0)

dp = [0] * (N + 1)

dp[0] = 1

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

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

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

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

for now in range(N):
    for next in range(now + 1, min(N + 1, now + 3)):
        if next not in a:
            dp[next] += dp[now]
            dp[next] = dp[next] % MOD

print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
l = [int(input())-1 for _ in range(m)]
res = [0, 1]

for i in range(n):
  if i in l:
    res[0] = res[1]
    res[1] = 0
  else:
    tmp = res[1]
    res[1] += res[0]
    res[0] = tmp
    res[1] %= 10**9 + 7
    res[0] %= 10**9 + 7
    
print(res[1])

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
mod = 10 ** 9 + 7
N, M = map(int, input().split())
a = []
for _ in range(M):
    a_m = int(input())
    if len(a) > 0 and a_m == a[-1] + 1:
        print(0)
        exit()
    a.append(a_m)

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

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

print(dp[-1] % mod)

Submission status: Time Limit Exceeded

Solution code:
mod = 10 ** 9 + 7
N, M = map(int, input().split())
a = []
for _ in range(M):
    a_m = int(input())
    if len(a) > 0 and a_m == a[-1] + 1:
        print(0)
        exit()
    a.append(a_m)

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

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

print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
# from fractions import gcd
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from functools import reduce
from bisect import bisect_left, insort_left
from heapq import heapify, heappush, heappop

INPUT = lambda: sys.stdin.readline().rstrip()
INT = lambda: int(INPUT())
MAP = lambda: map(int, INPUT().split())
S_MAP = lambda: map(str, INPUT().split())
LIST = lambda: list(map(int, INPUT().split()))
S_LIST = lambda: list(map(str, INPUT().split()))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


def main():
    N, M = MAP()
    A = [INT() for i in range(M)]

    dp = [1] * (N + 1)
    for a in A:
        dp[a] = 0

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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 in a:
          continue
     elif i == 0 or i == 1:
          dp[i] = 1
     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)]

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

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

Submission status: Time Limit Exceeded

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

dp = [0 for _ in range(n)]
if 1 in a:
    dp[0] = 0
elif not 1 in a:
    dp[0] = 1
if n >= 2 and 2 in a:
    dp[1] = 0
elif n >= 2 and not 2 in a:
    dp[1] = dp[0] + 1

for i in range(2, n):
    if i + 1 in a:
        dp[i] = 0
    else:
        dp[i] = (dp[i - 1] + dp[i - 2]) % (pow(10, 9) + 7)
#print(dp)
print(dp[n - 1] % (pow(10, 9) + 7))

Submission status: Time Limit Exceeded

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

    dp = [0] * (n + 1)

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

    if n > 1:
        if 2 not in a:
            dp[2] = 1 + dp[1]

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

    print(dp[n])

Submission status: Time Limit Exceeded

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

    dp = [0] * (n + 1)

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

    if n > 1:
        if 2 not in a:
            dp[2] = 1 + dp[1]

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

    print(dp[n] % mod)

Submission status: Time Limit Exceeded

Solution code:
a=open(0)
N,_,*a = map(int, a.read().split())

l,m = [0,0]
for i in range(1, N+1):
    if i in a:
        l,m = m,0
    elif i<3:
        l,m = m,m+1
    else:
        l,m = m,(l+m)%1000000007
print(m)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)

a=open(0)
N,_,*a = map(int, a.read().split())

dp = [-1 for _ in range(150000)]
dp[0] = 0
def rec(i):
    if dp[i] >= 0:
        return dp[i]
    if i in a:
        dp[i] = 0
        return 0
    if i<3:
        dp[i] = rec(i-1) + 1
        return dp[i]
    dp[i] = (rec(i-1)+rec(i-2))%1000000007
    return dp[i]
    
print(rec(N))

Submission status: Time Limit Exceeded

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

div = 1e9 + 7
ans = 0
prev1 = 1
prev2 = 0

for n in range(1, N+1):
  if n in A:
    path = 0
  else:
    path = int((prev1 + prev2) % div)

  prev1, prev2 = path, prev1

print(path)

Submission status: Time Limit Exceeded

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

div = 1e9 + 7
step = [0] * (N+1)
step[0] = 1

for n in range(1, N+1):
  if n in A:
    continue

  if n == 1:
    step[n] = 1
  else:
    step[n] = int((step[n-2] + step[n-1]) % div)

ans = step[N]
print(ans)

Submission status: Time Limit Exceeded

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


def main():
    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(1, N + 1):
        if i in A:
            continue

        if i == 1:
            dp[1] = dp[0]
            continue

        dp[i] = dp[i - 1] + dp[i - 2]
        dp[i] %= mod

    print(dp[N])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

read = sys.stdin.read

n, m, *a = map(int, read().split())
mod = 1000000007
dp = [0] * (n+1)
dp[0] = 1
if a and a[0] == 1:
    dp[1] = 0
    a.pop(0)
else:
    dp[1] = 1
for i in range(2, n+1):
    if a and i == a[0]:
        a.pop(0)
        dp[i] == 0
    else:
        dp[i] = (dp[i-1] + dp[i-2]) % mod
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
import math
mod = 10**9 + 7
import sys
sys.setrecursionlimit(2147483647)
input = sys.stdin.readline

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

pat = [0 for _ in range(N+1)]
pat[0] = 1
if 1 in a :
    pat[1] = 0
else :
    pat[1] = 1

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

print(pat[N])

Submission status: Time Limit Exceeded

Solution code:
def main():
  N,M,*alst=map(int, open(0).read().split())
  mod=10**9+7
  dp = [0] * (N+1)
  dp[:2] = [1, 1 if 1 not in alst else 0]
  for i in range(2, N+1):
    if i not in alst:
      dp[i] = (dp[i-2] + dp[i-1])%mod
  print(dp[N])

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from functools import lru_cache
sys.setrecursionlimit(1000000)
read=sys.stdin.read
N,M,*alst=map(int,read().split())
mod=10**9+7
dp = [1, 1 if 1 not in alst else 0]


@lru_cache(maxsize=None)
def a(n):
  if n==0:
    return dp[0]
  elif n==1:
    return dp[1]
  else:
    if n not in alst:
      return (a(n-2)+a(n-1))%mod
    else:
      return 0


print(a(N))

Submission status: Time Limit Exceeded

Solution code:
import sys
from functools import lru_cache
sys.setrecursionlimit(1000000)
read=sys.stdin.read
N,M,*alst=map(int,read().split())
mod=10**9+7
dp = [1, 1 if 1 not in alst else 0]
@lru_cache(maxsize=None)
def a(n):
  if n==0:
    return dp[0]
  elif n==1:
    return dp[1]
  else:
    if n not in alst:
      return (a(n-2)+a(n-1))%mod
    else:
      return 0
print(a(N))

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] = 1
for i in range(N):
    if i+1 not in A:
        dp[i+1] += dp[i]
        dp[i+1] %= MOD
    if i+2 <= N and i+2 not in A:
        dp[i+2] += dp[i]
        dp[i+2] %= MOD
print(dp[-1]%MOD)

Submission status: Time Limit Exceeded

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

if 0 in a:
    print(0)
    exit()
for i in range(n):
    if i+1 not    in a:
        dp[i+1]+=dp[i]
        dp[i+1]%=mod
    if i+2<=n and i+2 not  in a:
        dp[i+2]+=dp[i]
        dp[i+1]%=mod
print(dp[-1]%mod)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int, input().split())
a = [int(input()) for _ in range(m)]
p = [0]*(n+1)
p[0] = 1
if 1 not in a:
  p[1] = 1

t = 1000000007

for i in range(2, n+1):
  if i in a:
    continue
  s = p[i-1] + p[i-2]
  s = s%t
  p[i] = s
  
print(p[n])

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 [0]*m]
  mod=pow(10,9)+7
  ans=[0]*n
  ans[0]=1
  for i in range(n):
    if a.count(i+1)==1:
      ans[i]=0
    else:
      if i==1:
        ans[i]=ans[0]+1
      elif i>1:
        if ans[i-1]==0 and ans[i-2]==0:
          print(0)
          exit()
        ans[i]=(ans[i-1]%mod+ans[i-2]%mod)%mod
  print(ans[-1])
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#129_C
n,m=map(int,input().split())
a=[int(input()) for _ in range(m)]
mod=10**9+7
dp=[1 for i in range(n+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])%mod
        
print(dp[n]%mod)

Submission status: Time Limit Exceeded

Solution code:
#129_C
n,m=map(int,input().split())
a=[int(input()) for _ in range(m)]
dp=[1 for i in range(n+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]%(10**9+7))

Submission status: Time Limit Exceeded

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

step = [0]*(N+1)
step[0] = 1
if 1 in a:
    step[1] = 0
else:
    step[1] = 1

for i in range(2,N+1):
    if i in a:
        step[i] = 0
    else:
        step[i] = (step[i-1] + step[i-2])%(10**9+7)

print(step[N])

#再起関数供養
def count_step(a,n):
    if n == 0:
        return 1
    if n == 1 and 1 not in a:
        return 1
    if n in a:
        return 0
    return (count_step(a,n-1)+count_step(a,n-2))%(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)

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

    elif i not in a:
        dp[i-1]=dp[i-2]+dp[i-3]

print(dp[N-1]%1000000007)

Submission status: Time Limit Exceeded

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

ways = [0] * 3
ways[1] = 0 if 1 in a else 1
ways[2] = 0 if 2 in a else ways[1] + 1
for i in range(3, n+1):
    if i in a:
        ways.append(0)
    else:
        ways.append((ways[-2]+ways[-1])%(10**9+7))

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

Submission status: Time Limit Exceeded

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

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

for i in range(N):
  for j in range(i+1,min(N+1,i+3)):
    if j not in a:
      dp[j] += dp[i]
      dp[j] %= 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 = 10**9+7
dp = [0] * N

if 1 not in A:
    dp[0] = 1
    if (2 not in A) and N > 1:
        dp[1] = 2
elif N > 1:
    if 2 not in A:
        dp[1] = 1
    else:
        dp[1] = 0

for i in range(2, N):
    if i+1 not in A:
        #dp[i] = (dp[i-2] + dp[i-1]) % mod
        dp[i] = (sum(dp[i-2:i])) % mod

print(dp[N-1])

Submission status: Time Limit Exceeded

Solution code:
import sys

N, M = map(int, input().split())
A = []

for m in range(M):
  if m == 0:
    A.append(int(input()))
    continue

  i = int(input())
  if A[-1] == i-1:
    print(0)
    sys.exit()

  A.append(i)

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


for n in range(1, N+1):
  if n in A:
    continue

  li[n] = li[n-1] + li[n-2]

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

Submission status: Time Limit Exceeded

Solution code:
n, m = (int(x) for x in input().split())
ab = []
for _ in range(m):
    a=int(input())
    ab.append(a)
dp = [0]*(n+1)
dp[0] = 1

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

Submission status: Time Limit Exceeded

Solution code:
import sys #追加
sys.setrecursionlimit(50000000) #追加
N,M=map(int,input().split())
a=[]
for i in range(0,M):
    a.append(int(input()))
if M==0:
    a=[-1]
ans=1
s=[-1]*(N+1)
s[0]=1
def dp(n):
    if n==0:
        return 1
    elif n==1:
        return 0 if 1 in a else 1
    if s[n-1]!=-1:
        c=s[n-1]
    elif n-1 in a:
        s[n-1]=0
        c=0
    else:
        c=dp(n-1)%1000000007
        s[n-1]=c
    if s[n-2]!=-1:
        b=s[n-2]
    elif n-2 in a:
        s[n-2]=0
        b=0
    else:
        b=dp(n-2)%1000000007
        s[n-2]=b
    return (c+b)%1000000007
print(dp(N)%1000000007)

Submission status: Time Limit Exceeded

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

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

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

print(dp[-1])

Submission status: Time Limit Exceeded

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

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

for i in range(1, n+1):
    dp[i] = (dp[i-1] + dp[i-2])
    if i in ab:
        dp[i] = 0

print(dp[-1]%1000000007)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
a_lst = [int(input()) for i in range(m)]
dp = [0]*(n+1)
dp[0] = 1
x = 10**9 + 7

for i in range(1,n+1):
    if i in a_lst:
        continue
    else:
        if i==1:
            dp[i] = dp[i-1]
        elif i>1:
            dp[i] = (dp[i-2] + dp[i-1]) % x

answer = dp[-1]

print(answer)

Submission status: Time Limit Exceeded

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

memo = [0]*(n + 1)

for i in range(n+1):
  if i in a:
    continue
  else:
    if i == 0 or i == 1:
      memo[i] = 1
    else:
      memo[i] = (memo[i-1] + memo[i-2])%((10**9)+7)

print(memo[n])

Submission status: Time Limit Exceeded

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

memo = [0]*(n + 1)

for i in range(n+1):
  if i in a:
    continue
  else:
    if i == 0 or i == 1:
      memo[i] = 1
    else:
      memo[i] = memo[i-1] + memo[i-2]

print(memo[n]%((10**9)+7))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

mod = 1000000007
print(dp[-1]%mod)

Submission status: Time Limit Exceeded

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

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

mod = 1000000007
print(dp[-1]%mod)

Submission status: Time Limit Exceeded

Solution code:


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

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

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

ans = dp[N]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = [int(x) for x in input().split()]
a = list(int(input()) for _ in range(M))

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

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

ans = dp[-1]
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import queue
q=queue.Queue()
l=[]
n,m=map(int,input().split())
for i in range(m):
  p=int(input())
  q.put(p)
que=q.get()
for j in range(n+1):
  if j==0:
    l.append(1)
  elif j==1 and que!=1:
    l.append(1)
  elif j==que:
    l.append(0)
    que=q.get()
  else:
    l.append(l[j-2]+l[j-1])
print(l[n]%(10**9+7))

Submission status: Time Limit Exceeded

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

for i in range(1,n+1):
    if i not in a:
        dan[i] += dan[i-1]
        if i >= 2:
            dan[i] += dan[i-2]

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

x=[0]*(n+1)
x[0]=1
if 1 in A:
    x[1]=0
else:
    x[1]=1

for j in range(2,n+1):
    if j in A:
        x[j]=0
    else:
        x[j]=(x[j-1]+x[j-2])%(10**9+7)
        

print(x[n])

Submission status: Time Limit Exceeded

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

x=[0]*(n+1)
x[0]=1
if 1 in A:
    x[1]=0
else:
    x[1]=1

for j in range(2,n+1):
    if j in A:
        x[j]=0
    else:
        x[j]=x[j-1]+x[j-2]
        x[j]=x[j]%1000000007

print(x[n])

Submission status: Time Limit Exceeded

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

x=[0]*(n+1)
x[0]=1
if 1 in A:
    x[1]=0
else:
    x[1]=1

for j in range(2,n+1):
    if j in A:
        x[j]=0
    else:
        x[j]=x[j-1]+x[j-2]

print(x[n]%1000000007)

Submission status: Time Limit Exceeded

Solution code:
N, M = [int(s) for s in input().split(' ')]
steps = [1] * (N + 1)
for m in range(M):
    a = int(input())
    steps[a] = -1
patterns = 1
mod = 1000000007
d = {
    0: 1,
    1: 1,
    2: 2,
}
mcn_d = {}
def mcn(m, n):
    if (m, n) in mcn_d:
        return mcn_d[(m, n)]
    mm = 1
    nn = 1
    for i in range(n):
        mm *= (m - i)
        nn *= (n - i)
    ret = mm // nn
    mcn_d[(m, n)] = ret
    return ret

def doit(n):
    if n in d:
        return d[n]
    ret = 0
    for two in range(n // 2 + 1):
        one = n - two * 2
        if one < 0:
            break
        ret += mcn(one + two, min(one, two))
    d[n] = ret
    return ret

conts = []
ret = 1
cont = 0
for step in steps:
    if cont == 0:
        cont += step
    elif cont > 0:        
        if step == 1:
            cont += step
        else:
            conts.append(cont)
            cont = step
    else:  # cont < 0
        if step == -1:
            cont += step
            ret *= 0
        else:
            conts.append(cont)
            cont = step
conts.append(cont)

for cont in conts:
    if cont < 0:
        continue
    ret *= doit(cont - 1)

print(ret % mod)

Submission status: Time Limit Exceeded

Solution code:
N, M = [int(s) for s in input().split(' ')]
steps = [1] * (N + 1)
for m in range(M):
    a = int(input())
    steps[a] = -1
patterns = 1
mod = 1000000007
d = {
    0: 1,
    1: 1,
    2: 2,
}
mcn_d = {}
def mcn(m, n):
    if (m, n) in mcn_d:
        return mcn_d[(m, n)]
    mm = 1
    nn = 1
    for i in range(n):
        mm *= (m - i)
        nn *= (n - i)
    ret = mm // nn
    mcn_d[(m, n)] = ret
    return ret

def doit(n):
    if n in d:
        return d[n]
    ret = 0
    for two in range(n // 2 + 1):
        one = n - two * 2
        if one < 0:
            break
        ret += mcn(one + two, two)
    d[n] = ret
    return ret

conts = []
ret = 1
cont = 0
for step in steps:
    if cont == 0:
        cont += step
    elif cont > 0:        
        if step == 1:
            cont += step
        else:
            conts.append(cont)
            cont = step
    else:  # cont < 0
        if step == -1:
            cont += step
            ret *= 0
        else:
            conts.append(cont)
            cont = step
conts.append(cont)

for cont in conts:
    if cont < 0:
        continue
    ret *= doit(cont - 1)

print(ret % mod)

Submission status: Time Limit Exceeded

Solution code:
N, M = [int(s) for s in input().split(' ')]
steps = [1] * (N + 1)
for m in range(M):
    a = int(input())
    steps[a] = -1
patterns = 1
mod = 1000000007
d = {
    0: 1,
    1: 1,
    2: 2,
}

def mcn(m, n):
    mm = 1
    nn = 1
    for i in range(n):
        mm *= (m - i)
        nn *= (n - i)
    return mm // nn

def doit(n):
    if n in d:
        return d[n]
    ret = 0
    for two in range(n // 2 + 1):
        one = n - two * 2
        if one < 0:
            break
        ret += mcn(one + two, two)
    d[n] = ret
    return ret

conts = []
ret = 1
cont = 0
for step in steps:
    if cont == 0:
        cont += step
    elif cont > 0:        
        if step == 1:
            cont += step
        else:
            conts.append(cont)
            cont = step
    else:  # cont < 0
        if step == -1:
            cont += step
            ret *= 0
        else:
            conts.append(cont)
            cont = step
conts.append(cont)

for cont in conts:
    if cont < 0:
        continue
    ret *= doit(cont - 1)

print(ret % mod)

Submission status: Time Limit Exceeded

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

dp = [1] * (n + 3)
for i in range(1, n+1):
    dp[i]  = dp[i-1] if i not in aaa else 0
    dp[i] += dp[i-2] if i >= 2 and i not in aaa else 0
    dp[i] = dp[i] % int(1e9 + 7)
print(dp[n])