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:
import sys
#from scipy.special import comb
#from scipy.misc import comb

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

sys.setrecursionlimit(100000)
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)]


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

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

A = [0]*M

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

A.append(N+1)

def step_comb(L):
    c = 0
    if L==1 or L == 0:
        c = 1
    else:
        for i in range(L//2 +1):
            j = L - 2*i
            #c += comb(j+i, i, exact=True)
            c += cmb(j+i, i)
    return c

total_comb = 1
NOW = 0
for a in A:
    if NOW == a:
        print(0)
        sys.exit()
    L = a-1-NOW
    total_comb *= step_comb(L)
    NOW = a + 1
    
print(total_comb % 1000000007 )

Submission status: Time Limit Exceeded

Solution code:
import sys
#from scipy.special import comb
#from scipy.misc import comb

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

sys.setrecursionlimit(100000)
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)]

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

A = [0]*M

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

A.append(N+1)

def step_comb(L):
    c = 0
    if L==1 or L == 0:
        c = 1
    else:
        for i in range(L//2 +1):
            j = L - 2*i
            #c += comb(j+i, i, exact=True)
            c += cmb(j+i, i)
    return c

total_comb = 1
NOW = 0
for a in A:
    if NOW == a:
        print(0)
        sys.exit()
    L = a-1-NOW
    total_comb *= step_comb(L)
    NOW = a + 1
    
print(total_comb % 1000000007 )

Submission status: Time Limit Exceeded

Solution code:
import sys
#from scipy.special import comb
#from scipy.misc import comb

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

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

A = [0]*M

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

A.append(N+1)

def step_comb(L):
    c = 0
    if L==1 or L == 0:
        c = 1
    else:
        for i in range(L//2 +1):
            j = L - 2*i
            #c += comb(j+i, i, exact=True)
            c += cmb(j+i, i)
    return c

total_comb = 1
NOW = 0
for a in A:
    if NOW == a:
        print(0)
        sys.exit()
    L = a-1-NOW
    total_comb *= step_comb(L)
    NOW = a + 1
    
print(total_comb % 1000000007 )

Submission status: Time Limit Exceeded

Solution code:
import sys
#from scipy.special import comb
from scipy.misc import comb

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

A = [0]*M

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

A.append(N+1)

def step_comb(L):
    c = 0
    if L==1 or L == 0:
        c = 1
    else:
        for i in range(L//2 +1):
            j = L - 2*i
            c += comb(j+i, i, exact=True)
    return c

total_comb = 1
NOW = 0
for a in A:
    if NOW == a:
        print(0)
        sys.exit()
    L = a-1-NOW
    total_comb *= step_comb(L)
    NOW = a + 1
    
print(total_comb % 1000000007 )

Submission status: Time Limit Exceeded

Solution code:
a = input().split()
a = [int(i) for i in a]

broken_stairs = []
kekka_flag = False


def fib(x, broken_stairs):
    count = [1, 2]
    if 1 in broken_stairs:
        count[0] = 0
        count[1] = 1
    if 2 in broken_stairs:
        count[1] = 0
    
    for i in range(x - 2):
        if i + 3 in broken_stairs:
            count.append(0)
        else:
            count.append((count[i] + count[i + 1]) % 1000000007)
    return count


for i in range(a[1]):
    broken_stairs.append(int(input()))

count = fib(a[0], broken_stairs)
if a[0] == 1:
    print(count[0])
else:
    print(count[-1] % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
a = input().split()
a = [int(i) for i in a]

broken_stairs = []
kekka_flag = False


def fib(x, broken_stairs):
    count = [1, 2]
    if 1 in broken_stairs:
        count[0] = 0
        count[1] = 1
    if 2 in broken_stairs:
        count[1] = 0
    
    for i in range(x - 2):
        if count[-1] > 1000000007:
            count = [i % 1000000007 for i in count]
        if i + 3 in broken_stairs:
            count.append(0)
        else:
            count.append(count[i] + count[i + 1])
    return count


for i in range(a[1]):
    broken_stairs.append(int(input()))

count = fib(a[0], broken_stairs)
if a[0] == 1:
    print(count[0])
else:
    print(count[-1] % 1000000007)

Submission status: Time Limit Exceeded

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

dp[0]=1
mod=10**9+7
for now in range(n):
    for next in range(now+1,min(n+1,now+3)):
        if ok[next]:
            dp[next]+=dp[now]
            dp[next]%mod

print(dp[n]%mod)

Submission status: Time Limit Exceeded

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

# In[2]:


N, M = map(int, input().split())
As = [int(input()) for i in range(M)]
"""
100 5
1
23
45
67
89
"""


# In[6]:


stairs = [0]*(N+1)
stairs[0] = 1
for i in range(N):
    #if i == N-1:
    #    break
    if i <= N-1:
        if i+1 not in As:
            stairs[i+1] += stairs[i]
    if i <= N-2:
        if i+2 not in As:
            stairs[i+2] += stairs[i]
    
print(stairs[N]%1000000007)


# In[ ]:

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
a=[int(input()) for _ in range(m)]
dp=[-1 for _ in range(n+1)]
dp[0]=dp[1]=1
def step(s):
    if s in a:
        dp[s]=0
        return
    elif dp[s]>=0:
        return 
    else:
        dp[s]=dp[s-1]+dp[s-2] 
        return
for i in range(n+1):
    step(i)
print(dp[-1]%1000000007)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
s=[int(input()) for i in range(m)]
l=[1]+[0]*(n)
INF=1000000007
if n ==1:
    print(1)
    exit()
if len(s)!=0 and s[0]== 1:l[1]=0
else:l[1]=1

for i in range(2,n+1):
    if i in s:num=0
    else:l[i] = (l[i-2]+l[i-1])%INF
print(l[-1])

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
s=[int(input()) for i in range(m)]
l=[1]
INF=1000000007
if n ==1:
    print(1)
    exit()
if len(s)!=0 and s[0]== 1:l.append(0)
else:l.append(1)

for i in range(2,n+1):
    if i in s:num=0
    else:num = (l[i-2]+l[i-1])%INF
    l.append(num)
print(l[-1])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
n,m=map(int,input().split())
a=[]
mod=1000000007
for _ in range(m):
    a.append(int(input()))
if 1 in a:
    ans=[1]+[0]+[0]*(n-1)
else:
    ans=[1]+[1]+[0]*(n-1)
for i in range(2,n+1):
    if i in a:
        ans[i]=0
    else:
        ans[i]=(ans[i-1]+ans[i-2])%mod
print(ans[n])

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

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 not 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 = [int(input()) for _ in range(m)]
MOD = 10 ** 9 + 7

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]) % 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 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]) % MOD

print(dp[-1])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:

mod=10**9+7
n, m = map(int, input().split())
ai=[]

for i in range(m):
    ai.append(int(input()))
#print(ai)

dp=[]
for i in range(n+1):
    dp.append(0)

dp[0]=1
if 1 in ai:
    dp[1]=0
else:
    dp[1]=1

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

#print(dp)
print(dp[n])

Submission status: Time Limit Exceeded

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

    S =[0]*(N + 1)
    S[0] = 1
    if 1 in A:
        S[1] = 0
    else:
        S[1] = 1

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

Submission status: Time Limit Exceeded

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

arr=[]
mod=pow(10,9)+7
for i in range(m):
    a=int(input())
    arr.append(a)

step=[int(0) for i in range(n+1)]
step[0]=1
step[1]=1
i=2
f=0
while i<=n:
    if i not in arr:
        if (i-1) in arr and (i-2) in arr:
            f+=1
            break
        else:
            if (i-1) not in arr and (i-2) not in arr:
                step[i]=step[i-1]+step[i-2]
            elif (i-1) not in arr and (i-2) in arr:
                step[i]=step[i-1]        
            elif (i-1) in arr and (i-2) not in arr:
                step[i]=step[i-2]


    i+=1  


#print(step)
if f!=0:
    print(0)
else:    
    print((step[n])%mod)

Submission status: Time Limit Exceeded

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

arr=[]
mod=pow(10,9)+7
for i in range(m):
    a=int(input())
    arr.append(a)

step=[int(i) for i in range(n+1)]
step[0]=1
step[1]=1
i=2
f=0
while i<=n:
    if i not in arr:
        if (i-1) in arr and (i-2) in arr:
            f+=1
            break
        else:
            if (i-1) not in arr and (i-2) not in arr:
                step[i]=step[i-1]+step[i-2]
            elif (i-1) not in arr and (i-2) in arr:
                step[i]=step[i-1]        
            elif (i-1) in arr and (i-2) not in arr:
                step[i]=step[i-2]


    i+=1  


#print(step)
if f!=0:
    print(0)
else:    
    print((step[n])%mod)

Submission status: Time Limit Exceeded

Solution code:
MOD = 1000000007
n, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
dp = [-1 for _ in range(n+1)]
dp[0] = 1
dp[1] = 1
if 1 in A:
    dp[1] = 0

step = 2
while True:
    if step == n+1:
        break
    
    if step in A:
        dp[step] = 0
    else:
        dp[step] = (dp[step-1] + dp[step-2]) % MOD
        
    step += 1
    
print(dp[n])

Submission status: Time Limit Exceeded

Solution code:
#4
#1 3 1 1
G, N = [int(_) for _ in input().split(" ")]
ret = ()
for i in range(N):
  ret += (int(input()),)

T = [0]*(G+1)

T[0] = 1
T[1] = 1

if 1 in ret:
  T[1] = 0

for i in range(2, G+1):
	if i in ret:
		T[i] = 0
		continue
	T[i] = (T[i-1] + T[i-2]) % 1000000007

print (T[G])

Submission status: Time Limit Exceeded

Solution code:
#4
#1 3 1 1
G, N = [int(_) for _ in input().split(" ")]
ret = ()
for i in range(N):
  ret += (int(input()),)

T = [0]*(G+1)

T[0] = 1
T[1] = 1

if 1 in ret:
  T[1] = 0

for i in range(2, G+1):
	if i in ret:
		T[i] = 0
		continue
	T[i] = T[i-1] + T[i-2]

print (T[G] % 1000000007)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
n,m=map(int,input().split())
arr=[1,2]
arr=arr+[0]*(n-2)
danger=list(map(int,sys.stdin))
danger.append(0)
if 1 in danger:
  arr[0]=0
  arr[1]=1
for i in range(n):
  if i+1 in danger:
    arr[i]=0
  elif i==0 or i==1:
    continue 
  else:
    arr[i]=(arr[i-1]+arr[i-2])%(10**9+7)
print(arr[n-1]%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import sys
n,m=map(int,input().split())
arr=[1,2]
arr=arr+[0]*(n-2)
danger=tuple(map(int,sys.stdin))
if 1 in danger:
  arr[0]=0
  arr[1]=1
for i in range(n):
  if i+1 in danger:
    arr[i]=0
  elif i==0 or i==1:
    continue 
  else:
    arr[i]=(arr[i-1]+arr[i-2])%(10**9+7)
print(arr[n-1]%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
arr=[1,2]
arr=arr+[0]*(n-2)
danger=[int(input()) for _ in range(m)]
if 1 in danger:
  arr[0]=0
  arr[1]=1
for i in range(n):
  if i+1 in danger:
    arr[i]=0
  elif i==0 or i==1:
    continue 
  else:
    arr[i]=(arr[i-1]+arr[i-2])%(10**9+7)
print(arr[n-1]%(10**9+7))

Submission status: Time Limit Exceeded

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

x=[0]*(N+1)
if len(x)!=0:
    x[0]=1
if len(x) >0:
    x[1]=1 if not 1 in a else 0

for i in range(2,N+1): 
    if not i in a:
        x[i]=x[i-1]+x[i-2]
    else:
        x[i]=0

print(int(x[N]%(1000000007)))

Submission status: Time Limit Exceeded

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

else:
    ls = []

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

if 1 in ls:
    dp[1]= 0
else:
    dp[1]= 1

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

Submission status: Time Limit Exceeded

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

else:
    ls = []

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

if 1 in ls:
    dp[1]= 0
else:
    dp[1]= 1

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

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())  # N段の階段, 壊れている床の個数M

# A = []

# flag = True
# for i in range(M):
#     A.append(int(input()))
#     if len(A) > 1:
#         if A[i] == A[i-1]+1:
#             print(0)
#             flag = False
#             break

# if flag:

A = [int(input()) for _ in range(M)]

dp = [0, 1]

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

print(dp[-1] % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())  # N段の階段, 壊れている床の個数M

# A = []

# flag = True
# for i in range(M):
#     A.append(int(input()))
#     if len(A) > 1:
#         if A[i] == A[i-1]+1:
#             print(0)
#             flag = False
#             break

# if flag:

A = [int(input()) for _ in range(M)]

dp = [0, 1]

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

print(dp[-1] % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

def count_step(n):
    num=n//2
    count=0
    for i in range(num+1):
        step=[]
        for _ in range(n-2*i):
            step.append(1)
        for _ in range(i):
            step.append(2)
        count+=len(list(itertools.combinations(step,i)))
    return count

if M!=0:
    a2=[a[0]-1]
    
    for i in range(M-1):
        p=a[i+1]-a[i]-2
        
        a2.append(p)
    
    a2.append(N-a[M-1]-1)

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

if p==0:
    pattern=0
else:
    pattern=1
    if M==0:
        pattern=count_step(N)
    else:
        for i in range(len(a2)):
            pattern*=count_step(a2[i])

print(pattern%1000000007)

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
ans = []
dp = [1] * N

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

print(dp[N-1] % MOD)

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
ans = []
dp = [1] * N

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

print(dp[N-1] % MOD)

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
j=0
for i in range(1,n+1):
  if i in a:
    #dp[a[j]] = 0 
    continue
  if i==1:
    dp[1] = dp[0]
    continue
  dp[i] = dp[i-1]+dp[i-2]
  dp[i]%=mod
print(dp[n])

Submission status: Time Limit Exceeded

Solution code:
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
j=0
for i in range(1,n+1):
  for j in range(m):
    dp[a[j]] = 0
    continue
  if i==1:
    dp[1] = dp[0]
    continue
  dp[i] = dp[i-1]+dp[i-2]
  dp[i]%=mod
print(dp[n])

Submission status: Time Limit Exceeded

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

# a = set()
# for i in range(m):
#     a_tmp = int(input())
#     a.add(a_tmp)

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

dp = [0] * (n + 1)
for i in range(n + 1):
    if i in a:
        dp[i] = 0
    else:
        if i == 0:
            dp[i] = 1
        elif i == 1:
            dp[i] = 1
        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())

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

dp = [0] * (n + 1)
for i in range(n + 1):
    if i in a:
        dp[i] = 0
    else:
        if i == 0:
            dp[i] = 1
        elif i == 1:
            dp[i] = 1
        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())
# A = set()
# for i in range(m):
#     a = int(input())
#     A.add(a)
a = []
for i in range(m):
    a.append(int(input()))
dp = [0] * (n + 1)
for i in range(n + 1):
    if i in a:
        dp[i] = 0
    else:
        if i == 0:
            dp[i] = 1
        elif i == 1:
            dp[i] = 1
        else:
            dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007
print(dp[n])

"""
100 5
1
23
45
67
89
"""

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

dp = [0] * (n + 1)

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

print(int(dp[n]))

"""
100 5
1
23
45
67
89
"""

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

dp = np.zeros(n + 1)

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

print(int(dp[n]))

"""
100 5
1
23
45
67
89
"""

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import numpy as np
from math import factorial
# 有理数型をインポート
from fractions import Fraction

# 組合せの総数
class Conb:
    def __init__(self, MOD=0):
        self.MOD=MOD
        self.memo = {}

    def comb(self, n, k):
        if (n, k) in self.memo:
            return self.memo[(n, k)]
        if n < 0 or k < 0:
            pdt = 0
        else:
            pdt = 1
            for s in range(1, k + 1):
                pdt *= Fraction(n - s + 1, s)
        # 戻り値をint型にするために分子を取り出す
        self.memo[(n,k)]=pdt.numerator%MOD
        return pdt.numerator%MOD

N, M = [int(x) for x in stdin.readline().rstrip().split()]
MOD = 10**9+7

stairs = []
now = 0
for i in range(M):
    a = int(stdin.readline().rstrip().split()[0])
    stairs.append(a-1 - now)
    now = a+1
stairs.append(N-now)
cb = Conb(MOD)
def f(n):
    if n==0:
        return 1
    if n==-1:
        return 0
    ret = 1
    for i in range(1,int(n/2)+1):
        ret += cb.comb((n-2*i+i),i)
    return ret%MOD
# print(stairs)

ans = 1
for s in stairs:
    #print("s =", s)
    ans *= f(s)
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import numpy as np
from math import factorial
# 有理数型をインポート
from fractions import Fraction

# 組合せの総数
def comb(n, k, MOD=1):

    if n < 0 or k < 0:
        pdt = 0

    else:
        pdt = 1
        for s in range(1, k + 1):
            pdt *= Fraction(n - s + 1, s)

    # 戻り値をint型にするために分子を取り出す
    return pdt.numerator%MOD

N, M = [int(x) for x in stdin.readline().rstrip().split()]
MOD = 10**9+7

stairs = []
now = 0
for i in range(M):
    a = int(stdin.readline().rstrip().split()[0])
    stairs.append(a-1 - now)
    now = a+1
stairs.append(N-now)

def f(n):
    if n==0:
        return 1
    if n==-1:
        return 0
    ret = 1
    for i in range(1,int(n/2)+1):
        ret += comb((n-2*i+i),i, MOD)
    return ret%MOD
# print(stairs)

ans = 1
for s in stairs:
    #print("s =", s)
    ans *= f(s)
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# n = int(sys.stdin.readline())
# a, b = map(int, sys.stdin.readline().split())
# c = list(map(int, sys.stdin.readline().split()))
# s = [list(map(int,list(sys.stdin.readline()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき

# a = 100
# b = 0.987654321
# print('{0:06d}-{1:6f}'.format(a,b))  # 0埋め, 小数点出力桁指定時のときの出力
# 000100-0.987654

import math
import sys
import itertools
import queue

mod = 1000000007

if __name__ == "__main__":
    N, M = map(int, sys.stdin.readline().split())

    broken = [int(sys.stdin.readline()) for _ in range(M)]
    dp = [0 for _ in range(N + 2)]
    dp[N] = 1
    for i in range(0, N)[::-1]:
        if i not in broken:
            dp[i] = dp[i + 1] + dp[i + 2]
    print(dp[0] % mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
max_num = 1000000007
input = sys.stdin.readline
N, M = map(int, input().split())
A = [int(input()) for i in range(M)]

current_step, prev_step, two_prev_step = 0, 1, 0
for i in sorted(range(N), reverse=True):
    if i in A:
        prev_step, two_prev_step = 0, prev_step
        continue

    current_step = prev_step + two_prev_step
    prev_step, two_prev_step = current_step, prev_step

print(current_step % max_num)

Submission status: Time Limit Exceeded

Solution code:
import sys
max_num = 1000000007
input = sys.stdin.readline
N, M = map(int, input().split())
A = list([int(input()) for i in range(M)])

current_step, prev_step, two_prev_step = 0, 1, 0
for i in sorted(range(N), reverse=True):
    if i in A:
        prev_step, two_prev_step = 0, prev_step
        continue

    current_step = prev_step + two_prev_step
    prev_step, two_prev_step = current_step, prev_step

print(current_step % max_num)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
A = list([int(input()) for i in range(M)])

current_step, prev_step, two_prev_step = 0, 1, 0
for i in sorted(range(N), reverse=True):
    if i in A:
        prev_step, two_prev_step = 0, prev_step
        continue

    current_step = prev_step + two_prev_step
    prev_step, two_prev_step = current_step, prev_step

print(current_step % 1000000007)

Submission status: Time Limit Exceeded

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

current_step, prev_step, two_prev_step = 0, 1, 0
for i in reversed(range(N)):
    if i in A:
        prev_step, two_prev_step = 0, prev_step
        continue

    current_step = prev_step + two_prev_step
    prev_step, two_prev_step = current_step, prev_step

print(current_step % 1000000007)

Submission status: Time Limit Exceeded

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

stairs = [1] * (N+1)
for i in reversed(range(N+1)):
    if i in A:
        stairs[i] = 0
        continue

    prev_step, two_prev_step = 1, 0
    if (N + 1) > i+1:
        prev_step = stairs[i+1]
    if (N + 1) > i+2:
        two_prev_step = stairs[i+2]

    stairs[i] = prev_step + two_prev_step
print(stairs[0] % 1000000007)

Submission status: Time Limit Exceeded

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

stairs = [1] * (N+1)
for i in reversed(range(N+1)):
    if i in A:
        stairs[i] = 0
        continue

    one_step, two_step = 1, 0
    if stairs[i+1:i+2]:
        one_step = stairs[i+1]
    if stairs[i+2:i+3]:
        two_step = stairs[i+2]

    stairs[i] = one_step + two_step
print(stairs[0] % 1000000007)

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]*(N+1) #dp[i]...i番目にいる時の移動方法の数

count = 0
for i in range(1,N):
    if i in a:
        count += 1
        if count == 2:
            print(0)
            exit()
    else:
        count = 0

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

print(dp[N])