Problem:


Score : 300 points

Problem Statement

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

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

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

Constraints

1 \leq N \leq 10^5

0 \leq M \leq N-1

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

Input

Input is given from Standard Input in the following format:

N M
a_1
a_2
 .
 .
 .
a_M

Output

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

Sample Input 1

6 1
3

Sample Output 1

4

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

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

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

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

0 \to 2 \to 4 \to 6

Sample Input 2

10 2
4
5

Sample Output 2

0

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

Sample Input 3

100 5
1
23
45
67
89

Sample Output 3

608200469

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



Sample input:
6 1
3


Sample output:
4

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
a=[]
for i in range(m):
  a.append(int(input()))
b=[0 for x in range(n+1)]
b[0]=1
for i in range(n-1):
  if i+1 not in a:
    b[i+1]+=b[i]
  if i+2 not in a:
    b[i+2]+=b[i]

if n not in a:
  b[n]+=b[n-1]

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

Submission status: Time Limit Exceeded

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

a = [int(line) for line in sys.stdin]

ans = [0] * (N + 1)

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

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

p,q=(0,1)
#累積和っぽい考え
for i in range(1, n+1):
	p,q = q,(p+q)*(not i in a)
print(q%(10**9+7))

Submission status: Time Limit Exceeded

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

p,q=(0,1)
#累積和っぽい考え
for i in range(1, n+1):
	p,q = q,(p+q)*(not i in a)
print(q%x)

Submission status: Time Limit Exceeded

Solution code:
# Typical Stairs

n, m = map(int, input().split())
a = []
for i in range(m):
    a.append(int(input()))
    
if n ==1:
    print(1)
    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:
        dp[i] = 0
    else:
        dp[i] = dp[i-1] + dp[i-2]
        dp[i] = dp[i] % 1000000007

print(dp[-1])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
INF = (10 ** 9) + 7
N, M = map(int, input().split())
aLst = [0] * M

for i in range(M):
    aLst[i] = int(input())
ansLst = [0] * (N + 1)
ans = 0
ansLst[0] = 1
for i in range(1, N + 1):
    if aLst.count(i) == 1:
        continue
    tmp = ansLst[i - 1]
    if i > 1:
        tmp += ansLst[i - 2]
    ansLst[i] = tmp % INF


print(ansLst[N])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

d=[0]*(n+1)
d[0]=1
d[1]=1 if 1 not in c else 0
for j in range(2,n+1):
    if j in c:
        pass
    else:
        d[j]=(d[j-1]+d[j-2])%1000000007

print(d[n])

Submission status: Time Limit Exceeded

Solution code:
import sys,math
N,M = map(int,input().split())
a = [int(input()) for i in range(M)]
dp = [0] * (N+1)
mod = 10**9+7
for i in range(N,-1,-1):
    if i in a:
        continue
    elif i == N or i == N-1:
        dp[i] = 1
    else:
        dp[i] = (dp[i+1] + dp[i+2])%mod
print(dp[0])

Submission status: Time Limit Exceeded

Solution code:
import sys,math
N,M = map(int,input().split())
a = [int(input()) for i in range(M)]
dp = [0] * (N+1)
mod = 10**9+7
for i in range(N,-1,-1):
    if i in a:
        continue
    elif i == N or i == N-1:
        dp[i] = 1
    else:
        dp[i] = dp[i+1] + dp[i+2]
print(dp[0]%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys,math
N,M = map(int,input().split())
a = []
cnt = 0
ans = 1
fi = []
fi.append(1)
fi.append(1)
fi.append(1)
for i in range(3,10**5+2):
    tmp = fi[i-1]+fi[i-2]
    fi.append(tmp)
for i in range(M):
    a.append(int(input()))
for i in range(N+1):
    if i in a:
        if cnt == 0:
            print(0)
            sys.exit()
        else:
            ans *= fi[cnt]
            cnt = 0
    else:
        cnt += 1
ans *= fi[cnt]

print(ans % 1000000007)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
import math

n, m = map(int, input().split())
li = [int(input()) for _ in range(m)]
li.append(n+1)
ans_li=[1 for i in range(m+1)]

def counter( start, end):
    one = end-start
    two = 0
    count = 0
    while 1:
        if one < 0:
            return max(count, 1)
        count+= (math.factorial(one+two)// (math.factorial(two)*math.factorial(one)))
        one -= 2
        two += 1

start_pos = 0
for i in range(0, m+1):
    if start_pos > li[i]-1:
        ans_li[i] = 0
        break
    ans_li[i] = counter(start_pos, li[i]-1)
    start_pos = li[i]+1

ans = 1
for i in ans_li:
    ans *=i
print(ans%(10**9+7))

Submission status: Time Limit Exceeded

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

mod = 10**9 + 7

if N == 1:
  print(1)
else:
  i1 = 1
  if 1 in A:
    i2 = 0
  else:
    i2 = 1
  for n in range(2, N+1):
    i3 = (i1 + i2) % mod
    if n in A:
      i3 = 0
    if (n-1 in A) and (n in A):
      print(0)
      break
    i1, i2 = i2, i3
  else:
    ans = i3
    print(ans)

Submission status: Time Limit Exceeded

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

mod = 10**9 + 7

if N == 1:
  print(1)
else:
  i1 = 1
  if 1 in A:
    i2 = 0
  else:
    i2 = 1
  for n in range(2, N+1):
    i3 = (i1 + i2) % mod
    if n in A:
      i3 = 0
    i1, i2 = i2, i3
  ans = i3
  print(ans)

Submission status: Time Limit Exceeded

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

mod = 10**9 + 7
for n in range(N+1):
  if N == 1:
    ans = 1
    break
  elif n == 0:
    i1 = 1
  elif n == 1:
    i2 = 1
    if n in A:
      i2 = 0
  else:
    i3 = (i1 + i2) % mod
    if n in A:
      i3 = 0
    i1, i2 = i2, i3
else:
  ans = i3
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = [int(nm) for nm in input().split()]
A = [-1]
for m in range(M):
  A.append(int(input()))
A.append(N+1)

import math
total_case = 1
for m in range(M+1):
  a1 = A[m]
  a2 = A[m+1]
  safe_stairs = a2 - a1 - 1
  if safe_stairs == 0:
    print(0)
    break
  howmany_jump1 = safe_stairs - 1
  mx_jump2 = howmany_jump1 // 2
  #２のジャンプは０回～（mx_jump2）回
  case = 0
  for j2 in range(mx_jump2 + 1):
    jump2 = j2
    jump1 = howmany_jump1 - (j2 * 2)
    
    factorial_jump12 = 1
    for p in range(2, jump1+jump2+1):
      factorial_jump12 *= p
    
    factorial_jump1 = 1
    for q in range(2, jump1+1):
      factorial_jump1 *= q
    
    factorial_jump2 = 1
    for r in range(2, jump2+1):
      factorial_jump2 *= r
    
    c = factorial_jump12 // (factorial_jump1 * factorial_jump2)
    case += c
  total_case *= case
else:
  ans = total_case % (10**9 + 7)
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = [int(nm) for nm in input().split()]
A = [-1]
for m in range(M):
  A.append(int(input()))
A.append(N+1)

import math
total_case = 1
for m in range(M+1):
  a1 = A[m]
  a2 = A[m+1]
  safe_stairs = a2 - a1 - 1
  if safe_stairs == 0:
    print(0)
    break
  elif safe_stairs==1 or safe_stairs==2:
    total_case *= 1
    continue
  elif safe_stairs==3:
    total_case *= 2
    continue
  howmany_jump1 = safe_stairs - 1
  mx_jump2 = howmany_jump1 // 2
  #２のジャンプは０回～（mx_jump2）回
  case = 0
  for j2 in range(mx_jump2 + 1):
    jump2 = j2
    jump1 = howmany_jump1 - (j2 * 2)
    c = math.factorial(jump1 + jump2) // (math.factorial(jump1) * math.factorial(jump2))
    case += c
  total_case *= case
else:
  ans = total_case % (10**9 + 7)
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = [int(nm) for nm in input().split()]
A = [-1]
for m in range(M):
  A.append(int(input()))
A.append(N+1)

import math
total_case = 1
for m in range(M+1):
  a1 = A[m]
  a2 = A[m+1]
  safe_stairs = a2 - a1 - 1
  if safe_stairs == 0:
    print(0)
    break
  elif safe_stairs==1 or safe_stairs==2:
    total_case *= 1
    continue
  howmany_jump1 = safe_stairs - 1
  mx_jump2 = howmany_jump1 // 2
  #２のジャンプは０回～（mx_jump2）回
  case = 0
  for j2 in range(mx_jump2 + 1):
    jump2 = j2
    jump1 = howmany_jump1 - (j2 * 2)
    c = math.factorial(jump1 + jump2) // (math.factorial(jump1) * math.factorial(jump2))
    case += c
  total_case *= case
else:
  ans = total_case % (10**9 + 7)
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = [int(nm) for nm in input().split()]
a1 = -1

import math
total_case = 1
for m in range(M+1):
  if m != M:
    a2 = int(input())
  else:
    a2 = N + 1
  safe_stairs = a2 - a1 - 1
  if safe_stairs == 0:
    print(0)
    break
  howmany_jump1 = safe_stairs - 1
  mx_jump2 = howmany_jump1 // 2
  #２のジャンプは０回～（mx_jump2）回
  case = 0
  for j2 in range(mx_jump2 + 1):
    jump2 = j2
    jump1 = howmany_jump1 - (j2 * 2)
    c = math.factorial(jump1 + jump2) // (math.factorial(jump1) * math.factorial(jump2))
    case += c
  total_case *= case
  a1 = a2
else:
  ans = total_case % (10**9 + 7)
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = [int(nm) for nm in input().split()]
A = [-1]
for m in range(M):
  A.append(int(input()))
A.append(N+1)

import math
total_case = 1
for m in range(M+1):
  a1 = A[m]
  a2 = A[m+1]
  safe_stairs = a2 - a1 - 1
  if safe_stairs == 0:
    print(0)
    break
  howmany_jump1 = safe_stairs - 1
  mx_jump2 = howmany_jump1 // 2
  #２のジャンプは０回～（mx_jump2）回
  case = 0
  for j2 in range(mx_jump2 + 1):
    jump2 = j2
    jump1 = howmany_jump1 - (j2 * 2)
    c = math.factorial(jump1 + jump2) // (math.factorial(jump1) * math.factorial(jump2))
    case += c
  total_case *= case
else:
  ans = total_case % (10**9 + 7)
  print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

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

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

print(dp[0] % MOD)

Submission status: Time Limit Exceeded

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

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

dp = [0] * (N + 2)
dp[N] = 1
for i in reversed(range(N)):
    if i in broken:
        dp[i] = 0
        if len(broken) != 0:
            broken.pop(-1)
        continue
    dp[i] = (dp[i+1] + dp[i+2]) % MOD

print(dp[0])

Submission status: Time Limit Exceeded

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

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

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

print(dp[0])

Submission status: Time Limit Exceeded

Solution code:
import sys
N, M = map(int,input().split())
x = [int(input()) for i in range(M)]
for i in range(len(x)-1):
    if x[i]+1 == x[i+1]:
        print(0)
        sys.exit()

a,b = 1,0
for i in range(1,N+1):
    if i - 2 in x:
        a,b = a, a
    elif i-1 in x:
        a,b = b,a
    else:
        a,b = a+b,a
    a %= 1000000007
    b %= 1000000007
print(a)

Submission status: Time Limit Exceeded

Solution code:
import  sys
N, M = map(int,input().split())
x = [int(input()) for i in range(M)]
for i in range(len(x)-1):
    if x[i]+1 == x[i+1]:
        print(0)
        sys.exit()

a,b = 1,0
for i in range(1,N+1):
    if i - 2 in x:
        a,b = a, a
    elif i-1 in x:
        a,b = b,a
    else:
        a,b = a+b,a
    a %= 1000000007
print(a)

Submission status: Time Limit Exceeded

Solution code:
N, B = map(int, input().split())
ana = []
dp = [0] * (N+2)

for i in range(B):
    ana.append(int(input()))

mod = 1000000007

dp[N] = 1
for i in reversed(range(N)):
    if i in ana:
        dp[i] = 0
        ana.pop(len(ana)-1)
        continue
    dp[i] = dp[i + 1] + dp[i + 2]
print(dp[0] % mod)

Submission status: Time Limit Exceeded

Solution code:
N, B = map(int, input().split())
ana = []
dp = [0] * (N+2)

for i in range(B):
    ana.append(int(input()))

mod = 1000000007

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

Submission status: Time Limit Exceeded

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)

#  f = open('C_input_29.txt')
#  lines = f.readlines()
#  f.close()
#  N, M = map(int, lines[0].split())
#  A = []
#  for line in lines[1:]:
#      A.append(int(line))

N, M = LI()
A = [_I() for i in range(M)]

#  if M != 0:
#      # 連続した壊れた段がある場合は0
#      B = [i for i in A]
#      B.remove(B[0])
#      B.append(10**15+100)
#      diffs = [b - a for a, b in zip(A,B)]
#      #  print(diffs)

#      if any(i == 1 for i in diffs):
#          # 隣同士なので0
#          print(0)
#          exit()
#  print('hoge')
"""
考え方
xにたどり着く通りは、x-1とx-2段目にたどり着く通りの合計
dp
3が障害のとき
1へは1通り
2へは0からと1からの2通り
3へは0通り
4へは2からの2通りと、3からの0通りで2通り
5へは3からの0通りと4からの2通りで2通り
6へは4からの2通りと5からの2通りで4通り
"""
#  dp = {}
dp = [0 for i in range(N+1)]
#  print('fua')
dp[0] = 1
dp[1] = 1 if 1 not in A else 0
#  [dp.update({i: (dp[i-1] + dp[i-2])%mod}) if i not in A else dp.update({i: 0}) for i in range(2, N+1)]
for i in range(2, N+1):
    #  print(i)
    # i段目までの通りを計算する
    if i not in A:
        # i段目が障害のときは0になっているので飛ばす
        dp[i] = dp[i-1] + dp[i-2]
        dp[i] %= mod

print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)

#  f = open('C_input_29.txt')
#  lines = f.readlines()
#  f.close()
#  N, M = map(int, lines[0].split())
#  A = []
#  for line in lines[1:]:
#      A.append(int(line))

N, M = LI()
A = []
for i in range(M):
    A.append(_I())

#  if M != 0:
#      # 連続した壊れた段がある場合は0
#      B = [i for i in A]
#      B.remove(B[0])
#      B.append(10**15+100)
#      diffs = [b - a for a, b in zip(A,B)]
#      #  print(diffs)

#      if any(i == 1 for i in diffs):
#          # 隣同士なので0
#          print(0)
#          exit()
#  print('hoge')
"""
考え方
xにたどり着く通りは、x-1とx-2段目にたどり着く通りの合計
dp
3が障害のとき
1へは1通り
2へは0からと1からの2通り
3へは0通り
4へは2からの2通りと、3からの0通りで2通り
5へは3からの0通りと4からの2通りで2通り
6へは4からの2通りと5からの2通りで4通り
"""
#  dp = {}
dp = [0 for i in range(N+1)]
#  print('fua')
dp[0] = 1
dp[1] = 1 if 1 not in A else 0
#  [dp.update({i: (dp[i-1] + dp[i-2])%mod}) if i not in A else dp.update({i: 0}) for i in range(2, N+1)]
for i in range(2, N+1):
    #  print(i)
    # i段目までの通りを計算する
    if i not in A:
        # i段目が障害のときは0になっているので飛ばす
        dp[i] = dp[i-1] + dp[i-2]
        dp[i] %= mod

print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)

#  f = open('C_input_29.txt')
#  lines = f.readlines()
#  f.close()
#  N, M = map(int, lines[0].split())
#  A = []
#  for line in lines[1:]:
#      A.append(int(line))

N, M = LI()
A = []
for i in range(M):
    A.append(_I())

#  if M != 0:
#      # 連続した壊れた段がある場合は0
#      B = [i for i in A]
#      B.remove(B[0])
#      B.append(10**15+100)
#      diffs = [b - a for a, b in zip(A,B)]
#      #  print(diffs)

#      if any(i == 1 for i in diffs):
#          # 隣同士なので0
#          print(0)
#          exit()
#  print('hoge')
"""
考え方
xにたどり着く通りは、x-1とx-2段目にたどり着く通りの合計
dp
3が障害のとき
1へは1通り
2へは0からと1からの2通り
3へは0通り
4へは2からの2通りと、3からの0通りで2通り
5へは3からの0通りと4からの2通りで2通り
6へは4からの2通りと5からの2通りで4通り
"""
#  dp = {}
dp = [0 for i in range(N+1)]
#  print('fua')
dp[0] = 1
dp[1] = 1 if 1 not in A else 0
#  [dp.update({i: (dp[i-1] + dp[i-2])%mod}) if i not in A else dp.update({i: 0}) for i in range(2, N+1)]
for i in range(2, N+1):
    #  print(i)
    # i段目までの通りを計算する
    if i not in A:
        # i段目が障害のときは0になっているので飛ばす
        dp[i] = (dp[i-1] + dp[i-2])
        dp[i] %= mod

print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)

#  f = open('C_input_29.txt')
#  lines = f.readlines()
#  f.close()
#  N, M = map(int, lines[0].split())
#  A = []
#  for line in lines[1:]:
#      A.append(int(line))

N, M = LI()
A = []
for i in range(M):
    A.append(_I())

#  if M != 0:
#      # 連続した壊れた段がある場合は0
#      B = [i for i in A]
#      B.remove(B[0])
#      B.append(10**15+100)
#      diffs = [b - a for a, b in zip(A,B)]
#      #  print(diffs)

#      if any(i == 1 for i in diffs):
#          # 隣同士なので0
#          print(0)
#          exit()
#  print('hoge')
"""
考え方
xにたどり着く通りは、x-1とx-2段目にたどり着く通りの合計
dp
3が障害のとき
1へは1通り
2へは0からと1からの2通り
3へは0通り
4へは2からの2通りと、3からの0通りで2通り
5へは3からの0通りと4からの2通りで2通り
6へは4からの2通りと5からの2通りで4通り
"""
#  dp = {}
dp = [0 for i in range(N+1)]
#  print('fua')
dp[0] = 1
dp[1] = 1 if 1 not in A else 0
#  [dp.update({i: (dp[i-1] + dp[i-2])%mod}) if i not in A else dp.update({i: 0}) for i in range(2, N+1)]
for i in range(2, N+1):
    #  print(i)
    # i段目までの通りを計算する
    if i not in A:
        # i段目が障害のときは0になっているので飛ばす
        dp[i] = (dp[i-1] + dp[i-2]) % mod

print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)

#  f = open('C_input_29.txt')
#  lines = f.readlines()
#  f.close()
#  N, M = map(int, lines[0].split())
#  A = []
#  for line in lines[1:]:
#      A.append(int(line))

N, M = LI()
A = []
for i in range(M):
    A.append(_I())

if M != 0:
    # 連続した壊れた段がある場合は0
    B = [i for i in A]
    B.remove(B[0])
    B.append(10**15+100)
    diffs = [b - a for a, b in zip(A,B)]
    #  print(diffs)

    if any(i == 1 for i in diffs):
        # 隣同士なので0
        print(0)
        exit()
#  print('hoge')
"""
考え方
xにたどり着く通りは、x-1とx-2段目にたどり着く通りの合計
dp
3が障害のとき
1へは1通り
2へは0からと1からの2通り
3へは0通り
4へは2からの2通りと、3からの0通りで2通り
5へは3からの0通りと4からの2通りで2通り
6へは4からの2通りと5からの2通りで4通り
"""
#  dp = {}
dp = [0 for i in range(N+1)]
#  print('fua')
dp[0] = 1
dp[1] = 1 if 1 not in A else 0
#  [dp.update({i: (dp[i-1] + dp[i-2])%mod}) if i not in A else dp.update({i: 0}) for i in range(2, N+1)]
for i in range(2, N+1):
    #  print(i)
    # i段目までの通りを計算する
    if i in A:
        # i段目が障害のときは0になっているので飛ばす
        #  dp[i] = 0
        continue
    
    dp[i] = (dp[i-1] + dp[i-2]) % mod

print(dp[N] % mod)

Submission status: Time Limit Exceeded

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)

#  f = open('C_input_29.txt')
#  lines = f.readlines()
#  f.close()
#  N, M = map(int, lines[0].split())
#  A = []
#  for line in lines[1:]:
#      A.append(int(line))

N, M = LI()
A = []
for i in range(M):
    A.append(_I())

if M != 0:
    # 連続した壊れた段がある場合は0
    B = [i for i in A]
    B.remove(B[0])
    B.append(10**15+100)
    diffs = [b - a for a, b in zip(A,B)]
    #  print(diffs)

    if any(i == 1 for i in diffs):
        # 隣同士なので0
        print(0)
        exit()
#  print('hoge')
"""
考え方
xにたどり着く通りは、x-1とx-2段目にたどり着く通りの合計
dp
3が障害のとき
1へは1通り
2へは0からと1からの2通り
3へは0通り
4へは2からの2通りと、3からの0通りで2通り
5へは3からの0通りと4からの2通りで2通り
6へは4からの2通りと5からの2通りで4通り
"""
dp = {}
#  print('fua')
dp[0] = 1
dp[1] = 1 if 1 not in A else 0
[dp.update({i: (dp[i-1] + dp[i-2])%mod}) if i not in A else dp.update({i: 0}) for i in range(2, N+1)]
#  for i in range(2, N+1):
#      print(i)
#      # i段目までの通りを計算する
#      if i in A:
#          # i段目が障害のときは0になっているので飛ばす
#          dp[i] = 0
#          continue
    
#      dp[i] = dp[i-1] + dp[i-2]

print(dp[N] % mod)

Submission status: Time Limit Exceeded

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)

#  f = open('C_input_29.txt')
#  lines = f.readlines()
#  f.close()
#  N, M = map(int, lines[0].split())
#  A = []
#  for line in lines[1:]:
#      A.append(int(line))

N, M = LI()
A = []
for i in range(M):
    A.append(_I())

if M != 0:
    # 連続した壊れた段がある場合は0
    B = [i for i in A]
    B.remove(B[0])
    B.append(10**15+100)
    diffs = [b - a for a, b in zip(A,B)]
    #  print(diffs)

    if any(i == 1 for i in diffs):
        # 隣同士なので0
        print(0)
        exit()
#  print('hoge')
"""
考え方
xにたどり着く通りは、x-1とx-2段目にたどり着く通りの合計
dp
3が障害のとき
1へは1通り
2へは0からと1からの2通り
3へは0通り
4へは2からの2通りと、3からの0通りで2通り
5へは3からの0通りと4からの2通りで2通り
6へは4からの2通りと5からの2通りで4通り
"""
dp = {}
#  print('fua')
dp[0] = 1
dp[1] = 1 if 1 not in A else 0
[dp.update({i: dp[i-1] + dp[i-2]}) if i not in A else dp.update({i:0}) for i in range(2, N+1)]
#  for i in range(2, N+1):
#      print(i)
#      # i段目までの通りを計算する
#      if i in A:
#          # i段目が障害のときは0になっているので飛ばす
#          dp[i] = 0
#          continue
    
#      dp[i] = dp[i-1] + dp[i-2]

print(dp[N] % mod)