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:
#create date: 2020-07-25 09:13

import sys
stdin = sys.stdin
mod = 10**9+7

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def main():
    n, m = na()
    a = list()
    for i in range(m):
        a.append(ni())

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

N, M = map(int, input().split())
A = set()
MOD = 10**9 + 7

for i in range(M):
    a = int(input())
    A.add(a)

seen = {}


def count(N, pos):
    # 一番上までたどり着いた時
    if N == 0:
        return 1

    # 再起
    res = 0
    if pos + 1 not in A:
        try:
            res += seen[N-1]
        except:
            way = count(N-1, pos+1) % MOD
            seen[N-1] = way
            res += way
        res %= MOD

    if pos + 2 not in A and N-2 >= 0:
        try:
            res += seen[N-2]
        except:
            way = count(N-2, pos+2) % MOD
            seen[N-2] = way
            res += way
        res %= MOD
    return res % MOD


print(count(N, 0))

Submission status: Time Limit Exceeded

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

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

N, M = map(int, input().split())
A = set()
MOD = 10**9 + 7

for i in range(M):
    a = int(input())
    A.add(a)

seen = {}


def count(N, pos):
    # 一番上までたどり着いた時
    if N == 0:
        return 1

    # 再起
    res = 0
    if pos + 1 not in A:
        try:
            res += seen[N-1]
        except:
            way = count(N-1, pos+1) % MOD
            seen[N-1] = way
            res += way
        res %= MOD

    if pos + 2 not in A and N-2 >= 0:
        try:
            res += seen[N-2]
        except:
            way = count(N-2, pos+2) % MOD
            seen[N-2] = way
            res += way
        res %= MOD
    return res % MOD


print(count(N, 0))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**5+10)
N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
MOD = 1000000007
memo = {}
def Fib(n, A, MOD):
    if n in A:
        return 0
    elif n == 0:
        return 1
    elif n == 1:
        return 1
    elif n in memo:
        return memo[n]
    else:
        memo[n] = ( Fib(n-1, A, MOD) + Fib(n-2, A, MOD) ) % MOD
        return memo[n]
print(Fib(N, A, MOD))

Submission status: Time Limit Exceeded

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

nums = [0]*(n+1)
nums[0] = 1
if 1 not in a: nums[1] = 1

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

Submission status: Time Limit Exceeded

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

nums = [0]*(n+1)
nums[0] = 1
if 1 not in a: nums[1] = 1

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

Submission status: Time Limit Exceeded

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

nums = [0]*(n+1)
nums[0] = 1
if 1 not in a: nums[1] = 1

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
 # -*- coding: utf-8 -*-
n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]

INF = 10 ** 9 + 7

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

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])%(10**9+7)
print(dp[-1])

Submission status: Time Limit Exceeded

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

dp=[0]*(n+1)
dp[0]=1
if 1 not in a:
  dp[1]=1

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

Submission status: Time Limit Exceeded

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

dp=[0]*(n+1)
dp[0]=1
if 1 not in a:
  dp[1]=1

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

Submission status: Time Limit Exceeded

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

dp=[0]*(n+1)
dp[0]=1
if 1 not in a:
  dp[1]=1

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

Submission status: Time Limit Exceeded

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

dp=[0]*(n+1)
dp[0]=1
if 1 not in a:
  dp[1]=1

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

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
a=[]
for i in range(m):
    A=int(input())
    a.append(A)
b=[1]
ans=1
for i in range(1,n+1):
    if i in a:
        b.append(0)
        ans*=b[i-1]
        ans=ans%1000000007
        if len(b)!=1:
            if b[i-1]==0:
                ans=0
                break
    else:
        if i==1 or b[i-1]==0:
            b.append(1)
        else:
            b.append(b[i-1]+b[i-2])
ans*=b[len(b)-1]
print(ans%1000000007)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
a=[]
for i in range(m):
    A=int(input())
    a.append(A)
b=[1]
ans=1
t=1
for i in range(1,n+1):
    if i in a:
        b.append(0)
        ans*=t
        ans=ans%1000000007
        t=1
        if len(b)!=1:
            if b[i-1]==0:
                ans=0
                break
    else:
        if i==1:
            b.append(1)
        elif b[i-1]==0:
            b.append(1)
        else:
            b.append(b[i-1]+b[i-2])
        t=b[i]
ans*=b[len(b)-1]
print(ans%1000000007)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
a=[]
for i in range(m):
    A=int(input())
    a.append(A)
b=[1]
ans=1
t=1
for i in range(1,n+1):
    if i in a:
        b.append(0)
        ans*=t
        t=1
        if len(b)!=1:
            if b[i-1]==0:
                ans=0
                break
    else:
        if i==1:
            b.append(1)
        elif b[i-1]==0:
            b.append(1)
        else:
            b.append(b[i-1]+b[i-2])
        t=b[i]
    ans=ans%1000000007
ans*=b[len(b)-1]
print(ans%1000000007)

Submission status: Time Limit Exceeded

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

dp = [0] * (N+1)
dp[0] = 1
dp[1] = 1 if 1 not in a else 0

for i in range(2, N+1):
    if i in a:
        continue
    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())
a = [int(input()) for _ in range(M)]
MOD = 10**9 + 7

dp = [0] * (N+1)
dp[0] = 1
dp[1] = 1 if 1 not in a else 0

for i in range(2, N+1):
    if i in a:
        continue
    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 = [int(input()) for _ in range(M)]
MOD = 10**9 + 7

dp = [0] * (N+1)
dp[0] = 1
dp[1] = 1 if 1 not in a else 0

a = [i for i in range(2, N+1) if i not in a]
for i in a:
    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 = [int(input()) for _ in range(M)]
MOD = 10**9 + 7

dp = [0] * (N+1)
dp[0] = 1
dp[1] = 1 if 1 not in a else 0

for i in range(2, N+1):
    if i in a:
        continue
    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 _ in range(m):
  a.append(int(input()))
if m==0:
  a=[-1]
dp=[0]*(n+1)
dp[0]=1
if 1 not in a:
  dp[1]=1
for i in range(2,n+1):
  if i-2 not in a and i-1 not in a:
     dp[i]=dp[i-2]+dp[i-1]
  elif i-2 not in a and i-1 in a:
    dp[i]=dp[i-2]
  elif i-2 in a and i-1 not in a:
    dp[i]=dp[i-1]
  else:
    dp[i]=0
print(dp[n]%(10**9+7))

Submission status: Time Limit Exceeded

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

mod = 10 ** 9 + 7

dp = [0] * (n + 1)
dp[0] = 1
if 1 not in broken:
    dp[1] = 1

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

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    import sys
    
    read = sys.stdin.read
    readline = sys.stdin.readline

    N, M = map(int, readline().split())
    a = [int(x) for x in read().split()]
    
    dp = [0] * (N + 2)
    dp[0] = 1
    
    for i in range(N):
        one = i + 1
        two = i + 2
        now = dp[i]
        if one not in a:
            dp[one] += now
        if two not in a:
            dp[two] += now
    print(dp[N] % 1_000_000_007)


resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
 
N,M = list(map(int,input().split()))
A = [int(input()) for _ in range(M)]
 
a2 = 1
a1 = 0 if 1 in A else 1 
for i in range(2,N+1):
    a = 0 if i in A else a2+a1
    a2 = a1
    a1 = a
    if a1 == 0 and a2 == 0:
        break
print(1 if N == 1 else a%1000000007)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
 
N,M = list(map(int,input().split()))
A = [int(input()) for _ in range(M)]
 
a2 = 1
a1 = 0 if 1 in A else 1
alis = [a2,a1]
for i in range(2,N+1):
    a = 0 if i in A else alis[-2]+alis[-1]
    alis.append(a)
print(1 if N == 1 else alis[-1]%1000000007)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
 
N,M = list(map(int,input().split()))
A = [int(input()) for _ in range(M)]
 
a2 = 1
a1 = 0 if 1 in A else 1 
for i in range(2,N+1):
    a = 0 if i in A else a2+a1
    a2 = a1
    a1 = a
print(1 if N == 1 else a%1000000007)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
 
N,M = list(map(int,input().split()))
A = [int(input()) for _ in range(M)]
 
a2 = 1
a1 = 0 if 1 in A else 1 
for i in range(2,N+1):
    a = 0 if i in A else (a2+a1)%1000000007
    a2 = a1
    a1 = a
print(1 if N == 1 else a%1000000007)

Submission status: Time Limit Exceeded

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

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

a2 = 1
a1 = 0 if 1 in A else 1 
for i in range(2,N+1):
    if i in A:
        a = 0
        a2 = a1
        a1 = a
    else:
        a = (a2+a1)%1000000007
        a2 = a1
        a1 = a
print(1 if N == 1 else a%1000000007)

Submission status: Time Limit Exceeded

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

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

a2 = 1
a1 = 0 if 1 in A else 1 
for i in range(2,N+1):
    if i in A:
        a = 0
        a2 = a1
        a1 = a
    else:
        a = a2+a1
        a2 = a1
        a1 = a
print(1 if N == 1 else a%1000000007)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
def gcd(*numbers): reduce(math.gcd, numbers)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
count = 0
ans = 0
inf = float("inf")

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

N,M = I()
a = []
for i in range(M):
    x = k()
    a.append(x)

dp = [0]*(N+1)
if 1 in a:
    dp[1] = 0
    dp[0] = 1
else:
    dp[0] = dp[1] =1

print(dpp(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 not in a:
    dp[1] = 1
    
for i in range(2,n+1):
    if i not in a:
        dp[i] = dp[i-1] + dp[i-2]
        dp[i] %= 1000000007
        
print(dp[n])

Submission status: Time Limit Exceeded

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

dp=[0]*(n+1)
dp[0]=1
if m>0:
    if a[0]==1:
        dp[1]=0
    else:
        dp[1]=1
else:
    dp[1]=1

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

print(dp[-1])

Submission status: Time Limit Exceeded

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

sys.setrecursionlimit(1000000)

n, m, *a = map(int, open(0).read().split())
dp = [0] * (n + 1)
ok = [True] * (n + 1)

for i in a:
    ok[i] = False


def count(n):
    if ok[n]:
        if n < 2:
            return 1
        if dp[n] != 0:
            return dp[n]
        dp[n] = (count(n - 1) + count(n - 2)) % (10**9 + 7)
        return dp[n]
    else:
        return 0


print(count(n))

Submission status: Time Limit Exceeded

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

sys.setrecursionlimit(1000000)

n, m, *a = map(int, open(0).read().split())
dp = [0] * (n + 1)
ok = [True] * (n + 1)

for i in a:
    ok[i] = False


def count(n):
    if n < 2:
        return 1
    if dp[n] != 0:
        return dp[n]
    dp[n] = (count(n - 1) * ok[n - 1] + count(n - 2) * ok[n - 2]) % (10**9 + 7)
    return dp[n]


print(count(n))

Submission status: Time Limit Exceeded

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

sys.setrecursionlimit(1000000)

n, m, *a = map(int, open(0).read().split())
memo = [0] * (n+ 1)


def count(n):
    if n < 2:
        return 1
    if memo[n] != 0:
        return memo[n]
    memo[n] = (count(n - 1)*(n-1 not in a) + count(n - 2)*(n-2 not in a) )%(10**9+7)
    return memo[n]

print(count(n))

Submission status: Time Limit Exceeded

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

sys.setrecursionlimit(1000000)


def count(n):
    if n < 2:
        return 1
    return count(n - 1) + count(n - 2)


n, m, *a = map(int, open(0).read().split())
if sum(a[i + 1] == a[i] + 1 for i in range(m - 1)) > 0:
    print(0)
    exit()

a.append(n + 1)
c = -1
ans = 1
for i in a:
    ans = ans * count(i - c - 2) % (10**9 + 7)
    c = i
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from functools import reduce
from operator import mul


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 stair(r):
    con = 0
    for i in range(r // 2 + 1):
        con += cmb(r - i, i)
    return con


n, m, *a = map(int, open(0).read().split())
if sum(a[i + 1] == a[i] + 1 for i in range(m - 1)) > 0:
    print(0)
    exit()

a.append(n + 1)
c = -1
ans = 1
for i in a:
    ans = ans * stair(i - c - 2) % (10**9 + 7)
    c = i
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from scipy.special import comb


def stair(r):
    con = 0
    for i in range(r // 2 + 1):
        con += comb(r - i, i, exact=True)
    return con


n, m, *a = map(int, open(0).read().split())
if sum(a[i + 1] == a[i] + 1 for i in range(m - 1)) > 0:
    print(0)
    exit()

a.append(n+1)
c = -1
ans = 1
for i in a:
    ans = ans * stair(i - c - 2) % (10**9 + 7)
    c = i
print(ans)

Submission status: Time Limit Exceeded

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

dp = [0] * (n+1)
if 1 not in a:
  dp[1] = 1
if 2 not in a and n != 1:
  dp[2] = dp[1] + 1
for i in range(3, n+1):
  if i not in a:
    dp[i] = dp[i-1] + dp[i-2]

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

Submission status: Time Limit Exceeded

Solution code:
import math
N,M = list(map(int,input().split()))
a = [-1]
for i in range(M):
    a.append(int(input()))
a.append(N+1)
b = []
c = []
fac_N =[1]
ans = 1
for i in range(M+1):
    b.append(a[i+1]-a[i]-2)
for i in range(1,max(b)+1):
    fac_N.append(fac_N[-1]*i)
 
 
for i in range(len(b)):
    counter= 0
    for num2 in range(b[i]//2+1):
        bi = b[i]-2*num2
        counter += fac_N[num2+bi]//fac_N[num2]//fac_N[bi]
    ans*=counter%1000000007
print(ans%1000000007)

Submission status: Time Limit Exceeded

Solution code:
import math
N,M = list(map(int,input().split()))
a = [-1]
for i in range(M):
    a.append(int(input()))
a.append(N+1)
b = []
c = []
fac_N =[1]
for i in range(M+1):
    b.append(a[i+1]-a[i]-2)
for i in range(1,max(b)+1):
    fac_N.append(fac_N[-1]*i)
 
 
for i in range(len(b)):
    counter= 0
    for num2 in range(b[i]//2+1):
        bi = b[i]-2*num2
        counter += fac_N[num2+bi]//fac_N[num2]//fac_N[bi]%1000000007
    c.append(counter)
ans = 1
for i in range(len(c)):
    ans *= c[i]%1000000007
print(ans%1000000007)

Submission status: Time Limit Exceeded

Solution code:
import math
N,M = list(map(int,input().split()))
a = [-1]
for i in range(M):
    a.append(int(input()))
a.append(N+1)
b = []
c = []
fac_N =[1]
#for i in range(M+1):
#    b.append(a[i+1]-a[i]-2)
for i in range(1,(N+1)):
    fac_N.append(fac_N[-1]*i)


for i in range(M+1):
    counter= 0
    for num2 in range((a[i+1]-a[i]-2)//2+1):
        counter += fac_N[num2+((a[i+1]-a[i]-2)-2*num2)]//fac_N[num2]//fac_N[(a[i+1]-a[i]-2)-2*num2]%1000000007
    c.append(counter)
ans = 1
for i in range(len(c)):
    ans *= c[i]%1000000007
print(ans%1000000007)

Submission status: Time Limit Exceeded

Solution code:
import math
N,M = list(map(int,input().split()))
a = [-1]
for i in range(M):
    a.append(int(input()))
a.append(N+1)
b = []
c = []
fac_N =[1]
for i in range(M+1):
    b.append(a[i+1]-a[i]-2)
for i in range(1,max(b)+1):
    fac_N.append(fac_N[-1]*i)


for i in range(len(b)):
    counter= 0
    for num2 in range(b[i]//2+1):
        counter += fac_N[num2+(b[i]-2*num2)]//fac_N[num2]//fac_N[b[i]-2*num2]%1000000007
    c.append(counter)
ans = 1
for i in range(len(c)):
    ans *= c[i]%1000000007
print(ans%1000000007)

Submission status: Time Limit Exceeded

Solution code:
import math
N,M = list(map(int,input().split()))
a = [-1]
for i in range(M):
    a.append(int(input()))
a.append(N+1)
b = []
c = []
fac_N =[1]
for i in range(M+1):
    b.append(a[i+1]-a[i]-2)
for i in range(1,max(b)+1):
    fac_N.append(fac_N[-1]*i)


for i in range(len(b)):
    counter= 0
    for num2 in range(b[i]//2+1):
        counter += fac_N[num2+(b[i]-2*num2)]//fac_N[num2]//fac_N[b[i]-2*num2]
    c.append(counter)
ans = 1
for i in range(len(c)):
    ans *= c[i]
print(ans%1000000007)

Submission status: Time Limit Exceeded

Solution code:
import math
N,M = list(map(int,input().split()))
a = [-1]
for i in range(M):
    a.append(int(input()))
a.append(N+1)
b = []
c = []
for i in range(M+1):
    b.append(a[i+1]-a[i]-2)
    for i in range(len(b)):
        counter= 0
        for num2 in range(b[i]//2+1):
            counter += math.factorial(num2+(b[i]-2*num2))//math.factorial(num2)//math.factorial(b[i]-2*num2)
    c.append(counter%1000000007)
ans = 1
for i in range(len(c)):
    ans *= c[i]
print(ans%1000000007)

Submission status: Time Limit Exceeded

Solution code:
import math
N,M = list(map(int,input().split()))
a = [-1]
for i in range(M):
    a.append(int(input()))
a.append(N+1)
b = []
c = []
for i in range(M+1):
    b.append(a[i+1]-a[i]-2)
    for i in range(len(b)):
        counter= 0
        for num2 in range(b[i]//2+1):
            counter += math.factorial(num2+(b[i]-2*num2))//math.factorial(num2)//math.factorial(b[i]-2*num2)
    c.append(counter)
ans = 1
for i in range(len(c)):
    ans *= c[i]
print(ans%1000000007)

Submission status: Time Limit Exceeded

Solution code:
import math
 
def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
 
def count_combinations(min_val, max_val):
    path_len = max_val - min_val - 2
    if path_len < 2:
        return 1
    twos = path_len // 2
    min_amount = twos + (path_len % 2)
    count = 0
    for i in range(min_amount, path_len + 1):
        count += comb(i, twos)
        twos -= 1
    return count
 
def conut_paths(a):
    paths = 1
    for i in range(len(a) - 1):
        paths *= count_combinations(a[i], a[i + 1])
    return paths % 1000000007
 
N, M = map(int, input().split())
A = [int(input()) for i in range(M)]
A.sort()
 
for i in range(1, M):
    if A[i - 1] + 1 == A[i]:
        print(0)
        exit()
 
A.insert(0, -1)
A.append(N + 1)
print(conut_paths(A))

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

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

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
cnt=[]
l=[int(input()) for _ in range(m)]
for i in range(n+1):
    cnt.append(0)
cnt[0]=1
l.sort()
for i in range(1,n+1):
    fl=False
    j=0
    while(j<m):
        t=l[j]
        if t==i:
            fl=True
            break
        if t>i:
            break
        j+=1
    if fl:
        cnt[i]=0
        continue
    else:
        cnt[i]+=cnt[i-1]
        if i>1:
            cnt[i]+=cnt[i-2]
#print(cnt)
print(cnt[n]%1000000007)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
dp = [0 for _ in range(N+1)]
MOD = int(1e9) + 7
dp[0] = 1
# DP
if 1 not in a:
    dp[1] = 1
for i in range(2, N+1):
    if i in a:
        continue
    dp[i] = (dp[i-2] + dp[i-1]) % MOD
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
dp = [0 for _ in range(N+1)]
MOD = int(1e9) + 7
dp[0] = 1
# DP
if 1 not in a:
    dp[1] = 1
for i in range(2, N+1):
    if i not in a:
        dp[i] = (dp[i-1] + dp[i-2]) % MOD
    else:
        dp[i] = 0
print(dp[-1])

Submission status: Time Limit Exceeded

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

nums = [0]*(n+1)
nums[0]  =1
if 1 not in a: nums[1] = 1

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

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
breaks = []
for _ in range(m):
  breaks.append(int(input())-1)
stairs = [0 for _ in range(n)]

if n == 1:
  print(1)
else:
  if 0 not in breaks:
    stairs[0]=1

  if 1 not in breaks:
    stairs[1]=1  

  for i in range(n):
    if i+1 not in breaks:
      if i+1>=n:
        pass
      else:
        stairs[i+1]=stairs[i]+stairs[i+1]
    if i+2 not in breaks:
      if i+2>=n:
        pass
      else:
        stairs[i+2]=stairs[i]+stairs[i+2]
    if i>3:
      if sum(stairs[i-3:]) == 0:
        break

  print(stairs[-1]%1000000007)

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
for i in range(n):
    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[-1] % 1000000007)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
a = [0]*m
#for i in range(m):
 # a[i] = int(input())
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 j in range(2,n+1):
  if j in a:
    dp[j] = 0
  else:
    dp[j] = (dp[j-1]+dp[j-2])%1000000007
print(dp[n])

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

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

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

if m==0:
    cnt = 0
    steps = n
    for j in range(steps//2+1):
        if j == 0:
            cnt += 1
        else:
            seat = steps - j
            cnt += combinations_count(seat,j)
    print(cnt % (10**9+7))
    exit()

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

ans = 1
for i in range(m+1):
    cnt = 0
    steps = l[i+1] - l[i] -2
    for j in range(steps//2+1):
        if j == 0:
            cnt += 1
        else:
            seat = steps - j
            cnt += combinations_count(seat,j)
    ans *= cnt

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

Submission status: Time Limit Exceeded

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

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

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

if m==0:
    cnt = 0
    steps = n
    for j in range(steps//2+1):
        if j == 0:
            cnt += 1
        else:
            seat = steps - j
            cnt += combinations_count(seat,j)
    print(cnt % (10**9+7))
    exit()

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

ans = 1
for i in range(m+1):
    cnt = 0
    steps = l[i+1] - l[i] -2
    if steps == 0:
        continue
    for j in range(steps//2+1):
        if j == 0:
            cnt += 1
        else:
            seat = steps - j
            cnt += combinations_count(seat,j)
    ans *= cnt

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