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(10 ** 6)

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

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

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, 1] + [None] * (n - 1)
a = [int(input()) for i in range(m)]

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
# python 3.4.3
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# function
# -------------------------------------------------------------


# -------------------------------------------------------------
# main
# -------------------------------------------------------------
N,M = map(int,input().split())
A = list(int(input()) for _ in range(M))

mod = 10**9+7

# dp[i] : i番目の階段までの場合の数
dp = [0]*(N+1) 
dp[0] = 1
dp[1] = 1 if 1 not in A else 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)]
dp=[0]*(n+1)
dp[0]=1
for i in range(1,n+1):
    dp[i]=(dp[i-1]+dp[i-2])%(10**9+7)
    if i in a:dp[i]=0
print(dp[n])

Submission status: Time Limit Exceeded

Solution code:
N, M  = map(int, input().split())
A = [int(input()) for i in range(M)]
 
dp = [1]
for _ in range(N+2):
  dp.append(0)
 
#N段目まで行くのにdp[N]通り
 
for i in range(N):
  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]%(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 = [1]
for _ in range(N+1):
  dp.append(0)
 
#N段目まで行くのにdp[N]通り
 
for i in range(N):
  if i not in A:
    dp[i+1] += dp[i]
    dp[i+2] += dp[i]
  else:
    dp[i] = 0
 
print(dp[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)]
step = [1] + [0]*n
mod = 10**9 + 7
for i in range(1,n+1):
    if i in a:
        continue
    else:
        if i-1 not in a:
            step[i] += step[i-1]%mod
        if i-2 not in a and i>=2:
            step[i] += step[i-2]%mod
        if i-1 in a and i-2 in a:
            print(0)
            exit()
print(step[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 = [1]
for _ in range(N+1):
  dp.append(0)
 
#N段目まで行くのにdp[N]通り
 
for i in range(N):
  if A.count(i) == 0:
    dp[i+1] += dp[i]
    dp[i+2] += dp[i]
  else:
    dp[i] = 0
 
print(dp[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 = [1]
for _ in range(N+1):
  dp.append(0)

#N段目まで行くのにdp[N]通り

for i in range(N):
  if A.count(i) == 0:
    dp[i+1] += dp[i]
    dp[i+2] += dp[i]
  else:
    dp[i] = 0

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

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
S = [int(input()) for _ in range(W)]
    
floor = list(range(0,H+1))
 
if S.count(1) >0:
	floor[1]=0
	floor[2]=1
	if S.count(2) >0:
		floor[2]=0
elif S.count(2) >0:
	floor[1]=1
	floor[2]=0
 
teiou = [0]*H
for i in range (0, H):
	teiou[i] = S.count(i)
    
for i in range (3, H+1):
		floor[i]=floor[i-2]*(1-teiou[i-2])+floor[i-1]*(1-teiou[i-1])

print(floor[H]%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
S = [int(input()) for _ in range(W)]
    
floor = list(range(0,H+1))
 
if S.count(1) >0:
	floor[1]=0
	floor[2]=1
if S.count(2) >0:
    floor[2]=0
 
teiou = [0]*H
for i in range (0, H+1):
	if S.count(i) >  0:
		teiou[i] = 1
    
for i in range (3, H+1):
		floor[i]=floor[i-2]*(1-teiou[i-2])+floor[i-1]*(1-teiou[i-1])
print(floor[H]%(10**9+7))

Submission status: Time Limit Exceeded

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

mod = 10**9+7

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

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

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
m = [int(input()) for k in range(M)]
ndic = {0:1}
for n in range(N):
    if not n+1 in m:
        if n+1 in ndic.keys():
            ndic[n+1] += ndic[n]
        else:
            ndic[n+1] = ndic[n]
#         print("add {} to {}".format(ndic[n], n+1))
    else:
        if not n+2 in ndic.keys():
            ndic[n+1] = 0
    if not  n+2 in m:
        if n+2  in ndic.keys():
            ndic[n+2]+= ndic[n]
        else:
            ndic[n+2]= ndic[n]
    else:
        if not n+2 in ndic.keys():
            ndic[n+2] = 0
#         print("add {} to {}".format(ndic[n],n+2 ))
print(ndic[N]%1000000007)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
m = [int(input()) for k in range(M)]
dic = {}
for n in range(N):
    dic[n]=[n+1 in m, n+2 in m]
ndic = {0:1}
for n in range(N):
    if not n+1 in m:
        if n+1 in ndic.keys():
            ndic[n+1] += ndic[n]
        else:
            ndic[n+1] = ndic[n]
#         print("add {} to {}".format(ndic[n], n+1))
    else:
        if not n+2 in ndic.keys():
            ndic[n+1] = 0
    if not  n+2 in m:
        if n+2  in ndic.keys():
            ndic[n+2]+= ndic[n]
        else:
            ndic[n+2]= ndic[n]
    else:
        if not n+2 in ndic.keys():
            ndic[n+2] = 0
#         print("add {} to {}".format(ndic[n],n+2 ))

print(ndic[N]%1000000007)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
m = [int(input()) for k in range(M)]
dic = {}
for n in range(N):
    dic[n]=[n+1 in m, n+2 in m]
ndic = {0:1}
for n in range(N):
    if not dic[n][0]:
        if n+1 in ndic.keys():
            ndic[n+1] += ndic[n]
        else:
            ndic[n+1] = ndic[n]
#         print("add {} to {}".format(ndic[n], n+1))
    else:
        if not n+1 in ndic.keys():
            ndic[n+1] = 0
    if not dic[n][1]:
        if n+2  in ndic.keys():
            ndic[n+2]+= ndic[n]
        else:
            ndic[n+2]= ndic[n]
    else:
        if not n+2 in ndic.keys():
            ndic[n+2] = 0
#         print("add {} to {}".format(ndic[n],n+2 ))

print(ndic[N]%1000000007)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
S = [int(input()) for _ in range(W)]
    
floor = list(range(0,H+1))

if S.count(1) >0:
	floor[1]=0
	floor[2]=1
if S.count(2) >0:
    floor[2]=0

teiou = [0]*H
for i in range (0, H+1):
	if S.count(i) >  0:
		teiou[i] = 1
    
for i in range (3, H+1):
		floor[i]=floor[i-2]*(1-teiou[i-2])+floor[i-1]*(1-teiou[i-1])
print(floor[H]%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
S = [int(input()) for _ in range(W)]
    
floor = list(range(0,H+1))

if S.count(1) >0:
	floor[1]=0
	floor[2]=1
if S.count(2) >0:
    floor[2]=0

for i in range (3, H+1):
		floor[i]=floor[i-2]*(1-S.count(i-2))+floor[i-1]*(1-S.count(i-1))
print(floor[H]%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
S = [int(input()) for _ in range(W)]
    
floor = list(range(0,H+1))

if S.count(1) >0:
	floor[1]=0
	floor[2]=1
if S.count(2) >0:
    floor[2]=0

for i in range (3, H+1):
	if S.count(i-2) > 0 and S.count(i-1) > 0:
		floor[i]=0
	elif S.count(i-2) > 0:
		floor[i]=floor[i-1]
	elif S.count(i-1) > 0:
		floor[i]=floor[i-2]
	else:
		floor[i]=floor[i-2]+floor[i-1]
print(floor[H]%(10**9+7))

Submission status: Time Limit Exceeded

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

a, b = 0, 0
x = (10 ** 9 + 7)

for i in range(n):
    if i + 1 in hole:
        a, b = 0, a
    else:
        if i == 0:
            a = 1
        elif i == 1:
            a, b = (a + 1) % x, a % x
        else:
            a, b = (a + b) % x, a % x
    
print(a)

Submission status: Time Limit Exceeded

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

a, b = 0, 0

for i in range(n):
    if i + 1 in hole:
        a, b = 0, a
    else:
        if i == 0:
            a = 1
        elif i == 1:
            a, b = a + 1, a
        else:
            a, b = a + b, a
    

print(a % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

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

p =  [0] * n

for i in range(n):
    if i + 1 in hole:
        p[i] = 0
    else:
        if i == 0:
            p[0] = 1
        elif i == 1:
            p[1] = p[0] + 1
        else:
            p[i] = p[i-1] + p[i-2]

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

Submission status: Time Limit Exceeded

Solution code:
import math
n, m = map(int, input().split())
a = [-1] + [int(input()) for i in range(m)] + [n+1]
func = math.factorial
count = 1
for i in range(m+1):
    k = a[i+1] - a[i] - 2
    if k == -1:
        count = 0
        break
    else:
        work = 0
        for b in range(k//2+1):
            work += func(k-b)//(func(k-2*b)*func(b))
        count *= work
print(count%1000000007)

Submission status: Time Limit Exceeded

Solution code:
import math
n, m = map(int, input().split())
a = [-1] + [int(input()) for i in range(m)] + [n+1]
a.append(n+1)
func = math.factorial
count = 1
for i in range(m+1):
    k = a[i+1] - a[i] - 2
    if k == -1:
        count = 0
        break
    else:
        work = 0
        for b in range(k//2+1):
            work += func(k-b)//(func(k-2*b)*func(b))
        count *= work
print(count%1000000007)

Submission status: Time Limit Exceeded

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


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

Submission status: Time Limit Exceeded

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

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

lst=[None]*(N+1)
def func(n):
    if n in a:
        return 0
    if n<=1:
        return 1
    else:
        if lst[n]:
            return lst[n]
        else:
            temp=(func(n-1)+func(n-2))%(10**9+7)
            lst[n]=temp
            return temp

print(func(N))

Submission status: Time Limit Exceeded

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

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

lst=[0]*(N+1)
def func(n):
    if n in a:
        return 0
    if n<=1:
        return 1
    else:
        if lst[n]:
            return lst[n]
        else:
            temp=(func(n-1)+func(n-2))%(10**9+7)
            lst[n]=temp
            return temp

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

print(dp[n])

Submission status: Time Limit Exceeded

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

#`dp[i] = i段目にいる通り数`
if not 0 in a:
    dp[0] = 1
if not 1 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]) % (10 ** 9 + 7)

print(dp[-1])

Submission status: Time Limit Exceeded

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

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

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

for i in range(N+1):
    if i==0 or i==1:
        if i in A:
            step[i] = 0
    else:
        step[i] = step[i-1]+step[i-2]
        if i in A:
            step[i] = 0
        step[i] %= mod

print(step[-1])

Submission status: Time Limit Exceeded

Solution code:
I=lambda:list(map(int,input().split()))
n,m=I()
b=[int(input()) for i in range(m)]
dp=[0]*(n+1)
dp[0]=1
for i in range(1,n+1):
    if i not in b:
        dp[i]=(dp[i-1]+dp[i-2])%(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)]
mod = 10**9+7
# i番目にたどり着く総数
dp = [0 for i in range(n+1)]
dp[0] = 1
if 1 in a:
    dp[1] = 0
else:
    dp[1] = 1
for i in range(n-1):
    if i+2 in a:
        dp[i+2] = 0
    else:
        dp[i+2] = (dp[i] + dp[i+1])%mod
print(dp[n])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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


MOD = 1000000007

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

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

print(d[-1])

Submission status: Time Limit Exceeded

Solution code:
#import sys
#sys.setrecursionlimit(10 ** 7)

'''
#import numpy as np
import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, functools, random
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop
from itertools import permutations, combinations, product, accumulate, groupby
from bisect import bisect_left, bisect_right, insort_left, insort_right
from operator import itemgetter as ig
#sys.setrecursionlimit(10 ** 7)
'''
#inf = 10 ** 20
'''
INF = float("INF")
mod = 10 ** 9 + 7
"""dd = [(-1, 0), (0, 1), (1, 0), (0, -1)];
ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)];
ddn9 = ddn + [(0, 0)]
for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""

def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]  # WideIntPoint
def ws(): return sys.stdin.readline().split()
def si(): return int(sys.stdin.readline())  # SingleInt
def ss(): return input()
def hi(n): return [si() for _ in range(n)]
def hs(n): return [ss() for _ in range(n)]  # HeightString
def s_list(): return list(input())
def mi(n): return [wi() for _ in range(n)]  # MatrixInt
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]
def num_grid(n): return [[int(i) for i in sys.stdin.readline().split()[0]] for _ in range(n)]  # NumberGrid
def grid(n): return [s_list() for _ in range(n)]

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

'''
#import numpy as np
import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, functools, random
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop
from itertools import permutations, combinations, product, accumulate, groupby
from bisect import bisect_left, bisect_right, insort_left, insort_right
from operator import itemgetter as ig
#sys.setrecursionlimit(10 ** 7)
'''
inf = 10 ** 20
'''
INF = float("INF")
mod = 10 ** 9 + 7
"""dd = [(-1, 0), (0, 1), (1, 0), (0, -1)];
ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)];
ddn9 = ddn + [(0, 0)]
for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""

def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]  # WideIntPoint
def ws(): return sys.stdin.readline().split()
def si(): return int(sys.stdin.readline())  # SingleInt
def ss(): return input()
def hi(n): return [si() for _ in range(n)]
def hs(n): return [ss() for _ in range(n)]  # HeightString
def s_list(): return list(input())
def mi(n): return [wi() for _ in range(n)]  # MatrixInt
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]
def num_grid(n): return [[int(i) for i in sys.stdin.readline().split()[0]] for _ in range(n)]  # NumberGrid
def grid(n): return [s_list() for _ in range(n)]

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

'''
if __name__ == '__main__':
    main()
'''

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

Submission status: Time Limit Exceeded

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

dp = [0]*(n+1)
if 1 in base:
  dp[1] = 0
else:
  dp[1] = 1

dp[0] = 1

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

Submission status: Time Limit Exceeded

Solution code:
# from math import factorial,sqrt
# from itertools import permutations as permus
# from fractions import gcd
# from collections import deque,Counter
# from decimal import Decimal, getcontext
# # getcontext().prec = 1000
# # eps = Decimal(10) ** (-100)

# import numpy as np
# import scipy as scp

# 入力の受け取り
n,m = map(int,input().split())
rows = [int(input()) for _ in range(m)]

mod = 1000000007

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

dp[0]=1
for now in range(n):
    for next in range(now+1,min(n,now+2)+1):
        if not next in rows:
            dp[next] += dp[now]
            dp[next] %= mod

print(dp[n])
# print("{:.10f}".format(ans))
# print(*ans)   # unpackして出力。間にスペースが入る
# for row in board:
#     print(*row,sep="")    #unpackして間にスペース入れずに出力する

Submission status: Time Limit Exceeded

Solution code:
import sys
import os

MOD = 10 ** 9 + 7


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, M = list(map(int, sys.stdin.buffer.readline().split()))
    A = [int(sys.stdin.buffer.readline().rstrip()) for _ in range(M)]

    ret = [0, 1]
    for i in range(1, N + 1):
        if i in A:
            ret.append(0)
        else:
            ret.append((ret[-1] + ret[-2]) % MOD)

    print(ret[-1] % MOD)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
A = []
for i in range(M):
    a = int(input())
    A.append(a)
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])%mod
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7

def solve():
    N, M = map(int, input().split())
    A = [int(input()) for _ in range(M)]
    
    if N == 1 and M == 0:
        return 1
    elif N == 1 and M == 1 and A[0] == 0:
        return 0

    dp = [0 for i in range(N+1)]
    dp[1] = 0 if 1 in A else 1
    dp[2] = 0 if 2 in A else dp[1] + 1

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

    return dp[N] % MOD

print(solve())

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7

def solve():
    N, M = map(int, input().split())
    A = [int(input()) for _ in range(M)]
    
    if N == 1 and M == 0:
        return 1
    elif N == 1 and M == 1 and A[0] == 0:
        return 0

    dp = [0] * (N+1)
    dp[1] = 0 if 1 in A else 1
    dp[2] = 0 if 2 in A else dp[1] + 1

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

    return dp[N] % MOD

print(solve())

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7

def solve():
    N, M = map(int, input().split())
    A = [int(input()) for _ in range(M)]
    
    if M > 1:
        for i in range(M-1):
            if A[i]+1 == A[i+1]:
                return 0

    if N == 1 and M == 0:
        return 1
    elif N == 1 and M == 1 and A[0] == 0:
        return 0

    dp = [0] * (N+1)
    dp[1] = 0 if 1 in A else 1
    dp[2] = 0 if 2 in A else dp[1] + 1

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

    return dp[N] % MOD

print(solve())

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7

def solve():
    N, M = map(int, input().split())
    A = [int(input()) for _ in range(M)]
    
    if M > 1:
        for i in range(M-1):
            if A[i]+1 == A[i+1]:
                return 0

    if N == 1 and M == 0:
        return 1
    elif N == 1 and M == 1 and A[0] == 0:
        return 0

    dp = [0] * (N+1)
    dp[1] = 0 if 1 in A else 1
    dp[2] = 0 if 2 in A else dp[1] + 1

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

    return dp[N] % MOD

print(solve())

Submission status: Time Limit Exceeded

Solution code:
# import bisect
# import copy
# import fractions
# import math
# import numpy as np
# from collections import Counter, deque
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product

def resolve():

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


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

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

    print(dp[N])

resolve()

Submission status: Time Limit Exceeded

Solution code:
# import bisect
# import copy
# import fractions
# import math
# import numpy as np
# from collections import Counter, deque
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product

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


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

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



resolve()

Submission status: Time Limit Exceeded

Solution code:
# import bisect
# import copy
# import fractions
# import math
# import numpy as np
# from collections import Counter, deque
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product

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


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

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



resolve()

Submission status: Time Limit Exceeded

Solution code:
# import bisect
# import copy
# import fractions
# import math
# import numpy as np
# from collections import Counter, deque
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product

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


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

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



resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys


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

d = [0] * (n + 2)
d[0] = 1
if 1 not in l:
    d[1] = 1
for i in range(n):
    if i in l and i + 1 in l:
        print(0)
        sys.exit()
    elif i in l:
        d[i + 2] = d[i + 1]
    elif i + 1 in l:
        d[i + 2] = d[i]
    else:
        d[i + 2] = d[i] + d[i + 1]
    d[i + 2] = d[i + 2] % (10 ** 9 + 7)
print(d[-2])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

N, M = map(int, input().split())
a = [0]*M
mod = 10**9+7

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

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

Submission status: Time Limit Exceeded

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

N, M = map(int, input().split())
a = [0]*M
mod = 10**9+7

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

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])%mod
        
print(DP[N])

Submission status: Time Limit Exceeded

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

N, M = map(int, input().split())
a = [0]*M
mod = 1000000007

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

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])%mod
        
print(DP[N])

Submission status: Time Limit Exceeded

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

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

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])%mod
        
print(DP[N])

Submission status: Time Limit Exceeded

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

for i in range(1,n+1):
  if i==1:
    if i not in q:
      a=1
      b=1
    else:
      a=1
      b=0
  else:
    if i in q:
      a,b=b,0
    else:
      a,b=b,(a+b)%mod
print(b)

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]
    dp[i] %= MOD
# print(dp)
print(dp[N] % MOD)