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:
Mod = 10**9+7
N,M = map(int, input().split())
a = [int(input()) for _ in range(M)]
b = [1]+[0]*N
for i in range(1,N+1):
    if i in a:
        continue
    if i == 1:
        b[1] += b[0]
        continue
    b[i] += b[i-1]+b[i-2]
print(b[N]%Mod)

Submission status: Time Limit Exceeded

Solution code:
#一時間以上かかった
#一つだけTLE
#そっから30ぷん

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

n,m=map(int ,input().split())
a1=[int(input()) for i in range(m)]
a1.append(n+1)
c1=1
a2=0
for i in a1:
    a3=i-1-a2
    c2=0
    for j in range(a3//2+1):
        c2+=combinations_count(a3-j,j)
    c1=(c1*c2)%(1000000007)
    a2=i+1
    if c1==0:
        break



print(c1)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
broken = [int(input()) for _ in range(m)]
f = [1, 1]

for i in range(2, n+1):
  f_nm1 = f[i-1] if i-1 not in broken else 0
  f_nm2 = f[i-2] if i-2 not in broken else 0
  f.append(f_nm1 + f_nm2)

print(f[-1]%1000000007)

Submission status: Time Limit Exceeded

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

for i in range(2, n+1):
  f_nm1 = f[i-1] if i-1 not in broken else 0
  f_nm2 = f[i-2] if i-2 not in broken else 0
  f.append(f_nm1 + f_nm2)

print(f[-1]%1000000007)

Submission status: Time Limit Exceeded

Solution code:
import operator as op
from functools import reduce
import sys
input = sys.stdin.readline

def ncr(n, r):
  r = min(r, n-r)
  numer = reduce(op.mul, range(n, n-r, -1), 1)
  denom = reduce(op.mul, range(1, r+1), 1)
  return numer // denom

def climbStairs(n):
  #if n == 0:
  #  return 0
  
  c = 0
  for i in range(n//2+1):
    c += ncr(i+n-2*i, i)
  return int(c)

n, m = map(int, input().split())

stairs = []
c = 0
for _ in range(m):
  broken = int(input())
  stairs.append(broken - c - 1)
  c = broken + 1

if c != n:
  stairs.append(n - c)

print(reduce(op.mul, map(climbStairs ,stairs), 1)%1000000007)

Submission status: Time Limit Exceeded

Solution code:
import operator as op
from functools import reduce

def ncr(n, r):
  r = min(r, n-r)
  numer = reduce(op.mul, range(n, n-r, -1), 1)
  denom = reduce(op.mul, range(1, r+1), 1)
  return numer // denom

def climbStairs(n):
  #if n == 0:
  #  return 0
  
  c = 0
  for i in range(n//2+1):
    c += ncr(i+n-2*i, i)
  return int(c)

n, m = map(int, input().split())

stairs = []
c = 0
for _ in range(m):
  broken = int(input())
  stairs.append(broken - c - 1)
  c = broken + 1

if c != n:
  stairs.append(n - c)

print(reduce(op.mul, map(climbStairs ,stairs), 1)%1000000007)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r)*math.factorial(r))

n,m=[int(i) for i in input().split()]
a1=[int(input()) for i in range(m)]
a1.append(n+1)
c1=1
a2=0
for i in a1:
    a3=i-1-a2
    c2=0
    for j in range(a3//2+1):
        c2+=combinations_count(a3-j,j)
    c1=(c1*c2)%(1000000007)
    a2=i+1
    if c1==0:
        break



print(c1)

Submission status: Time Limit Exceeded

Solution code:
#一時間以上かかった
#一つだけTLE

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

n,m=[int(i) for i in input().split()]
a1=[int(input()) for i in range(m)]
a1.append(n+1)
c1=1
a2=0
for i in range(m+1):
    a3=a1[i]-1-a2
    c2=0
    for j in range(0,a3//2+1):
        c2+=combinations_count(a3-j,j)
    c1=(c1*c2)%(1000000007)
    a2=a1[i]+1
    if c1==0:
        break



print(c1)

Submission status: Time Limit Exceeded

Solution code:
import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r)*math.factorial(r))

n,m=[int(i) for i in input().split()]
a1=[int(input()) for i in range(m)]
a1.append(n+1)
c1=1
a2=0
for i in range(m+1):
    a3=a1[i]-1-a2
    a4=a3//2
    c2=0
    c3=1
    for j in range(0,a4+1):
        c3=combinations_count(a3-j,j)
        c2+=c3
        #print(c3)
    #print(c2)
    c1=c1*c2%(1000000007)
    a2=a1[i]+1
    if c1==0:
        break



print(c1)

Submission status: Time Limit Exceeded

Solution code:
import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r)*math.factorial(r))

n,m=[int(i) for i in input().split()]
a1=[int(input()) for i in range(m)]
a1.append(n+1)
c1=1
a2=0
for i in range(m+1):
    a3=a1[i]-1-a2
    a4=a3//2
    c2=0
    c3=1
    for j in range(0,a4+1):
        c3=combinations_count(a3-j,j)
        c2+=c3
        #print(c3)
    #print(c2)
    c1=c1*c2%(1000000007)
    a2=a1[i]+1



print(c1)

Submission status: Time Limit Exceeded

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

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

print(fibo[-1])

Submission status: Time Limit Exceeded

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

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

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

else:
    ans = dp[-1] % 1000000007

print(ans)

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
ans = 0

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

else:
    ans = dp[-1] % 1000000007

print(ans)

Submission status: Time Limit Exceeded

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

if 1 in a:
  fibo=[1,0]
else:
  fibo=[1,1]
mod=10**9+7
for i in range(2,n+1):
  if i in a:
    f=0
  else:
    f=(fibo[-2]+fibo[-1])%mod
  fibo.append(f)

print(fibo[-1])

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
ans = 0

for i in range(1, N+1):
    if i in a:
        dp[i] = 0
        if dp[i-1] == 0:
            ans = 0
            break
    else:
        try:
            dp[i] = dp[i-1] + dp[i-2]
        except:
            dp[i] = dp[i-1]
else:
    ans = dp[-1] % 1000000007

print(ans)

Submission status: Time Limit Exceeded

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

dp = [1, 2]
A = [int(input()) for _ in range(M)]
if M != 0:
    if M >= 2 and A[0] == 1 and A[1] == 2:
        dp = [0, 0]
    elif A[0] == 1:
        dp = [0, 1]
    elif A[0] == 2:
        dp = [1, 0]
else:
    A = [0]

MOD = 1000000007

if N == 1:
    while True:
        pass
    print (0)
if N == 2:
    print (dp[-1])
else:
    cnt = 0
    for n in range(2, N):
        while(cnt < M - 1 and A[cnt] < n + 1):
            cnt += 1
        if A[cnt] == n + 1:
            dp[0] = dp[1]
            dp[1] = 0
        else:
            new_val = (max(dp[0], 0) + max(dp[1], 0)) % MOD
            dp[0] = dp[1]
            dp[1] = new_val

    print (dp[-1])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import math
import copy
import fractions
import numpy as np

# ===FUNCTION===

def getInputNum():
    inputNum = int(input())
    return inputNum

def getInputListInt():
    outputoData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData

def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList

def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList

# ===CODE===

n, m = map(int, input().split())

broken = getSomeInputInt(m)

mod = 1000000007

dp = np.zeros(n+1)
dp[0] = 1

for i in range(n+1):
    if not(i+1 in broken) and i+1 < n+1:
        dp[i+1] += dp[i]
        dp[i+1] %= mod

    if not (i + 2 in broken) and i+2 < n+1:
        dp[i + 2] += dp[i]
        dp[i + 2] %= mod

print(int(dp[n]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math
MOD = 1000000007

def a1b2(a, b):
    return ((math.factorial(a+b)) // (math.factorial(a) * math.factorial(b)))

def houhou(first, second):
    sa = second-first
    sum = 0
    for b in range((sa // 2)+1):
        a = sa - 2*b
        sum += a1b2(a, b)
        sum = sum % MOD

    return sum

a = input().split()
dan_num = int(a[0])
hole_num = int(a[1])
areas =[[0, None]]
holes = []
hole = None
before_hole = None
shippai = False
for i in range(hole_num):
    hole = int(input())
    areas[i][1] = hole-1
    areas.append([hole + 1, None])
    if before_hole == (hole -1) :
        shippai = True
    before_hole = hole
areas[-1][1] = dan_num

ways = 1
if dan_num == 1:
    print(1)
elif shippai:
    print(0)
else:
    for area in areas:
        ways *= houhou(area[0], area[1])
        ways = ways % MOD
    print(ways)

Submission status: Time Limit Exceeded

Solution code:
import math
import sys
import queue
from collections import Counter
from itertools import accumulate
from fractions import gcd
from functools import reduce

def lcm(a, b):
    return a * b // gcd(a, b)

def combination_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)

mod = 1000000007

"""
# 標準入力取得
## 文字列
    = sys.stdin.readline().rstrip()
    = list(sys.stdin.readline().rstrip())

## 数値
    = int(sys.stdin.readline())
    = map(int, sys.stdin.readline().split())
    = list(map(int, sys.stdin.readline().split()))
    = [list(map(int,list(sys.stdin.readline().split()))) for i in range(N)]
"""

if __name__ == "__main__":
    N , M = map(int, sys.stdin.readline().split())
    A = [int(sys.stdin.readline()) for _ in range(M)]
    broken = [True if i in A else False for i in range(N + 1)]
    L = [0] * (N + 1)
    L[0] = 1
    if 1 not in A:
        L[1] = 1
    for i in range(2, N + 1):
        if not broken[i]:
            L[i] = L[i - 1] + L[i - 2]
    print(L[N] % mod)

Submission status: Time Limit Exceeded

Solution code:
import math
import sys
import queue
from collections import Counter
from itertools import accumulate
from fractions import gcd
from functools import reduce

def lcm(a, b):
    return a * b // gcd(a, b)

def combination_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)

mod = 1000000007

"""
# 標準入力取得
## 文字列
    = sys.stdin.readline().rstrip()
    = list(sys.stdin.readline().rstrip())

## 数値
    = int(sys.stdin.readline())
    = map(int, sys.stdin.readline().split())
    = list(map(int, sys.stdin.readline().split()))
    = [list(map(int,list(sys.stdin.readline().split()))) for i in range(N)]
"""

if __name__ == "__main__":
    N , M = map(int, sys.stdin.readline().split())
    A = [int(sys.stdin.readline()) for _ in range(M)]
    L = [0] * (N + 1)
    L[0] = 1
    if 1 not in A:
        L[1] = 1
    for i in range(2, N + 1):
        if i not in A:
            L[i] = L[i - 1] + L[i - 2]
    print(L[N] % mod)

Submission status: Time Limit Exceeded

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

#通過できない階段をaに格納
a = [int(input()) for _ in range(m)]    
count = [0 for _ in range(n+1)]
count[0] = 1
for i in range(1,n+1):
    if i not in a:
        count[i] = count[i-1]+count[i-2]        

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

Submission status: Time Limit Exceeded

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

#通過できない階段をaに格納
a = [int(input()) for _ in range(m)]    
count = [0]*(n+1)
count[0] = 1
for i in range(1,n+1):
    if i not in a:
        count[i] = count[i-1]+count[i-2]        

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

Submission status: Time Limit Exceeded

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

a = []
#通過できない階段をaに格納
for _ in range(m):
    a.append(int(input()))
    
count = [0]*(n+1)
count[0] = 1
for i in range(1,n+1):
    if i in a:
        continue
    else:
        count[i] = count[i-1]+count[i-2]

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

Submission status: Time Limit Exceeded

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

a = []
#通過できない階段をaに格納
for _ in range(m):
    a.append(int(input()))
    
count = [0]*(n+1)
count[0] = 1
for i in range(1,n+1):
    if i in a:
        count[i] = 0
    else:
        count[i] = count[i-1]+count[i-2]

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

Submission status: Time Limit Exceeded

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

f = [1, 1]
for i in range(n-1)[::-1]:
  flag1 = True if i+1 not in alist else False
  flag2 = True if i+2 not in alist else False
  if flag1 is False and flag2 is False:
    print(0)
    exit()
  elif flag1 is False and flag2 is True:
    f = [f[1]] + [f[0]]
  elif flag1 is True and flag2 is False:
    f = [f[0]] + [f[0]]
  else:
    f = [f[0]+f[1]] + [f[0]]
     
print(int(f[0]%div_num))

Submission status: Time Limit Exceeded

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

f = [1, 1]
for i in range(n-1)[::-1]:
  if i+1 in alist and i+2 in alist:
    print(0)
    exit()
  elif i+1 in alist and i+2 not in alist:
    f = [f[1]] + [f[0]]
  elif i+1 not in alist and i+2 in alist:
    f = [f[0]] + [f[0]]
  else:
    f = [f[0]+f[1]] + [f[0]]
     
print(int(f[0]%div_num))

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9+7
n,m = map(int,input().split())
lst = [int(input()) for _ in range(m)]
dp = [0]*(n+1)
for i in range(1,n+1):
    if i in lst:
        continue
    elif i==1:
        dp[i] = 1
    elif i==2:
        dp[i] = dp[1]+1
    else:
        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())
a=[int(input()) for _ in range(M)]
dp=[1]*(N+1)
if 1 in a:
  dp[1]=0
else:
  dp[1]=1
for i in range(2,N+1):
  if i in a:
    dp[i]=0
  else:
    dp[i]=dp[i-1]+dp[i-2]
  dp[i]%=1000000007
print(dp[N])

Submission status: Time Limit Exceeded

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

As = []
a_ = -1
for i in range(m):
  a = int(input())
  if a == a_ + 1:
    print(0)
    sys.exit()
  As.append(a)
  a_ = a

nums = [1] + [0] * n
if 1 in As:
  pass
else:
  nums[1] = 1
  
for i in range(2, n + 1):
  if i in As:
    continue
  else:
    nums[i] = (nums[i-1] + nums[i-2]) % 1000000007
    
print(nums[-1])

Submission status: Time Limit Exceeded

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

As = []
a_ = -1
for i in range(m):
  a = int(input())
  if a == a_ + 1:
    print(0)
    sys.exit()
  As.append(a)
  a_ = a

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

Submission status: Time Limit Exceeded

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

As = []
a_ = -1
for i in range(m):
  a = int(input())
  if a == a_ + 1:
    print(0)
    sys.exit()
  As.append(a)
  a_ = a

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

Submission status: Time Limit Exceeded

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

As = []
for i in range(m):
  As.append(int(input()))

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
MOD = 10**9 + 7

N, M = map(int, input().split())
broken_floors = [int(input()) for _ in range(M)]
dp = [0]*(N+2)
dp[1] = 1

for i in range(1, N+1):
    if i not in broken_floors:
        dp[i+1] = (dp[i] + dp[i-1]) % MOD

print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
big = 10**9 + 7

def typical_stairs(n,m,a):

    route = [0]*(n+1)
    route[0] = 1
    ans = route[0]
    tmp = 0
    a.append(-1)
    for j in range(m+1):
        for i in range(tmp,n):
            if a[j] == i+1:
                #print("a=%d, i+2=%d "%(a[j],i+2))
                route[i+1] = 0
                tmp = a[j]
                #print("route%d, %d = 0 + 0, route-> %s"%(i+1,route[i+1],route))
                if route[i] == 0 and route[i+1] == 0:
                    return 0
                else:
                    break
            else:
                route[i+1] = route[i] + route[i-1]

                #print("route%d, %d = %d + %d, route-> %s"%(i+1,route[i+1],route[i],route[i-1],route))
            ans = route[i+1]
    return ans%big
if __name__ == '__main__':
    n,m = map(int,raw_input().split())
    a = [int(raw_input()) for _ in range(m)]

    print typical_stairs(n,m,a)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

MOD = 10 ** 9 + 7
n,m = map(int,input().split())
A = [int(input()) for _ in range(m)] #壊れた階段

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

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

print(dp[n])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

n,m = map(int,input().split())
A = [int(input()) for _ in range(m)] #壊れた階段

pos = 0
count = 1
dp = [0] * (n+1)
dp[0] = 1 #dp[i] i段目の時点での場合の数 dp[n]まで

for i in range(n):
    # dp[i] %= 1000000007
    if (i+1) in A and (i+2) in A:
        print(0)
        exit()
    if (i+1) not in A:
        dp[i+1] += dp[i]
    if (i+2) not in A and (i+2) <= n:
        dp[i+2] += dp[i]

print(dp[n] % 1000000007)

Submission status: Time Limit Exceeded

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

if 1 not in lis:
    ans[1]=1

for i in range(n-1):
    if i+2 not in lis:
        ans[i+2]=ans[i]+ans[i+1]

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

print(dp[n]%1000000007)

Submission status: Time Limit Exceeded

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

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

print(dp[n]%1000000007)

Submission status: Time Limit Exceeded

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

dp = [1,1]
temp = 1

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

print(dp[n]%1000000007)

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 = [1]*2 + [0 for _ in range(n-1)]
MOD = 10**9+7
   
for i in range(n-1):
  if i+1 in a:
    dp[i+1] = 0
  dp[i+2] = dp[i]+dp[i+1]
  dp[i+2] %= MOD

print(dp[-1])

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

print(dp[-1])

Submission status: Time Limit Exceeded

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

print(dp[-1]%mod)

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 = [1]*2 + [0 for _ in range(n-1)]
mod = 1000000007
for i in range(1,m):
  if a[i]==a[i-1]+1:
    print(0)
    sys.exit() 
    
for i in range(n-1):
  if i+1 in a:
    dp[i+1] = 0
  dp[i+2] = dp[i]+dp[i+1]
  
  if dp[i+2] >= mod:
    dp[i+2] %= mod

print(dp[-1]%mod)

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 = [1]*2 + [0 for _ in range(n-1)]
mod = 1000000007
  
for i in range(n-1):
  if i+1 in a:
    dp[i+1] = 0
  dp[i+2] = dp[i]+dp[i+1]
  
  if dp[i+2] >= mod:
    dp[i+2] %= mod

print(dp[-1]%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
n,m = map(int,input().split())
a = [int(input()) for i in range(m)]
dp = [1]*2 + [0 for _ in range(n-1)]
mod = 1000000007
  
for i in range(n-1):
  if i+1 in a:
    dp[i+1] = 0
  dp[i+2] = dp[i]+dp[i+1]
  
  if dp[i+2] >= mod:
    dp[i+2] -= mod

print(dp[-1]%mod)

Submission status: Time Limit Exceeded

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

print(dp[-1]%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline

n,m = [int(i) for i in readline().split()]
a = [int(sys.stdin.readline()) for i in range(m)]
dp = [1]*2 + [0]*(n-1)
mod = 1000000007
 
for i in range(1,m):
  if a[i]==a[i-1]+1:
    print(0)
    sys.exit()
  
for i in range(n-1):
  if i+1 in a:
    dp[i+2] = dp[i]
    dp[i+1] = 0
  else:
    dp[i+2] = dp[i]+dp[i+1]

print(dp[-1]%mod)

Submission status: Time Limit Exceeded

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

print(dp[-1]%mod)

Submission status: Time Limit Exceeded

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

print(dp[-1]%mod)

Submission status: Time Limit Exceeded

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

print(dp[-1]%mod)

Submission status: Time Limit Exceeded

Solution code:

import sys
sys.setrecursionlimit(1000000)

# 壊れている床を無視すればフィボナッチ数になってる
from collections import defaultdict

def Fib(n, dd, broken):
    if n in broken:
        return 0

    if dd[n] != 0:
        return dd[n]

    if n <= 1:
        return 1

    x = Fib(n-1, dd, broken) + Fib(n-2, dd, broken)
    dd[n] = x
    return x

dd = defaultdict(int)

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

ans = Fib(n, dd, A)
print(ans % 1000000007)

Submission status: Time Limit Exceeded

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

d = [0] * (n+5)
d[1] = (1 if len(a) == 0 or a[0] != 1 else 0)
d[2] = (d[1] + 1 if len(a) == 0 or 2 not in a else 0)

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

Submission status: Time Limit Exceeded

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

mod = 1000000007

dp = [0 for _ in range(N + 1)]
dp[0] = 1
if 1 not in A:
    dp[1] = 1

for n in range(2, N + 1):
    if n in A:
        dp[n] = 0
    else:
        dp[n] = dp[n - 1] + dp[n - 2]
        if dp[n] >= mod:
            dp[n] -= mod
            
print(dp[N])

Submission status: Time Limit Exceeded

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

mod = 1000000007

dp = [0 for _ in range(N + 1)]
dp[0] = 1
if 1 not in A:
    dp[1] = 1

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

print(dp[N])

Submission status: Time Limit Exceeded

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

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

print (dp[n] % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline

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

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

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

Submission status: Time Limit Exceeded

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

for i in range(m):
  obs.append(int(input()))
  
#i段目にいる確率
for i in range(n+1):
  if i==0:
    idou.append(1)
  elif i==1 and not(i in obs):
    idou.append(1)
  elif i in obs:
    idou.append(0)
  else:
    tasu = idou[-1] + idou[-2]
    tasu = tasu%1000000007
    idou.append(tasu)
    
print(idou[-1])

Submission status: Time Limit Exceeded

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

bads = []
for i in range(m):
    bads.append(int(input()))

dp = [1, 1]
for i in range(2, n+1):
    dp.append(0)
    if i-1 not in bads:
        dp[i] += dp[i-1]
    if i-2 not in bads:
        dp[i] += dp[i-2]
    dp[i] %= 1000000007

print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
mod=10**9+7
dp=[0 for i in range(N+1)]
dp[0]=1
dp[-1]=0
A=[]
for i in range(M):
  A.append(int(input()))
#print(A)
for i in range(1,N+1):
  if dp[i-1]==0 and dp[i-2]==0:
    break
  elif i in A:
    continue
  else:
    dp[i]=(dp[i-1]+dp[i-2])%mod
print(dp[N]%mod)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
mod=10**9+7
A=[]
for i in range(M):
  A.append(int(input()))
#print(A)
next=0
dp=[0 for i in range(N+1)]
dp[0]=1
dp[-1]=0
for i in range(1,N+1):
  if i in A:
    if next==1:
      break
    else:
      dp[i]=1
      next=1
  elif next==1:
    dp[i]=dp[i-2]
    next=2
  elif next==2:
    dp[i]=dp[i-1]
    next=0
  else:
    dp[i]=(dp[i-1]+dp[i-2])%mod
print(dp[N]%mod)

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
mod=10**9+7
n1=-1
n2=-1
stop=0
A=[]
for i in range(M):
  n1=n2
  n2=int(input())
  if n2-n1==1:
    stop=1
  A.append(n2)
#print(A,stop,sep="おい")
if stop==1:
  print("0")
else:
  next=0
  dp=[0 for i in range(N+1)]
  dp[0]=1
  dp[-1]=0
  for i in range(1,N+1):
    if i in A:
      dp[i]=1
      next=1
    elif next==1:
      dp[i]=dp[i-2]
      next=2
    elif next==2:
      dp[i]=dp[i-1]
      next=0
    else:
      dp[i]=(dp[i-1]+dp[i-2])%mod
  print(dp[N]%mod)

Submission status: Time Limit Exceeded

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

dp = [0] * (N+1)
dp[0] = 1
if 1 in A:
  dp[1] = 0
else:
  dp[1] = 1
div = 1000000007

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

print(dp[N]%div)

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)]
mod = (10**9)+7
dp = [1] + [0]*(n)
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[-1])

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int, input().split())
a = [int(input()) for i in range(m)]
mod = (10**9)+7
dp = [1] + [0]*(n)
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[-1])

Submission status: Time Limit Exceeded

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