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:
def main():
    N, M = list(map(int, input().split(' ')))
    hole_indice = [int(input()) - 1 for i in range(M)]
    holes = [True if i in hole_indice else False for i in range(N)]

    if holes[0] and holes[1]:
        print(0)
        return

    dp = [1]
    if not holes[0]:
        dp.append(2)
    else:
        dp.append(1)

    for i in range(2, N):
        if holes[i]:
            if holes[i-1]:
                print(0)
                return
            else:
                dp.append(dp[i-1])

        else:
            if not holes[i-1] and not holes[i-2]:
                dp.append((dp[i-1] + dp[i-2]) % 1000000007)
            else:
                dp.append(dp[i-1])

    print(dp[N-1])

main()

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
lista = []
for m in range(M):
    am = int(input())
    lista. append(am)
an = 0
an1 = 1 
for n in range(N):
    if n+1 in lista:
        an, an1 = an1, 0
    else:
        an, an1 = an1, (an+an1)%1000000007
print(an1)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
lista = []
for m in range(M):
    am = int(input())
    lista. append(am)
listans = [0]*N 
an = 0
an1 = 1 
for n in range(N):
    if n+1 in lista:
        an, an1 = an1, 0
    else:
        an, an1 = an1, an+an1
print(an1%1000000007)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
lista = []
for m in range(M):
    am = int(input())
    lista. append(am)
listans = [0]*N 
for n in range(N):
    if n+1 in lista:
        pass
    elif n == 0:
        listans[0] = 1
    elif n == 1:
        listans[1] = listans[0]+1
    else:
        listans[n] = (listans[n-1]+listans[n-2])%1000000007    
#print(listans)       
ans = listans[N-1] 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
lista = []
for m in range(M):
    am = int(input())
    lista. append(am)
listans = [0]*N 
for n in range(N):
    if n+1 in lista:
        pass
    elif n == 0:
        listans[0] = 1
    elif n == 1:
        listans[1] = listans[0]+1
    else:
        listans[n] = listans[n-1]+listans[n-2]    
#print(listans)       
ans = listans[N-1]%1000000007 
print(ans)

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
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 not in a:
        dp[i] = (dp[i-1] + dp[i-2]) % MOD
print(dp[n])

Submission status: Time Limit Exceeded

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

MOD = 10**9+7
n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
dp = [0] * (n+1)
dp[0] = 1
if 1 in a:
    dp[1] = 0

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

print(dp[n] % MOD)

Submission status: Time Limit Exceeded

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

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 not in a:
        if i == 1:
            dp[1] = 1
        else:
            dp[i] = (dp[i-1] + dp[i-2])

print(dp[n] % MOD)

Submission status: Time Limit Exceeded

Solution code:
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:
        dp[i] = 0
    else:
        if i == 1:
            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())
array = []
c = 0
for i in range(M):
    a = int(input())
    if a-1 not in array:
        array.append(a)
    else:
        c = 1
        break
if c == 1:
    print(0)
else:
    dp = [0 for i in range(N+1)]
    dp[0] = 1
    for i in range(N-1):
        if i+1 not in array:
            dp[i+1] += dp[i]%(10**9+7)
        if i+2 not in array:
            dp[i+2] += dp[i]%(10**9+7)
    if N-1 not in array:
        dp[N] += dp[N-1]%(10**9+7)
    print(dp[-1]%(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]+[0]*(n+1)
for i in range(n):
    if i in A:
        continue
    dp[i+1] += dp[i]
    dp[i+2] += dp[i]
print(dp[n]%(10**9 + 7))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
 
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
         
MOD = 10**9+7
n = [1, 1]
cnt = 2
while cnt!=N+1:
    if cnt-1 in a:n[1]=0
    n[0], n[1] = n[1], (n[0]+n[1])%MOD 
    cnt += 1
    if n[1]==0:break
 
print(n[-1]%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
a = [int(input()) for m in range(M)]
ans = []
P = 10**9+7
for n in range(N):
    if n+1 in a:
        ans.append(0)
    else:
        if n == 0:
            ans.append(1)
        elif n == 1:
            ans.append(ans[0]+1)
        else:
            ans.append((ans[n-1]+ans[n-2])%P)
print(ans[N-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N,M = map(int,input().split())
a = [int(input()) for m in range(M)]
ans = []
P = 10**9+7
for n in range(N):
    if n+1 in a:
        ans.append(0)
    else:
        if n == 0:
            ans.append(1)
        elif n == 1:
            ans.append(ans[0]+1)
        else:
            ans.append((ans[n-1]+ans[n-2])%P)
print(ans[N-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N,M = map(int,input().split())
a = deque([int(input()) for m in range(M)])
ans = []
P = 10**9+7
for n in range(N):
    if n+1 in a:
        ans.append(0)
        a.popleft()
    else:
        if n == 0:
            ans.append(1)
        elif n == 1:
            ans.append(ans[0]+1)
        else:
            ans.append((ans[n-1]+ans[n-2])%P)
print(ans[N-1])

Submission status: Time Limit Exceeded

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

#TLEの対策.配列ではなく変数を使う.
p,q=0,1

for i in range(1,n+1):
    #最新のp,q以前の値は捨てて良い.つまり配列を使用する必要なし.
    p,q=q,(p+q)%(10**9+7)*(not i in a) #n*Trueは1, n*Falseは0を表す.
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 for i in range(n+1)]
dp[0] = 1

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

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

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:
        pass
    else:
        dp[i] = dp[i-1] + dp[i-2]
    
print(dp[n]%(10**9+7))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
a=[]
for i in range(m):
    a.append(int(input()))
dp=[0]*(n+1)
dp[0]=1
dp[1]=1
if 1 in a:
    dp[1]=0
mod=10**9+7
for i in range(2,n+1):
    if i in a:
        continue
    dp[i]=dp[i-1]+dp[i-2]
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 _ in range(M)]
         
n = [1, 1]
cnt = 2
while cnt!=N+1:
    if cnt-1 in a:n[1]=0
    n[0], n[1] = n[1], n[0]+n[1] 
    cnt += 1
    if n[1]==0:break

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

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
         
n = [1, 1]
cnt = 2
while cnt!=N+1:
    if cnt-1 in a:n[1]=0
    n[0], n[1] = n[1], n[0]+n[1] 
    cnt += 1
    if n[1]==0:break

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

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
         
n = [1, 1]
cnt = 2
while cnt!=N+1:
    if cnt-2 in a:n[0]=0
    if cnt-1 in a:n[1]=0
    n[0], n[1] = n[1], n[0]+n[1] 
    cnt += 1
    if n==[0,0]:break

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

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
         
n = [1, 1]
cnt = 2
while cnt!=N+1:
    if cnt-2 in a:n[0]=0
    if cnt-1 in a:n[1]=0
    n[0], n[1] = n[1], n[0]+n[1] 
    cnt += 1

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

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
         
n = [1, 1]
  
for i in range(2, N+1):
    if i-2 in a:n[i-2]=0
    if i-1 in a:n[i-1]=0
    n.append(n[i-2]+n[i-1])

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

Submission status: Time Limit Exceeded

Solution code:
import sys

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

dp = [0 for i in range(n+1)]
dp[0] =1
#print(dp)

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


print(dp[-1]%1000000007)

Submission status: Time Limit Exceeded

Solution code:
import sys

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

dp = [0 for i in range(n+1)]
dp[0] =1
#print(dp)

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


print(dp[-1]%1000000007)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000000)
n, m = map(int, sys.stdin.readline().split())
A = [int(sys.stdin.readline()) for _ in range(m)]

cnt=0
def calc(d):
    if d >=n:
        if d ==n:
            global cnt
            cnt+=1
        return
    if d in A:
        return
    else:
        calc(d+1)
        calc(d+2)



calc(0)
print(cnt%1000000007)

Submission status: Time Limit Exceeded

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

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

for i in range(2, N+1):
    if not i in a:
        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 = sorted([int(input()) for _ in range(M)])
dp = [0]*(N+1)
dp[0] = 1
for i in range(1,N+1):
    dp[i] = (dp[i-1] + dp[i-2])%(1000000007)
    if i in A:dp[i] = 0
    
print(dp[N])

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(1,N+1):
    dp[i] = (dp[i-1] + dp[i-2])%(1000000007)
    if i in A:dp[i] = 0
    
print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N, M = [int(x) for x in input().strip().split()]
A = tuple([int(input()) for _ in range(M)])
s = [0 for _ in range(N + 1)]
s[0] = 1
if 1 not in A:
  s[1] = 1

for n in range(2, N+1):
  if n in A:
    continue
  else:
    s[n] = s[n-1] + s[n-2]
print(s[-1] % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N, M = [int(x) for x in input().strip().split()]
A = [int(input()) for _ in range(M)]
s = [0 for _ in range(N + 1)]
s[0] = 1
if 1 not in A:
  s[1] = 1

for n in range(2, N+1):
  if n in A:
    continue
  else:
    s[n] = s[n-1] + s[n-2]
print(s[-1] % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N, M = [int(x) for x in input().strip().split()]
A = [int(input()) for _ in range(M)]
s = 1
s_ = 0
for n in range(1, N+1):
  if n in A:
    s, s_ = 0, s
    continue
  s, s_ = s + s_, s
print(s % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N, M = [int(x) for x in input().strip().split()]
A = [int(input()) for _ in range(M)]
s = 1
s_ = 0
for n in range(1, N+1):
  if n in A:
    s, s_ = 0, s
    continue
  s, s_ = (s + s_) % (10 ** 9 + 7), s
print(s)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N, M = [int(x) for x in input().strip().split()]
A = [int(input()) for _ in range(M)]
s = 1
s_ = 0
for n in range(1, N+1):
  if n in A:
    s, s_ = 0, s
    continue
  s, s_ = (s + s_) % (10 ** 9 + 7), s
print(s)

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

x=1 if 1 not in a else 0
dp=[1,x]+[0]*(n-1)

for i in range(2,n+1):
    if i in a:#階段破損部位は無視する
        continue
    dp[i]=(dp[i-1]+dp[i-2])
print(dp[-1]%mod)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from operator import mul
from functools import reduce

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

def sumcmb(T):
    count=0
    m=T
    while m>=0:
        count+=cmb(T,m)
        T-=1
        m-=2
        count%=mod

    return(count)


N,M=map(int,input().split())
A=[int(input()) for i in range(M)]
mod=10**9+7
for i in range(M-1):
    if A[i]+1==A[i+1]:
        print(0)
        exit()

if 1 not in A:
    A.insert(0,-1)
if N not in A:
    A.append(N+1)


count=1
for i in range(len(A)-1):
    T=max(A[i+1]-1 - (A[i]+1),1)
    #print(sumcmb(T))
    count*=sumcmb(T)
    count%=mod

print(count)

Submission status: Time Limit Exceeded

Solution code:
from operator import mul
from functools import reduce

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

def sumcmb(T):
    count=0
    m=T
    while m>=0:
        count+=cmb(T,m)
        T-=1
        m-=2
    return(count)


N,M=map(int,input().split())
A=[int(input()) for i in range(M)]
mod=10**9+7
for i in range(M-1):
    if A[i]+1==A[i+1]:
        print(0)
        exit()

if 1 not in A:
    A.insert(0,-1)
if N not in A:
    A.append(N+1)


count=1
for i in range(len(A)-1):
    T=max(A[i+1]-1 - (A[i]+1),1)
    #print(sumcmb(T))
    count*=sumcmb(T)
    if count>mod:
        count%=mod
print(count)

Submission status: Time Limit Exceeded

Solution code:
from operator import mul
from functools import reduce

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

def sumcmb(T):
    count=0
    m=T
    while m>=0:
        count+=cmb(T,m)
        T-=1
        m-=2
    return(count)


N,M=map(int,input().split())
A=[int(input()) for i in range(M)]
mod=10**9+7
for i in range(M-1):
    if A[i]+1==A[i+1]:
        print(0)
        exit()

if 1 not in A:
    A.insert(0,-1)
if N not in A:
    A.append(N+1)


count=1
for i in range(len(A)-1):
    T=max(A[i+1]-1 - (A[i]+1),1)
    #print(sumcmb(T))
    count*=sumcmb(T)
    count%=mod
print(count)

Submission status: Time Limit Exceeded

Solution code:
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 sumcmb(T):
    count=0
    m=T
    while m>=0:
        count+=cmb(T,m)
        T-=1
        m-=2
    return(count)


N,M=map(int,input().split())
A=[int(input()) for i in range(M)]
mod=10**9+7
for i in range(M-1):
    if A[i]+1==A[i+1]:
        print(0)
        exit()

if 1 not in A:
    A.insert(0,-1)
if N not in A:
    A.append(N+1)


count=1
for i in range(len(A)-1):
    T=max(A[i+1]-1 - (A[i]+1),1)
    #print(sumcmb(T))
    count*=sumcmb(T)
    count%=mod
print(count)

Submission status: Time Limit Exceeded

Solution code:
#c
def main():
    import sys
    input = sys.stdin.readline
    n,m = map(int,input().split())
    a=[]
    for i in range(m):
        a.append(int(input()) )
    mod=10**9 + 7
    

    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

    
    c=0
    for i in range(m-1):
        if a[i]==a[i+1]-1: c+=1
    if c!=0:
        print(0)
    elif m==0:
         print( sum( cmb(n-i,i)%mod for i in range(n//2+1) )%mod )
        
        
    else:
        b=[a[0]-1] + [a[j+1]-a[j]-2 for j in range(m-1)] + [n-a[-1]-1]
        cc=[ sum( cmb(bb-i,i)%mod for i in range(bb//2+1) )%mod for bb in b ]
    
        ans=1
        for ccc in cc:
            ans = ans*ccc%mod
        print(ans)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:

def main():
    import sys
    input = sys.stdin.readline
    n,m = map(int,input().split())
    a=[]
    for i in range(m):
        a.append(int(input()) )
    mod=10**9 + 7
    
    def cmb(n, r, m,g1,g2):
        if ( r<0 or r>n ):
            return 0
        r = min(r, n-r)
        return g1[n] * g2[r] * g2[n-r] % m
    
    def nCrMOD(n,r,m):
        g1 = [1, 1]
        g2 = [1, 1]
        inverse = [0, 1]
        for i in range( 2, n + 1 ):
            g1.append( ( g1[-1] * i ) % m )
            inverse.append( ( -inverse[m % i] * (m//i) ) % m )
            g2.append( (g2[-1] * inverse[-1]) % m )
        return cmb(n,r,m,g1,g2)
    
    
    c=0
    for i in range(m-1):
        if a[i]==a[i+1]-1: c+=1
    if c!=0:
        print(0)
    elif m==0:
         print( sum( nCrMOD(n-i,i,mod) for i in range(n//2+1) )%mod )
        
        
    else:
        b=[a[0]-1] + [a[j+1]-a[j]-2 for j in range(m-1)] + [n-a[-1]-1]
        cc=[ sum( nCrMOD(bb-i,i,mod) for i in range(bb//2+1) )%mod for bb in b ]
    
        ans=1
        for ccc in cc:
            ans = ans*ccc%mod
        print(ans)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def cmb(n, r, m,g1,g2):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % m

def nCrMOD(n,r,m):
    g1 = [1, 1]
    g2 = [1, 1]
    inverse = [0, 1]
    for i in range( 2, n + 1 ):
        g1.append( ( g1[-1] * i ) % m )
        inverse.append( ( -inverse[m % i] * (m//i) ) % m )
        g2.append( (g2[-1] * inverse[-1]) % m )
    return cmb(n,r,m,g1,g2)


c=0
for i in range(m-1):
    if a[i]==a[i+1]-1: c+=1
if c!=0:
    print(0)
elif m==0:
     print( sum( nCrMOD(n-i,i,mod) for i in range(n//2+1) )%mod )
    
    
else:
    b=[a[0]-1] + [a[j+1]-a[j]-2 for j in range(m-1)] + [n-a[-1]-1]
    cc=[ sum( nCrMOD(bb-i,i,mod) for i in range(bb//2+1) )%mod for bb in b ]

    ans=1
    for ccc in cc:
        ans = ans*ccc%mod
    print(ans)

Submission status: Time Limit Exceeded

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

def cmb(n, r, m,g1,g2):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % m

def nCrMOD(n,r,m):
    g1 = [1, 1]
    g2 = [1, 1]
    inverse = [0, 1]
    for i in range( 2, n + 1 ):
        g1.append( ( g1[-1] * i ) % m )
        inverse.append( ( -inverse[m % i] * (m//i) ) % m )
        g2.append( (g2[-1] * inverse[-1]) % m )
    return cmb(n,r,m,g1,g2)


c=0
for i in range(m-1):
    if a[i]==a[i+1]-1: c+=1
if c!=0:
    print(0)
elif m==0:
     print( sum( nCrMOD(n-i,i,mod) for i in range(n//2+1) )%mod )
    
    
else:
    b=[a[0]-1] + [a[j+1]-a[j]-2 for j in range(m-1)] + [n-a[-1]-1]
    cc=[ sum( nCrMOD(bb-i,i,mod) for i in range(bb//2+1) )%mod for bb in b ]

    ans=1
    for ccc in cc:
        ans = ans*ccc%mod
    print(ans)

Submission status: Time Limit Exceeded

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

def cmb(n, r, m,g1,g2):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % m

def nCrMOD(n,r,m):
    g1 = [1, 1]
    g2 = [1, 1]
    inverse = [0, 1]
    for i in range( 2, n + 1 ):
        g1.append( ( g1[-1] * i ) % m )
        inverse.append( ( -inverse[m % i] * (m//i) ) % m )
        g2.append( (g2[-1] * inverse[-1]) % m )
    return cmb(n,r,m,g1,g2)


c=0
for i in range(m-1):
    if a[i]==a[i+1]-1: c+=1
if c!=0:
    print(0)
elif m==0:
     print( sum( nCrMOD(n-i,i,mod) for i in range(n//2+1) )%mod )
    
    
else:
    b=[a[0]-1] + [a[j+1]-a[j]-2 for j in range(m-1)] + [n-a[-1]-1]
    cc=[ sum( nCrMOD(bb-i,i,mod) for i in range(bb//2+1) )%mod for bb in b ]

    ans=1
    for ccc in cc:
        ans = ans*ccc%mod
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M = list(map(int,input().split()))
a = []
for _ 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]
        dp[i] %= 1000000007
print(dp[N])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
INF = float("inf") #const

def main():
    n,m = map(int,input().split())
    a = [int(input()) for i in range(m)]
    dp = [0]*(n+1)
    dp[0],dp[1] = 1,1

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

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


def issafe(i,a):
    if i in a:
        return False
    else:
        return True


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000*10000)

INF = float("inf") #const

def main():
    n,m = map(int,input().split())
    a = [int(input()) for i in range(m)]
    dp = [0]*(n+1)
    dp[0],dp[1] = 1,1

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

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


def issafe(i,a):
    if i in a:
        return False
    else:
        return True


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
if sys.platform =='ios':
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline

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

dp = [0 for _ in range(N+1)]
dp[0] = 1

for i in range(N+1):
	if a.count(i):
		continue
	for j in [1, 2]:
		if i - j >= 0 and not a.count(i-j):
			dp[i] += dp[i-j]
print(dp[-1]%1000000007)

Submission status: Time Limit Exceeded

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

B=[1]
if 1 in A:
  B +=[0]
else:
  B +=[1]
for i in range(2,N+1):
  if i in A:
    B +=[0]
  else:
    B +=[(B[i-1]+B[i-2])%mod]
print(B[-1]%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 +=[int(input())]

B=[1]
if 1 in A:
  B +=[0]
else:
  B +=[1]
for i in range(2,N+1):
  if i in A:
    B +=[0]
  else:
    B +=[B[i-1]%mod+B[i-2]%mod]
print(B[-1]%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 +=[int(input())]

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

Submission status: Time Limit Exceeded

Solution code:
MOD=10**9+7
N,M=map(int,input().split())
A=[0]*M

for i in range(M):
    A[i]=(int(input())+1)

S=[0]*(N+2)
S[1]=1
for i in range(2,N+2):
    if(i not in A):
        S[i]=(S[i-1]+S[i-2])%MOD
    else:
        S[i]=0
print(S[N+1])

Submission status: Time Limit Exceeded

Solution code:
import math

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

'''
factorial_list = [1] * (N+1)
for i in range(1,N+1):
    factorial_list[i] = factorial_list[i-1] * i

def combinations_count(n, r):
    return factorial_list[n] // (factorial_list[n - r] * factorial_list[r])
'''

def nCk(n, k):
    ret = 1
    mo = 10**9 + 7
    for i in range(k):
        ret = ret * (n - i) * pow(i + 1, mo - 2, mo) % mo
    return ret

def one_two_comb(N):
    two_n = N//2
    comb_list = []
    for i in range(1,two_n+1):
        comb_list.append([N-i,i])
    return comb_list

def sum_comb(comb_list):
    comb_sum = 0
    for val in comb_list:
        comb_sum += nCk(val[0],val[1])
    return comb_sum
    

diff_list = []
current_num = 0
max_diff = -1
for a in An:
    diff = a - current_num
    if diff == 0:
        print(0)
        exit(0)
    diff_list.append(diff)
    current_num = a +1
diff = N+1 - current_num
diff_list.append(diff)
#print(diff_list)


all_sum = 1
for idx,diff in enumerate(diff_list):
    if idx == 0 or len(diff_list):
        diff -= 1
    '''
    else:
        diff -= 2
    '''

    if diff == 0:
        all_sum *= 1
    else:
        internal_comb_list = one_two_comb(diff)
        comb_count = sum_comb(internal_comb_list) + 1
        if all_sum > 10**9+7:
            all_sum = all_sum%(10**9+7)
        all_sum *= comb_count
print(all_sum%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import math

N,M = map(int,input().split(' '))
An = [ int(input()) for _ in range(M)]
factorial_list = [1] * (N+1)
for i in range(1,N+1):
    factorial_list[i] = factorial_list[i-1] * i

def combinations_count(n, r):
    return factorial_list[n] // (factorial_list[n - r] * factorial_list[r])

def one_two_comb(N):
    two_n = N//2
    comb_list = []
    for i in range(1,two_n+1):
        comb_list.append([N-i,i])
    return comb_list

def sum_comb(comb_list):
    comb_sum = 0
    for val in comb_list:
        comb_sum += combinations_count(val[0],val[1])
    return comb_sum
    

diff_list = []
current_num = 0
max_diff = -1
for a in An:
    diff = a - current_num
    if diff == 0:
        print(0)
        exit(0)
    diff_list.append(diff)
    current_num = a +1
diff = N+1 - current_num
diff_list.append(diff)
#print(diff_list)


all_sum = 1
for idx,diff in enumerate(diff_list):
    if idx == 0 or len(diff_list):
        diff -= 1
    '''
    else:
        diff -= 2
    '''

    if diff == 0:
        all_sum *= 1
    else:
        internal_comb_list = one_two_comb(diff)
        comb_count = sum_comb(internal_comb_list) + 1
        if all_sum > 10**9+7:
            all_sum = all_sum%(10**9+7)
        all_sum *= comb_count
print(all_sum%(10**9+7))