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 = [int(input()) for i in range(M)]

dp = [0]*(N+1)

dp[0] = 1
for now in range(N+1):
    next1 = now + 1
    next2 = now + 2
    if next1 <= N:
        if next1 not in A:
            dp[next1] += dp[now]
    if next2 <= N:
        if next2 not in A:
            dp[next2] += dp[now]
print(dp[N]%1000000007)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from decimal import Decimal
import numpy as np
from math import factorial
# [【Python】組み合わせ\(nCr\) 計算の高速化 \- Qiita](https://qiita.com/derodero24/items/91b6468e66923a87f39f#%E6%97%A2%E5%AD%98%E3%83%84%E3%83%BC%E3%83%AB%E3%82%92%E7%94%A8%E3%81%84%E3%81%9F%E6%89%8B%E6%B3%95%EF%BC%93%E8%A9%95%E4%BE%A1-)
# [floating point \- How to manage division of huge numbers in Python? \- Stack Overflow](https://stackoverflow.com/questions/27946595/how-to-manage-division-of-huge-numbers-in-python)
 
 
def get_pattern(num):
    ret = 0
 
    if num == 1:
        ret = 1
    else:
        for i in range(int(num / 2) + 1):
            n = num - i
            r = i
            tmp = factorial(n) // factorial(r) // factorial(n - r)
            ret = ret + tmp
 
    return int(ret)
 
 
if __name__ == '__main__':
    N, M = [int(x) for x in stdin.readline().rstrip().split()]
    a = [int(input()) for i in range(M)]
 
    ret = 1
 
    # M = 0 以外のとき
    for j in range(M):
 
        if j == 0:
            # 0マス目からa[j]-1マスまで移動するパターン数
            ret = ret * get_pattern(a[j]-1)
        elif a[j] - a[j-1] == 1:
            # 危険個所が連続していてパターン最後まで移動できるパターンなし
            ret = 0
            break
        else:
            # a[j-1]+1マスからa[j]-1マスまで移動するパターン数
            ret = ret * get_pattern((a[j]-1) - (a[j-1]+1))
 
        if j == M - 1:
            # a[j]+1マスからNマスへの移動パターン
            ret = ret * get_pattern(N - (a[j] + 1))
 
    # M = 0　のとき
    if M == 0:
        ret = get_pattern(N)
 
    print(ret % 1000000007)

Submission status: Time Limit Exceeded

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

a,b,n=0,1,1
while n<=N:
    if n in A:
        a,b=b,0
    else:
        a,b=b,a+b
    n+=1

print(b%MOD)

Submission status: Time Limit Exceeded

Solution code:
import sys
mod = 10 ** 9 + 7

n,m = map(int,input().split())
if n in [0,1]:
    print(1)
    sys.exit()
    
if not m == 0:
    lis = [int(input()) for x in range(m)]
else:
    lis = []
val1 = 1
if 1 in lis:
    val2 = 0
else:
    val2 = 1
#print(stairs)
f = 0
for x in range(2,n):
    if x in lis:
        now = 0
    else:
        now = (val1 + val2) % mod
    val1,val2 = val2,now
    
#print(stairs)
print((val1 + val2) % mod)

Submission status: Time Limit Exceeded

Solution code:
import sys

readline = sys.stdin.readline

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

A = A + [N + 1]
ans = 1


current = 0

_count = 0
for a in A:
    diff = a - 1 - current
    current = a + 1

    if diff < 0:
        ans = 0
        break
    
    s = 1
    s_total = 1
    for x in range(1, diff // 2 + 1):
        _count += 1
        y = diff - x * 2
        s = s * (y + 1) * (y + 2) // (x + y + 1) // x
        #s = s % P
        s_total = (s_total + s) % P
    
    ans = (ans * s_total) % P

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
mod = 10 ** 9 + 7

n,m = map(int,input().split())
if n in [0,1]:
    print(1)
    sys.exit()
    
if not m == 0:
    lis = [int(input()) for x in range(m)]
else:
    lis = []
stairs = [0 for x in range(n)]
stairs[0] = 1
if 1 in lis:
    stairs[1] = 0
else:
    stairs[1] = 1
#print(stairs)
f = 0
for x in range(2,n):
    if x in lis:
        stairs[x] = 0
    else:
        stairs[x] = (stairs[x-1] + stairs[x-2]) % mod
    
#print(stairs)
print((stairs[n-1] + stairs[n-2]) % mod)

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

if 1 in a:
  step = [1,0]
else:
  step = [1,1]

for i in range(2, n + 1):
  if i in a:
    step.append(0)
  else:
    step.append((step[-1] + step[-2])%1000000007)
    
print(step[-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()))

if 1 in a:
  step = [1,0]
else:
  step = [1,1]

for i in range(2, n + 1):
  if i in a:
    step.append(0)
  else:
    step.append(step[-1] + step[-2])
    
print(step[-1]%1000000007)

Submission status: Time Limit Exceeded

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

pre2 = 0
pre1 = 0
cur = 1

for i in range(n):
    pre2 = pre1
    pre1 = cur 
    cur = pre1 + pre2
    if i+1 in a:
        cur = 0
    if cur == 0 and pre1 == 0:
        break
print(cur%1000000007)

Submission status: Time Limit Exceeded

Solution code:
import sys

readline = sys.stdin.readline

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

A = A + [N + 1]
ans = 1

current = 0

_count = 0
for a in A:
    diff = a - 1 - current
    current = a + 1

    if diff < 0:
        ans = 0
        break
    
    s = 1
    s_total = 1
    for x in range(1, diff // 2 + 1):
        _count += 1
        assert _count < 100000
        y = diff - x * 2
        s = s * (y + 1) * (y + 2) // (x + y + 1) // x
        s_total = s_total + s
    
    ans = (ans * s_total) % P

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

readline = sys.stdin.readline

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

A = A + [N + 1]
ans = 1

assert N < 100001

current = 0

_count = 0
for a in A:
    diff = a - 1 - current
    current = a + 1

    if diff < 0:
        ans = 0
        break
    
    s = 1
    s_total = 1
    for x in range(1, diff // 2 + 1):
        _count += 1
        y = diff - x * 2
        s = s * (y + 1) * (y + 2) // (x + y + 1) // x
        s_total = s_total + s
    
    ans = (ans * s_total) % P

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

readline = sys.stdin.readline

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

A = A + [N + 1]
ans = 1

current = 0

_count = 0
for a in A:
    diff = a - 1 - current
    current = a + 1

    if diff < 0:
        ans = 0
        break
    
    s = 1
    s_total = 1
    for x in range(1, diff // 2 + 1):
        _count += 1
        if _count > 100000:
            assert False
        y = diff - x * 2
        s = s * (y + 1) * (y + 2) // (x + y + 1) // x
        s_total = s_total + s
    
    ans = (ans * s_total) % P

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

readline = sys.stdin.readline

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

A = A + [N + 1]
ans = 1

current = 0

_count = 0
for a in A:
    diff = a - 1 - current
    current = a + 1

    if diff < 0:
        ans = 0
        break
    
    s = 1
    s_total = 1
    for x in range(1, diff // 2 + 1):
        _count += 1
        if _count > 1000000:
            assert False
        y = diff - x * 2
        s = s * (y + 1) * (y + 2) // (x + y + 1) // x
        s_total = s_total + s
    
    ans = (ans * s_total) % P

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

readline = sys.stdin.readline

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

A = A + [N + 1]
ans = 1

current = 0
for a in A:
    diff = a - 1 - current
    current = a + 1

    if diff < 0:
        ans = 0
        break
    
    s = 1
    s_total = 1
    for x in range(1, diff // 2 + 1):
        y = diff - x * 2
        s = s * (y + 1) * (y + 2) // (x + y + 1) // x
        s_total = s_total + s
    
    ans = (ans * s_total) % P

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

X = [0] * (N + 1)
for i in range(N + 1):
  if i == 0:
    X[i] = 1
  elif i == 1:
    if 1 not in A:
      X[i] = 1
    else:
      X[i] = 0
  else:
    if i in A:
      X[i] = 0
    else:
      X[i] = (X[i - 1] + X[i - 2]) % 1000000007

print(X[N])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

DP = [0 for i in range(N)]
for i in range(N):
    if i == 0:
        if i+1 not in a:
            DP[0] = 1
        else:
            DP[0] = 0
    elif i == 1:
        if i+1 not in a:
            DP[1] = DP[0]+1
        else:
            DP[1] = 0
    else:
        if i+1 not in a:
            DP[i] = DP[i-1]+DP[i-2]
        else:
            DP[i] = 0
            
print(DP[N-1]%1000000007)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N,W = input().split()
aArr = list()
ans = 0
tmp = int(N)
MOD = 10**9+7
for i in range(int(W)):
    inputInt = int(input())
    aArr.append(inputInt)
    if inputInt - tmp == 1:
        print(ans)
        exit()
    tmp = inputInt

tmp = 0
tmpB = 0
ans = 1
for i in range(int(N)):
    if(i in aArr):
        tmp = 0
    elif i < 2:
        tmp = 1
    else:
        tmp = ans
    ans = (tmp + tmpB) % MOD
    tmpB = tmp
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
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:
MOD = 10**9+7
N, M = [int(x) for x in input().split()]
a_list = []
if (M != 0):
    a_list = [int(input()) for _ in range(M)]
dp = [0] * (N+1)
dp[0] = 1
dp[1] = int(not (1 in a_list))
for i in range(2, N+1):
    if (i not in a_list):
        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())

breakstep = []

for _ in range(m):
    breakstep.append(int(input()))

sl = [1]
def solve(i):
    global sl
    l = len(sl)
    if l < i+1:
        while l < i+1:
            if l in breakstep: 
                sl.append(0)
                l += 1
                continue
            elif l == 1:
                l += 1
                sl.append(1)
                continue
            sl.append((sl[l-1] + sl[l-2])%1000000007)
            l += 1
    return sl[i]

print(solve(n)%1000000007)

Submission status: Time Limit Exceeded

Solution code:
MOD = 1000000007
def solve(n, m, a):
    dp = [0] * (n+1)
    dp[n] = 1
    for i in range(n-1, -1, -1):
        for d in range(1, 3):
            j = i + d
            if (j <= n) and (not j in a):
                dp[i] = (dp[i] + dp[j]) % MOD
    return dp[0]

n, m = map(int, input().split())
a = [int(input()) for i in range(m)]
print(solve(n, m, a))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
from functools import lru_cache


n,m=map(int,input().split())
A = [int(input()) for i in range(m)]
mod = 10**9+7
memo={}
memo[1]=1
memo[0]=1

@lru_cache(maxsize=10000000)
def fib(n):
  if n in A:
  	memo[n]=0
  	return 0
  if n not in memo:
    memo[n] = fib(n-1) + fib(n-2)
  return memo[n]

print(fib(n)%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
from functools import lru_cache


n,m=map(int,input().split())
A = [int(input()) for i in range(m)]
mod = 10**9+7
memo={}
memo[1]=1
memo[0]=1

@lru_cache(maxsize=10000000)
def fib(n):
  if n in A:
  	memo[n]=0
  	return memo[n]
  if n not in memo:
    memo[n] = fib(n-1) + fib(n-2)
  return memo[n]

print(fib(n)%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
n,m=map(int,input().split())
A = [int(input()) for i in range(m)]
mod = 10**9+7
memo={}
memo[1]=1
memo[0]=1

def fib(n):
  if n in A:
  	memo[n]=0
  	return memo[n]
  if n not in memo:
    memo[n] = fib(n-1) + fib(n-2)
  return memo[n]

print(fib(n)%mod)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
mod = 1000000007
falls = []

for j in range(m):
    falls.append(int(input())) 

results =[]

if 1 in falls:
    result = 0
else:
    result = 1

results.append(result)

if 2 in falls:
    result = 0
else:
    if results[0] == 0:
        result = 1
    else:
        result = 2

results.append(result)

for i in range(3,n+1):
    number = i

    if number in falls:
        result = 0

    else:
        result = (results[i-3] + results[i-2]) % mod

    results.append(result)

print(results[n-1])

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
mod = 1000000007
falls = []

for j in range(m):
    falls.append(int(input()))

results =[]

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

    if number in falls:
        result = 0

    else:
        if number == 1:
            result = 1
        elif number == 2:
            if results[0] == 0:
                result = 1
            else:
                result = 2
        else:
            result = (results[i-3] + results[i-2])%mod

    results.append(result)

print(results[n-1])

Submission status: Time Limit Exceeded

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

is_broken = [1] * (n+1)
for i in range(n):
    if i in a:
        is_broken[i] = 0

step = [i for i in range(n+1)]
step[0] = 1

for i in range(n):
    if i - 1 >= 0:
        step[i+1] = step[i] * is_broken[i] + step[i-1] * is_broken[i-1]
    else:
        step[i+1] = step[i] * is_broken[i]
    step[i+1] %= mod

print(step[n])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
NM = input()
N, M = NM.split(" ")
del NM
N, M = int(N), int(M)
#all_steps = [num for num in range(N+1)]
all_steps = list(np.ones((1, N+1), dtype=np.int32)[0])
broken_steps = [int(input()) for num in range(M)]
ok_steps = [0 if num in broken_steps else 1 for num in range(len(all_steps))]
#for num in range(len(all_steps)):
#  if num in broken_steps:
#    ok_steps.append(0)
#  else:
#  	ok_steps.append(1)
#del all_steps, broken_steps

#temp0 = [ok_steps[(num + 1)] + ok_steps[(num + 2 )] if ok_steps[num]==1 else 0 for num in reversed(range(len(ok_steps)-2)) ]
for num in range(0, len(ok_steps)):
  i = - (num + 1)
  if (i==-1 or i==-2):
    pass
  else:
    if ok_steps[i]==0:
      pass
    else:
      ok_steps[i] = ok_steps[i+1] + ok_steps[i+2]
    
print(ok_steps[0]%1000000007)

Submission status: Time Limit Exceeded

Solution code:
NM = input()
N, M = NM.split(" ")
del NM
N, M = int(N), int(M)
all_steps = [num for num in range(N+1)]
broken_steps = [int(input()) for num in range(M)]
ok_steps = [0 if all_steps[num] in broken_steps else 1 for num in range(len(all_steps))]
#for num in range(len(all_steps)):
#  if num in broken_steps:
#    ok_steps.append(0)
#  else:
#  	ok_steps.append(1)
del all_steps, broken_steps

for num in range(0, len(ok_steps)):
  i = - (num + 1)
  if (i==-1 or i==-2):
    pass
  else:
    if ok_steps[i]==0:
      pass
    else:
      ok_steps[i] = ok_steps[i+1] + ok_steps[i+2]
    
print(ok_steps[0]%1000000007)

Submission status: Time Limit Exceeded

Solution code:
NM = input()
N, M = NM.split(" ")
del NM
N, M = int(N), int(M)
all_steps = [num for num in range(N+1)]
broken_steps = [int(input()) for num in range(M)]
ok_steps = []
for num in range(len(all_steps)):
  if num in broken_steps:
    ok_steps.append(0)
  else:
  	ok_steps.append(1)
del all_steps, broken_steps

for num in range(0, len(ok_steps)):
  i = - (num + 1)
  if (i==-1 or i==-2):
    pass
  else:
    if ok_steps[i]==0:
      pass
    else:
      ok_steps[i] = ok_steps[i+1] + ok_steps[i+2]
    
print(ok_steps[0]%1000000007)

Submission status: Time Limit Exceeded

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

MOD = 10 ** 9 + 7

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

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

#print(dp)
print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

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

if 1 not in A:
    tmp[1] = 1
    
if 2 not in A and N >= 2:
    tmp[2] = tmp[1] + 1

for i in range(3, N+1):
    
    if i not in A:
        tmp[i] = tmp[i-1] + tmp[i-2] 
        

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

Submission status: Time Limit Exceeded

Solution code:
N,M=[int(i) for i in input().split()]
inf=1000000007
aa=[]
for i in range(M):
	aa.append(int(input()))
dp=[0]*(N+1)
dp[0]=1
if 1 in aa:
	dp[1]=0
else:
	dp[1]=1
for i in range(2,N+1):
	if i in aa:
		dp[i]=0
	else:
		dp[i]=dp[i-2]%inf+dp[i-1]%inf
print(dp[N]%inf)

Submission status: Time Limit Exceeded

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

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

A = []
a_prev = None
for i in range(M):
  a_i = int(input())
  if a_prev == a_i:
    print(0)
    exit()
  A.append(a_i)
  a_prev = a_i

N_2 = 1
N_1 = 1  
ans = 0
for i in range(1, N):
  if i in A:
    N_1 = 0
  ans = (N_1 + N_2)%1000000007
  N_2 = N_1
  N_1 = ans
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache

import sys
sys.setrecursionlimit(1000000)

N, M = map(int, input().split())

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

@lru_cache(None)
def dfs(pos):
    if pos > N:
        return 0
    if pos == N:
        return 1
    if pos in A:
        return 0
    return dfs(pos + 2) + dfs(pos + 1)

for i in reversed(range(N+1)):
    dfs(i)

print(dfs(0) % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache

import sys
sys.setrecursionlimit(1000000)

N, M = map(int, input().split())

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

@lru_cache(None)
def dfs(pos):
    if pos > N:
        return 0
    if pos == N:
        return 1
    if pos in A:
        return 0
    return dfs(pos + 2) + dfs(pos + 1)

for i in reversed(range(N)):
    dfs(i)

print(dfs(0) % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache

import sys
sys.setrecursionlimit(1000000)

N, M = map(int, input().split())

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

@lru_cache(1000000)
def dfs(pos):
    if pos > N:
        return 0
    if pos == N:
        return 1
    if pos in A:
        return 0
    return dfs(pos + 2) + dfs(pos + 1)

print(dfs(0) % 1000000007)

Submission status: Time Limit Exceeded

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

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

for i in range(N):
    if (i + 1) not in A and (i + 1) <= N:
        dp[i + 1] += dp[i]
    if (i + 2) not in A and (i + 2) <= N:
        dp[i + 2] += dp[i]


print str(dp[N]%1000000007)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache

import sys
sys.setrecursionlimit(1000000)

N, M = map(int, input().split())

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

@lru_cache(100000)
def dfs(pos):
    if pos > N:
        return 0
    if pos == N:
        return 1
    if pos in A:
        return 0
    return dfs(pos + 1) + dfs(pos + 2)

print(dfs(0) % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache

import sys
sys.setrecursionlimit(1000000)

N, M = map(int, input().split())

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

@lru_cache(1000000)
def dfs(pos):
    if pos > N:
        return 0
    if pos == N:
        return 1
    s = 0
    if (pos + 1) not in A:
        s += dfs(pos + 1)
    if (pos + 2) not in A:
        s += dfs(pos + 2)
    return s

print(dfs(0) % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache

import sys
sys.setrecursionlimit(1000000)

N, M = map(int, input().split())

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

@lru_cache(100000)
def dfs(pos):
    if pos > N:
        return 0
    if pos == N:
        return 1
    s = 0
    if (pos + 1) not in A:
        s += dfs(pos + 1)
    if (pos + 2) not in A:
        s += dfs(pos + 2)
    return s

print(dfs(0) % 1000000007)

Submission status: Time Limit Exceeded

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

DP=[0 for _ in range(N+10)]
DP[0]=1
for i in range(N):
  for j in [1,2]:
    if i+j not in a:
      DP[i+j]+=DP[i]
      
print(DP[N]%D)

Submission status: Time Limit Exceeded

Solution code:
from sys import exit

N, M = map(int, input().split())

_a = -1
A = []
ans = 0

for _ in range(M):
    a_ = int(input())
    if _a + 1 == a_:
        print(0)
        exit()
    _a = a_
    A.append(_a)

step = [0] * (N + 1)

step[0] = 1

for s in range(1, N + 1):
    if s in A:
        step[s] = 0
        continue
    if s == 1:
        step[s] = 1
        continue
    else:
        step[s] = (step[s - 1] + step[s - 2]) % 1000000007

print(step[N])

Submission status: Time Limit Exceeded

Solution code:
from sys import exit
import sys

N, M = map(int, input().split())

_a = -1
B = []
ans = 0
count = 0

for i in range(M):
    a_ = int(input())
    if _a + 1 == a_:
        print(0)
        exit()
    _a = a_
    N -= 2
    count += 1
    B.append(_a + 2 - 2 * count)


step = [1]

for s in range(1, N + 1):
    if s == 1:
        step.append(1)
        continue
    if s in B:
        step.append(step[s - 1])
        continue
    else:
        step.append((step[s - 1] + step[s - 2]) % 1000000007)

print(step[N] % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
from sys import exit
import sys

N, M = map(int, input().split())

_a = -1
B = []
ans = 0
count = 0

for i in range(M):
    a_ = int(input())
    if _a + 1 == a_:
        print(0)
        exit()
    _a = a_
    N -= 2
    count += 1
    B.append(_a + 2 - 2 * count)


step = [1]

for s in range(1, N + 1):
    if s == 1:
        step.append(1)
        continue
    if s in B:
        step.append(step[s - 1])
        continue
    else:
        step.append(step[s - 1] + step[s - 2])

print(step[N] % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
from sys import exit
import sys
sys.setrecursionlimit(10000)

N, M = map(int, input().split())

_a = -1
a = []
ans = 0

for _ in range(M):
    a_ = int(input())
    if _a + 1 == a_:
        print(0)
        exit()
    _a = a_
    a.append(_a)


step = [1]

for s in range(1, N + 1):
    if s in a:
        step.append(0)
        continue
    if s == 1:
        step.append(1)
        continue
    else:
        step.append(step[s - 1] + step[s - 2])

print(step[N] % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
a=[int(input()) for _ in range(M)]
A=[0]*(N+2)
A[0:2]=[0,1]

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

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
dp[1] = 1

for i in range(2, N+1):
    # 壊れた床がなく単純に求める場合
    #dp[i] = dp[i-1]+dp[i-2]

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

print(dp[N] % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
a=[-1]
k=[1,1]
ansk=1
d=[]
renzoku=1
for i in range(m):
 a.append(int(input()))
 if a[i+1]==a[i]+1:
    renzoku=0
a.append(n+1)
for i in range(max(a)):
 s=k[i+1]+k[i]
 k.append(s)
for i in range(m+1):
 d.append(a[i+1]-a[i]-1)
 ansk*=k[d[i]-1]
if renzoku==1:
 print(ansk%1000000007)
else:
 print(0)

Submission status: Time Limit Exceeded

Solution code:
def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def solve(inputs):
    [N, M] = list(map(lambda x: int(x), inputs[0].split()))
    broke_steps = list(map(lambda x: int(x), inputs[1:]))

    SSSS = 1000000007

    patterns = [1]
    for step in range(1, N + 1):
        if step in broke_steps:
            ap = 0
        elif step == 1:
            ap = 1
        else:
            ap = (patterns[step - 1] + patterns[step - 2]) % SSSS
        patterns.append(ap)

    return patterns[-1]


if __name__ == "__main__":
    first = input()
    [N, M] = list(map(lambda x: int(x), first.split()))
    inputs_str = inputs(M)
    inputs_str.insert(0, first)
    ret = solve(inputs_str)
    print(ret)

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

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

print(dp[n])

Submission status: Time Limit Exceeded

Solution code:
n,m = (int(i) for i in input().split())
a = [int(input()) for i in range(m)]
oks = [True if not i in a else False for i in range(n+1)]
mod = 1000000007
dp = [0 for _ in range(n+1)]
dp[0] = 1
dp[1] = 1 if not 1 in a else 0
for i in range(2,n+1):
    if oks[i] is True:
        dp[i] = (dp[i-1]+dp[i-2])%mod
print(dp[n])

Submission status: Time Limit Exceeded

Solution code:
N,M = (int(i) for i in input().split())
a = [int(input()) for i in range(M)]
hoge = [0] * N
if 1 not in a:
    hoge[0] = 1
if 2 not in a and N >= 2:
    hoge[1] = hoge[0] + 1

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

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

Submission status: Time Limit Exceeded

Solution code:
N,M = (int(i) for i in input().split())
a = [int(input()) for i in range(M)]
hoge = [0] * N
if 1 not in a:
    hoge[0] = 1
if 2 not in a and N >= 2:
    hoge[1] = hoge[0] + 1

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

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
n, m = map(int, input().split())
a = [int(sys.stdin.readline()) for _ in range(m)]
mod = 1000000007

def main():
    dp = [0] * (n + 1)
    dp[0] = 1
    dp[1] = dp[0] if not 1 in a else 0
    for i in range(2, n + 1):
        if not i in a:
            dp[i] = (dp[i - 1] + dp[i - 2]) % mod
        else:
            dp[i]=  0
    ans =dp[n]
    return ans
print(main())