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())
dp=[0]*(n+1)
dp[0]=1
mod=10**9+7
a=[int(input()) for i in range(m)]
for i in range(1,n+1):
    dp[i]=(dp[i-1]+dp[i-2])%mod
    if i in a:
        dp[i]=0
print(int(dp[n]))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

for _ in range(M):
    k = int(input())
    A.append(k)

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

print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env pypy
import sys

readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
MOD = 10 ** 9 + 7


def main():
    n, m = map(int, readline().split())
    # a = readlines()
    a = list(map(int, readlines()))
    # diff_a = [a[i+1] - a[i] for i in range(m - 1)]
    # if 1 in diff_a:
    #     print(0)
    #     return
    p1, p2 = 0, 1
    if 1 not in a:
        p1 = 1

    for i in range(2, n + 1):
        if i in a:
            p1, p2 = 0, p1
        else:
            p1, p2 = (p1 + p2) % MOD, p1

    print(p1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env pypy
import sys

readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
MOD = 10 ** 9 + 7


def main():
    n, m = map(int, readline().split())
    # a = readlines()
    a = list(map(int, readlines()))
    diff_a = [a[i+1] - a[i] for i in range(m - 1)]
    if 1 in diff_a:
        print(0)
        return
    p1, p2 = 0, 1
    if 1 not in a:
        p1 = 1

    for i in range(2, n + 1):
        if i in a:
            p1, p2 = 0, p1
        else:
            p1, p2 = (p1 + p2) % MOD, p1

    print(p1)


if __name__ == '__main__':
    main()

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
anlist=[]
inf=10**9+7
if 1 not in a:
  dp[1]=1
else:
  dp[1]=0
for i in range(2,N+1):
  if i in a:
    continue
  else:
    dp[i]=dp[i-1]+dp[i-2]
ans=dp[N]%inf
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)
dp[0]=1
anlist=[]
inf=10**9+7
if 1 not in a:
  dp[1]=1
else:
  dp[1]=0
for i in range(2,N+1):
  if i in a:
    continue
  else:
    dp[i]=dp[i-1]+dp[i-2]
for i in dp:
  i=i%inf
  anlist.append(i)
ans=anlist[N]%inf
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env pypy
import sys

input = sys.stdin.readline


def main():
    n, m = map(int, input().split())
    a = [int(input()) for _ in range(m)]
    diff_a = [a[i+1] - a[i] for i in range(m - 1)]
    if 1 in diff_a:
        print(0)
        return
    method = [0] * (n + 1)
    method[0] = 1
    if 1 not in a:
        method[1] = 1

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

    print(method[n])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env pypy


def main():
    n, m = map(int, input().split())
    a = [int(input()) for _ in range(m)]
    diff_a = [a[i+1] - a[i] for i in range(m - 1)]
    if 1 in diff_a:
        print(0)
        return
    method = [0] * (n + 1)
    method[0] = 1
    if 1 not in a:
        method[1] = 1
    for i in range(2, n + 1):
        if i in a:
            continue
        else:
            method[i] = method[i-1] + method[i-2]
            # method[i] %= 1000000007
    print(method[n] % 1000000007)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env pypy


def main():
    n, m = map(int, input().split())
    a = [int(input()) for _ in range(m)]
    diff_a = [a[i+1] - a[i] for i in range(m - 1)]
    if 1 in diff_a:
        print(0)
        return
    method = [0] * (n + 1)
    method[0] = 1
    if 1 not in a:
        method[1] = 1
    for i in range(2, n + 1):
        if i in a:
            continue
        else:
            method[i] = method[i-1] + method[i-2]
            method[i] %= 1000000007
    print(method[n])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3


def main():
    n, m = map(int, input().split())
    a = [int(input()) for _ in range(m)]
    diff_a = [a[i+1] - a[i] for i in range(m - 1)]
    if 1 in diff_a:
        print(0)
        return
    method = [0] * (n + 1)
    method[0] = 1
    if 1 not in a:
        method[1] = 1
    for i in range(2, n + 1):
        if i in a:
            continue
        else:
            method[i] = method[i-1] + method[i-2]
            method[i] %= 1000000007
    print(method[n])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    import sys
    input = sys.stdin.readline
    # 整数 1 つ
    #n, m = int(input())
    # 整数複数個
    n, m = map(int, input().split())
    # 整数 N 個 (改行区切り)
    A = [int(input()) for i in range(m)]
    # 整数 N 個 (スペース区切り)
    #A = list(map(int, input().split()))
    # 整数 (縦 H 横 W の行列)
    # A = [list(map(int, input().split())) for i in range(H)]

    Route = [0] * (n+1)
    Route[0] = 1
    if 1 not in A:
        Route[1] = 1
    MOD = 10**9 + 7
    for i in range(2, n+1):
        if i not in A:
            Route[i] = (Route[i-1] + Route[i-2]) % MOD
#            Route[i] %= MOD

    print(Route[n])
#    print(Route)
resolve()

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    import sys
    input = sys.stdin.readline
    # 整数 1 つ
    #n, m = int(input())
    # 整数複数個
    n, m = map(int, input().split())
    # 整数 N 個 (改行区切り)
    A = [int(input()) for i in range(m)]
    # 整数 N 個 (スペース区切り)
    #A = list(map(int, input().split()))
    # 整数 (縦 H 横 W の行列)
    # A = [list(map(int, input().split())) for i in range(H)]

    Route = [0] * (n+1)
    Route[0] = 1
    for i in range(n):
        if i+1 not in A:
            Route[i+1] = (Route[i] + Route[i+1]) % (10**9 + 7)
            #Route[i+1] %= 10**9 + 7
        if i+2 not in A and i+2 <= n:
            Route[i+2] = (Route[i] + Route[i+2]) % (10**9 + 7)
            #Route[i+2] %= 10**9 + 7

    print(Route[n])
resolve()

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    # 整数 1 つ
    #n, m = int(input())
    # 整数複数個
    n, m = map(int, input().split())
    # 整数 N 個 (改行区切り)
    A = [int(input()) for i in range(m)]
    # 整数 N 個 (スペース区切り)
    #A = list(map(int, input().split()))
    # 整数 (縦 H 横 W の行列)
    # A = [list(map(int, input().split())) for i in range(H)]

    Route = [0] * (n+1)
    Route[0] = 1
    for i in range(n):
        if i+1 not in A:
            Route[i+1] = (Route[i] + Route[i+1]) % (10**9 + 7)
            #Route[i+1] %= 10**9 + 7
        if i+2 not in A and i+2 <= n:
            Route[i+2] = (Route[i] + Route[i+2]) % (10**9 + 7)
            #Route[i+2] %= 10**9 + 7

    print(Route[n])
resolve()

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    # 整数 1 つ
    #n, m = int(input())
    # 整数複数個
    n, m = map(int, input().split())
    # 整数 N 個 (改行区切り)
    A = [int(input()) for i in range(m)]
    # 整数 N 個 (スペース区切り)
    #A = list(map(int, input().split()))
    # 整数 (縦 H 横 W の行列)
    # A = [list(map(int, input().split())) for i in range(H)]

    Route = [0] * (n+1)
    Route[0] = 1
    for i in range(n):
        if i+1 not in A:
            Route[i+1] += Route[i]
            Route[i+1] %= 10**9 + 7
        if i+2 not in A and i+2 <= n:
            Route[i+2] += Route[i]
            Route[i+2] %= 10**9 + 7

    print(Route[n])
#    print(Route)


resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
large_p = 10**9 + 7
a = []
kazu_memo = {}
def f(target_step):
    global kazu_memo
    #print(target_step)
    if target_step in a:
        return 0
    elif target_step < 0:
        return 0
    elif target_step == 0:
        return 1
    else:
        if kazu_memo[target_step] > 0:
            return kazu_memo[target_step]
        else:
            kazu_tmp = 0
            kazu_tmp += f(target_step - 1)
            kazu_tmp += f(target_step - 2)
            kazu_memo[target_step] = kazu_tmp % large_p
            return kazu_tmp % large_p

def main():
    global a, kazu_memo
    n, m = map(int, input().split())
    a = [int(input()) for _ in range(m)]

    kazu_memo = {e: -1 for e in range(1, n + 1)}
    r = f(n)
    print(r % large_p)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
A = list(int(input()) for i in range(M))
MOD = 10 ** 9 + 7
DP = [0] * (N + 10)
if 1 not in A:
    DP[1] = 1
if 2 not in A and 1 in A:
    DP[2] = 1
if 2 not in A and 1 not in A:
    DP[2] = 2
for i in range(3, N + 1):
    if i not in A:
        DP[i] = (DP[i - 1] + DP[i - 2]) % MOD
print(DP[N])

Submission status: Time Limit Exceeded

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

mod = 1000000007

A = []
for i in range(M):
    A.append(int(input()))
    
DP = [0]*(N+2)
DP[1] = 1

for i in range(2, N+2):
    if i-1 not in A:
        DP[i] =  DP[i-1]%mod + DP[i-2]%mod

print(DP[N+1]%mod)

Submission status: Time Limit Exceeded

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

mod = 1000000007

A = []
for i in range(M):
    A.append(int(input()))
    
DP = [0]*(N+2)
DP[1] = 1

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

print(DP[N+1]%mod)

Submission status: Time Limit Exceeded

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

P = [-1] * (N+1)
P[0] = 1
P[1] = 1
flg=False
MOD = 10**9 + 7
for i in range(2, N+1):
    if i in a:
        continue
    if (i-1 not in a) and (i-2 not in a):
        P[i] = (P[i-1] + P[i-2]) % MOD
    elif i-1 not in a:
        P[i] = P[i-1] % MOD
    elif i-2 not in a:
        P[i] = P[i-2] % MOD
    else:
        flg=True
if flg:
    print(0)
else:
    print(P[N] % MOD)

Submission status: Time Limit Exceeded

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

P = [10**12] * (N+1)
P[0] = 1
P[1] = 1
flg=False
for i in range(2, N+1):
    if i in a:
        continue
    if (i-1 not in a) and (i-2 not in a):
        P[i] = P[i-1] + P[i-2]
    elif i-1 not in a:
        P[i] = P[i-1]
    elif i-2 not in a:
        P[i] = P[i-2]
    else:
        flg=True
if flg:
    print(0)
else:
    print(P[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()))
d=[1]*(n+1)
if 1 in a:
  d[1]=0

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

print(d[n])

Submission status: Time Limit Exceeded

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

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

if b[0] == 1:
  dp[1] = 1
  b.pop(0)
else:
  dp[1] = 0

  
for i in b:
  dp[i] = (dp[i-1]%1000000007 + dp[i-2]%1000000007)%1000000007
  
print(dp[n]%1000000007)

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(int(1e6))

n,m=map(int,input().split())
memo=[0]*(n+1)
memo[0]=1
memo[1]=1
for i in range(m):
    memo[int(input())]=-2
def dp(i):
    if memo[i]==-2:
        return 0
    elif memo[i]==0:
        s=dp(i-1)
        if i>=2:
            s+=dp(i-2)
        memo[i]=s%(10**9+7)
        return memo[i]
    else:
        return memo[i]
        
print(dp(n))

Submission status: Time Limit Exceeded

Solution code:
# input
N, M = map(int, input().split())
a = []
a_append = a.append

for n in range(M):
    a_append(int(input()))

mod = 1000000007

# check
check = {}
for n in range(N + 1):
    if n in a:
        check[n] = False
    else:
        check[n] = True

dp = {0: 1}
if check[1] is True:
    dp[1] = 1
else:
    dp[1] = 0

for n in range(2, N + 1):
    dp[n] = 0
    if check[n - 1] is True:
        dp[n] += dp[n - 1]
    if check[n - 2] is True:
        dp[n] += dp[n - 2]
    dp[n] %= mod

print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
# input
N, M = map(int, input().split())
a = []
a_append = a.append

for n in range(M):
    a_append(int(input()))

mod = 1000000007

# check
dp = {0: 1, 1: 1}
for n in range(2, N + 1):
    dp[n] = 0
    if n - 1 not in a:
        dp[n] += dp[n - 1]
    if n - 2 not in a:
        dp[n] += dp[n - 2]

print(dp[N] % mod)

Submission status: Time Limit Exceeded

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

dp = [0] * (n + 1)
dp[0] = 1
if 1 in a:
    dp[1] = 0
else:
    dp[1] = 1
MOD = 10 ** 9 + 7

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

print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,M = LI()
a = [I() for _ in range(M)]
dp = [0]*(N+1) #1_indexed
dp[0] = 1
dp[1] = 0 if 1 in a else 1
for i in range(2,N+1):
    if i in a:
        dp[i] = 0
        continue
    dp[i] = dp[i-1]+dp[i-2]
    dp[i] %= 10**9+7
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
import itertools,sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,M = LI()
a = [I() for _ in range(M)]
dp = [0]*(N+1) #1_indexed
dp[0] = 1
dp[1] = 0 if 1 in a else 1
for i,j in itertools.product(range(2,N+1),[1,2]):
    if i in a:
        dp[i] = 0
        continue
    dp[i] += dp[i-j]
    dp[i] %= 10**9+7
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
import bisect,collections,copy,heapq,itertools,math,numpy,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
N, M = LI()
A = [I() for _ in range(M)]
md = 10**9+7

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

for now in range(N):
  for next in range(now+1, now+3):
    if next == N:
      dp[next] += dp[now]
      dp[next] %= md
      break
    if next in A:
      continue
    else:
      dp[next] += dp[now]
      dp[next] %= md

print(dp[N])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

before = -1
count = 1
for i in range(m+1):
    if i == m:
        a = n+1
    else:
        a = int(input())
    sa = a-before-2
    
    if a-before == 1:
        print(0)
        exit()
    elif sa <= 1 :
        before = a    
        continue
    else:
        twonum = sa//2
        tmp = 1
        for k in range(1,twonum+1):
            wa12 = k + (sa-k*2)           
            tmp = (tmp + cmb(wa12,k))%(10**9+7)       
        count = (count * tmp)%(10**9+7)
        before = a

print(count)

Submission status: Time Limit Exceeded

Solution code:
n,m =map(int,input().split())
import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

before = -1
count = 1
for i in range(m+1):
    if i == m:
        a = n+1
    else:
        a = int(input())
    sa = a-before-2
    
    if a-before == 1:
        print(0)
        exit()
    elif sa <= 1 :
        before = a    
        continue
    else:
        twonum = sa//2
        tmp = 1
        for k in range(1,twonum+1):
            wa12 = k + (sa-k*2)           
            tmp = (tmp + combinations_count(wa12,k))%(10**9+7)
                    
        count = (count * tmp)%(10**9+7)
        before = a

print(count)

Submission status: Time Limit Exceeded

Solution code:
n,m =map(int,input().split())
import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

before = -1
count = 1
for i in range(m+1):
    if i == m:
        a = n+1
    else:
        a = int(input())
    sa = a-before-2
    
    if a-before == 1:
        print(0)
        exit()
    elif sa <= 1 :
        before = a    
        continue
    else:
        twonum = sa//2
        tmp = 1
        for k in range(1,twonum+1):
            wa12 = k + (sa-k*2)           
            tmp = (tmp + combinations_count(wa12,k))
                    
        count = (count * tmp)%(10**9+7)
        before = a

print(count)

Submission status: Time Limit Exceeded

Solution code:
n,m =map(int,input().split())
import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

before = -1
count = 1
for i in range(m+1):
    if i == m:
        a = n+1
    else:
        a = int(input())
    sa = a-before-2
    
    if a-before == 1:
        print(0)
        exit()
    elif sa <= 1 :
        before = a    
        continue
    else:
        twonum = sa//2
        tmp = 1
        for k in range(1,twonum+1):
            wa12 = k + (sa-k*2)
            
            tmp = (tmp + combinations_count(wa12,k))
            

        
        count = (count * tmp)%(10**9+7)
        before = a

print(count)

Submission status: Time Limit Exceeded

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

dp=[0]*(n+1)
#dp=[-1]*(n+1)
dp[0]=1
if 1 not in mList:
  dp[1]=1

for i in range(2,n+1):
  if i in mList: continue
  dp[i]+=dp[i-1]
  dp[i]+=dp[i-2]
  dp[i]%=1000000007

#def calc(i):
#  if dp[i]!=-1: return dp[i]
#  if i in mList:
#    dp[i]=0
#    return dp[i]
#  dp[i]=calc(i-1)+calc(i-2)
#  dp[i]%=1000000007
#  return dp[i]

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

Submission status: Time Limit Exceeded

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

#dp=[float("inf")*n]
dp=[0]*n
#dp[0]=0
dp[0]=1
for i in range(1,n):
  #print(i,"に来る方法")
  if i in mList: continue
  dp[i]+=dp[i-1]
  #dp[i]=min(dp[i],dp[i-1]+abs(dp[i]-dp[i-1]))
  if i==1: continue
  dp[i]+=dp[i-2]
  #print(dp[i])
  #dp[i]=min(dp[i],dp[i-2]+abs(dp[i]-dp[i-2]))

print(dp[n-1]%1000000007)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math
N,M = list(map(int,input().split()))
A = np.array([-1]+[int(input()) for _ in range(M)]+[N+1])
A = np.diff(A, n= 1)
cnt = 0
ans = 1
for d in A:
  d -= 2
  cnt = 0
  for j in range(d//2+1):
    cnt += math.factorial(d-j)//(math.factorial(d-j*2)*math.factorial(j))
  ans *= cnt
print(ans%1000000007)

Submission status: Time Limit Exceeded

Solution code:
import math
N,M = list(map(int,input().split()))
A = [-1]+[int(input()) for _ in range(M)]+[N+1]
cnt = 0
ans = 1
for i in range(M+1):
  cnt = 0
  d = A[i+1]-A[i]-2
  for j in range(d//2+1):
    cnt += math.factorial(d-j)//(math.factorial(d-j*2)*math.factorial(j))
  ans *= cnt
print(ans%1000000007)

Submission status: Time Limit Exceeded

Solution code:
import math
N,M = list(map(int,input().split()))
A = [-1]+[int(input()) for _ in range(M)]+[N+1]
cnt = 0
ans = 1
for i in range(M+1):
  cnt = 0
  d = A[i+1]-A[i]-2
  for j in range(d//2+1):
    cnt += math.factorial(d-j)//(math.factorial(d-j*2)*math.factorial(j))
  ans *= cnt
print(ans%1000000007)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7
N, M = map(int, input().split())
A = tuple(int(input()) for _ in range(M))
table = [0] * (N + 1)
table[0] = 1
for i in range(N + 1):
    now = table[i]
    if i + 1 < N + 1 and i + 1 not in A:
        table[i + 1] = (table[i + 1] + now) % MOD
    if i + 2 < N + 1 and i + 2 not in A:
        table[i + 2] = (table[i + 2] + now) % MOD
print(table[N])

Submission status: Time Limit Exceeded

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

s = [1]*(n+1)

if 1 in a:
    s[1] = 0

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

Submission status: Time Limit Exceeded

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

if 1 in a:
    s[1] = 0

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

print(s[-1])

Submission status: Time Limit Exceeded

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

if 1 in a:
    s[1] = 0

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

print(s[-1])

Submission status: Time Limit Exceeded

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

    if 1 in a:
        s[1] = 0

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

    print(s[-1])

main()

Submission status: Time Limit Exceeded

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

if 1 in a:
    s[1] = 0

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

print(s[-1])

Submission status: Time Limit Exceeded

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

if 1 in a:
    s[1] = 0

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

print(s[-1])

Submission status: Time Limit Exceeded

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

if 1 in a:
    s[1] = 0

for i in range(n-1):
    if i+2 in a:
        s[i+2] = 0
        continue
    if i+2 not in a:
        s[i+2] = (s[i+1] + s[i]) % (10**9+7)

print(s[-1])

Submission status: Time Limit Exceeded

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

print(s[-1])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
A = [int(input()) for _ in range(M)]
dp = [0 for _ in range(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]
print(dp[N]%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
A = [int(input()) for _ in range(M)]
dp = [0 for _ in range(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]
print(dp[N]%(10**9+7))

Submission status: Time Limit Exceeded

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

dp[0] = 1

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

print(dp[n])

Submission status: Time Limit Exceeded

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

mod = 1000000007

dp=[0]*(n+1)

dp[0]=1
dp[1]=1

for _ in range(m):
    s = int(input())
    a.append(s)

    dp[s]=0


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

print(dp[-1]%mod)

Submission status: Time Limit Exceeded

Solution code:
def typical_stairs(n, m, ali):

    mod = 10**9+7

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

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

    return dp[i]

def main():
    n, m = map(int, input().split())
    ali = [int(input())for i in range(m)]
    print(typical_stairs(n, m, ali))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def typical_stairs(n, m, ali):

    mod = 10**9+7

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

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

    return dp[i]%mod

def main():
    n, m = map(int, input().split())
    ali = [int(input())for i in range(m)]
    print(typical_stairs(n, m, ali))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from itertools import permutations, accumulate, combinations, combinations_with_replacement
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce
from fractions import gcd
import sys
def I(): return int(input())
def Is(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()
def LS(): return list(input())
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(10**6)
MOD = 10**9+7
INF = float('inf')


n, m = Is()
A = IR(m)
dp = [0]*(n+3)
dp[0] = 1

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

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

print(dp[n] % MOD)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline

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