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()
for i in range(m):
    a = int(input())
    A.append(a)
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-2] + dp[i-1]
        dp[i] = dp[i]%1000000007
print(dp[-1]%1000000007)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7

import sys
input = sys.stdin.readline

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

# 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):
    dp[i] = (dp[i-1] + dp[i-2]) % MOD if i not in a else 0

print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7

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

# 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):
    dp[i] = (dp[i-1] + dp[i-2]) % MOD if i not in a else 0

print(dp[-1])

Submission status: Time Limit Exceeded

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

MOD = 1000000007

# DPテーブル
dp = [0]*(N+1)
dp[0] = 1
if 1 not in A:  # 1段目が壊れている場合もあるので注意
    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[-1])

Submission status: Time Limit Exceeded

Solution code:
l = input().split()
N = int(l[0])
M = int(l[1])

A = []
for i in range(M):
    l = input().split()
    A.append(int(l[0]))

mod = 1000000007

# print(N, M, A)

DP = [0]*(N+2)
DP[0] = 1
for i in range(N):
    if i in A:
        continue
    DP[i + 1] = (DP[i] + DP[i + 1]) % mod
    DP[i + 2] = (DP[i] + DP[i + 2]) % mod
print(DP[N])

Submission status: Time Limit Exceeded

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

l = list(range(1, n+1))
divider = 10**9 + 7
ans = [0]*(n + 1)
ans[0] = 1
ans[1] = 1

for i in range(m):
    inp = int(input())
    l.remove(inp)
    if inp == 1:
        ans[1] = 0

if 1 in l:
    l.remove(1)

for i in l:
    ans[i] = ans[i-1] + ans[i-2]
    
   
print(ans[n] % divider)

Submission status: Time Limit Exceeded

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

divider = 10**9 + 7
ans = [0]*(n + 1)
ans[0] = 1
ans[1] = 1
l = list(range(2, n+1))

if 1 in s:
    ans[1] = 0
    s.remove(1)


for i in s:
    l.remove(i)   

for i in l:
    ans[i] = ans[i-1] + ans[i-2]
    
   
print(ans[n] % divider)

Submission status: Time Limit Exceeded

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

divider = 10**9 + 7
ans = [0]*(n + 1)
ans[0] = 1
ans[1] = 1

if 1 in s:
    ans[1] = 0
        
for i in range(2, n+1):
    
    if i in s:
        continue
    else:
        ans[i] = ans[i-1] + ans[i-2]
    
   
print(ans[n] % divider)

Submission status: Time Limit Exceeded

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

divider = 10**9 + 7
ans = [0]*(n + 1)
ans[0] = 1
ans[1] = 1

if 1 in s:
    ans[1] = 0
        
for i in range(2, n+1):
    
    ans[i] = ans[i-1] + ans[i-2]
    if i in s:
        ans[i] = 0
   
print(ans[n] % divider)

Submission status: Time Limit Exceeded

Solution code:
n, m = [int(i) for i in input().split(" ")]
s = [int(input()) for _ in range(m)]
divider = 10**9 + 7
ans = [0]*(n + 1)
ans[0] = 1
ans[1] = 1

for j in [0,1]:
    if j in s:
        ans[j] = 0
        
for i in range(2, n+1):
    
    ans[i] = ans[i-1] + ans[i-2]
    if i in s:
        ans[i] = 0
   
print(ans[n] % divider)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
mod = 1000000007
n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
ans = 0
dp = [0] * (n+1)
dp[0] = 1
for i in range(n):
    dp[i] %= mod
    if i in a:
        continue
    if i + 1 <= n:
        dp[i+1] += dp[i]
    if i + 2 <= n:
        dp[i+2] += dp[i]
print(dp[n] % mod)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
Num = 10 ** 9 + 7
N, M = map(int, input().split())
danger = []
for i in range(M):
  danger.append(int(input()))
l = [1, 1]
for i in range(1, N):
  if i in danger:
    l[1] = 0
  l = [l[1] % Num, l[0] + l[1]]
  if l == [0, 0]:
    break
if N in danger:
  l[1] = 0
print(l[1] % Num)

Submission status: Time Limit Exceeded

Solution code:
Num = 10 ** 9 + 7
N, M = map(int, input().split())
danger = []
for i in range(M):
  danger.append(int(input()))
l = [1, 1]
for i in range(1, N):
  if i in danger:
    l[1] = 0
  l = [l[1] % Num, (l[0] + l[1]) % Num]
  if l == [0, 0]:
    break
if N in danger:
  l[1] = 0
print(l[1])

Submission status: Time Limit Exceeded

Solution code:
Num = 10 ** 9 + 7
N, M = map(int, input().split())
danger = []
for i in range(M):
  danger.append(int(input()))
l = [1, 1]
for i in range(1, N):
  if i in danger:
    l[1] = 0
  l = [l[1] % Num, (l[0] + l[1]) % Num]
if N in danger:
  l[1] = 0
print(l[1])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

for i in range(1, n+1):
    dp[i] = (dp[i-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 = [int(x) for x in input().split()]
a = []
for _ in range(m):
    a.append(int(input()))

mod = 1000000007

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

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

print(dp[n])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N,M,*a=map(int,open(0).read().split())
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
    dp[i]=(dp[i-1]+dp[i-2])
print(dp[-1]%1000000007)

Submission status: Time Limit Exceeded

Solution code:
N,M,*a=map(int,open(0).read().split())
dp=[1]*(N+1)
for i in a:
    dp[i]=0
for i in range(2,N+1):
    if i in a:
        continue
    dp[i]=(dp[i-1]+dp[i-2])%1000000007
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
N,M,*a=map(int,open(0).read().split())
dp=[1]*(N+1)
for i in a:
    dp[i]=0
for i in range(2,N+1):
    if i in a:
        continue
    dp[i]=dp[i-1]+dp[i-2]
print(dp[-1]%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 i in a:
    dp[i]=0
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]
print(dp[-1]%1000000007)

Submission status: Time Limit Exceeded

Solution code:
N,M,*a=map(int,open(0).read().split())
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]
print(dp[-1]%1000000007)

Submission status: Time Limit Exceeded

Solution code:

def main(N, M, a):
    dp = [0] * (N+1)
    dp[0] = 1
    dp[1] = 1 if 1 not in a else 0
    for i in range(2, len(dp)):
        dp[i] = dp[i-1] + dp[i-2] if i not in a else 0
    return dp[-1] % (10**9+7)

N, M = map(int, input().split())
a = list(int(input()) for _ in range(M))
print(main(N,M,a))

Submission status: Time Limit Exceeded

Solution code:
def calculate(n, bindexes):
    arr = []
    for i in range(n):
        if bindexes.__contains__(i):
            arr.append(0)
            continue

        if i == 0:
            arr.append(1)
        elif i == 1:
            arr.append(arr[i-1] + 1)
        else:
            arr.append(arr[i-1] + arr[i-2])
    return arr

S = input().split(" ")

n = int(S[0])
m = int(S[1])
brokenStairIndexes = []

for i in range(m):
    brokenStairIndexes.append(int(input())-1)

arr = calculate(n,brokenStairIndexes)

print(arr[n-1] % 1000000007)

Submission status: Time Limit Exceeded

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

dp = [0] * (n + 1)
dp[0] = 1
MOD = 10 ** 9 + 7
for i in range(1, n + 1):
    if i in s:
        continue
    x = dp[i - 1]
    if i > 1:
        x += dp[i - 2]
    dp[i] = x % MOD

print(dp[n])

Submission status: Time Limit Exceeded

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


dp = [0] * (n + 1)
dp[0] = 1
MOD = 10 ** 9 + 7
for i in range(1, n + 1):
    if i not in s:
        x = dp[i - 1]
        if i > 1:
            x += dp[i - 2]
        dp[i] = x % MOD

print(dp[n])

Submission status: Time Limit Exceeded

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

dp = [0] * (n + 1)
dp[0] = 1
MOD = 10 ** 9 + 7
for i in range(1, n + 1):
    if i not in s:
        x = dp[i - 1]
        if i > 1:
            x += dp[i - 2]
        dp[i] = x % MOD

print(dp[n])

Submission status: Time Limit Exceeded

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

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

for i in range(1, n + 1):
    if i not in s:
        x = dp[i - 1]
        if i > 1:
            x += dp[i - 2]
        x %= 10 ** 9 + 7
        dp[i] = x

print(dp[n])

Submission status: Time Limit Exceeded

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

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

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

print(dp[n])

Submission status: Time Limit Exceeded

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

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

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

print(dp[n])

Submission status: Time Limit Exceeded

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys

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

dp = [0] * (N+3)

if 1 in li:
  dp[1] = 0
  dp[2] = 1
else:
  dp[1] = 1
  dp[2] = 2
  
if 2 in li:
  dp[2] = 0

for n in range(1, N+1):
  if n == 1 or n == 2:
    continue
  
  if n in li:
    if flag:
      print(0)
      sys.exit()
    
    flag = True
    continue
  
  dp[n] = (dp[n-1] + dp[n-2]) % 1000000007
  flag = False
  
print(dp[N])

Submission status: Time Limit Exceeded

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

dp = [0] * (n + 10)

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

print(dp[n] % 1000000007)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

f = [0]*(n+3)
f[0] = 1
endf = 0
for i in range(1,n+1):
    if i in xx:
        endf += 1
        if endf ==2:
            print(0)
            break
        continue
    else :
        if endf == 1:
            endf = 0
            f[i] = f[i-2]
        else :
            endf = 0
            f[i] = f[i-1] + f[i-2]
else:
    print(f[n]%1000000007)

Submission status: Time Limit Exceeded

Solution code:
from operator import mul
from functools import reduce

mod = 10 ** 9 + 7
def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

def pat(n):
  cnt = 0
  for i in range(n//2 + 1):
    cnt += int(combinations_count(n - i, i))
  return cnt

n, m = map(int, input().split())
a = []
start = 0
cnt = 1
for i in range(m):
  ko = int(input())
  end = ko - 1
  cnt = cnt * pat(end - start)
  start = ko + 1
cnt = cnt * pat(n - start)

print(cnt % mod)

Submission status: Time Limit Exceeded

Solution code:
from operator import mul
from functools import reduce

mod = 10 ** 9 + 7
def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

def pat(n):
  cnt = 0
  for i in range(n//2 + 1):
    cnt += int(combinations_count(n - i, i))
  return cnt

n, m = map(int, input().split())
a = []
start = 0
cnt = 1
for i in range(m):
  ko = int(input())
  end = ko - 1
  cnt = cnt * pat(end - start)
  start = ko + 1
cnt = cnt * pat(n - start)

print(cnt % mod)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

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

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

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

#print(dp)
print(dp[-1]%mod)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

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

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

#print(dp)
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

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 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]
        dp[i] = dp[i]%mod
    else:
        dp[i] = 0

#print(dp)
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys

N, M = list(map(int, input().split()))
if M == 0:
  h = []
else:
  h = np.array(sys.stdin.readlines()).flatten().astype(int)

if N==1:
  print(1)
elif N==2:
  if M==1:
    print(1)
  else:
    print(2)
else:
  DP = np.zeros(N+1)
  DP[0] = 1
  if 1 in h:
    DP[1] = -1
  else:
    DP[1] = 1
  for i in range(2,N+1):
    if DP[i-2]<0 and DP[i-1]<0:
      print(0)
      exit()
    if i in h:
      DP[i] = -1
    else:
      if DP[i-1]>=0:
        DP[i] += DP[i-1]
      if DP[i-2]>=0:
        DP[i] += DP[i-2]
      DP[i] = DP[i] % 1000000007
  print(int(DP[N]))

Submission status: Time Limit Exceeded

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

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


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

print(dp[n] % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
input = sys.stdin.readline
N,M=map(int,input().split())
A=[0]*M
for i in range(M):
    A[i]=int(input())
#print(A)
def dp(n):
    dp=[0]*(N+1)
    dp[0]=1
    dp[1]=0 if 1 in A else 1
    for i in range(N-1):
        if (i+2) in A:
            dp[i+2]=0
        else:
            dp[i+2]=dp[i+1]+dp[i]
    return dp[n]
print(dp(N)%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
N,M=map(int,input().split())
A=[0]*M
for i in range(M):
    A[i]=int(input())
#print(A)
def dp(n):
    dp=[0]*(N+1)
    dp[0]=1
    dp[1]=0 if 1 in A else 1
    for i in range(N-1):
        if (i+2) in A:
            dp[i+2]=0
        else:
            dp[i+2]=dp[i+1]+dp[i]
    return dp[n]
print(dp(N)%(10**9+7))

Submission status: Time Limit Exceeded

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

t2 = 1
t1 = 0 if 1 in l else 1

if n == 1:
  print(1)
else:
  for i in range(2,n+1):
    if l == [] or i != l[0]:
      t0 = 0 if i in l else (t2+t1)%mod
    else:
      l.pop(0)
      t0 = 0
    t2 = t1
    t1 = t0
  print(t0)

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

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

#print(dp)
print(dp[-1]%1000000007)

Submission status: Time Limit Exceeded

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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
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 I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n,m=LI()
  l=[I() for _ in range(m)]

  dp=[0 for _ in range(n+1)]
  dp[0]=1
  for i in range(n):
    for j in range(1,3):
      if i+j<=n and i not in l:
        dp[i+j]+=dp[i]

  # print(dp)
  return dp[n]%mod

# main()
print(main())

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
hole_ids = [int(input()) - 1 for _ in range(m)]
X = 1000000007


def solve(n, hole_ids):
    # nums = []
    nums = [0] * n
    for i in range(n):
        if i in hole_ids:
            # nums.append(0)
            nums[i] = 0
            continue

        if i == 0:
            # nums.append(1)
            nums[i] = 1
        elif i == 1:
            # 1つ前から1段上がるから2つ前から2個飛ばし
            # nums.append(nums[-1] + 1)
            nums[i] = nums[i-1] + 1
        else:
            # nums.append((nums[-1] % X + nums[-2] % X) % X)
            nums[i] = (nums[i-1] + nums[i-2]) % X
    return nums[-1]


print(solve(n, hole_ids))

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
hole_ids = [int(input()) - 1 for _ in range(m)]
X = 1000000007


def solve(n, hole_ids):
    nums = []
    for i in range(n):
        if i in hole_ids:
            nums.append(0)
            continue

        if i == 0:
            nums.append(1)
        elif i == 1:
            # 1つ前から1段上がるから2つ前から2個飛ばし
            nums.append(nums[-1] + 1)
        else:
            nums.append((nums[-1] % X + nums[-2] % X) % X)
    return nums[-1]


print(solve(n, hole_ids))

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
hole_ids = [int(input()) - 1 for _ in range(m)]
X = 1000000007


def solve(n, hole_ids):
    nums = []
    for i in range(n):
        if i in hole_ids:
            nums.append(0)
            continue

        if i == 0:
            nums.append(1)
        elif i == 1:
            # 1つ前から1段上がるから2つ前から2個飛ばし
            nums.append(nums[-1] + 1)
        else:
            nums.append((nums[-1] + nums[-2]) % X)
    return nums[-1]


print(solve(n, hole_ids))

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
hole_ids = [int(input()) - 1 for _ in range(m)]
X = 1000000007


def solve(n, hole_ids):
    nums = []
    for i in range(n):
        if i in hole_ids:
            nums.append(0)
            continue

        if i == 0:
            nums.append(1)
        elif i == 1:
            # 1つ前から1段上がるから2つ前から2個飛ばし
            nums.append(nums[-1] + 1)
        else:
            nums.append(nums[-1] + nums[-2])
    return nums[-1]


print(solve(n, hole_ids) % X)

Submission status: Time Limit Exceeded

Solution code:
MOD = 1e9 + 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:
        continue
    if i > 1:
        dp[i] = (dp[i-1] + dp[i-2]) % MOD
    else:
        dp[i] = dp[i-1]

print(int(dp[n]))

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
mod = 10 ** 9 + 7
li=[int(input()) for i in range(m)] # 壊れてる段

for i in range(n+1):
  # i-2までがa, i-1までがb
  if i == 0:
    a=1
  elif i == 1:
    if 1 in li:
      a,b=1,0
    else:
      a,b=1,1
  else:
    if i-2 in li and i-1 in li:
      print(0)
      exit()
    elif i-2 in li and i-1 not in li:
      a,b = b,b
    elif i-2 not in li and i-1 in li:
      a,b = 0,a
    else:
      a,b = b,(a+b) % mod
print(b)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial
from operator import mul
from functools import reduce

def c(n,r):
  r = min(n-r,r)
  if r == 0 or r == n:
    return 1
  else:
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under
def num(k): # k段昇る場合の数
  l,r = k // 2, 0
  for i in range(l+1):
    r += c(k-i,i)
    r %= mod
  return r

n,m=map(int,input().split())
mod = 10 ** 9 + 7

if m == 0:
  print(num(n) % mod)
  exit()

a=[int(input()) for i in range(m)] # 壊れてる段

# ここから先 m > 0
a = [-1] + a + [n+1] # len(a)=m+2
sa = [a[i+1]-a[i]-2 for i in range(len(a)-1)]
ans = 1
#print(sa)
for i in sa:
  ans *= num(i)
  ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial
def c(n,k):
  a = factorial(n) // factorial(k) // factorial(n - k)
  return a
def num(k): # k段昇る場合の数
  l,r = k // 2, 0
  for i in range(l+1):
    r += c(k-i,i)
    r %= mod
  return r

n,m=map(int,input().split())
mod = 10 ** 9 + 7

if m == 0:
  print(num(n) % mod)
  exit()

a=[int(input()) for i in range(m)] # 壊れてる段

# ここから先 m > 0
a = [-1] + a + [n+1] # len(a)=m+2
sa = [a[i+1]-a[i]-2 for i in range(len(a)-1)]
ans = 1
#print(sa)
for i in sa:
  ans *= num(i)
  ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial
def c(n,k):
  a = factorial(n) // factorial(k) // factorial(n - k)
  return a
def num(k): # k段昇る場合の数
  l,r = k // 2, 0
  for i in range(l+1):
    r += c(k-i,i)
    r %= mod
  return r

n,m=map(int,input().split())
mod = 10 ** 9 + 7

if m == 0:
  print(num(n) % mod)
  exit()

a=[int(input()) for i in range(m)] # 壊れてる段

# ここから先 m > 0
a = [-1] + a + [n+1] # len(a)=m+2
sa = [a[i+1]-a[i]-2 for i in range(len(a)-1)]
ans = 1
#print(sa)
for i in sa:
  ans *= num(i)
  ans %= mod
print(ans)

Submission status: Time Limit Exceeded

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

broken = []
for _ in range(m):
  broken.append(int(input()))
  
dp = [0] * (n + 1)

dp[0] = 1
if 1 not in broken:
  dp[1] = 1

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

Submission status: Time Limit Exceeded

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

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

print(memo[n])

Submission status: Time Limit Exceeded

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

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

print(memo[n]%1000000007)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
brokensteps = [int(input()) for x in range(m)]
dp = [0] * (n+1)
for i in range(n+1):
    if i in brokensteps:
        dp[i] = 0
        continue
    
    elif i <= 1:
        dp[i] = 1

    else:
        dp[i] = (dp[i-1]%(10**9+7) + dp[i-2]%(10**9+7))%(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)]

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

print(r[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())

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

print(r[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())

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

print(r[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())


r1 = 1
if 1 in a:
  r = 0
else:
  r = 1
for i in range(2, n+1):
  r2 = r1
  r1 = r
  if i in a:
    r = 0
  elif r1 == 0 and r2 == 0:
    r = 0
    break
  else:
    r = (r1 + r2)%1000000007

print(r)

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


r1 = 1
if 1 in a:
  r = 0
else:
  r = 1
for i in range(2, n+1):
  r2 = r1
  r1 = r
  if i in a:
    r = 0
  elif r1 == 0 and r2 == 0:
    r = 0
    break
  else:
    r = r1 + r2

print(r%1000000007)

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


r1 = 1
if 1 in a:
  r = 0
else:
  r = 1
for i in range(2, n+1):
  r2 = r1
  r1 = r
  if i in a:
    r = 0
  else:
    r = r1 + r2

print(r%1000000007)

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

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

print(r[n]%1000000007)