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())
o = [int(input()) for _ in range(m)]
#print(o)
mod = (10**9)+7
dp = [1]+[0]*(n)
flag1 = False
 
for i in range(n):
  if i+1 not in o:
    dp[i+1] = dp[i] + dp[i-1]
  else:
    dp[i+1] = 0
  #print(i,dp)
#print(dp)
print(dp[-1]%mod)

Submission status: Time Limit Exceeded

Solution code:
nm=list(map(int,input().split()))
n=nm[0]
m=nm[1]

inp=[]
if m==0:
    inp=[n+1]
    dis=[n+1]
else:
    for inpset in range(m):
        inp.append(int(input()))
    

    dis=[max(inp[0],1)]
    p=0
    for i in inp[:-1]:
        dis.append(inp[p+1]-inp[p]-1)
        p+=1
    dis.append(max(n-inp[-1],1))
    #print (dis)

import math

def kaijo(x):
    ans=(math(100000)%1000000007)
    return ans

def combinations_count(n, r):
    return (math.factorial(n) // (math.factorial(n - r) * math.factorial(r)))%1000000007

def counting(x):
    if x==1:
        return 1
    else:
        
        res=0
        for a in range(x-1):
            if x-1-a>=a:
                res+=combinations_count(x-1-a,a)
                # print(x-1-a,a)
            else:
                break
        res=res%1000000007
        return res

if 0 in dis:
    print(0)
else:
    ans=1
    dis.sort()
    for d in dis:
        ans*=counting(d)
        ans=ans%1000000007
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
nm=list(map(int,input().split()))
n=nm[0]
m=nm[1]

inp=[]
if m==0:
    inp=[n+1]
    dis=[n+1]
else:
    for inpset in range(m):
        inp.append(int(input()))
    

    dis=[max(inp[0],1)]
    p=0
    for i in inp[:-1]:
        dis.append(inp[p+1]-inp[p]-1)
        p+=1
    dis.append(max(n-inp[-1],1))
    #print (dis)

import math

def kaijo(x):
    ans=(math(100000)%1000000007)
    return ans

def combinations_count(n, r):
    return (math.factorial(n) // (math.factorial(n - r) * math.factorial(r)))%1000000007

def counting(x):
    if x==1:
        return 1
    else:
        
        res=0
        for a in range(x-1):
            if x-1-a>=a:
                res+=combinations_count(x-1-a,a)
                # print(x-1-a,a)
                res=res%1000000007
            else:
                break
        return res

if 0 in dis:
    print(0)
else:
    ans=1
    dis.sort()
    for d in dis:
        ans*=counting(d)
        ans=ans%1000000007
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Apr 20 20:47:47 2019

@author: Owner
"""

import numpy as np
import sys
import collections
import scipy.misc
import math
from operator import itemgetter
import itertools
import copy
import bisect

#素因数を並べる
def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(int(i))
    i += 1
  if n > 1:
    table.append(int(n))
  return table   
# 桁数を吐く
def digit(i):
    if i > 0:
        return digit(i//10) + [i%10]
    else:
        return []
    
def getNearestValueIndex(list, num):
    """
    概要: リストからある値に最も近い値のインデックスを取得する関数
    @param list: データ配列
    @param num: 対象値
    @return 対象値に最も近い値
    """

    # リスト要素と対象値の差分を計算し最小値のインデックスを取得
    idx = np.abs(np.asarray(list) - num).argmin()
    return idx

def find_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]

    def find(self, x):
        """
        x が属するグループを探索
        """
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        """
        x と y のグループを結合
        """
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]

    def is_same(self, x, y):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)

    def get_size(self, x):
        """
        x が属するグループの要素数
        """
        x = self.find(x)
        return self.size[x]
    

"""
N, X = map(int, input().split())

x = list(map(int, input().split()))

P = [0]*N
Y = [0]*N
for n in range(N):
    P[n], Y[n] = map(int, input().split())

# 多次元配列の宣言（あとでintにすること。）（タプルにすること。）
dp = np.zeros((N+1, 4,4,4))
    
all(nstr.count(c) for c in '753')

# 複数配列を並び替え
ABT = zip(A, B, totAB)
result = 0
# itemgetterには何番目の配列をキーにしたいか渡します
sorted(ABT,key=itemgetter(2))
A, B, totAB = zip(*ABT)
A.sort(reverse=True)

# 2進数のbit判定
(x >> i) & 1

# dp最小化問題
dp = [np.inf]*N
for n in range(N):
    if n == 0:
        dp[n] = 0
    else:
        for k in range(1,K+1):
            if n-k >= 0:
                dp[n] = min(dp[n], dp[n-k] + abs(h[n]-h[n-k]))
            else:
                break
# 累積和
add = 1 # 問題によって決まる
res = 0
sums = [0]*(len(nums)+1)
for i in range(len(nums)):
    sums[i+1] = sums[i] + nums[i]
for i in range(0, len(nums), 2):
    left = i
    right = min(i+add, len(nums))
    tmp = sums[right] - sums[left]
    res = max(tmp, res)

#２分探索
li, ri = bisect.bisect_left(p_ac, l[i]-1), bisect.bisect_right(p_ac, r[i]-1)    

#ソート関数
org_list = [3, 1, 4, 5, 2]
new_list = sorted(org_list)
print(org_list)
print(new_list)
# [3, 1, 4, 5, 2]
# [1, 2, 3, 4, 5]

#Distance Transformation
    for h in range(0,H):
        for w in range(0,W):
            if h == 0 and w == 0:
                pass
            elif h == 0:
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h-1][W-w]+1)
            elif w == 0:   
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h][W-w-1]+1)
            else:
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h][W-w-1]+1, D[H-h-1][W-w]+1, D[H-h][W-w]+2)
            d_max = max(D[H-h-1][W-w-1], d_max)

"""



N, M = list(map(int, input().split()))
a = [0]*M
for m in range(M):
    a[m] = int(input())
MOD = 10**9 + 7

def main(): 
    dp = [0]*(N+2)
    dp[0] = 1
    for n in range(1,N+1):
        if n ==1:
            if n in a:
                dp[n] = 0
            else:
                dp[n] += dp[n-1]
        else:                        
            if n in a:
                dp[n] = 0
            else:
                dp[n] += dp[n-2] + dp[n-1]
                
    #print(dp)
    print(dp[N]%MOD)
                
                
                
            
            
                

    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n,m=(int(i) for i in input().split())
a = [int(input()) for i in range(m)]
#print(n,m,a)

d=[0 for i in range(100000+10)]
p=1000000007
#n=100
#a=[1, 23, 45, 67, 89]
aa=[0 for i in range(100000+10)]

for i in range(10**5+10):
    if i in a:
        aa[i]=1
#print(aa)

d[0]=1
if aa[1] == 0:
    d[1]=1
else:
    d[1]=0
    
if aa[2] == 0:
    d[2]=d[1]+d[0]
else:
    d[2]=0
    
for i in range(2,n+1):
    if aa[i] == 0:
        d[i]=d[i-1]+d[i-2]
        d[i]=d[i]%p
    else:
        d[i]=0
#print(d)

print(d[n]%p)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, M = map(int, input().split())
    A = [int(input()) for _ in range(M)]
    dp = [0] * (N + 2)
    dp[-2] = 1
    for i in range(N - 1, -1, -1):
        if i in A:
            continue
        elif i + 1 in A:
            dp[i] = dp[i + 2]
        elif i + 2 in A:
            dp[i] = dp[i + 1]
        elif i + 1 in A and i + 2 in A:
            break
        else:
            dp[i] = dp[i + 1] + dp[i + 2]
    print(dp[0] % 1000000007)


main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
A = [0 for i in range(N + 2)]
A[0] = 0
A[1] = 1
brokun = []
for i in range(M):
    brokun.append(int(input()) + 1)
for i in range(2, N+2):
    if i in brokun:
        A[i] = 0
    else:
        A[i] = A[i-1]+ A[i-2]
        A[i] = A[i] % 1000000007
    #print(A)
print(A[N + 1])

Submission status: Time Limit Exceeded

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

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

print(dp[n]%mo)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

N, M = map(int, input().split())
# 0段目からN段目まである
N += 1
broken_stairs = [int(input()) for _ in range(M)]

# dp[i] = i段目に辿り着くまでの経路本数
dp = [0 for _ in range(N)]

# 初期化する
if 0 not in broken_stairs:
    dp[0] = 1
if 1 not in broken_stairs:
    dp[1] = 1

# MOD用
MOD = 10 ** 9 + 7

for i in range(2, N):
    """TLEだったやつ
    # 1段上が範囲内で使用可能なら現在の段の経路数を足す
    if i + 1 < N and i + 1 not in broken_stairs:
        # MODを取って更新
        dp[i + 1] += dp[i] % MOD
    # 2段上が範囲内で使用可能なら現在の段の経路数を足す
    if i + 2 < N and i + 2 not in broken_stairs:
        # MODを取って更新
        dp[i + 2] += dp[i] % MOD
    """
    # i段目が使用可能なら1段前と2段前の経路数を足した値を入れる
    if i not in broken_stairs:
        dp[i] = (dp[i - 1] + dp[i - 2]) % MOD


print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

N, M = map(int, input().split())
# 0段目からN段目まである
N += 1
broken_stairs = [int(input()) for _ in range(M)]

# dp[i] = i段目に辿り着くまでの経路本数
dp = [0 for _ in range(N)]

# 初期値
dp[0] = 1

# MOD用
MOD = 10 ** 9 + 7

for i in range(N):
    # 1段上が範囲内で使用可能なら現在の段の経路数を足す
    if i + 1 < N and i + 1 not in broken_stairs:
        # MODを取って更新
        dp[i + 1] += dp[i] % MOD
    # 2段上が範囲内で使用可能なら現在の段の経路数を足す
    if i + 2 < N and i + 2 not in broken_stairs:
        # MODを取って更新
        dp[i + 2] += dp[i] % MOD

print(int(dp[-1] % MOD))

Submission status: Time Limit Exceeded

Solution code:
lis=list(map(int,input().split()))
alist=list([int(input()) for _ in range(lis[1])])
steps=[0]*(lis[0]+2)
steps[1]=1
for i in range(2,lis[0]+2):
    if i-1 not in alist:
        steps[i]=(steps[i-1]+steps[i-2])
ans=steps[-1]%((10**9)+7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
lis=list(map(int,input().split()))
alist=[]
for i in range(lis[1]):
    alist.append(int(input()))
steps=[0]*(lis[0]+2)
steps[1]=1
for i in range(2,lis[0]+2):
    if i-1 not in alist:
        steps[i]=(steps[i-1]+steps[i-2])
ans=steps[-1]%((10**9)+7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
lis=list(map(int,input().split()))
alist=[]
for i in range(lis[1]):
    alist.append(int(input()))
steps=[0]*(lis[0]+2)
steps[1]=1
for i in range(2,lis[0]+2):
    if i-1 not in alist:
        steps[i]=(steps[i-1]+steps[i-2])%((10**9)+7)
ans=steps[-1]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, raw_input().split(' '))
P = 1000000007

skip = []
for i in range(M):
    skip.append(int(raw_input()))


steps = [0] * (N + 2)
steps[0] = 1

for i in range(0, N):
    if i+1 not in skip:
        steps[i+1] += steps[i]
        steps[i+1] %= P

    if i+2 not in skip:
        steps[i+2] += steps[i]
        steps[i+2] %= P

print steps[N]

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, raw_input().split(' '))
P = 1000000007

skip = []
for i in range(M):
    skip.append(int(raw_input()))


steps = [0] * (N + 2)
steps[0] = 1

for i in range(0, N):
    if i+1 not in skip:
        steps[i+1] += steps[i]
        steps[i+1] %= P

    if i+2 not in skip:
        steps[i+2] += steps[i]
        steps[i+1] %= P

print steps[N]

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
#d=["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]
#import numpy as np
#n=int(input())
#import fractions
#import math
#lis=list(input().split())
#lis=list(map(float,input().split()))
#n=int(input())
#S=input()
import itertools

lis=list(map(int,input().split()))
alist=[-1]
ans=1
for i in range(lis[1]):
    alist.append(int(input()))
alist.append(lis[0]+1)

for i in range(lis[1]+1):
    l=alist[i+1]-alist[i]-2
    tmp=0
    t=int((l+l%2)/2)
    h=int((l-l%2)/2)
    for j in range(h+1):
        tmp+=len(list(itertools.combinations(range(t+j),h-j)))%((10**9)+7)
    ans=(ans*tmp)%((10**9)+7)
print(ans)

Submission status: Time Limit Exceeded

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

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

print(dp[0])

Submission status: Time Limit Exceeded

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

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

mod = 10**9+7

for i in range(N):
  for j in range(i+1, min(N, i+2)+1):
    if j not in A:
      dp[j] += dp[i]
      dp[j] %= mod
print(dp[N])

Submission status: Time Limit Exceeded

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

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

print(dp[0] % mod)

Submission status: Time Limit Exceeded

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

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

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

print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
 
N, M = map(int, input().split())
mod = 1000000007
dp = [0] * (N+1)
A = [int(input()) for _ in range(M)] 
if (N-1 in A) == False:
    dp[N], dp[N-1] = 1, 1
else:
    dp[N] = 1

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

print(dp[0] % mod)

Submission status: Time Limit Exceeded

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

dp = [1, 1]
if 1 in a:
  dp[1] = 0

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

print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
 
N, M = map(int, input().split())
mod = 1000000007
dp = [0] * (10**5 + 1)
A = [int(input()) for _ in range(M)] 
if (N-1 in A) == False:
    dp[N], dp[N-1] = 1, 1
else:
    dp[N] = 1

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

print(dp[0])

Submission status: Time Limit Exceeded

Solution code:
N, M = list(map(int, input().split()))
not_used = [int(input()) for i in range(M)]
mod_value = 1000000007
 

dp = [0] * (N + 1)
dp[0] = 1
for i in range(N):
  if i+1 not in not_used:
    dp[i+1] += dp[i]
    dp[i+1] %= mod_value
  
  if i+2 not in not_used and i+2 < N+1:
    dp[i+2] += dp[i]
    dp[i+2] %= mod_value

print(dp[-1])

Submission status: Time Limit Exceeded

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

if 1 in a:
    dp[1] = 0

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

print(dp[n])

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
def main():
    N, M = map(int, input().split())
    a = []
    for i in range(M):
        a.append(int(input()))
    
    #print("a", a)
    
    dp = ([0] * N)
    dp.append(1)
    dp.append(0)
    mod = 1000000007
    
    for s in reversed(range(N)):
        if s in a: # xだったら
            if s+1 in a:
                dp[s] = 0 # 2回連続で穴があったら0返して終了
                break
            else:
                dp[s] = 0 # 無を代入
        else: # oだったら
            dp[s] = (dp[s+1] + dp[s+2]) % mod # DP!! DP!!
            
    print(dp[0])

main()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
N, M = map(int, input().split())
a = []
for i in range(M):
    a.append(int(input()))

#print("a", a)

dp = ([0] * N)
dp.append(1)
dp.append(0)
mod = 1000000007

for s in reversed(range(N)):
    if s in a: # xだったら
        if s+1 in a:
            dp[s] = 0 # 2回連続で穴があったら0返して終了
            break
        else:
            dp[s] = 0 # 無を代入
    else: # oだったら
        dp[s] = (dp[s+1] + dp[s+2]) % mod # DP!! DP!!
        
print(dp[0])

Submission status: Time Limit Exceeded

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

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

from functools import lru_cache
@lru_cache(maxsize=None)

def fib(n):
  a, b = 1, 2
  for i in range(1,n+1):  
    if (i == 1):
      if (i in lst1):
        a, b = 0, 1
    else:
      if (i in lst1):
        a, b = 0, a
      else:
        a, b = b, b+a
  return a

print(fib(N)  % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
# fx = fx-1 + fx-2
N,M = map(int,input().split())
aa = [int(input()) for _ in range(M)]

oks = [True for _ in range(N)] + [False] + [False]
for a in aa:
    oks[a-1] = False
dp = [0]*(N+1)
dp[0]=1
# print(oks)
MOD = 10**9+7

for i in range(1,N+1):
    if i in aa:
        continue
    if i==1:
        dp[1] = dp[0]
        continue
    dp[i] = dp[i-1] + dp[i-2]
    dp[i] %= MOD
print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
N, M = map(int, input().split())
a = []
for i in range(M):
    a.append(int(input()))

#print("a", a)

dp = [1, 0]
mod = 1000000007

for s in reversed(range(N)):
    if s in a: # xだったら
        if s+1 in a:
            dp[0] = 0 # 2回連続で穴があったら
            break
        else:
            dp.insert(0, 0) # 無を代入
        #continue
    else: # oだったら
        t = (dp[0] + dp[1]) % mod # DP!! DP!!
        dp.insert(0, t)
        
print(dp[0])

Submission status: Time Limit Exceeded

Solution code:
#ABC129C-TypicalStairs.py

#import list
import numpy as np
from sys import stdin, setrecursionlimit
from functools import lru_cache

input = stdin.readline
setrecursionlimit(1000)

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

#variable
rootList = [1]+[0]*(N)

#function

#class

#main function
def main():
    for i in range(N):
        rootList[i+1] = rootList[i]+rootList[i-1]
        if i+1 in A:
            rootList[i+1] = 0
    print(rootList[N]%1000000007)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

def fib(n):
  a, b = 1, 2
  for i in range(1,n+1):  
    if (i == 1):
      if (i in lst1):
        a, b = 0, 1
    else:
      if (i in lst1):
        a, b = 0, a
      else:
        a, b = b, b+a
  return a

print(fib(N)  % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
N, M = map(int, input().split())
a = []
for i in range(M):
    a.append(int(input()))
a.append(N+1)
a.append(N+2)
#print("a", a)

dp = [1, 0]
#s = 0
mod = 1000000007

for s in reversed(range(N)):
    if s in a: # xだったら
        dp.insert(0, 0) # 無を代入
        #continue
    else: # oだったら
        t = (dp[0] + dp[1]) % mod
        dp.insert(0, t)
        
print(dp[0])

Submission status: Time Limit Exceeded

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

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

from functools import lru_cache
@lru_cache(maxsize=1000000007)
def fib(n):
  a, b = 1, 2
  for i in range(1,n+1):  
    if (i == 1):
      if (i in lst1):
        a, b = 0, 1
      yield a
    else:
      if (i in lst1):
        a, b = 0, a
      else:
        a, b = b, b+a
      yield a

lst2 = [i for i in fib(N)]
print(lst2[-1] % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
#ABC129C-TypicalStairs.py

#import list
from sys import stdin, setrecursionlimit
from functools import lru_cache

input = stdin.readline
setrecursionlimit(10000)

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

#variable

#function
@lru_cache(maxsize=None)
def rootCount(position):
    if position < 0:
        return 0
    elif position == 0:
        return 1
    elif position in A:
        return 0
    else:
        return (rootCount(position-1)+rootCount(position-2)) % 1000000007
#class

#main function
def main():
    i = 1
    while i < N:
        rootCount(i)
        i += 1
    print(rootCount(N))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

mod_num = 10 ** 9 + 7
a = [0] * M

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

val = [0,1]
j = 0
for i in range(1, N + 1):
    ans = (val[0] + val[1]) % mod_num
    val[0] = val[1]
    val[1] = ans
    if i in a:
        val[1] = 0

 
print(ans)

Submission status: Time Limit Exceeded

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

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

def fib(n):
  a, b = 1, 2
  for i in range(1,n+1):  
    if (i == 1):
      if (i in lst1):
        a, b = 0, 1
      yield a
    else:
      if (i in lst1):
        a, b = 0, a
      else:
        a, b = b, b+a
      yield a

lst2 = [i for i in fib(N)]
print(lst2[-1] % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
import numpy
N,M=map(int,input().split())
if(M>0):a=[0]*M
else:a=[0]
if(N>1):tori=[0]*N
else:tori=[0]*2
for num in range(M):
    a[num]=int(input())

tori[0]=1
tori[1]=2
if(1 in a):
    tori[0]=0
    tori[1]=1
if(2 in a):
    tori[1]=0
gen=3
while(gen<=N):
    tori[gen-1]=(tori[gen-2]+tori[gen-3])%1000000007
    if(gen in a):
        tori[gen-1]=0
    gen=gen+1

print(tori[N-1])

Submission status: Time Limit Exceeded

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

mod_num = 10 ** 9 + 7
a = [0] * N

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

val = [0,1]
j = 0
for i in range(1, N + 1):
    ans = (val[0] + val[1]) % mod_num
    val[0] = val[1]
    val[1] = ans
    if i in a:
        val[1] = 0
 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
MOD = 1000000007

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

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

print(dp[0][N] % MOD)

Submission status: Time Limit Exceeded

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

x = 1
y = 1
for i in range(1, n+1):
  if i in a:
    if i == 1:
      y = 0
    else:
      x = y
      y = 0
  else:
    if i != 1:
      tmp = x + y
      x = y
      y = tmp

print(y % 1000000007)

Submission status: Time Limit Exceeded

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

dp = [0 for _ in range(N+1)]
P = 10**9 + 7

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

Submission status: Time Limit Exceeded

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

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

for n in range(N+1):
    if n>1:
        if n-1 in A and n in A:
            print(0)
            break
        elif n in A:
            ans[n]=0
        else:
            ans[n]=(ans[n-1]+ans[n-2]) % 1000000007
else:
    print(ans[N])

Submission status: Time Limit Exceeded

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

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

mod = 10 ** 9 + 7
f2, f1 = 0, 1
for i in range(1, N + 1):
  if i in broken:
    if i - 1 in broken:
      print(0)
      exit()
    f2 = f1
    f1 = 0
    continue
  f = (f2 + f1) % mod
  f2 = f1
  f1 = f
print(f)

Submission status: Time Limit Exceeded

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

dp = [0] * (N + 1)
dp[0] = 1
if 1 not in a:
	dp[1] = 1
else:
	dp[1] = 0
for i in range(2, N + 1):
	if i in a:
		continue
	dp[i] = dp[i - 1] + dp[i - 2]
	dp[i] %= INF

print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline

n, m = map(int, input().split())
a_list = []
comb_list = [0, 1, 2]
for _ in range(m):
    a = int(input())
    if a == 1:
        comb_list[a] = 0
        comb_list[a+1] = 1
    elif a == 2:
        comb_list[a] = 0
    else:
        a_list.append(a)
for i in range(3, n+1):
    if i in a_list:
        comb_list.append(0)
    else:
        comb_list.append((comb_list[-2]+comb_list[-1])%(10**9+7))
print(comb_list[n])

Submission status: Time Limit Exceeded

Solution code:
# fx = fx-1 + fx-2
N,M = map(int,input().split())
aa = [int(input()) for _ in range(M)]

oks = [(i not in aa) for i in range(N+1)]+[False]
dp = [0]*(N+1)
dp[0]=1
# print(oks)
MOD = 10**9+7

for i in range(N):
    for j in [1,2]:
        if oks[i+j]:
            dp[i+j] += dp[i]
            dp[i+j] %= MOD

print(dp[N])

Submission status: Time Limit Exceeded

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

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

val = [0,1]
for i in range(1, N + 1):
    ans = (val[0] + val[1]) % (10**9 +7)
    val[0] = val[1]
    val[1] = ans
    if i in a:
        val[1] = 0


print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import scipy.special as scm

def co(a,b):
    ans = 1
    for k in range(min(a-b,b)):
        ans = ans * (a-k) // (k+1)
    return ans

def comb(N):
    if N == 1:
        return 1
    else:
        sum0 = 0
        for i in range(N//2+1):
            sum0 = (sum0+co(N-i, i))%1000000007
        return sum0

def main():
    n, m = map(int, input().split())
    a = [-1]
    for i in range(m):
        a0 = int(input())
        a.append(a0)
    a.append(n+1)
    a = np.array(a)
    a = np.diff(a) -2
    # if a[0] == 0:
    #     a[0] = 1
    # if a[-1] == 0:
    #     a[-1] = 1
    if -1 in a:
        print(0)
        return
    sum1 = 1
    for i in a:
        sum1 = (sum1*comb(i))%1000000007
    print(int(sum1))
    return

main()

Submission status: Time Limit Exceeded

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

def dp(n,ls):
    dp_table=[[0 for i in range(n+1)]]
    dp_table[0][0]=1
    sum=0
    count=1
    edge=0
    while True:
        row=[0]*count
        previous=dp_table[-1]
        for i in range(count,n+1):
            if i in ls:
                row.append(0)
            elif i==0:
                row.append(0)
            elif i==1:
                row.append(previous[0])
            else:
                row.append(previous[i-1]+previous[i-2])
            if i==edge+2:
                edge=i
                row=row+([0]*(n-edge))
                break
        sum+=row[-1]
        if row.count(0)==n+1:
            return sum
        dp_table.append(row)
        count+=1
 
print(dp(n,ls)%1000000007)

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

l = [1]
for i in range(1, n+1):
  if len(l) == 2:
    tmp = l[0]
    tmp1 = l[1]
    if i in a:
      if tmp1 == 0:
        print(0)
        exit()
      l[0] = tmp1
      l[1] = 0
    else:
      l[0] = tmp1
      l[1] = tmp + tmp1
  else:
    if i in a:
      l.append(0)
    else:
      l.append(1)

print(l[-1] % 1000000007)

Submission status: Time Limit Exceeded

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

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

val = [0,1]
for i in range(1, N + 1):
    ans = val[-2] + val[-1]
    val.append(ans)
    if len(a) > 0:
        if i == a[0]:
            val[-1] = 0
            a.pop(0)

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