Problem:


Score : 300 points

Problem Statement

There is a staircase with N steps. Takahashi is now standing at the foot of the stairs, that is, on the 0-th step.
He can climb up one or two steps at a time.

However, the treads of the a_1-th, a_2-th, a_3-th, \ldots, a_M-th steps are broken, so it is dangerous to set foot on those steps.

How many are there to climb up to the top step, that is, the N-th step, without setting foot on the broken steps?
Find the count modulo 1\ 000\ 000\ 007.

Constraints

1 \leq N \leq 10^5

0 \leq M \leq N-1

1 \leq a_1 < a_2 <  ...  < a_M \leq N-1

Input

Input is given from Standard Input in the following format:

N M
a_1
a_2
 .
 .
 .
a_M

Output

Print the number of ways to climb up the stairs under the condition, modulo 1\ 000\ 000\ 007.

Sample Input 1

6 1
3

Sample Output 1

4

There are four ways to climb up the stairs, as follows:

0 \to 1 \to 2 \to 4 \to 5 \to 6

0 \to 1 \to 2 \to 4 \to 6

0 \to 2 \to 4 \to 5 \to 6

0 \to 2 \to 4 \to 6

Sample Input 2

10 2
4
5

Sample Output 2

0

There may be no way to climb up the stairs without setting foot on the broken steps.

Sample Input 3

100 5
1
23
45
67
89

Sample Output 3

608200469

Be sure to print the count modulo 1\ 000\ 000\ 007.



Sample input:
6 1
3


Sample output:
4

Submission status: Time Limit Exceeded

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

mod = 1000000007

ans = [0] * (N + 1)

ans[0] = 1

for i in range(len(ans)):
	if i in A:
		continue
	if(i+1 < len(ans)):
		ans[i+1] += ans[i]
		ans[i+1] %= mod
	if(i+2 < len(ans)):
		ans[i+2] += ans[i]
		ans[i+2] %=mod

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
  f2 = f1
  f1 = f
print(f % mod)

Submission status: Time Limit Exceeded

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

broken_step = []
for _ in range(M):
    broken_step.append(int(input()))
    
import sys
sys.setrecursionlimit(10000000)

mod = 1000000007

memo = [-1] * (N+1)

if 0 not in broken_step:
    memo[0] = 1
elif N == 0 and N in broken_step:
    memo[0] = 0

if 1 not in broken_step:
    memo[1] = 1
elif 1 in broken_step:
    memo[1] = 0

def step_memo(N):
    
    if N in broken_step:
        memo[N] = 0
        return 0
        
    if memo[N] != -1:
        return memo[N]
    
    memo[N] =  (step_memo(N-1) + step_memo(N-2)) % mod
    return (step_memo(N-1) + step_memo(N-2)) % mod
  
print(step_memo(N))

Submission status: Time Limit Exceeded

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

mod = 1000000007

ans = [0] * (N + 1)

ans[0] = 1

for i in range(len(ans)):
	if i in A:
		continue
	if(i+1 < len(ans) and i+1 not in A):
		ans[i+1] += ans[i]
		ans[i+1] %= mod
	if(i+2 < len(ans) and i+2 not in A):
		ans[i+2] += ans[i]
		ans[i+2] %=mod

print(ans[N])

Submission status: Time Limit Exceeded

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


print("{}".format(dp[-1]))

Submission status: Time Limit Exceeded

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

mod = 1000000007

ans = [0] * (N + 1)

ans[0] = 1

for i in range(len(ans)):
	if i in A:
		continue
	ans[i] %= mod
	if(i+1 < len(ans) and i+1 not in A):
		ans[i+1] += ans[i]
	if(i+2 < len(ans) and i+2 not in A):
		ans[i+2] += ans[i]

print(ans[N])

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 i in a:
    if l[i-1] != 0:
      l.append(0)
    else:
      print(0)
      exit()
  else:
    if i != 1:
      l.append(l[i-2] + l[i-1])
    else:
      l.append(1)

print(l[-1] % 1000000007)

Submission status: Time Limit Exceeded

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

from operator import mul
from functools import reduce

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


def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def calc_routes(dan):
    tmp = 1
    for i in range(int(dan/2)):
        i += 1
        n = dan - i
        # tmp += factorial(n) / factorial(i) / factorial(n - i)
        tmp += cmb(n, i)

    return tmp

routes = 1
prev = 0
for x in a:
    if x == prev:
        routes = 0
        break
    else:
        dan = (x-1) - prev
        routes = (routes * calc_routes(dan)) % 1000000007
        prev = x+1

routes = (routes * calc_routes(N-prev)) % 1000000007
print(int(routes))

Submission status: Time Limit Exceeded

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

if 1 in danger:
    steps[1]=0
else:
    steps[1]=1

for this_step in range(2,n+1):
    if this_step in danger:
        ap=0
    else:
        steps[this_step]=steps[this_step-1]+steps[this_step-2]

print(steps[-1]%1000000007)

Submission status: Time Limit Exceeded

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

mod = 1000000007

ans = [0] * (N + 1)

ans[0] = 1

for i in range(len(ans)):
	if i in A:
		continue
	ans[i] %= mod
	if(i+1 < len(ans) and i+1 not in A):
		ans[i+1] += ans[i] % mod
	if(i+2 < len(ans) and i+2 not in A):
		ans[i+2] += ans[i] % mod

print(ans[N])

Submission status: Time Limit Exceeded

Solution code:
import math
n, m = map(int, input().split())
p = []
pre = 0

def pattern_count(a,b):
    if a == 0 or b == 0:
        return 1
    else:
        return math.factorial(a+b)//(math.factorial(a)*math.factorial(b))

def count(a):
    ret = 0
    for i in range(a//2 + 1):
        ret += pattern_count(i, a-i*2)
    if ret == 0:
        return 1
    else:
        return ret

fault = False
for _ in range(m):
    a = int(input())
    if a == pre:
        fault = True
        break
    p.append(count(a-pre-1))
    pre = a+1

if fault:
    print(0)
else:
    p.append(count(n-pre))

    ans = 1
    for a in p:
        ans *= a

    print(ans % 1000000007)

Submission status: Time Limit Exceeded

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

from operator import mul
from functools import reduce

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


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

def calc_routes(dan):
    tmp = 1
    for i in range(int(dan/2)):
        i += 1
        n = dan - i
        # tmp += factorial(n) / factorial(i) / factorial(n - i)
        tmp += cmb(n, i)

    return tmp

routes = 1
prev = 0
for x in a:
    if x == prev:
        routes = 0
        break
    else:
        dan = (x-1) - prev
        routes = (routes * calc_routes(dan)) % 1000000007
        prev = x+1

routes = (routes * calc_routes(N-prev)) % 1000000007
print(int(routes))

Submission status: Time Limit Exceeded

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

broken_step = []
for _ in range(M):
    broken_step.append(int(input()))
    
import sys
sys.setrecursionlimit(10000000)

mod = 1000000007

memo = [-1] * (N+1)

if 0 not in broken_step:
    memo[0] = 1
elif N == 0 and N in broken_step:
    memo[0] = 0

if 1 not in broken_step:
    memo[1] = 1
elif 1 in broken_step:
    memo[1] = 0

def step_memo(N):
    
    try:
        broken_step.remove(N)
        memo[N] = 0
        return 0
    except ValueError:
        pass
        
    #if N in broken_step:
    #    broken_step.remove(N)
    #    memo[N] = 0
    #    return 0
        
    if memo[N] != -1:
        return memo[N]
    
    memo[N] =  (step_memo(N-1) + step_memo(N-2)) % mod
    return (step_memo(N-1) + step_memo(N-2)) % mod
  
print(step_memo(N))

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int, input().split())
bl = [int(input())-1 for _ in range(m)]
l = [i for i in range(n) if i not in set(bl)]
mod = 1000000007
al = [0]*n
if 0 in l and 1 in l:
    al[0] = 1
    al[1] = 2
elif 0 in l:
    al[0] =1
elif 1 in l:
    al[1] = 1
else:
    print(0)
    exit()

    
li = [i for i in l if i>=2]

for i in li:
    al[i] = (al[i-1] + al[i-2])%mod
    if al[i] == 0:
        print(0)
        exit()

print(al[-1])

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 len(a) > 0:
        if i == a[0]:
            val[1] = 0
            a.pop(0)

print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

broken_step = []
for _ in range(M):
    broken_step.append(int(input()))
    
import sys
sys.setrecursionlimit(10000000)

mod = 1000000007

memo = [-1] * (N+1)

if 0 not in broken_step:
    memo[0] = 1
elif N == 0 and N in broken_step:
    memo[0] = 0

if 1 not in broken_step:
    memo[1] = 1
elif 1 in broken_step:
    memo[1] = 0

def step_memo(N):
    
    if N in broken_step:
        broken_step.remove(N)
        memo[N] = 0
        return 0
        
    if memo[N] != -1:
        return memo[N]
    
    memo[N] =  (step_memo(N-1) + step_memo(N-2)) % mod
    return (step_memo(N-1) + step_memo(N-2)) % mod
  
print(step_memo(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]
    val[0] = val[1]
    val[1] = ans
    if len(a) > 0:
        if i == a[0]:
            val[1] = 0
            a.pop(0)

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

Submission status: Time Limit Exceeded

Solution code:
n,_,*a=map(int,open(0).read().split())
c,d=1,0
for i in range(n):n=(c+d)%(10**9+7)*(not-~i in set(a));c,d=n,c
print(n)

Submission status: Time Limit Exceeded

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

if 1 in danger:
    steps=[1,0]
else:
    steps=[1,1]

for this_step in range(2,n+1):
    if this_step in danger:
        ap=0
    else:
        ap=steps[-1]+steps[-2]
    steps.append(ap)

print(steps[-1]%1000000007)

Submission status: Time Limit Exceeded

Solution code:
n,_,*a=map(int,open(0).read().split())
c,d=1,0
for i in range(n):n=(c+d)%(10**9+7)*(not-~i in a);c,d=n,c
print(n)

Submission status: Time Limit Exceeded

Solution code:
import math
n, m = [int(i) for i in input().split()]
p = [int(input()) for i in range(m)]
 
a = []
a.append(1)
if 1 in p:
    a.append(0)
else:
    a.append(1)
for i in range(2, n + 1):
    if i in p:
        a.append(0)
    else:
        a.append((a[i - 2] + a[i - 1]) % 1000000007)
    
print(a[n])

Submission status: Time Limit Exceeded

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


print("{}".format(dp[-1]%mod))

Submission status: Time Limit Exceeded

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



N,M = input().split()

N = int(N)
M = int(M)

a = []
ans = 1

for i in range(M):
    newa = int(input())
    a.append(newa)

if (M != 0):
    for k in range(M-1):
        if (a[k+1] - a[k] == 1):
            ans = 0
            
    
    
    for i in range(M + 1):
    

        if (i == 0):
            dan = a[i] - 1
        elif (i == M):
            dan = N - a[i - 1] - 1
        else:
            dan = a[i] - a[i - 1] - 2

        abletwo = (dan - (dan % 2)) // 2
        now = 0

        if (dan != 0):

            for j in range(abletwo + 1):

                now += cmb (dan - j , j )

        else:
            now = 1
        
        ans *= now

else:
    ans = 0
    abletwo = (N - (N % 2)) // 2

    for j in range(abletwo + 1):

        ans += cmb (N - j , j )

ans = ans % 1000000007
print (ans)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split(" "))
a=[]
ans = 1
for i in range(m):
    a.append(int(input()))
    if a[i]-1 == a[i-1]:
        ans = 0
if ans == 1:
    for j in range(n,-1,-1):
        if j in a:
            ans *= 1
        elif j+1 in a or j+2 in a:
            ans *= 1
        elif j+2 > n:
            ans *= 1
        elif not(j+3 in a) and not(j+3 > n):
            temp = ans
            ans += t
            t = temp
        else:
            t = ans
            ans *= 2

print(ans % 1000000007)

Submission status: Time Limit Exceeded

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

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

import sys
sys.setrecursionlimit(10000000)

mod = 1000000007

memo = [-1] * (N+1)

if 0 not in broken_step:
    memo[0] = 1
elif N == 0 and N in broken_step:
    memo[0] = 0

if 1 not in broken_step:
    memo[1] = 1
elif 1 in broken_step:
    memo[1] = 0

def step_memo(N):
    
    if N in broken_step:
        return 0
        
    if memo[N] != -1:
        return memo[N]
    
    memo[N] =  (step_memo(N-1) + step_memo(N-2)) % mod
    return (step_memo(N-1) + step_memo(N-2)) % mod
  
print(step_memo(N))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import math
n, m = [int(i) for i in input().split()]
p = [int(input()) for i in range(m)]

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

Submission status: Time Limit Exceeded

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

for i in range(n-2):
    c =b[i]
    d = b[i+1]
    e = c + d
    b.append(e)

c = []
if a[1] == 0:
    c.append(1)
else:
    c.append(b[a[1] - a[0]  - 1])
i = 1
while i <= m:
    if a[i + 1] - a[i] - 3 >= 0:
        c.append(b[a[i + 1] - a[i]  - 3])
        i += 1
    elif a[i + 1] - a[i] - 2 == 0:
        c.append(1)
    else:
        c.append(0)
        break
#print(c)
d = c[0] 
i = 1
#print(d)
while i < len(c):
    d = d * c[i]
    i += 1
e = 1000000007
print(d % e)
#print(b[0])

Submission status: Time Limit Exceeded

Solution code:
N,W = input().split()
aArr = list()
ans = 0
tmp = int(N)
for i in range(int(W)):
    inputInt = int(input())
    aArr.append(inputInt)
    if inputInt - tmp == 1:
        print(ans)
        exit()
    tmp = inputInt
tmp = 0
intArr = list()
for i in range(int(N)+1):
    if(i in aArr):
        intArr.append(0)
    elif i < 2:
        intArr.append(1)
    else:
        intArr.append(intArr[i-2] + intArr[i-1])
print(intArr[int(N)] % 1000000007)

Submission status: Time Limit Exceeded

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

mod = 10**9+7
dp = {}
for i in range(N+1):
    dp[i] = 1
dp[1] = 0 if 1 in l else 1

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

print(dp[N]%mod)

Submission status: Time Limit Exceeded

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

mod = 10**9+7
dp = {}
for i in range(N+1):
    dp[i] = 1
dp[1] = 0 if 1 in l else 1

for i in range(2,N+1):
    if i in l:
        dp[i] = 0
        continue
    else:
        dp[i] = dp[i-1] + dp[i-2]

print(dp[N]%mod)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
  
broken_step = []
for _ in range(M):
    broken_step.append(int(input()))
      
import sys
sys.setrecursionlimit(10000000)

mod = 1000000007

memo = [-1] * (N+1)

def step_memo(N):
    if N == 0 and N not in broken_step:
        memo[N] = 1
        return 1
    elif N == 0 and N in broken_step:
        memo[N] = 0
        return 0
    
    if N == 1 and N not in broken_step:
        memo[N] = 1
        return 1
    elif N == 1 and N in broken_step:
        memo[N] = 0
        return 0

    a = 1
    b = 1
    
    if N in broken_step:
        a, b = 0, 0
        
    if memo[N] != -1:
        return memo[N]
    
    memo[N] =  (a * step_memo(N-1) + b * step_memo(N-2)) % mod
    return (a * step_memo(N-1) + b * step_memo(N-2)) % mod

print(step_memo(N))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)

def intinput(): return map(int,sys.stdin.readline().split())

fib=[0,1,1]
for i in range(3,100003):
    fib.append(fib[i-1]+fib[i-2])

n,m=intinput()
mod=10**9+7
a=[int(sys.stdin.readline()) for _ in range(m)]
k=1
y=1
for i in range(n):
    if i in a:
        k*=fib[y-1]
        y=0
    y+=1
k*=fib[y]
print(k%mod)

Submission status: Time Limit Exceeded

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

if 1 in ls:
    steps=[1,0]
else:
    steps=[1,1]

for this_step in range(2,n+1):
    if this_step in ls:
        ap=0
    else:
        ap=steps[-1]+steps[-2]
    steps.append(ap)

print(steps[-1]%1000000007)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
 
a_list=[]
 
for index in range(m):
    a_list.append(int(input()))
 
ans_list=[]
 
for index in range(n + 1):
    ans_list.append(0)
 
for index in range(n + 1):
    if index == 0:
        ans_list[index] += 1
        continue
    if index == 1 and (index not in a_list):
        ans_list[index] += ans_list[index - 1]
        continue
    
    if index not in a_list:
        if (index - 1) not in a_list:
            ans_list[index] += ans_list[index - 1]
            ans_list[index] %= 1000000007
        if (index - 2) not in a_list:
            ans_list[index] += ans_list[index - 2]
            ans_list[index] %= 1000000007
 
print(ans_list[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+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:
import sys
import operator
from functools import reduce
from scipy.misc import comb


def ncr(n, r):
    return comb(n, r, exact=True)


def step2patterns(num_step, step_dict):
    try:
        return step_dict[num_step]
    except KeyError:
        ret = step2patterns(num_step-2, step_dict) + step2patterns(num_step-1, step_dict)
        step_dict[num_step] = ret
        return ret


sys.setrecursionlimit(100000)
num_stair, num_wet = map(int, input().split(' '))

last_wet = -1
num_pattern = 1
d = {0: 1, 1: 1, 2: 2}

for i in range(0, num_wet):
    wet = int(input())
    dry_step = wet - last_wet - 1
    last_wet = wet

    if dry_step <= 0:
        print('0')
        exit(0)

    elif dry_step == 1 or dry_step == 2:
        continue

    else:
        num_pattern *= step2patterns(dry_step - 1, d)

    num_pattern %= 1000000007

# last step
dry_step = num_stair - last_wet

num_pattern *= step2patterns(dry_step - 1, d)

print(num_pattern % 1000000007)
exit(0)

Submission status: Time Limit Exceeded

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

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

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

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

Submission status: Time Limit Exceeded

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

if 1 in ls:
    steps=[1,0]
else:
    steps=[1,1]

while len(steps)<=n:
    this_step=len(steps)
    if this_step in ls:
        ap=0
    else:
        ap=steps[-1]+steps[-2]
    steps.append(ap)

print(steps[-1]%1000000007)

Submission status: Time Limit Exceeded

Solution code:
import sys
import operator
from functools import reduce
from scipy.misc import comb


def ncr(n, r):
    return comb(n, r, exact=True)


def step2patterns(num_step, step_dict):
    try:
        return step_dict[num_step]
    except KeyError:
        ret = step2patterns(num_step-1, step_dict) + step2patterns(num_step-2, step_dict)
        step_dict[num_step] = ret
        return ret


sys.setrecursionlimit(100000)
num_stair, num_wet = map(int, input().split(' '))

last_wet = -1
num_pattern = 1
d = {0: 1, 1: 1, 2: 2}

for i in range(0, num_wet):
    wet = int(input())
    dry_step = wet - last_wet - 1
    last_wet = wet

    if dry_step <= 0:
        print('0')
        exit(0)

    elif dry_step == 1 or dry_step == 2:
        continue

    else:
        num_pattern *= step2patterns(dry_step - 1, d)

    num_pattern %= 1000000007

# last step
dry_step = num_stair - last_wet

num_pattern *= step2patterns(dry_step - 1, d)

print(num_pattern % 1000000007)
exit(0)

Submission status: Time Limit Exceeded

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

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


for i in range(M - 1):
    if a[i] + 1 == a[i+1]:
        print(0)
        exit()

dp = [0] * (N + 1)

if N == 1 and M != 1:
    print(1)
    exit()
elif N == 1 and M == 1:
    print(0)
    exit()

if 1 in a and 2 in a:
    print(0)
    exit()

if 1 in a:
    dp[1] = 0
    dp[2] = 1
elif 2 in a:
    dp[1] = 1
    dp[2] = 0
else:
    dp[1] = 1
    dp[2] = 2

for i in range(3,N+1):
    if i in a:
        dp[i] = 0
        a.remove(i)
    else:
        dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007

print(dp[N])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
MOD = (10**9 + 7)
broken_step = []
     
line = [int(s) for s in input().split()]
     
N, M = line[0], line[1]
     
for i in range(M):
    step_num = int(input().split()[0])
    broken_step.append(step_num)
        
        
dp = [0]*(N+1)
dp[0] = 1
if 1 in broken_step:
    dp[1] = 0
else:
    dp[1] = 1
     
for i in range(2, N+1):
    dp[i] = (dp[i-1]+dp[i-2])%MOD if i not in broken_step else 0
print(dp[N])

Submission status: Time Limit Exceeded

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

sys.setrecursionlimit(1000000)

MAX_N = 100010
memo = [-1] * MAX_N

def f(n, a_list):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    elif n == 2:
        for a in a_list:
            if N - a == 1:
                return 1
        return 2
    # すでに探索済みならメモを参照する
    elif memo[n] != -1:
        return memo[n]
    else:
        is_next_damaged = False
        is_2next_damaged = False
        for a in a_list:
            if N - a == n-1:
                is_next_damaged = True
            if N - a == n-2:
                is_2next_damaged = True
        if is_next_damaged == True and is_2next_damaged == False:
            res = f(n-2, a_list)
        if is_next_damaged == False and is_2next_damaged == True:
            res = f(n-1, a_list)
        if is_next_damaged == False and is_2next_damaged == False:
            res = f(n-1, a_list) + f(n-2, a_list)

    # メモ
    memo[n] = res
    return res

if __name__ == '__main__':
    N, M = map(int, input().split())
    a_list = [int(input()) for i in range(M)]

    divided_by = 1000000007

    answer = -1

    # まず移動方法がない場合を考える。
    min_diff = sys.maxsize
    for i in range(1, len(a_list)):
        min_diff = min(min_diff, a_list[i] - a_list[i - 1])

    if min_diff == 1:
        answer = 0
    else:
        # 何らかなの移動方法が必ず存在する場合
        answer = f(N, a_list)%divided_by

    print(answer)

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import factorial

def combination(n,r):
    nCr = factorial(n) // factorial(r) // factorial(n - r)
    return(nCr)

n, m = [int(i) for i in input().split()]
a = [-1]
for i in range(m):
    a.append(int(input()))
    if a[-1] - a[-2] == 1:
        print(0)
        sys.exit()
a.append(n+1)
# print(a)

ans = 1
for i in range(len(a)-1):
    # print('i',i,ans)
    a_begin = a[i]
    a_end = a[i+1]
    # print(a_begin,a_end)
    num_stair = a_end - a_begin - 2
    max_num_two_up = num_stair // 2
    # print(num_stair,max_num_two_up)
    comb = 1
    #print(comb)
    ans_tmp = comb
    for j in range(1, max_num_two_up+1):
        comb = comb * (num_stair - (j-1) - (j-1)) * (num_stair - (j-1) - (j-1) - 1) // j // (num_stair - (j-1))
        ans_tmp += comb % 1000000007
        #print(comb)
    ans *= ans_tmp % 1000000007

ans = ans % 1000000007
print(ans)

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

def stairs(n):
    if(n<=0):
        return 1
    comb = 0
    for i in range(int(n/2)+1):
        comb += combinations_count(n-i,i)
    return comb

def main():
    N,M = map(int,input().split(" "))
    broken_l = []
    for _ in range(M):
        broken_l.append(int(input()))

    broken_l.append(-1)
    broken_l.append(N+1)
    broken_l.sort()
    ans = 1
    for i in range(len(broken_l)-1):
        step = broken_l[i+1] - broken_l[i]
        if(step == 1 and broken_l[i+1]!=1):
            print(0)
            exit(0)
        else:
            ans *= stairs(step-2)
            ans = ans%(10**9+7)

    print(ans)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
broken_step = []
     
line = [int(s) for s in input().split()]
     
N, M = line[0], line[1]
     
for i in range(M):
    step_num = int(input().split()[0])
    broken_step.append(step_num)
        
        
dp = [0]*(N+1)
dp[0] = 1
if 1 in broken_step:
    dp[1] = 0
else:
    dp[1] = 1
     
for i in range(2, N+1):
    dp[i] = (dp[i-1]+dp[i-2])%(10**9 + 7) if i not in broken_step else 0
print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9 + 7

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

dp = {}
for i in range(n + 1):
    dp[i] = 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] % mod + dp[i - 2] % mod
        dp[i] %= mod

print(dp[n] % mod)

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(100000)

N,M = map(int,input().split(' '))
l = [int(input()) for i in range(M)]

pre = 0
last = -1
ans_l = []
flag = False
l.append(N+1)

nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]

for i in l:
    if i==1:
        last = 1
        continue
    if i-last==1:
        flag =True
        break
    n = i - last - 3
    r = 0
    tmp = 1
    dif = 1
    # print("n",n)
    while dif>0:
        r += 1
        if n<=0 or n<r:
            break
        # print(n,r)
        tmp += cmb(n, r)
        dif = n-r
        # print("tmp",tmp,n,r)
        n -= 1
    ans_l.append(tmp)
    # print(i,ans_l)
    last = i
if flag:
    print(0)
else:
    ans = 1
    for i in ans_l:
        ans*=i
    print(ans%1000000007)

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9 + 7

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

dp = [1] * (n + 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] % mod + dp[i - 2] % mod
        dp[i] %= mod

print(dp[n] % mod)

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9 + 7

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

dp = [1] * (n + 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] % mod + dp[i - 2] % mod

print(dp[n] % mod)

Submission status: Time Limit Exceeded

Solution code:
N, M  = map(int, input().split())
a  = []
for _ in range(M):
  a.append(int(input()))
sdic  = {}
nn1 = 1
nn2 = 0
for n in reversed(range(N)):
  if n in a:
    nn2 = nn1
    nn1 = 0
    continue
  t = nn1 + nn2
  if t == 0:
    print(0)
    quit()
  nn2 = nn1
  nn1 = t
  
print(nn1%1000000007)