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

def resolve():
    (N, M) = list(map(int, input().split(" ")))
    As = [int(input()) for i in range(M)]
    mems = [False] * (N+1)

    def rec(target):
        if target in As:
            return 0
        
        if target == 1:
            return 1
        
        if target == 2:
            return 2 if 1 not in As else 1

        if not mems[target]:
            one = rec(target-1)
            two = rec(target-2)
            mems[target] = one + two
        
        return mems[target]
    
    print(rec(N)%1000000007)

if '__main__' == __name__:
    resolve()

Submission status: Time Limit Exceeded

Solution code:
mod = 1000000007
n, m = map(int, input().split())
dat_m = []
dp = []
for i in range(m):
    dat_m.append(int(input()))
dp.append(1)
for i in range(1, n + 1):
    t = 0
    t = dp[i - 1]
    if i > 1:
        t += dp[i - 2]
    if i in dat_m:
        t = 0
    t = t % mod
    dp.append(t)

print(dp[n])

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
broken_list = [int(input()) for _ in range(m)]
enable_list = [i for i in range(2, n+1) if not i in broken_list]
a = [0] * (n+1)
a[0] = 1
a[1] = 0 if 1 in broken_list else 1

if n == 1:
  print(1)
  exit()
if n == 2:
  if broken_list:
    print(1)
  else:
    print(2)
  exit()
  
for i in enable_list:
  a[i] = a[i-1] + a[i-2]

print(a[n]%1000000007)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
N,M = [int(x) for x in stdin.readline().rstrip().split()]
data = [0] * M
for _ in range(M):
    data[_] = (int(stdin.readline().rstrip()))
 
ans = [1] + [0] * (N)
if 1 in data != True:
    ans[1] = 1
for i in range(1,N + 1):
    if i in data:
      ans[i] = 0
    else:
      ans[i] = ans[i-1] + ans[i-2]
print(ans[-1] % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
from bisect import bisect_left, bisect_right

# import numpy as np
# from scipy.special import perm
# from scipy.special import comb

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
INF = float("inf")

########

N, M = l_inpl()
a = []
for _ in range(M):
    ai = i_inpl()
    a.append(ai)

dp = [None] * (N+1)

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

print(dp[0] % 1000000007)

Submission status: Time Limit Exceeded

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

case = [0] * (N + 1)
case[0] = 1
if not 1 in A:
    case[1] = 1
for x in range(2, N + 1):
    if x in A:
        case[x] = 0
    elif x - 1 in A:
        case[x] = case[x - 2]
    else:
        case[x] = case[x - 1] + case[x - 2] % 1000000007

print(case[N]%1000000007)

Submission status: Time Limit Exceeded

Solution code:

import math


def calc(_n):
    _i = (_n - 1) // 2
    c = 0
    for j in range(_i+1):
        c += math.factorial(_n-1-j) // (math.factorial(j) * math.factorial(_n - 1 - j*2))
    return c


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

b = 0
s = 1
for i in a:
    s *= calc(i-b)
    b = i + 1
if b != n:
    s *= calc(n+1-b)
print(s % 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)]
x = 0
y = 1
for i in range(N):
  if i+1 in a:
    z = 0
  else:
    z = x + y
  x,y = y,z  
print(z%MOD)

Submission status: Time Limit Exceeded

Solution code:

import sys
input = sys.stdin.readline
def isSafe(position):
    return not position in listM


STEP = 2
N,M = map(int,input().split())
dp = [0] * (N+1)
cnt = 0


listM=[int(input()) for i in range(M)]
dp[0] = 1

for i in range(N):
    if i+1 > N:
        break
    if isSafe(i+1):
        dp[i+1] += dp[i]
    if i+2 > N:
        break
    if isSafe(i+2):
        dp[i+2] += dp[i]
        #dp[j] = 0
    #print(dp)
        
print(dp[N] % 1000000007)

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import math
n, m = map(int, input().split())
now_step = 0
checked_steps = {}
factorial_dict = {}
divide_num = 1000000007 

def count_steps(number):
    global checked_steps
    global factorial_dict
    if(number in checked_steps.keys()):
        return checked_steps[number]
    # count=1*a+2*bとなるような、0以上の全てのa,bについて、1をa個、2をb個並べる並べ方を返す.
    # [1,(a+b)]からa個を選ぶ選び方と同じ
    # 余り残は和・積に関して分割法則が成り立つので1,000,000,007 で割ってもいい
    counter = 0
    for i in range(0, number + 1, 2):
        a = number - i
        b = i // 2
        if((a+b) not in factorial_dict):
            factorial_dict[a+b] = math.factorial(a+b)
        if(a not in factorial_dict):
            factorial_dict[a] = math.factorial(a)
        if(b not in factorial_dict):
            factorial_dict[b] = math.factorial(b)
        counter += factorial_dict[a+b] // (factorial_dict[a] * factorial_dict[b])
    checked_steps[number] = counter % divide_num
    return checked_steps[number]

all_count = 1
for i in range(m):
    a = int(input())
    all_count = (all_count * count_steps(a - 1 - now_step)) % divide_num
    now_step = a + 1
all_count = (all_count * count_steps(n - now_step)) % divide_num
print(all_count % divide_num)

Submission status: Time Limit Exceeded

Solution code:
MOD = 1000000007

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

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

print(dp[N] % MOD)

Submission status: Time Limit Exceeded

Solution code:

import sys
input = sys.stdin.readline
def isSafe(position):
    return not position in listM


STEP = 2
N,M = map(int,input().split())
dp = [0] * (N+1)
cnt = 0


listM=[int(input()) for i in range(M)]
dp[0] = 1

for i in range(N):
    for k in range(1, STEP+1):
        if i+k > N:
            break
        if isSafe(i+k):
            dp[i+k] += dp[i]
            
        #dp[j] = 0
    #print(dp)
        
print(dp[N] % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
 
a_list=[]
 
for index in range(m):
    a_list.append(int(input()))
 
ans_list=[]
 
for index in range(n + 1):
    ans_list.append(0)
 
for index in range(n + 1):
    if index == 0:
        ans_list[index] += 1
        continue
    if index == 1 and (index not in a_list):
        ans_list[index] += ans_list[index - 1]
        continue
    
    if index not in a_list:
        if (index - 1) not in a_list:
            ans_list[index] += ans_list[index - 1]
            ans_list[index] %= 1000000007
        if (index - 2) not in a_list:
            ans_list[index] += ans_list[index - 2]
            ans_list[index] %= 1000000007
 
print(ans_list[n])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)

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

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

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

def step_memo(N):
    if N == 0:
        return 1
    if N == 1:
        return 1

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
MOD = 1000000007

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

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

print(dp[0][N] % MOD)

Submission status: Time Limit Exceeded

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

dp[0] = 1
for i in range(1, n + 1):
    #print(dp)
    dp[i] = dp[i - 1]
    if i > 1:
        dp[i] += dp[i - 2]
    if i in dat_m:
        dp[i] = 0
    dp[i] = dp[i] % mod

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

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int, input().split())
l = [int(input()) for i in range(m)]
ll = [0]*(n+2)
ll[1] = 1
for i in range(2,n+2):
    if not i-1 in l:
        ll[i] = ll[i-1] + ll[i - 2]
print(ll[-1] % 1000000007)

Submission status: Time Limit Exceeded

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

if n == 1:
  print(1)
  exit()
if n == 2:
  if broken_list:
    print(1)
  else:
    print(2)
  exit()
  
for i in range(2, n+1):
  if i in broken_list:
    a[i] = 0
  else:
    a[i] = a[i-1] + a[i-2]

print(a[n]%1000000007)

Submission status: Time Limit Exceeded

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

def dp(n,ls):
    dp_table=[[0 for i in range(n+1)]]
    dp_table[0][0]=1
    sum=0
    while True:
        row=[]
        previous=dp_table[-1]
        for i in range(n+1):
            if i in ls:
                row.append(0)
            elif i==0:
                row.append(0)
            elif i==1:
                row.append(previous[0])
            else:
                row.append(previous[i-1]+previous[i-2])
        sum+=row[-1]
        if row.count(0)==n+1:
            return sum
        dp_table.append(row)

print(dp(n,ls)%1000000007)

Submission status: Time Limit Exceeded

Solution code:
val = list(map(int, input().strip().split()))
n = val[0]
m = val[1]
a = []

for i in range(m):
    a.append(int(input().strip()))

pastpast_result = 0
past_result = 1
result = 0

for i in range(n):
    result = 0
    if i not in a:
        result += past_result
    if i-1 not in a:
        result += pastpast_result

    if result > 1000000007:
        result = result % 1000000007
    
    pastpast_result = past_result
    past_result = result

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

Submission status: Time Limit Exceeded

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

n, m = map(int, input().split())
a = []
for i in range(m):
    aa = int(input())
    if a:
        if a[-1] == aa - 1:
            print(0)
            exit()
    a.append(aa)
dp = [0] * (n + 1)
mod = 10 ** 9 + 7

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

Submission status: Time Limit Exceeded

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

if 1 in a and 2 in a:
  print(0)
else:
  k = [0, 1]    
  for i in range(1, N+1): #インデックスは-1
    if i in a:
      k.append(0)
    else:
      sum = k[i-1] + k[i]
      k.append(sum)
      
  print(k[-1]%1000000007)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
val = list(map(int, input().strip().split()))
n = val[0]
m = val[1]
a = []

for i in range(m):
    a.append(int(input().strip()))

pastpast_result = 0
past_result = 1
result = 0

for i in range(n):
    result = 0
    if i not in a:
        result += past_result
    if i-1 not in a:
        result += pastpast_result
    
    pastpast_result = past_result
    past_result = result

print(result % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
INF = 1000000007
a = list(set(a))

ans, start = 1, 0

x = [1] * (N + 1)  #x[i]は0からiまでの階段の移動方法の数
x[0], x[1] = 1, 1
for i in range(2, N + 1):
	x[i] = (x[i - 1] + x[i - 2]) % INF

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

for k in range(N):
	if k in a:
		# print("hit")
		ans *= x[k - 1 - start]
		ans %= INF
		start = k + 1
	# print(k, "now", ans)
ans *= x[N - start]
print(ans % INF)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)

n,m = map(int,input().split())
# 差が0だと通れない
tmp=10000000
a_list=[]
for i in range(m):
    a=int(input())
    a_list.append(a)
    if abs(tmp-a)==1:
        print(0)
        exit()
    tmp=a

def count(now,s,e):
    if now > e:
        return 0
    if now == e:
        return 1
    cnt=0
    cnt+=count(now+1,s,e)
    cnt+=count(now+2,s,e)
    return cnt


c_mod=1000000007
start=0
end=0
ans=1
for a in a_list:
    # 各部分の移動方法
    end=a-1
    ans=ans*count(start,start,end)%c_mod
    start=a+1
if end<n:
    end=n
    ans=ans*count(start,start,end)%c_mod
print(ans)

Submission status: Time Limit Exceeded

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

C = [0]*(N+1)
C[0]=1
#print(C)
for i in range(N):
    if i+1 not in A:
        C[i+1]+=C[i]%MOD
    if i+2 not in A and i<N-1:
        C[i+2]+=C[i]%MOD
    #print(C)
print(C[N]%MOD)

Submission status: Time Limit Exceeded

Solution code:
def isSafe(position):
    return not position in listM


STEP =2
N,M= map(int,input().split())
dp = [0] * (N+1)
cnt = 0


listM=[]
for i in range(M):
    listM.append(int(input()))

dp[0] = 1

for i in range(N):
    for k in range(1, STEP+1):
        if i+k > N:
            break
        if isSafe(i+k):
            dp[i+k] += dp[i]
            
        #dp[j] = 0
    #print(dp)
        
print(dp[N] % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
N,M = [int(x) for x in stdin.readline().rstrip().split()]
data = []
for _ in range(M):
    data.append(int(input()))

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

Submission status: Time Limit Exceeded

Solution code:
mod = 1000000007
n, m = map(int, input().split())
dat_m = []
dp = [0] * (n + 1)
for i in range(m):
    dat_m.append(int(input()))
dp[0] = 1
for i in range(1, n + 1):
    #print(dp)
    dp[i] = dp[i - 1]

    if i > 1:
        dp[i] += dp[i - 2]

    if i in dat_m:
        dp[i] = 0

    dp[i] = dp[i] % mod

#import pprint
print(dp[n])
#pprint.pprint(dp)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N, M = map(lambda x: int(x), input().split())
a = [int(input()) for i in range(M)]
#print(N)
#print(M)
#print(a)
old = [0]
while not all(map(lambda y: y==N, old)):
  new = []
  for x in old:
    if x == N:
      new.append(x)
    if x+1 not in a and x+1 <= N:
      new.append(x+1)
    if x+2 not in a and x+2 <= N:
      new.append(x+2)
  old = new
print(len(old)%1000000007)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
def lmi(): return list(map(int, input().split()))

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

l = [0] * (n+1)
l[0] = 1
h = list(range(n+1))
for i in a:
    h.remove(i)
for i in h:
     if i == 1:
        l[i] = 1
     elif i >= 2:
        l[i] = l[i-1] + l[i-2]
        l[i] %= 1000000007


#print(l)
print(l[n] % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
def next_step_patterns(i, n_patterns1, n_patterns2):
    """
    i段目に登る場合の数を計算する
    n_patterns1 (int):
        i-1段目に登る場合の数
    n_patterns2 (int):
        i-2段目に登る場合の数
    """
    
    if i in A:
        return 0
    
    if i == 1:
        return 1
    elif i == 2:
        return 1 + n_patterns1
    else:
        return n_patterns1 + n_patterns2
      
      
N, M = list(map(int, input().split()))
A = [int(input()) for _ in range(M)]

n_patterns1, n_patterns2 = 0, 0
for i in range(1, N+1):
    now = next_step_patterns(i, n_patterns1, n_patterns2)
    n_patterns2 = n_patterns1
    n_patterns1 = now
print(now%1000000007)

Submission status: Time Limit Exceeded

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

a_list=[]

for index in range(m):
    a_list.append(int(input()))

ans_list=[]

for index in range(n + 1):
    ans_list.append(0)

for index in range(n + 1):
    if index == 0:
        ans_list[index] += 1
        continue
    if index == 1 and (index not in a_list):
        ans_list[index] += ans_list[index - 1]
        continue
    
    if index not in a_list:
        if (index - 1) not in a_list:
            ans_list[index] += ans_list[index - 1]
            ans_list[index] %= 1000000007
        if (index - 2) not in a_list:
            ans_list[index] += ans_list[index - 2]
            ans_list[index] %= 1000000007

print(ans_list[n])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N ,M = map(lambda x: int(x),input().split())
A = list(range(1,N+1))
if M>0:
    for i in range(M):
        A.remove(int(input()))

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

for i in A:
    if i>=2:
        total[i] += total[i-2]
    if i>=1:
        total[i] += total[i-1]

    total[i] = total[i]%1000000007

print(int(total[N]))

Submission status: Time Limit Exceeded

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

NG=[ 0 for i in range(N+1) ]
for i in range(M):
	a=input()
	NG[a]=1

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

mod=10**9+7

for i in range(N):
	if i+1<=N and NG[i+1]==0:
		dp[i+1]+=dp[i]
		dp[i+1]%=mod
	if  i+2<=N and NG[i+2]==0:
		dp[i+2]+=dp[i]
		dp[i+2]%=mod

print dp[N]%mod

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
N, M = map(int, input().split())
A = []
for _ in range(M):
    A.append(int(input()))

num_goup = [1]
for s in range(1, N + 1):
    if s in A:
        num_goup.append(0)
        continue
    
    if s == 1:
        num_goup.append(1)
        continue
    
    if num_goup[-1] == 0:
        if num_goup[-2] == 0:
            num_goup.append(0)
            break
        else:
            num_goup.append(num_goup[-2])
    else:
        if num_goup[-2] == 0:
            num_goup.append(num_goup[-1])
        else:
            num_goup.append(num_goup[-1] + num_goup[-2])
    
print(num_goup[-1] % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import operator
import os
from collections import Counter, deque
from fractions import gcd
from functools import lru_cache
from functools import reduce
import functools
import heapq
import itertools
import math
import numpy as np
import re
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

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

MOD = 10 ** 9 + 7
A = np.array(A)


# https://atcoder.jp/contests/abc066/submissions/5721975
def mod_invs(max, mod):
    """
    逆元のリスト 0 から max まで
    https://atcoder.jp/contests/abc127/submissions/5630531
    ここから。あんまり良くわかってない
    :param max:
    :param mod:
    :return:
    """
    invs = [1] * (max + 1)
    for x in range(2, max + 1):
        invs[x] = (-(mod // x) * invs[mod % x]) % mod
    return invs


def get_factorials(max, mod=None):
    """
    階乗 0!, 1!, 2!, ..., max!
    :param int max:
    :param int mod:
    :return:
    """
    ret = [1]
    n = 1
    if mod:
        for i in range(1, max + 1):
            n *= i
            n %= mod
            ret.append(n)
    else:
        for i in range(1, max + 1):
            n *= i
            ret.append(n)
    return ret


def can_go():
    # 上までいける？
    return len(A) < 2 or min(np.diff(A)) > 1


def mod_inv(a, mod):
    """
    a の逆元
    :param int a:
    :param int mod:
    :return:
    """
    return pow(a, mod - 2, mod)


def ncr(n, r, mod=None):
    """
    scipy.misc.comb または scipy.special.comb と同じ
    組み合わせの数 nCr
    :param int n:
    :param int r:
    :param int mod: 3 以上の素数であること
    :rtype: int
    """
    if n < r:
        return 0

    # 何度も呼ぶ場合は最大の n 以下の階乗を事前に計算しておくといい
    if mod:
        return (
                math.factorial(n)
                * mod_inv(math.factorial(r), mod)
                * mod_inv(math.factorial(n - r), mod)
                % mod
        )
    else:
        return math.factorial(n) // math.factorial(r) // math.factorial(n - r)


if not can_go():
    print(0)
    exit()


def count(n):
    ans = 0
    for r in range(n):
        if r > n - r:
            break
        ans += ncr(n - r, r, MOD)
    return max(1, ans)


step = 0
ans = 1
for a in A:
    ans = ans * count(a - step - 1) % MOD
    step = a + 1
ans *= count(N - step)
print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
def solve():
    N, M = map(int, input().split())
    A = [int(input()) for _ in range(M)]
    mm = 10 ** 9 + 7
    dp = [0] * (N + 1)
    dp[0] = 1  # 0段目に行くパターンは1とする
    dp[1] = 0 if 1 in A else 1  # 1段目の行き方を設定
    for i in range(2, N + 1):
        if i in A:
            continue
        dp[i] = (dp[i - 1] + dp[i - 2]) % mm
    print(dp[N])


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

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

if 1 in a and 2 in a:
  print(0)
else:
  k = [0, 1]    
  for i in range(1, N+1): #インデックスは-1
    if i in a:
      k.append(0)
    else:
      k.append(k[i-1]+k[i])
      
  print(k[-1]%1000000007)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:


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

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

for i in range(N):
    c=l[i]%1000000007
    if i>N-2:
        if i not in a:
            l[i+1]+=c
    elif i not in a:
        l[i+1]+=c
        l[i+2]+=c

print(l[N]%1000000007)

Submission status: Time Limit Exceeded

Solution code:
mod = 1000000007
n, m = map(int, input().split())
dat_m = []
dp = []
for i in range(n + 1):
    dp.append([0] * (n + 1))
for i in range(m):
    dat_m.append(int(input()))
dp[0][0] = 1
#print(dp[0][0])
for i in range(1, n + 1):
    #dp[i][:i-1] = dp[i-1][:i - 1]
    dp[i][i-1] = dp[i - 1][i - 1]
    dp[i][i] = dp[i - 1][i - 1]

    if i > 1:
        dp[i][i] += dp[i - 1][i - 2]
        dp[i][i-2] = dp[i - 1][i - 2]

    if i in dat_m:
        dp[i][i] = 0

    dp[i][i] = dp[i][i] % mod

import pprint
print(dp[n][n])
#pprint.pprint(dp)

Submission status: Time Limit Exceeded

Solution code:
mod=1000000007
n,m=map(int,input().split())
a=[]
for i in range(m):
    a.append(int(input()))
f=0
for i in range(len(a)):
    if a[i]+1 in a:
        f=1
        break
if f==1:
    print(0)
else:
    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]%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys

N, M = map(int,input().split())
a_lists = []

if N == 1:
    if M == 0:
        print (1)
        sys.exit()
    else:
        print(0)
        sys.exit()

for m in range (M):
    temp = int(input())
    a_lists.append(temp-1)
    
datas = [0]*N
if 0 in a_lists:
    datas[0] = 0
else:
    datas[0]=1

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

print(datas[-1]%1000000007)

Submission status: Time Limit Exceeded

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

dp = [0]*(N+3)
dp[0] = 1

for i in range(N+1):
    dp[i] = dp[i] % (10**9 + 7)
    if not i+1 in A:
        dp[i+1] += dp[i]
    if not i+2 in A:
        dp[i+2] += dp[i]
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()))

p = [0 for i in range(n)]

if 1 not in a:
    p[0] = 1

if n >= 2 and 2 not in a:
    p[1] = p[0] + 1

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

print(p[n - 1] % 1000000007)

Submission status: Time Limit Exceeded

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

B = [0] * (N + 1)
B[0] = 1
if 1 not in A:
    B[1] = 1
else:
    B[1] = 0
mod = 10**9 + 7

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

Submission status: Time Limit Exceeded

Solution code:
mod = 1000000007
n, m = map(int, input().split())
dat_m = []
dp = []
for i in range(n + 1):
    dp.append([0] * (n + 1))
for i in range(m):
    dat_m.append(int(input()))
dp[0][0] = 1
#print(dp[0][0])
for i in range(1, n + 1):
    dp[i][:i-1] = dp[i-1][:i - 1]
    dp[i][i-1] = dp[i - 1][i - 1]
    dp[i][i] = dp[i - 1][i - 1]

    if i > 1:
        dp[i][i] += dp[i - 1][i - 2]

    if i in dat_m:
        dp[i][i] = 0

    dp[i][i] = dp[i][i] % mod

import pprint
print(dp[n][n])
#pprint.pprint(dp)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def solve():
	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
	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]

	print(dp[N]%1000000007)

solve()

Submission status: Time Limit Exceeded

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

for i in range(N+1):
    if i+1<=N and (i+1) not in A:
        table[i+1] += table[i]
    if i+2<=N and (i+2) not in A:
        table[i+2] += table[i]

print(table[N]%MOD)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
A = list(int(input()) for _ in range(M))
P = 10**9 + 7

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

Submission status: Time Limit Exceeded

Solution code:

from collections import defaultdict
import sys
sys.setrecursionlimit(100000)

N, M = map(int, input().rstrip().split(' '))

A = [0] * (N + 1)
for _ in range(M):
    A[int(input())] = 1

dp = defaultdict(lambda: -1)
def dfs(n):
    if n > N:
        return 0
    if A[n] == 1:
        return 0
    if n == N:
        return 1
    if dp[n] != -1:
        return dp[n]
        
    count = 0
    count += dfs(n + 1)
    count += dfs(n + 2)
    
    dp[n] = count
    
    return count
    
print(dfs(0) % (1000000007))