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, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)

#  f = open('C_input.txt')
#  lines = f.readlines()
#  f.close()
#  N, M = map(int, lines[0].split())
#  A = []
#  for line in lines[1:]:
#      A.append(int(line))
#  print(A)
N, M = LI()
A = []
for i in range(M):
    A.append(_I())

if M != 0:
    # 連続した壊れた段がある場合は0
    B = [i for i in A]
    B.remove(B[0])
    B.append(10**15+100)
    diffs = [b - a for a, b in zip(A,B)]
    #  print(diffs)

    if any(i == 1 for i in diffs):
        # 隣同士なので0
        print(0)
        exit()
"""
考え方
xにたどり着く通りは、x-1とx-2段目にたどり着く通りの合計
dp
3が障害のとき
1へは1通り
2へは0からと1からの2通り
3へは0通り
4へは2からの2通りと、3からの0通りで2通り
5へは3からの0通りと4からの2通りで2通り
6へは4からの2通りと5からの2通りで4通り
"""
dp = [None if i not in A else 0 for i in range(0, N+1)]
dp[0] = 1
dp[1] = 1 if 1 not in A else 0
for i in range(2, N+1):
    # i段目までの通りを計算する
    if dp[i] == 0:
        # i段目が障害のときは0になっているので飛ばす
        continue
    
    dp[i] = dp[i-1] + dp[i-2]

print(dp[-1] % mod)

Submission status: Time Limit Exceeded

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)

#  f = open('C_input.txt')
#  lines = f.readlines()
#  f.close()
#  N, M = map(int, lines[0].split())
#  A = []
#  for line in lines[1:]:
#      A.append(int(line))
#  print(A)
N, M = LI()
A = []
for i in range(M):
    A.append(_I())

"""
考え方
xにたどり着く通りは、x-1とx-2段目にたどり着く通りの合計
dp
3が障害のとき
1へは1通り
2へは0からと1からの2通り
3へは0通り
4へは2からの2通りと、3からの0通りで2通り
5へは3からの0通りと4からの2通りで2通り
6へは4からの2通りと5からの2通りで4通り
"""
dp = [None if i not in A else 0 for i in range(0, N+1)]
dp[0] = 1
dp[1] = 1 if 1 not in A else 0
for i in range(2, N+1):
    # i段目までの通りを計算する
    if dp[i] == 0:
        # i段目が障害のときは0になっているので飛ばす
        continue
    
    dp[i] = dp[i-1] + dp[i-2]

print(dp[-1] % mod)

Submission status: Time Limit Exceeded

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


dp = [0] * (N+1)

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

ans = dp[N]
print(ans)

Submission status: Time Limit Exceeded

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


dp = [0] * (N+1)

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

ans = dp[N]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)

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

mod = 10 ** 9 + 7
dp = [0 for _ in range(N+1)]
dp[0] = 1
for i in range(1, N+1):
    if i in inputs:
        continue
    if i == 1:
        dp[i] = dp[i-1]
    else:
        if i - 1 not in inputs:
            dp[i] += dp[i-1]
        if i - 2 not in inputs:
            dp[i] += dp[i-2]

print(dp[-1] % mod)

Submission status: Time Limit Exceeded

Solution code:
#A問題
N,M = map(int,input().split())
A = []
mod = 1000000007
for i in range(M):
    A.append(int(input()))

sta = []
for i in range(N+1):
    if i == 0:
        sta.append(1)
    elif i == 1:
        sta.append(1)
    elif i == 2:
        sta.append(2)
    else:
        sta.append(sta[i-1]+sta[i-2])

row = []
now = 1
flag = 0
for i in range(N):
    I = i+1
    if i == 0:
        if I in A:
            now = 0
            flag = 1
        else:
            now+=1
    else:
        if I in A:
            if flag == 1:
                flag = 2
                break
            else:
                row.append(now)
                now = 0
                flag = 1
        else:
            flag = 0
            now+=1

if flag == 2:
    print(0)
else:
    row.append(now)
    ans = 1
    for r in row:
        ans = (ans*sta[r-1])%mod
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
#A問題
N,M = map(int,input().split())
A = []
mod = 1000000007
for i in range(M):
    A.append(int(input()))

sta = []
for i in range(N+1):
    if i == 0:
        sta.append(1)
    elif i == 1:
        sta.append(1)
    elif i == 2:
        sta.append(2)
    else:
        sta.append(sta[i-1]+sta[i-2])

row = []
now = 1
flag = 0
for i in range(N):
    I = i+1
    if i == 0:
        if I in A:
            now = 0
            flag = 1
        else:
            now+=1
    else:
        if I in A:
            if flag == 1:
                flag = 2
                break
            else:
                row.append(now)
                now = 0
                flag = 1
        else:
            flag = 0
            now+=1

if flag == 2:
    print(0)
else:
    row.append(now)
    ans = 1
    for r in row:
        ans*=sta[r-1]
        ans%=mod
    print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
#A問題
N,M = map(int,input().split())
A = []
mod = 1000000007
for i in range(M):
    A.append(int(input()))

sta = []
for i in range(N+1):
    if i == 0:
        sta.append(1)
    elif i == 1:
        sta.append(1)
    elif i == 2:
        sta.append(2)
    else:
        sta.append(sta[i-1]+sta[i-2])

row = []
now = 1
flag = 0
for i in range(N):
    I = i+1
    if i == 0:
        if I in A:
            now = 0
            flag = 1
        else:
            now+=1
    else:
        if I in A:
            if flag == 1:
                flag = 2
                break
            else:
                row.append(now)
                now = 0
                flag = 1
        else:
            flag = 0
            now+=1

if flag == 2:
    print(0)
else:
    row.append(now)
    ans = 1
    for r in row:
        ans*=sta[r-1]
    print(ans%mod)

Submission status: Time Limit Exceeded

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

if n >= 3:
    if 1 not in a  and 2 not in a:
        c = [1,2]
    elif 1 in a and 2 not in a:
        c = [0,1]
    elif 1 not in a and 2 in a:
        c = [1,0]
    else:
        c = [0,0]

    one,two = map(int, c)

    for i in range(3,n+1):
        if i in a:
            temp = 0
            one = two
            two= temp
        else:
            temp = one+two
            one = two
            two = temp

    print(temp%mod)
    sys.exit()
elif n == 2:
    if 1 not in a  and 2 not in a:
        c = [1,2]
    elif 1 in a and 2 not in a:
        c = [0,1]
    elif 1 not in a and 2 in a:
        c = [1,0]
    else:
        c = [0,0]

    print(c[1])
    sys.exit()
elif n == 1:
    if 1 in a:
        print(0)
        sys.exit()
    else:
        print(1)
        sys.exit()

Submission status: Time Limit Exceeded

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

if n >= 3:
    if 1 not in a  and 2 not in a:
        c = [1,2]
    elif 1 in a and 2 not in a:
        c = [0,1]
    elif 1 not in a and 2 in a:
        c = [1,0]
    else:
        c = [0,0]

    for i in range(2,n):
        if i+1 in a:
            c.append(0)
        else:
            c.append((c[i-2] + c[i-1])%mod)

    print(c[len(c)-1])
    sys.exit()
elif n == 2:
    if 1 not in a  and 2 not in a:
        c = [1,2]
    elif 1 in a and 2 not in a:
        c = [0,1]
    elif 1 not in a and 2 in a:
        c = [1,0]
    else:
        c = [0,0]

    print(c[1])
    sys.exit()
elif n == 1:
    if 1 in a:
        print(0)
        sys.exit()
    else:
        print(1)
        sys.exit()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)

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

mod = 10 ** 9 + 7
def dfs(count):
    if count in inputs or count > N:
        return 0
    if count == N:
        return 1
    return dfs(count+1) + dfs(count+2)

print(dfs(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()))

r=[0]*(n+1)
r[0]=1

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

print(r[n])

Submission status: Time Limit Exceeded

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

r=[0]*(n+1)
r[0]=1

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

print(r[n]%1000000007)

Submission status: Time Limit Exceeded

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

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


dp[0] = 1
for i in range(N):
    if i+1 not in A:
        dp[i+1] += dp[i]
        dp[i] %= 1000000007
    if i+2 not in A:
        dp[i+2] += dp[i]
        dp[i] %= 1000000007

print(dp[N] % 1000000007)

Submission status: Time Limit Exceeded

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

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


dp[0] = 1
for i in range(N):
    if i+1 not in A:
        dp[i+1] += dp[i]
    if i+2 not in A:
        dp[i+2] += dp[i]
    dp[i] %= 1000000007

print(dp[N] % 1000000007)

Submission status: Time Limit Exceeded

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

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

dp[0] = 1
for i in range(N):
    if i in A:
        dp[i] = 0
        continue

    dp[i+1] += dp[i]
    dp[i+2] += dp[i]
    dp[i] %= 1000000007

print(dp[N] % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
a = [int(input()) for _ in range(m)]
mod = 10**9+7
dp1=0;dp2=1
for i in range(n):
	dp1,dp2=dp2,(dp1+dp2)*(not i+1 in a)
	if dp1==dp2==0:
		print(0);exit()
print(dp2%mod)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
bro = [int(input()) for i in range(M)]
mod = 10**9 + 7
dp = [0]*(N+1)
dp[0] = 1
if len(bro) >= 1 and bro[0] != 1:
    dp[1] = 1
elif len(bro) >= 1:
    del bro[0]
elif len(bro) == 0:
    dp[1] = 1
for i in range(2,N+1):
    if i in bro:
        continue
    else:
        dp[i]= (dp[i-1] + dp[i-2]) % mod
print(dp[-1] % mod)

Submission status: Time Limit Exceeded

Solution code:
import math
def main():
  n, m = map(int,input().split())
  if m != 0:
    BStep = [int(input()) for _ in range(m)]
    sumstep = culc(0,BStep[0]-1)
    for i in range(1,m):
      sumstep*=culc(BStep[i-1]+1,BStep[i]-1)
    sumstep*=culc(BStep[m-1]+1,n)
  else:
    sumstep=culc(0,n)
  print(sumstep%1000000007)

def culc(fromstep,tostep):
  up = tostep - fromstep
  if up==0:
    ans = 1
  elif up<0:
    ans = 0
  else:
    stepsum = 0
    tsmax = up//2
    for i in range(tsmax+1):
      one = up - 2*i
      stepsum += math.factorial(one + i)//(math.factorial(one)*math.factorial(i))
      # print(" ",stepsum)
    ans = stepsum
  # print(ans)
  return ans


main()

Submission status: Time Limit Exceeded

Solution code:
a, b = map(int, input().split())
c = [int(input())for _ in range(b)]
d = [0] * (a+1)
d[0] = 1 if 0 not in c else 0
d[1] = 1 if 1 not in c else 0
for i in range(2, a+1):
    if i not in c:
        d[i] = (d[i-1] + d[i-2]) % 1000000007
    else:
        d[i] = 0
print(d[len(d)-1])

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

memo = [0] * (N+1)
memo[0] = 1
cnt = 1
while cnt <= N:
  if cnt in broken:
    memo[cnt] = 0
  elif cnt == 1:
    memo[cnt] = 1
  else:
    memo[cnt] = (memo[cnt-1] + memo[cnt-2])%MOD
  cnt += 1
  
print(memo[N])

Submission status: Time Limit Exceeded

Solution code:
import math
import collections as c
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

n,m=map(int,input().split())
a = [-1]+[int(input()) for _ in range(m)]+[n+1]

def comb(dann):
    num_comb = 0
    for i in range((dann//2)+1):
        num_comb += combinations_count(dann-i, i)
    return num_comb

danns = c.Counter([(a[i+1] - a[i]) - 2 for i in range(len(a)-1)])

ans = 1
ddict = {}
for j in set(list(danns.keys())):
    ans *= comb(j) ** danns[j]
print(ans%1000000007)

Submission status: Time Limit Exceeded

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

n,m=map(int,input().split())
a = [-1]+[int(input()) for _ in range(m)]+[n+1]

def comb(dann):
    num_comb = 0
    for i in range((dann//2)+1):
        num_comb += combinations_count(dann-i, i)
    return num_comb

danns = [(a[i+1] - a[i]) - 2 for i in range(len(a)-1)]

ans = 1
for j in danns:
    ans *= comb(j)
print(ans%1000000007)

Submission status: Time Limit Exceeded

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

n,m=map(int,input().split())
a = [-1]+[int(input()) for _ in range(m)]+[n+1]

def comb(dann):
    num_comb = 0
    for i in range((dann//2)+1):
        num_comb += combinations_count(dann-i, i)
    return num_comb

danns = [(a[i+1] - a[i]) - 2 for i in range(len(a)-1)]

ans = 1
for j in danns:
    ans *= comb(j) % 1000000007
print(ans%1000000007)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
broken = []
for i in range(m):
    broken.append(int(input()))
    
num = [0] * (n + 1)
num[0] = int(0 not in broken)
num[1] = int(1 not in broken)

for i in range(2, n):
    if i in broken:
        num[i] = 0
    else:
        num[i] = (num[i-1] + num[i-2])%1000000007
        
if n <= 1:
    print(num[n])
else:
    print((num[n-1]+num[n-2])%1000000007)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
broken = []
for i in range(m):
    broken.append(int(input()))
num = {0: int(0 not in broken), 1: int(1 not in broken)}



for i in range(2, n):
    if i in broken:
        num[i] = 0
    else:
        num[i] = (num[i-1] + num[i-2])%1000000007
        
if n <= 1:
    print(num[n])
else:
    print((num[n-1]+num[n-2])%1000000007)

Submission status: Time Limit Exceeded

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

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

print(ans)

Submission status: Time Limit Exceeded

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

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

print(ans)

Submission status: Time Limit Exceeded

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

for i in range(N+1):
    if i in broken:
        continue
    elif i==0 or i==1:
        l[i] = 1
    else:
        l[i] = l[i-1] + l[i-2]
    l[i] %= MOD

print(l[N])

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
bad = [int(input()) for _ in range(m)]
back2 = 0
back1 = 1
MOD = int(1e9+7)

for i in range(n):
    if i + 1 in bad:
        back2, back1 = back1%MOD, 0
    else:
        back2, back1 = back1%MOD, (back2+back1)%MOD

print(back1)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
bad = [int(input()) for _ in range(m)]
back2 = 0
back1 = 1
MOD = int(1e9+7)

for i in range(n):
    if i + 1 in bad:
        back2, back1 = back1, 0
    else:
        back2, back1 = back1, back2+back1

print(back1%MOD)

Submission status: Time Limit Exceeded

Solution code:
import math

def routeCombCount(distance):
  comb_count = 1
  max_skippable_count = distance // 2

  if max_skippable_count == 0:
    return 1

  for skippable_count in range(1, max_skippable_count + 1):
    step_count = distance - skippable_count
    comb_count += combinations_count(step_count, skippable_count)

  return comb_count

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

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

count = 1
aim_stage = N
now_stage = 0
before_broken = -1
for i in range(M):
  broken = int(input())
  if broken == before_broken + 1:
    count = 0
    break

  aim_stage = broken - 1
  distance = aim_stage - now_stage

  count *= routeCombCount(distance)

  before_broken = broken
  now_stage = broken + 1

distance = N - now_stage
count *= routeCombCount(distance)

print(count % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
import re
import sys
from operator import mul
from functools import reduce


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


def Step(num):
    ans = 0
    for i in range(num//2 + 1):
        ans += cmb(num-i, i)
    return ans


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

if M > 0:
    step = ['1']*N
    for i in range(M-1):
        if a[i]+1 == a[i+1]:
            print(0)
            exit()
        else:
            step[a[i]-1] = step[a[i]] = '2'
    step[a[M-1]-1] = step[a[M-1]] = '2'
elif M == 0:
    print(Step(N) % 1000000007)
    exit()

one_one = list(map(len, re.findall(r'1+', ''.join(step))))
ans = 1
for i in one_one:
    ans *= Step(i)

print(ans % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(1000000)

def steps(n):
    if memo[n] != -1:
        return memo[n]
    if n-1 not in broken:
        one = memo[n-1] if memo[n-1] != -1 else steps(n-1)
    else:
        one = 0
        
    if n-2 not in broken:
        two = memo[n-2] if memo[n-2] != -1 else steps(n-2)
    else:
        two = 0
    
    memo[n] = one + two
    return memo[n]

n, m = map(int, input().split())
broken = [int(input()) for i in range(m)]
memo = [-1 for i in range(n+1)]
memo[0] = 1
memo[1] = 1

print(steps(n) % (10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import sys

def cul_1to2(i):
	global ppre_step
	global pre_step
	global now_step
	if i == 1:
		if i not in denger_list:
			ppre_step,pre_step,now_step = pre_step,0,1

		if i in denger_list:
			ppre_step,pre_step,now_step = pre_step ,0,0

	if i == 2:
		if i not in denger_list:
			if 1 in denger_list:
				ppre_step,pre_step,now_step = pre_step,now_step,1	
			else:
				ppre_step,pre_step,now_step = pre_step,now_step,2
		if i in denger_list:
			ppre_step,pre_step,now_step = pre_step ,now_step,0

	return ppre_step,pre_step,now_step


N,M = map(int,input().split())
step_list = list(range(N+1))
denger_list = list()
Int_pre =None
for i in range(M):
	if Int_pre != None:
		Int = int(input())
		if abs(Int - Int_pre) == 1:
			print(0)
			sys.exit()
		else:
			denger_list.append(Int)
			Int_pre = Int
	else:
		Int = int(input())
		denger_list.append(Int)
		Int_pre = Int

ppre_step = None
pre_step  = None
now_step  = 0

for i in range(N+1):
	if i == 0:
		continue
	if i <= 2:
		cul_1to2(i)
	else:
		if i not in denger_list:
			ppre_step = pre_step
			pre_step  = now_step
			now_step  = ppre_step + pre_step

		elif i in denger_list:
			ppre_step = pre_step
			pre_step  = now_step
			now_step  = 0 

print(now_step%1000000007)

Submission status: Time Limit Exceeded

Solution code:
import sys

def cul_1to2(i):
	global ppre_step
	global pre_step
	global now_step
	if i == 1:
		if i not in denger_list:
			ppre_step,pre_step,now_step = pre_step,0,1

		if i in denger_list:
			ppre_step,pre_step,now_step = pre_step ,0,0

	if i == 2:
		if i not in denger_list:
			if 1 in denger_list:
				ppre_step,pre_step,now_step = pre_step,now_step,1	
			else:
				ppre_step,pre_step,now_step = pre_step,now_step,2
		if i in denger_list:
			ppre_step,pre_step,now_step = pre_step ,now_step,0

	return ppre_step,pre_step,now_step


N,M = map(int,input().split())
step_list = list(range(N+1))
denger_list = list()
Int_pre =None
for i in range(M):
	if Int_pre != None:
		Int = int(input())
		if abs(Int - Int_pre) == 1:
			print(0)
			sys.exit()
		else:
			denger_list.append(Int)
			Int_pre = Int
	else:
		Int = int(input())
		denger_list.append(Int)
		Int_pre = Int

ppre_step = None
pre_step  = None
now_step  = 0

for i in range(N+1):
	if i == 0:
		continue

	if i <= 2:
		cul_1to2(i)
	
	else:

		if i not in denger_list:
			ppre_step = pre_step
			pre_step  = now_step
			now_step  = ppre_step + pre_step

		elif i in denger_list:
			ppre_step = pre_step
			pre_step  = now_step
			now_step  = 0 




print(now_step%1000000007)

Submission status: Time Limit Exceeded

Solution code:

def cul_1to2(i):
	global ppre_step
	global pre_step
	global now_step
	if i == 1:
		if i not in denger_list:
			ppre_step,pre_step,now_step = pre_step,0,1

		if i in denger_list:
			ppre_step,pre_step,now_step = pre_step ,0,0

	if i == 2:
		if i not in denger_list:
			if 1 in denger_list:
				ppre_step,pre_step,now_step = pre_step,now_step,1	
			else:
				ppre_step,pre_step,now_step = pre_step,now_step,2
		if i in denger_list:
			ppre_step,pre_step,now_step = pre_step ,now_step,0

	return ppre_step,pre_step,now_step


N,M = map(int,input().split())
step_list = list(range(N+1))
denger_list = list()
for i in range(M):
	denger_list.append(int(input()))


ppre_step = None
pre_step  = None
now_step  = 0

for i in range(N+1):
	if i == 0:
		continue

	if i <= 2:
		cul_1to2(i)
	
	else:
		#そのステップが危険でない場合、そこのステップ
		#への移動は、2つ前までの移動方法数の和となる
		if i not in denger_list:
			ppre_step = pre_step
			pre_step  = now_step
			now_step  = ppre_step + pre_step
		#そのステップが危険な場合、そこの値は
		#移動不可能なので0通りとなる
		elif i in denger_list:
			ppre_step = pre_step
			pre_step  = now_step
			now_step  = 0 
	# print('========')
	# print('i:',i)
	# print('ppre_step:',ppre_step)
	# print('pre_step:',pre_step)
	# print('now_step:',now_step)



print(now_step%1000000007)

Submission status: Time Limit Exceeded

Solution code:
import re
from operator import mul
from functools import reduce


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


def Step(num):
    ans = 0
    for i in range(num//2 + 1):
        ans += cmb(num-i, i)
    return ans


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

if M > 0:
    step = ['1' for _ in range(N)]
    for i in range(M-1):
        if a[i]+1 == a[i+1]:
            print(0)
            exit()
        else:
            step[a[i]-1] = step[a[i]] = '2'
    step[a[M-1]-1] = step[a[M-1]] = '2'
elif M == 0:
    print(Step(N) % 1000000007)
    exit()

one_one = list(map(len, re.findall(r'1+', ''.join(step))))
ans = 1
for i in one_one:
    ans *= Step(i)

print(ans % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
import re
from operator import mul
from functools import reduce


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


def Step(num):
    ans = 0
    for i in range(num//2 + 1):
        ans += cmb(num-i, i)
    return ans


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

if M > 0:
    step = ['1' for _ in range(a[0]-1)]
    for i in range(M-1):
        if a[i]+1 == a[i+1]:
            print(0)
            exit()
        else:
            step += (['2'] + ['1' for _ in range(a[i]+1, a[i+1]-1)])

    step += (['2'] + ['1' for _ in range(a[M-1]+1, N)])

elif M == 0:
    step = ['1' for _ in range(N)]

one_one = list(map(len, re.findall(r'1+', ''.join(step))))

ans = 1
for i in one_one:
    ans *= Step(i)

print(ans % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
x = [None] * N
for n in range(N):
  if n + 1 in a:
    x[n] = 0
    continue
  elif n == 0:
    x[n] = 1
    continue
  elif n == 1:
    x[n] = x[n - 1] + 1
    continue
  x[n] = x[n - 1] + x[n - 2]
  if x[n] == 0 and x[n - 1] == 0:
    print(0)
    exit()
print(x[-1] % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
step_list = list(range(N+1))
denger_list = list()
for i in range(M):
	denger_list.append(int(input()))


ppre_step = None
pre_step  = None
now_step  = 0

for i in range(N+1):
	if i == 0:
		continue
	if i == 1:
		if i not in denger_list:
			ppre_step,pre_step,now_step = pre_step,0,1

		if i in denger_list:
			ppre_step,pre_step,now_step = pre_step ,0,0

	if i == 2:
		if i not in denger_list:
			if 1 in denger_list:
				ppre_step,pre_step,now_step = pre_step,now_step,1	
			else:
				ppre_step,pre_step,now_step = pre_step,now_step,2
		if i in denger_list:
			ppre_step,pre_step,now_step = pre_step ,now_step,0

	else:
		#そのステップが危険でない場合、そこのステップ
		#への移動は、2つ前までの移動方法数の和となる
		if i not in denger_list:
			ppre_step = pre_step
			pre_step  = now_step
			now_step  = ppre_step + pre_step
		#そのステップが危険な場合、そこの値は
		#移動不可能なので0通りとなる
		elif i in denger_list:
			ppre_step = pre_step
			pre_step  = now_step
			now_step  = 0 
	# print('========')
	# print('i:',i)
	# print('ppre_step:',ppre_step)
	# print('pre_step:',pre_step)
	# print('now_step:',now_step)



print(now_step%1000000007)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
import sys

def input():
    return sys.stdin.readline().strip()

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

for i in range(1, N + 1):
    if i in a:
        continue
    else:
        li[i] = li[i - 1] + li[i - 2]
print(li[-1] % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
import sys

def input():
    return sys.stdin.readline().strip()

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

for i in range(1, N + 1):
    if i in a:
        li[i] = 0
    else:
        li[i] = li[i - 1] + li[i - 2]
print(li[-1] % (pow(10,9) + 7))

Submission status: Time Limit Exceeded

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


f = []

for i in range(n + 1):
    if i == 0:
        f.append(1)
        continue
    if i in a:
        f.append(0)
        continue
    if i == 1:
        f.append(1)
        continue
    f.append(f[i - 1] + f[i - 2])
    
print(f[n] % 1000000007)