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
sys.setrecursionlimit(1000000000)
N,M = (int(x) for x in input().split())
a = set(int(input()) for _ in range(M))
mem = [0] * N
def count_steps(n):
    if mem[n-1]:
        return mem[n-1]
    elif n == 1:
        if 1 in a:
            return 0
        else:
            mem[0] = 1
            return 1
    elif n == 2:
        if 1 in a:
            mem[1] = 1
            return 1
        else:
            mem[1] = 2
            return 2
    elif n - 1 in a and n - 2 in a:
        return 0
    elif n - 1 in a:
        mem[n-1] = count_steps(n-2)
        return mem[n-1]
    elif n - 2 in a:
        mem[n-1] = count_steps(n-1)
        return mem[n-1]
    else:
        mem[n-1] = (count_steps(n-1) + count_steps(n-2)) % 1000000007
        return mem[n-1]
print(count_steps(N))

Submission status: Time Limit Exceeded

Solution code:
# C - Typical Stairs

MOD = (10 ** 9) + 7
INF = float('inf')
N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
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:
        dp[i] = 0
    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 = list(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[-1]%1000000007)

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 in a :
        continue
    else:
        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=[0]*M
for i in range(M):
    a[i]=int(input())
MOD = 1000000007

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):
    #n-1段目が安全なら
    if i-1 not in a:
        dp[i]+=dp[i-1]
    #n-2段目が安全なら
    if i-2 not in a:
        dp[i]+=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 _ in range(M)]
MOD = int(1e9) + 7

stair = []
for i in range(N):
    if i+1 in a:
        stair.append(False)
    else:
        stair.append(True)

# DP
dp = [0] * N
if stair[0]:
    dp[0] = 1
if N >= 2:
    if stair[1]:
        dp[1] = dp[0] + 1
    else:
        dp[1] = 0

for i in range(2, N):
    if not stair[i]:
        dp[i] = 0
        continue
    if stair[i-1] and stair[i-2]:
        dp[i] = (dp[i-1] + dp[i-2])%MOD
    elif stair[i-1]:
        dp[i] = dp[i-1]
    elif stair[i-2]:
        dp[i] = dp[i-2]

print(dp[N-1])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

for i in range(m-1):
    if m == 1:
        break
    if a[i+1] - a[i] == 1:
        print(0)
        exit()

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
    dp[i] = dp[i-1] + dp[i - 2]
    dp[i] %= 1000000007

print(dp[n])

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
a = list(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
    dp[i] = dp[i-1] + dp[i - 2]
    dp[i] %= 1000000007

print(dp[n])

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
a = list(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
    dp[i] = dp[i-1] + dp[i - 2]
    dp[i] %= 1000000007

print(dp[n])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n,ng = map(int,input().split())
nglist = list(int(input()) for i in range(ng))

MOD   = 10**9+7 
dp    = [0]*(n+1)
dp[0] = 1
 
for i in range(1,n+1):

  if i in nglist:
    dp[i] = 0
    continue

  if i==1:
    dp[1] = dp[0]
    continue
  
  dp[i] = (dp[i-2] + dp[i-1]) % MOD

print(dp[n])

Submission status: Time Limit Exceeded

Solution code:
n,ng = map(int,input().split())
nglist = list(int(input()) for i in range(ng))

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

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

  if i in nglist:
    dp[i] = 0
    continue

  if i==1:
    dp[1] = dp[0]
    continue
  
  dp[i] = dp[i-2] + dp[i-1]

print(dp[n] % MOD)

Submission status: Time Limit Exceeded

Solution code:
n,ng = map(int,input().split())
nglist = list(int(input()) for i in range(ng))

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

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

  if i in nglist:
    dp[i] = 0
    continue

  if i==1:
    dp[1] = dp[0]
    continue
  
  dp[i] = (dp[i-2] + dp[i-1]) % MOD

print(dp[n])

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
def main():
  n,m=map(int,input().split())
  a=tuple(int(input()) for _ in range(m))
  mod=10**9+7
  pattern=[0]*(n+1)
  pattern[0]=pattern[1]=1
  if 1 in a:
      pattern[1]=0
  for i in range(2,n+1):
      if i in a:
          pattern[i]=0
      else:
          pattern[i]=(pattern[i-1]+pattern[i-2])%mod
  print(pattern[n])
main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

mod = pow(10, 9)+7
point = [0]*(n+1)
point[0] = 1
if 1 in a:
    point[1] = 0
else:
    point[1] = 1

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


print(point[-1] % mod)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

##### 割り算の切り上げ #####
# tmp = -(-4 // 3)

##### dict の for文 #####
# for k, v in d.items():
#     print(k, v)

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N,M = inputMap()
	ans = [0 for i in range(N+1)]
	ans[0] = 1
	a = []
	for i in range(M):
		tmp = inputInt()
		a.append(tmp)

	for i in range(N+1):
		if i+1 <= N:
			if i+1 in a:
				pass
			else:
				ans[i+1] = (ans[i+1] + ans[i]) % mod
		if i+2 <= N:
			if i+2 in a:
				pass
			else:
				ans[i+2] = (ans[i+2] + ans[i]) % mod

	print(ans[N])


#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)


class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# dfs のサンプル
def dfs(graph,parent,counter,edge):
    stk = []
    stk.append(edge)
    while len(stk) > 0:
        p = stk.pop()
        for e in graph[p]:
            if parent[p] == e:
                continue
            else:
                parent[e] = p
                counter[e] += counter[p]
                stk.append(e)

if __name__ == "__main__":
	main()

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

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

#print(dp)
print(dp[n])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

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

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

print(dp[N])

Submission status: Time Limit Exceeded

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

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

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

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

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

Submission status: Time Limit Exceeded

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

    # i段目に到達するまでのルートの総数
    dp = [1] * (n + 1)

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

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

        dp[i] = dp[i - 1]
        if i >= 2:
            dp[i] += dp[i - 2]

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

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
dp[0] = 1
dp[1] = 0 + (1 not in a)

for i in range(2, -~n):
    if i in a:
        continue
    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 _ in range(m)]
MOD = 1000000007
dp = [0] * (n+1)
dp[0] = 1
if 1 not in a:
    dp[1] = 1
else:
    dp[1] = 0
    
for i in range(2,n+1):
    if i in a:
        continue
        
    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 _ in range(m)]
MOD = 10 ** 9 + 7
dp = [0] * (n+1)
dp[0] = 1
if 1 not in a:
    dp[1] = 1
else:
    dp[1] = 0
    
for i in range(2,n+1):
    if i in a:
        continue
        
    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 _ in range(m)]
MOD = 10 ** 9 + 7
dp = [0] * (n+1)
dp[0] = 1
if 1 not in a:
    dp[1] = 1
else:
    dp[1] = 0
    
for i in range(2,n+1):
    if i in a:
        pass
    else:
        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())
MOD=1000000007
a=[]
tmp2=10000000000000
for i in range(m):
    tmp=int(input())
    if (tmp-tmp2)==1:
        print(0)
        exit()
    a.append(tmp)
    tmp2=tmp
dp=[0]*(n+1)
dp[0]=1
dp[1]=1
for i in range(2,n+1):
    if i-1 in a:
        dp[i]=dp[i-2]%MOD
    elif i-2 in a:
        dp[i]=dp[i-1]%MOD
    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 i in range(m)]
mod=10**9+7

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

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

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

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

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

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
N,M = map(int,input().split())
a = [int(stdin.readline()) for _ in range(M)]
A = [0]*(N+1)
mod = 1000000007
A[0] = 1
if not(1 in a):
  A[1] = 1
for i in range(2,N+1):
    if i in a:
      A[i] = 0
    else:
      A[i] = (A[i-2] + A[i-1]) % mod
print(A[N])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

a = [int(input()) for x in range(m)]
_MOD = 1000000007

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

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

for i in range(1,n):
    if (i + 1) in a:
        dp[i + 1] = 0
    else:
        dp[i + 1] = (dp[i] + dp[i - 1]) % _MOD

print(dp[n])

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
    else:
        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())
a=[0]*m
for i in range(m):
    a[i]=int(input())
p0=1
if 1 in a:
    p1=0
else:
    p1=1
for i in range(2,n+1):
    if i in a:
        p2=0
    else:
        p2=p1+p0
    p0,p1=p1,p2
print(p1%1000000007)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
step=list(range(2,n+1))
broken=[]
for i in range(m):
    broken+=[int(input())]
mod=10**9+7
dp=[0]*(n+1)
dp[0]=1
if m==0:
    dp[1]=1
elif not broken[0]==1:
    dp[1]=1
for i in step:
    if not i in broken:
        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())
arr = [int(input()) for _ in range(0,M)]
dp = [0 for _ in range(0,N+1)]
dp[0] = 1 if 0 not in arr else 0
dp[1] = 1 if 1 not in arr else 0
for i in range(2,N+1):
    if dp[i-1] == 0 and dp[i-2] == 0:
        break
    if (i-1) not in arr: dp[i] += dp[i-1]
    if (i-2) not in arr: dp[i] += dp[i-2]
print(dp[N] % (10**9 + 7))

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
step=list(range(n+1))
broken=[]
for i in range(m):
    broken+=[int(input())]
mod=10**9+7
enable=[i for i in step if not i in broken and not i == 0]
dp=[0]*(n+1)
dp[0]=1
if enable[0]==1:
    dp[1]=1
    enable.pop(0)
for i in enable:
    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())
step=list(range(n+1))
broken=[]
for i in range(m):
    broken+=[int(input())]
mod=10**9+7
enable=[i for i in step if not i in broken and not i == 0]
dp=[0]*(n+1)
dp[0]=1
if enable[0]==1:
    dp[1]=1
    enable.pop(0)
for i in enable:
    dp[i]=(dp[i-1]+dp[i-2])
print(dp[n]%mod)

Submission status: Time Limit Exceeded

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

MOD = 10 ** 9 + 7

list = [0] * N

for i in range(N):
    if i == 0:
        if (i + 1) in a:
            list[i] = 0
        else:
            list[i] = 1
    elif i == 1:
        if (i + 1) in a:
            list[i] = 0
        elif i in a:
            list[i] = 1
        else:
            list[i] = 2
    else:
        if (i + 1) in a:
            list[i] = 0
        else:
            list[i] = (list[i - 1] + list[i - 2]) % MOD
            
ans = list[N - 1]
print(ans)

Submission status: Time Limit Exceeded

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

MOD = 10 ** 9 + 7

list = [0] * N

for i in range(N):
    if i == 0:
        if (i + 1) in a:
            list[i] = 0
        else:
            list[i] = 1
    elif i == 1:
        if (i + 1) in a:
            list[i] = 0
        elif i in a:
            list[i] = 1
        else:
            list[i] = 2
    else:
        if (i + 1) in a:
            list[i] = 0
        else:
            list[i] = (list[i - 1] + list[i - 2]) % MOD
            
ans = list[N - 1]
print(ans)

Submission status: Time Limit Exceeded

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

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()))
mod = 1000000007
dp=[0]*(N+1)
dp[0]=1
if M != 0:
    if A[0]!=1:
        dp[1]=1 
    else:
        dp[1]=0
else:
    dp[1]=1
    
for i in range(2,N+1):
    if i in A:
        dp[i]=0
    else:
        dp[i] = (dp[i-1]+dp[i-2])%mod

print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
l = [int(input()) for _ in range(m)]
q = 10**9+7
memo = [0]*(n+1)
memo[0]=1
su = 0
if 1 in l:
  memo[1]=0
else:
  memo[1]=1

for i in range(2,n+1):
  if i in l:
    continue
  else:
    memo[i]=(memo[i-1]+memo[i-2])%q
print(memo[-1]%q)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
l = [int(input()) for _ in range(m)]
q = 10**9+7
memo = [0]*(n+1)
memo[0]=1
su = 0
if 1 in l:
  memo[1]=0
else:
  memo[1]=1

for i in range(2,n+1):
  if i in l:
    continue
  else:
    memo[i]=memo[i-1]+memo[i-2]
print(memo[-1]%q)

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

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

n, m = map(int, input().split())
ans = [0 for _ in range(n+1)]
z = 10**9 + 7

a_list = [int(input()) for _ in range(m)]
# print(a_list)

ans[0] = 1
if 1 not in a_list:
    ans[1] = 1
else:
    ans[1] = 0
        
for i in range(2, n+1):
    if i in a_list:
        ans[i] = 0
    else:
        ans[i] += ans[i-1]+ans[i-2]
        
# print(ans)
print(int(ans[-1]%z))

Submission status: Time Limit Exceeded

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

arr = [-1]+arr+[N+1]
from math import factorial

count = 0
memo = {}
for i in range(0,len(arr)-1):
    start,end = arr[i],arr[i+1]
    span = end - start - 2 # the first step is taken by a certain step (with no choice)
    if span < 0:
        count = 0 # impossible
        break 
    nptn = int(span/2)
    regional_count = 0

    for k in range(0,nptn+1):
        key = '{} {}'.format(span,k)
        if key in memo.keys():
            regional_count += memo[key]
        else:
            val = factorial(span-k) // factorial(k) // factorial(span-2*k)
            regional_count += val
            memo[key] = val
    
    if count == 0:
        count += regional_count
    else:
        count *= regional_count
print(count % 1000000007)

Submission status: Time Limit Exceeded

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

arr = [-1]+arr+[N+1]
#from math import factorial
from functools import reduce
count = 0
for i in range(0,len(arr)-1):
    start,end = arr[i],arr[i+1]
    span = end - start - 2 # the first step is taken by a certain step (with no choice)
    if span < 0:
        count = 0 # impossible
        break 
    nptn = int(span/2)
    regional_count = 0

    for k in range(0,nptn+1):
        #regional_count += factorial(span-k) // factorial(k) // factorial(span-2*k)
        mul = lambda a,b: a*b
        regional_count += reduce(mul, range(span-k,k,-1),1) // reduce(mul, range(1,span-2*k+1),1)
    
    if count == 0:
        count += regional_count
    else:
        count *= regional_count
print(count % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
    
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(n):
        if not(i+1 in A):
            dp[i+1]+=dp[i]%mod
        if not(i+2 in A) and i<n-1:
            dp[i+2]+=dp[i]%mod
    print(dp[n]%mod)

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

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

arr = [-1]+arr+[N+1]

from operator import mul
from functools import reduce

def factorial(n):
    return reduce(mul, range(n, 0, -1), 1)
  
count = 0

for i in range(0,len(arr)-1):
    start,end = arr[i],arr[i+1]
    span = end - start - 2 # the first step is taken by a certain step (with no choice)
    if span < 0:
        count = 0 # impossible
        break 
    nptn = int(span/2)
    regional_count = 0

    for k in range(0,nptn+1):
        regional_count += factorial(span-k) // factorial(k) // factorial(span-2*k)
    
    if count == 0:
        count += regional_count
    else:
        count *= regional_count
print(count % 1000000007)

Submission status: Time Limit Exceeded

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

arr = [-1]+arr+[N+1]
from math import factorial
count = 0
for i in range(0,len(arr)-1):
    start,end = arr[i],arr[i+1]
    span = end - start - 2 # the first step is taken by a certain step (with no choice)
    if span < 0:
        count = 0 # impossible
        break 
    nptn = int(span/2)
    regional_count = 0

    for k in range(0,nptn+1):
        regional_count += factorial(span-k) // factorial(k) // factorial(span-2*k)
    
    if count == 0:
        count += regional_count
    else:
        count *= regional_count
print(count % 1000000007)

Submission status: Time Limit Exceeded

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

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

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

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

print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()
A = []
for m in range(M):
    a = ir()
    A.append(a)
C = [0 for _ in range(N+1)]
C[0] = 1
for i in range(len(C)):
    if i in A:
        continue
    if i >= 2:
        C[i] += C[i-2]
        C[i] += C[i-1]
        C[i] %= 1000000007
    elif i >= 1:
        C[i] += C[i-1]
        C[i] %= 1000000007

print(C[N] % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()
A = []
for m in range(M):
    a = ir()
    A.append(a)
C = [0 for _ in range(N+1)]
C[0] = 1
for i in range(len(C)):
    if i in A:
        continue
    if i >= 2:
        C[i] += C[i-2]
    if i >= 1:
        C[i] += C[i-1]

print(C[N] % 1000000007)

Submission status: Time Limit Exceeded

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

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

dp = []
for dpi in range(n):
    dp.append(0)

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

print(dp[n-1] % 1000000007)