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 math

def f(n):
    global memo
    if memo[n]==0:
        ans = 0
        for i in range(n+1):
            cnt_1 = n - 2*i
            cnt_2 = 0 + 1*i
            if cnt_1 < 0:
                break
            else:
                ans += math.factorial(cnt_1+cnt_2)//(math.factorial(cnt_1)*math.factorial(cnt_2))
        memo[n] = ans
    return memo[n]

memo = [0] * (10**5 + 1)

n,m = map(int,input().split())
start = 0
ans = 1
for i in range(m):
    a = int(input())
    if start == a:
        ans = 0
        break
    else:
        ans = ans * f((a-1)-start)
        start = a + 1
ans = ans * f(n-start)
print(ans%1000000007)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

for x in range(n):
    if not x in a:
        l[x+1]+=l[x]
        l[x+2]+=l[x]
print(l[n]%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import math
import sys

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

def nCr(n, r):
  c = math.factorial(n) // (math.factorial(n-r) * math.factorial(r))
  return c

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

    sys.exit()


a.insert(0, -1)
a.append(n+1)

cnt = 1

for i in range(m+1):
  step = (a[i+1] - 1) - (a[i] + 1)
  pattern = 1
  for j in range(1, step//2 + 1):
    k = j
    if j > (step - j) // 2:
      k = step - 2*j
    pattern += nCr(step - j, k)
  cnt *= pattern

print(cnt%1000000007)

Submission status: Time Limit Exceeded

Solution code:
import math
import sys

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

def nCr(n, r):
  c = math.factorial(n) // (math.factorial(n-r) * math.factorial(r))
  return c

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

    sys.exit()


a.insert(0, -1)
a.append(n+1)

cnt = 1

for i in range(m+1):
  step = (a[i+1] - 1) - (a[i] + 1)
  pattern = 1
  for j in range(1, step//2 + 1):
    pattern += nCr(step - j, j)
  cnt *= pattern

print(cnt%1000000007)

Submission status: Time Limit Exceeded

Solution code:
n,m =map(int, input().split())
    #idxへの行き方の通りをリスト化
num_list = [0]*(n+1)
num_list[0] = 1
a_list =[int(input()) for _ in range(m)]
if 1 not in a_list:
    num_list[1] = 1
for i in range(2,n+1):
    if i not in a_list:
        num_list[i] = num_list[i-1] + num_list[i-2]
print(num_list[n]%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
def main():
    n,m =map(int, input().split())
    #idxへの行き方の通りをリスト化
    num_list = [0]*(n+1)
    num_list[0] = 1
    a_list =[int(input()) for _ in range(m)]
    if 1 not in a_list:
        num_list[1] = 1
    
    for i in range(2,n+1):
        if i not in a_list:
            num_list[i] = num_list[i-1] + num_list[i-2]
    #print(num_list)
    return num_list[n]

if __name__=='__main__':
    print(main()%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
def main():
    n,m =map(int, input().split())
    #idxへの行き方の通りをリスト化
    num_list = [0]*(n+1)
    num_list[0] = 1
    a_list =[int(input()) for _ in range(m)]
    div =1000000007
    if 1 not in a_list:
        num_list[1] = 1
    
    for i in range(2,n+1):
        if i not in a_list:
            num_list[i] = num_list[i-1] + num_list[i-2]
    #print(num_list)
    return num_list[-1]%div

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

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 in a: nums[i] = 0
  else: 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 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 not in a:
        dp[i] = (dp[i-1] + dp[i-2]) % 1000000007
#print(dp)
print(dp[n])

Submission status: Time Limit Exceeded

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

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

dp = [0] * (n + 1)
dp[0] = 1
for now in range(0, n + 1):
    for next_step in range(now + 1, min(n + 1, now + 3)):
        if not next_step in a:
            dp[next_step] += dp[now]
            dp[next_step] %= 1000000007

print(dp[n])

Submission status: Time Limit Exceeded

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

broken_list = []
if M > 0:
    for i in range(M):
        broken_list.append(int(input()))

nums = [0] * (N + 1)
nums[0] = 1

if 1 not in broken_list:
    nums[1] = 1

for i in range(2, N + 1):
    nums[i] = nums[i - 1] + nums[i - 2]
    if i in broken_list:
        nums[i] = 0

print(nums[N] % 1000000007)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

dp[1] = 1

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

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

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
br = []
dp = [0]*(N+1)
for i in range(M):
    a = int(input())
    br.append(a)

dp[0] = 1

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

for i in range(2,N+1):
    if i in br:
        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())
br = []
dp = [0]*(N+1)
for i in range(M):
    a = int(input())
    br.append(a)

dp[0] = 1

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

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

ans = dp[N] % (10**9+7)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
lst=[int(input()) for i in range(m)]
DP=[0]*(n+1)
temp=0
DP[0]=1
for i in range(1, n+1):
  if i==1 and i not in lst:
    DP[i]=1
  elif i==1 and i in lst:
    DP[i]=0
  elif i in lst:
    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())
lst=[int(input()) for i in range(m)]
DP=[0]*(n+1)
temp=0
DP[0]=1
for i in range(1, n+1):
  if i==1 and i not in lst:
    DP[i]=1
  elif i==1 and i in lst:
    DP[i]=0
  elif i in lst:
    DP[i]=0
  else:
    DP[i]=DP[i-1]+DP[i-2]
print(DP[n]%1000000007)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
lst=[int(input()) for i in range(m)]
DP=[0]*(n+1)
temp=0
DP[0]=1
for i in range(1, n+1):
  if i==1 and i not in lst:
    DP[i]=1
  elif i==1 and i in lst:
    DP[i]=1
    temp=i+1
  else:
    if i-1 not in lst and i-2 not in lst:
      DP[i]+=DP[i-1]+DP[i-2]
    elif i-1 not in lst and i-2 in lst:
      DP[i]+=DP[i-1]
    elif i-1 in lst and i-2 not in lst:
      DP[i]+=DP[i-2]
    else:
      break;
print(DP[n]%1000000007)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
lst=[int(input()) for i in range(m)]
DP=[0]*(n+1)
temp=0
DP[0]=1
for i in range(1, n+1):
  if i==1:
    DP[i]=1
    if i in lst:
      temp=i+1
  elif i!=temp and i in lst:
    DP[i]=DP[i-1]
    temp=i+1
  elif i==temp:
    if i in lst:
      break;
    else:
      DP[i]=DP[i-1]
  elif i-2 in lst:
    DP[i]=DP[i-1]
  else:
    DP[i]=DP[i-1]+DP[i-2]
print(DP[n]%1000000007)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
lst=[int(input()) for i in range(m)]
DP=[0]*(n+1)
temp=0
DP[0]=1
for i in range(1, n+1):
  if i==1 and i not in lst:
    DP[i]=1
  elif i==1 and i in lst:
    DP[i]=1
    temp=i+1
  elif i!=temp and i in lst:
    DP[i]=DP[i-1]
    temp=i+1
  elif i==temp and i in lst:
    break;
  elif i==temp and i not in lst:
    DP[i]=DP[i-1]
  elif i-2 in lst:
    DP[i]=DP[i-1]
  else:
    DP[i]=DP[i-1]+DP[i-2]
print(DP[n]%1000000007)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
ais = []
for _ in range(m):
    ai = int(input())
    ais.append(ai)
dp = [0]*(n+1)
dp[0]=1
if 1 in ais:
  dp[1]=0
else:
  dp[1]=1
for i in range(2,n+1):
    if i in ais:
        dp[i] = 0
    else:
        dp[i] = dp[i-1] + dp[i-2]
print(dp[n]%1000000007)

Submission status: Time Limit Exceeded

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

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[n])

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
a = [int(input()) for _ in range(m)]
for i in range(len(a)-1):
    if a[i+1] == a[i]+1:
        print(0)
        exit()
x = [0]*(n+1)
x[0]=1
div = 1000000007

if not 1 in a:
    x[1]=1

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

Submission status: Time Limit Exceeded

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

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

print(ans[-1])

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)
if n==1:
  print(1)
  exit()
if 1 in a and 2 in a:
  print(0)
  exit()
elif 1 in a:
  dp[1]=0
  dp[2]=1
elif 2 in a:
  dp[1]=1
  dp[2]=0
else:
  dp[1]=1
  dp[2]=2
  
for i in range(3,n+1):
  if i in a:
    dp[i]=0
  else:
    dp[i]=(dp[i-1]+dp[i-2])%MOD
print(dp[-1]%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 not in A:
        if i == 1:
            dp[i] = dp[i - 1] % mod
        else:
            dp[i] = dp[i - 1] + dp[i - 2] % mod
print(dp[n] % mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
from functools import lru_cache
sys.setrecursionlimit(10**9)
MOD=10**9+7
n,m=map(int,input().split())
a=[int(input()) for _ in range(m)]
if n==1:
  print(1)
  exit()
if 1 in a and 2 in a:
  print(0)
  exit()
elif 1 in a:
  ans=[0,0,1]
elif 2 in a:
  ans=[0,1,0]
else:
  ans=[0,1,2]

@lru_cache(maxsize=None)
def cnt(x):
  if x<3:
    return ans[x]
  if x in a:
    return 0
  else:
    return (cnt(x-1)+cnt(x-2))%MOD

print(cnt(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)]
if n==1:
  print(1)
  exit()
if 1 in a and 2 in a:
  print(0)
  exit()
elif 1 in a:
  ans=[0,1]
elif 2 in a:
  ans=[1,0]
else:
  ans=[1,2]

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

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

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
ans = 1
MOD = 10**9+7
MAX = 10**5+1
fact = [1] * MAX

for i, j in zip(a[:m-1], a[1:]):
    if j - i == 1:
        print(0)
        exit()

def comb_init():
    fact[0], fact[1] = 1, 1
    for i in range(2, MAX):
        fact[i] = fact[i-1] * i

def comb(n, r):
    return (fact[n]%MOD) * pow(fact[r], -1, MOD) * pow(fact[n-r], -1, MOD) 

def f(k):
    idx = k // 2
    num = 0
    for i in range(1, idx+1):
        num += comb(k-i, i)
        num %= MOD
    return num+1

comb_init()
for i in range(m+1):
    left = 0 if i == 0 else a[i-1] + 1
    right = n if i == m else a[i] - 1
    between = right - left
    ans *= f(between)
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
A = [int(input()) for m in range(M)]
dp = (N+1)*[0]
dp[0] = 1

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

print(dp[-1])

Submission status: Time Limit Exceeded

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

mod = 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 not in A:
    dp[i] = dp[i-1] + dp[i-2]
    dp[i] %= mod

print(dp[n])

Submission status: Time Limit Exceeded

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

# In[15]:


from collections import deque


# In[9]:


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


# In[31]:


dp = deque([0]*2)
dp[0] = 1
ans = 0
mod = 1000000007
if N == 1:
    ans = 1
else:
    if 1 in alist:
        dp[1] = 0
    else:
        dp[1] = 1
    for i in range(2,N+1):
        if i in alist:
            dp.append(0)
        else:
            dp.append((dp[0] + dp[1])%mod)
        dp.popleft()
    ans = dp[-1]
print(ans)


# In[ ]:

Submission status: Time Limit Exceeded

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

# In[15]:


from collections import deque


# In[9]:


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


# In[18]:


dp = deque([0]*2)
dp[0] = 1
ans = 0
mod = 1000000007
if N == 1:
    ans = 1
else:
    if 1 in alist:
        dp[1] = 0
    else:
        dp[1] = 1
    for i in range(2,N+1):
        dp.append((dp[i-1] + dp[i-2])%mod)
        if i in alist:
            dp[-1] = 0
        dp.popleft
    ans = dp[-1]
print(ans)


# In[ ]:

Submission status: Time Limit Exceeded

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

# In[9]:


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


# In[14]:


dp = [0]*(N+1)
dp[0] = 1
ans = 0
mod = 1000000007
if N == 1:
    ans = 1
else:
    if 1 in alist:
        dp[1] = 0
    else:
        dp[1] = 1
    for i in range(2,N+1):
        dp[i] = (dp[i-1] + dp[i-2])%mod
        if i in alist:
            dp[i] = 0
    ans = dp[-1]
print(ans)


# In[ ]:

Submission status: Time Limit Exceeded

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

# In[9]:


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


# In[12]:


dp = [0]*(N+1)
dp[0] = 1
ans = 0
if N == 1:
    ans = 1
else:
    if 1 in alist:
        dp[1] = 0
    else:
        dp[1] = 1
    for i in range(2,N+1):
        dp[i] = dp[i-1] + dp[i-2]
        if i in alist:
            dp[i] = 0
    ans = dp[-1]%1000000007
print(ans)


# In[ ]:

Submission status: Time Limit Exceeded

Solution code:
INF = 1_000_000_007


def comb(n, k):
    k = min(n - k, k)
    if n == 0 or k == 0:
        return 1
    a = n
    for i in range(n - 1, n - k, -1):
        a *= i
    b = 1
    for i in range(2, k + 1):
        b *= i
    return a // b


N, M = list(map(int, input().split()))
A = [-1] + [int(input()) for _ in range(M)] + [N + 1]
res = 1
for i in range(M + 1):
    t = A[i + 1] - A[i] - 2
    if t < 0:
        res = 0
    else:
        _t = 0
        for i in range(t // 2 + 1):
            _t += comb(t - i, i)
        res *= _t
print(res % INF)

Submission status: Time Limit Exceeded

Solution code:
import sys
INF = 1_000_000_007


def comb(n, k):
    if n == 0 or k == 0:
        return 1
    a = n
    for i in range(n - 1, n - k, -1):
        a *= i
    b = 1
    for i in range(2, k + 1):
        b *= i
    return a // b


N, M = list(map(int, input().split()))
A = [-1] + [int(input()) for _ in range(M)] + [N + 1]
res = 1
for i in range(M + 1):
    t = A[i + 1] - A[i] - 2
    if t < 0:
        print(0)
        sys.exit()
    else:
        _t = 0
        for i in range(t // 2 + 1):
            _t += comb(t - i, i)
        res *= _t
print(res % INF)

Submission status: Time Limit Exceeded

Solution code:
INF = 1_000_000_007


def comb(n, k):
    if n == 0 or k == 0:
        return 1
    a = n
    for i in range(n - 1, n - k, -1):
        a *= i
    b = 1
    for i in range(2, k + 1):
        b *= i
    return a // b


N, M = list(map(int, input().split()))
A = [-1] + [int(input()) for _ in range(M)] + [N + 1]
res = 1
for i in range(M + 1):
    t = A[i + 1] - A[i] - 2
    if t < 0:
        res = 0
    else:
        _t = 0
        for i in range(t // 2 + 1):
            _t += comb(t - i, i)
        res *= _t
print(res % INF)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7

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

dp = [1] * (N+1)

if 1 in A: dp[1] = 0

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

Submission status: Time Limit Exceeded

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

dp = [0]*(n+1)
dp[0] = 1
for i in range(n):
    for j in range(i+1, min(n, i+2)+1):
        if j not in am:
            dp[j] += dp[i]
            dp[j] %=1000000007
print(dp[n])

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, m = map(int, input().split())
    As = [int(input()) for _ in range(m)]
    mod = 10**9+7

    Steps = [0] * (n+1)
    Steps[0] = 1
    if 1 not in As:
        Steps[1] = 1

    for i in range(2, n+1):
        if i in As:
            continue
        Steps[i] = Steps[i-1] + Steps[i-2]
    ans = Steps[-1] % mod
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

    Steps = [0] * (n+1)
    Steps[0] = 1
    if 1 not in As:
        Steps[1] = 1

    for i in range(2, n+1):
        if i in As:
            continue
        Steps[i] = Steps[i-1] + Steps[i-2]
    ans = Steps[-1] % (10**9+7)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import copy
import sys
sys.setrecursionlimit(200000)

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

start = 0
stop = N

reached_ = list(range(stop - start + 1))
reached = copy.copy(reached_)
for v in a:
    reached[v] = 'x'
#print(reached)
#history = []

count = 0
def dfs(x):
    global count

    if x > N:
        return

    if x == N:
        count += 1
        #h.append(x)
        #history.append(h)
        #reached[x] = -1
        return
    
    if reached[x] == 'x':
        return
    
    #h.append(x)

    #reached[x] = -1

    dfs(x + 1)
    dfs(x + 2)

    #reached[x] = reached_[x]

dfs(0)
print(count%100000007)
#print(history)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int,input().split())
A_list = [int(input()) for _ in range(M)]
Dp_list = [0] * (N+1)
Dp_list[0] = 1
inf = 1000000007

if 1 in A_list:
    Dp_list[1] = 0
else:
    Dp_list[1] = 1

if N != 1:
    for i in range(2, N + 1):
        if i in A_list:
            continue

        Dp_list[i] = Dp_list[i-2] + Dp_list[i-1]
        Dp_list[i] %= inf
    print(Dp_list[N])
else:
    print(1)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int,input().split())
A_list = [int(input()) for _ in range(M)]
Dp_list = [0] * (N+1)
Dp_list[0] = 1

if 1 in A_list:
    Dp_list[1] = 0
else:
    Dp_list[1] = 1

if N != 1:
    for i in range(2, N + 1):
        if i in A_list:
            continue

        Dp_list[i] = Dp_list[i-2] + Dp_list[i-1]
        Dp_list[i] %= 1000000007
    print(Dp_list[N])
else:
    print(1)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int,input().split())
A_list = [int(input()) for _ in range(M)]
Dp_list = [0] * (N+1)
Dp_list[0] = 1

if 1 in A_list:
    Dp_list[1] = 0
else:
    Dp_list[1] = 1

if N != 1:
    for i in range(2, N + 1):
        if i in A_list:
            continue
#        elif i in A_list and i-1 in A_list:
#            Dp_list = [0] * (N + 1)
#            break
        Dp_list[i] = Dp_list[i-2] + Dp_list[i-1]
#        else:
#            Dp_list[i] = 0
        if Dp_list[i] > 1000000007:
            Dp_list[i] -= 1000000007
    print(Dp_list[N])
else:
    print(1)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int,input().split())
A_list = [int(input()) for _ in range(M)]
Dp_list = [0] * (N+1)
Dp_list[0] = 1
#for i in range(M):
#    A_list.append(int(input()))
if A_list:
    if A_list[0] == 1:
        Dp_list[1] = 0
    else:
        Dp_list[1] = 1
else:
    Dp_list[1] = 1
if N != 1:
    for i in range(2, N + 1):
        if i in A_list:
            continue
#        elif i in A_list and i-1 in A_list:
#            Dp_list = [0] * (N + 1)
#            break
        Dp_list[i] = Dp_list[i-2] + Dp_list[i-1]
#        else:
#            Dp_list[i] = 0
        if Dp_list[i] > 1000000007:
            Dp_list[i] -= 1000000007
    print(Dp_list[N])
else:
    print(1)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int,input().split())
A_list = []
Dp_list = [0] * (N+1)
Dp_list[0] = 1
for i in range(M):
    A_list.append(int(input()))
if A_list:
    if A_list[0] == 1:
        Dp_list[1] = 0
    else:
        Dp_list[1] = 1
else:
    Dp_list[1] = 1
if N != 1:
    for i in range(2, N + 1):
        if i in A_list:
            continue
#        elif i in A_list and i-1 in A_list:
#            Dp_list = [0] * (N + 1)
#            break
        Dp_list[i] = Dp_list[i-2] + Dp_list[i-1]
#        else:
#            Dp_list[i] = 0
        if Dp_list[i] > 1000000007:
            Dp_list[i] -= 1000000007
    print(Dp_list[N])
else:
    print(1)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int,input().split())
A_list = []
Dp_list = [0] * (N+1)
Dp_list[0] = 1
for i in range(M):
    A_list.append(int(input()))
if A_list:
    if A_list[0] == 1:
        Dp_list[1] = 0
    else:
        Dp_list[1] = 1
else:
    Dp_list[1] = 1
if N != 1:
    for i in range(2, N + 1):
        if i not in A_list:
            Dp_list[i] = Dp_list[i-2] + Dp_list[i-1]
        elif i in A_list and i-1 in A_list:
            Dp_list = [0] * (N + 1)
            break
        else:
            Dp_list[i] = 0
        if Dp_list[i] > 1000000007:
            Dp_list[i] -= 1000000007
    print(Dp_list[N])
else:
    print(1)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int,input().split())
A_list = []
for i in range(M):
    A_list.append(int(input()))
if A_list:
    if A_list[0] == 1:
        Dp_list = [1,0] + [0] * (N-1)
    else:
        Dp_list = [1,1] + [0] * (N-1)
else:
    Dp_list = [1,1] + [0] * (N-1)
if N != 1:
    for i in range(2, N + 1):
        if i not in A_list:
            Dp_list[i] = Dp_list[i-2] + Dp_list[i-1]
        elif i in A_list and i-1 in A_list:
            Dp_list = [0] * (N + 1)
            break
        else:
            Dp_list[i] = 0
        if Dp_list[i] > 1000000007:
            Dp_list[i] -= 1000000007
    print(Dp_list[N])
else:
    print(1)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int,input().split())
A_list = []
for i in range(M):
    A_list.append(int(input()))
if A_list:
    if A_list[0] == 1:
        Dp_list = [1,0]
    else:
        Dp_list = [1,1]
else:
    Dp_list = [1,1]
if N != 1:
    for i in range(2, N + 1):
        if i not in A_list:
            Dp_list.append(Dp_list[i-2] + Dp_list[i-1])
        elif i in A_list and i-1 in A_list:
            Dp_list = [0] * (N + 1)
            break
        else:
            Dp_list.append(0)
        if Dp_list[i] > 1000000007:
            Dp_list[i] -= 1000000007
    print(Dp_list[N])
else:
    print(1)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int,input().split())
A_list = []
for i in range(M):
    A_list.append(int(input()))
if A_list:
    if A_list[0] == 1:
        Dp_list = [1,0]
    else:
        Dp_list = [1,1]
else:
    Dp_list = [1,1]
if N != 1:
    for i in range(2, N + 1):
        if i not in A_list:
            Dp_list.append(Dp_list[i-2] + Dp_list[i-1])
        elif i in A_list and i-1 in A_list:
            Dp_list = [0] * (N + 1)
            break
        else:
            Dp_list.append(0)
        if Dp_list[i] > 1000000007:
            Dp_list[i] -= 1000000007
    print(Dp_list[N]%1000000007)
else:
    print(1)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int,input().split())
A_list = []
for i in range(M):
    A_list.append(int(input()))
if A_list:
    if A_list[0] == 1:
        Dp_list = [1,0]
    else:
        Dp_list = [1,1]
else:
    Dp_list = [1,1]
if N != 1:
    for i in range(2, N + 1):
        if i not in A_list:
            Dp_list.append(Dp_list[i-2] + Dp_list[i-1])
        elif i in A_list and i-1 in A_list:
            Dp_list = [0] * (N + 1)
            break
        else:
            Dp_list.append(0)
        if Dp_list[i-1] > 1000000007:
            Dp_list[i-1] -= 1000000007
            Dp_list[i] -= 1000000007
    print(Dp_list[N]%1000000007)
else:
    print(1)

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

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, n+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()