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: Accepted

Solution code:
#!/usr/bin/env python3

import sys

P_NUM = 1000000007


def solv(n, m, a):
    no_hole = [1] * (n+1)
    for i in range(2, n+1):
        no_hole[i] = no_hole[i-1] + no_hole[i-2]

    ans = 1
    start = 0
    for broken in a:
        dist = broken-1-start
        if dist < 0:
            return 0
        ans *= no_hole[dist] % P_NUM
        start = broken+1

    dist = n-start
    if dist < 0:
        return 0
    ans *= no_hole[dist] % P_NUM

    return ans % P_NUM


if __name__ == '__main__':

    n, m = map(int, input().split())
    a = map(int, sys.stdin)

    ans = solv(n, m, a)

    print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

P_NUM = 1000000007


def solv(n, m, a):
    no_hole = [1] * (n+1)
    for i in range(2, n+1):
        no_hole[i] = no_hole[i-1] + no_hole[i-2]

    ans = 1
    start = 0
    for broken in a:
        dist = broken-1-start
        if dist < 0:
            return 0
        ans *= no_hole[dist] % P_NUM
        start = broken+1

    dist = n-start
    if dist < 0:
        return 0
    ans *= no_hole[dist] % P_NUM

    return ans % P_NUM


if __name__ == '__main__':

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

    ans = solv(n, m, a)

    print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

P_NUM = 1000000007


def solv(n, m, a):
    start = 0
    dists = []
    max_dist = 0
    for broken in a:
        dist = broken-1-start
        if dist < 0:
            return 0
        elif dist > max_dist:
            max_dist = dist
        dists.append(dist)
        start = broken+1
    dist = n-start
    if dist < 0:
        return 0
    elif dist > max_dist:
        max_dist = dist
    dists.append(dist)

    no_hole = [1] * (max_dist+1)
    for i in range(2, max_dist+1):
        no_hole[i] = no_hole[i-1] + no_hole[i-2]

    ans = 1
    for dist in dists:
        ans = (ans * no_hole[dist]) % P_NUM

    return ans


if __name__ == '__main__':

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

    ans = solv(n, m, a)

    print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys

P_NUM = 1000000007


def solv(n, m, a):
    comb_m2 = 1
    if 1 in a:
        comb_m1 = 0
    else:
        comb_m1 = 1

    for i in range(2, n+1):
        if i in a:
            comb_m1, comb_m2 = 0, comb_m1
        else:
            comb_m1, comb_m2 = (comb_m1 + comb_m2) % P_NUM, comb_m1

    return comb_m1


if __name__ == '__main__':

    n, m = map(int, input().split())
    if m:
        a = set(map(int, sys.stdin))
    else:
        a = set()

    ans = solv(n, m, a)

    print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys

P_NUM = 1000000007


def solv(n, m, a):
    comb_m2 = 1
    if 1 in a:
        comb_m1 = 0
    else:
        comb_m1 = 1

    comb = 1
    for i in range(2, n+1):
        if i in a:
            comb = 0
            a.remove(i)
        else:
            comb = (comb_m1 + comb_m2) % P_NUM

        comb_m1, comb_m2 = comb, comb_m1

    return comb


if __name__ == '__main__':

    n, m = map(int, input().split())
    if m:
        a = set(map(int, sys.stdin))
    else:
        a = set()

    ans = solv(n, m, a)

    print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys

P_NUM = 1000000007


def solv(n, m, a):
    comb_m2 = 1
    if 1 in a:
        comb_m1 = 0
    else:
        comb_m1 = 1

    comb = 1
    for i in range(2, n+1):
        if i in a:
            comb = 0
        else:
            comb = (comb_m1 + comb_m2) % P_NUM

        comb_m1, comb_m2 = comb, comb_m1

    return comb


if __name__ == '__main__':

    n, m = map(int, input().split())
    if m:
        a = set(map(int, sys.stdin))
    else:
        a = set()

    ans = solv(n, m, a)

    print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys

P_NUM = 1000000007


def solv(n, m, a):
    comb =  [1] * (n+1)
    for i in a:
        comb[i] = 0

    for i in range(2, n+1):
        comb[i] *= (comb[i-1] + comb[i-2]) % P_NUM

    return comb[-1]


if __name__ == '__main__':

    n, m = map(int, input().split())
    if m:
        a = map(int, sys.stdin)
    else:
        a = []

    ans = solv(n, m, a)

    print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import array


P_NUM = 1000000007


def solv(n, m, a):
    comb = array.array('I', [1] * (n+1))
    for i in a:
        comb[i] = 0

    for i in range(2, n+1):
        comb[i] *= (comb[i-1] + comb[i-2]) % P_NUM

    return comb[-1]


if __name__ == '__main__':

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

    ans = solv(n, m, a)

    print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import array


P_NUM = 1000000007


def solv(n, m, a):
    comb = array.array('I', [1] * (n+1))
    for i in a:
        comb[i] = 0

    for i in range(2, n+1):
        if comb[i] != 0:
            comb[i] = (comb[i-1] + comb[i-2]) % P_NUM

    return comb[-1]


if __name__ == '__main__':

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

    ans = solv(n, m, a)

    print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

P_NUM = 1000000007


def solv(n, m, a):
    comb = [1] * (n+1)
    for i in a:
        comb[i] = 0

    for i in range(2, n+1):
        if comb[i] != 0:
            comb[i] = (comb[i-1] + comb[i-2]) % P_NUM

    return comb[-1]


if __name__ == '__main__':

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

    ans = solv(n, m, a)

    print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

P_NUM = 1000000007


def solv(n, m, a):
    comb = [1] * (n+1)
    for i in a:
        comb[i] = 0

    for i in range(2, n+1):
        if comb[i] != 0:
            comb[i] = comb[i-1] + comb[i-2]

    return comb[-1]


if __name__ == '__main__':

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

    ans = solv(n, m, a)

    print(ans % P_NUM)

Submission status: Accepted

Solution code:
n, m = map(int,input().split())
a = set()
for i in range(m):
    a.add(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: Accepted

Solution code:
n, m = map(int,input().split())
p = [0 for i in range(n+1)]
a = [0 for i in range(n+1)]
for i in range(m):
    a[int(input())] = 1
for i in range(1,n+1):
    if a[i] == 1:
        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: Accepted

Solution code:
N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
B = [0 for _ in range(N+1)]
for a in A:
  B[a] = 1
mod = 10**9 + 7
dp = [-1 for _ in range(N+1)]
dp[0] = 1
dp[1] = 1
for i in range(2, N+1):
  if B[i-2] == 0 and B[i-1] == 1:
    dp[i] = dp[i-2]
  elif B[i-2] == 1 and B[i-1] == 0:
    dp[i] = dp[i-1]
  elif B[i-2] == 0 and B[i-1] == 0:
    dp[i] = dp[i-1] + dp[i-2]
  else:
    dp[i] = 0
  dp[i] %= mod
 
print(dp[-1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import math
from functools import lru_cache


def ncr(n, r):
    r = min(r, n - r)
    # 桁が小さいときは直接 math.factorial を使ったほうが早い
    if n + r < 4000:
        return math.factorial(n) // math.factorial(n-r) // math.factorial(r)
    if r == 0:
        return 1
    if r == 1:
        return n
    numerator = list(range(n - r + 1, n + 1))
    denominator = list(range(1, r+1))
    for p in range(2, r + 1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p - 1, r, p):
                numerator[k - offset] //= pivot
                denominator[k] //= pivot
    result = 1
    for k in range(r):
        result *= numerator[k]
    return result


# 穴なしで n step 離れている場合の組み合わせ
def no_hole(n):
    count = 0
    m = n // 2
    for i in range(0, m+1):
        count += ncr(n-i, i)
    return count


# 穴なしで n step 離れている場合の組み合わせ(高速化版)
@lru_cache(maxsize=8192)
def no_hole2(n):
    if n <= 5:
        return (1, 1, 2, 3, 5, 8)[n]
    if n % 2:
        h = (n-1) // 2
        m1 = no_hole2(h-1)
        m0 = no_hole2(h)
        return 2 * m1 * m0 + m0 * m0
    else:
        h = n // 2
        m2 = no_hole2(h-2)
        m1 = no_hole2(h-1)
        m0 = no_hole2(h)
        return m1 * m1 + m2 * m0 + m1 * m0


def solv(n, m, a):
    ans = 1
    current_pos = 0
    for pos in a:
        dist = pos - 1 - current_pos
        if dist < 0:
            return 0
        ans *= no_hole2(dist)
        current_pos = pos + 1
    dist = n - current_pos
    ans *= no_hole2(dist)
    return ans


if __name__ == '__main__':

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

    ans = solv(n, m, a)

    P_NUM = 1000000007
    print(ans % P_NUM)

Submission status: Accepted

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

a=[True]*(n+1)
for i in range(m):
    a[int(input())]=False

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

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

print(r[n])

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
# print(n,m)
dparr=[[0,False] for i in range(n+1)]
b=[0 for i in range (n+1)]
adash=[0 for i in range(n+1)]
i=0
while(i<m):
	k=int(input())
	adash[k]=1
	i+=1
s=0
i=n
while(i>=0):
	if(adash[i]==1):
		b[i]=0
	else:
		if(i==n):
			b[i]=1
		elif(i==n-1):
			b[i]=1
		else:
			b[i]=(b[i+1]+b[i+2])%1000000007

	i-=1
print(b[0])

Submission status: Accepted

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

for i in range(M - 1):
    if A[i] + 1 == A[i + 1]:
        print(0)
        exit()

MAX_N = int(1e5) + 10
memo = [0 for i in range(MAX_N + 10)]
memo[0] = 1
memo[1] = 1
memo[2] = 2
for i in range(3, MAX_N + 10):
    memo[i] = memo[i - 1] + memo[i - 2]

now = 0
ans = 1

for a in A:
    diff = a - now - 1
    ans *= memo[diff]
    ans %= int(1e9 + 7)
    now = a + 1

diff = N - now
ans *= memo[diff]
ans %= int(1e9 + 7)
print(ans)

Submission status: Accepted

Solution code:
import sys
N,M = map(int,input().split(' '))
A = set([int(sys.stdin.readline()) for _ in range(M)])
dp = [0]*(N+1)
dp[0] = 1
dp[1] = 0 if 1 in A else 1

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

Submission status: Accepted

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

dp = [0] * (n+1)
broken = [0] * (n+1)

for i in range(m):
    broken[int(input())] = 1

dp[0] = 1

if broken[1] == 1:
    dp[1] = 0
else:
    dp[1] = 1

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

Submission status: Accepted

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

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

def check(n):
    i = bisect.bisect_left(A, n)
    if i != M and A[i] == n:
        return False
    else:
        return True

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

print(dp[N] % 1000000007)

Submission status: Accepted

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

broken = [0] * (n+1)
dp = [0] * (n+1)

for _ in range(m):
  broken[int(input())] = 1
  if broken[-1] == 1 and broken[-2] == 1:
    print(0)
    exit()

dp[0] = 1

if broken[1] == 1:
  dp[1] = 0
else:
  dp[1] = 1

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

print(dp[n])

Submission status: Accepted

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

broken = [0] * (n+1)
dp = [0] * (n+1)

for _ in range(m):
  broken[int(input())] = 1
  if sum(broken[-2:]) == 2:
    print(0)
    exit()

dp[0] = 1

if broken[1] == 1:
  dp[1] = 0
else:
  dp[1] = 1

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

print(dp[n])

Submission status: Accepted

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

broken = [0] * (n+1)
dp = [0] * (n+1)

for _ in range(m):
  broken[int(input())] = 1

dp[0] = 1

if broken[1] == 1:
  dp[1] = 0
else:
  dp[1] = 1

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

print(dp[n])

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
ali = [int(input()) for _ in range(m)]
mod=10**9+7;dif = [];cap = 0
for num in ali:
  dif.append(num-cap)
  cap = num
dif.append(n-cap+1)
dif[0] += 1
ref = [0,0,1,1]
a,b = 1,1
for i in range(100000):
  a,b = b,a+b 
  ref.append(b)
ans = 1
for num in dif:
  ans *= (ref[num] % mod)
print(ans % mod)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = [True] * (N+1)
for _ in range(M):
  idx = int(input())
  A[idx] = False

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

Submission status: Accepted

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

af = [0]*(n+1)
for ai in a:
  af[ai]+=1

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

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

print(dp[-1]%1000000007)

Submission status: Accepted

Solution code:
def C_TypicalStairs():
    N, M = map(int, input().split())
    am = [int(input()) for i in range(M)]
    can_move = True
    num_move = 0
    if(M == 0):
        num_move = fib(N+1)
    else:
        # 到達不可を除く
        for i in range(M-1):
            if ((am[i] + 1) == am[i+1]):
                can_move = False
        if (can_move):
            num_move = fib(am[0])
            if (M <= 1):
                pass
            else:
                for i in range(M-1):
                    num_move *= fib(am[i+1] - am[i] - 1)
            num_move *= fib(N - am[M-1])
    print(num_move % 1000000007)

def fib(n):
    if (n <= 1):
        a0 = n
    else:
        a0, a1 = 0, 1
        for _ in range(n):
            a0, a1 = a1, a0 + a1
    return a0
if __name__ == "__main__":
    C_TypicalStairs()

Submission status: Accepted

Solution code:
def C_TypicalStairs():
    N, M = map(int, input().split())
    am = [int(input()) for i in range(M)]
    n_list = [i for i in range(N+1)]
    can_move = True
    num_move = 0
    if(M == 0):
        num_move = fib(len(n_list))
    else:
        # 到達不可を除く
        for i in range(M-1):
            if ((am[i] + 1) == am[i+1]):
                can_move = False
        if (can_move):
            num_move = fib(len(n_list[:am[0]]))
            if (M <= 1):
                pass
            else:
                for i in range(M-1):
                    num_move *= fib(len(n_list[am[i]+1:am[i+1]]))
            num_move *= fib(len(n_list[am[M-1]+1:]))
    print(num_move % 1000000007)

def fib(n):
    if (n <= 1):
        a0 = n
    else:
        a0, a1 = 0, 1
        for _ in range(n):
            a0, a1 = a1, a0 + a1
    return a0
if __name__ == "__main__":
    C_TypicalStairs()

Submission status: Accepted

Solution code:
#coding:utf-8
#DPの練習

n, m = map(int, input().split())

#壊れている階段とそうでない階段を判別するリスト
broken = [0] * (n+1)

#段ごとに何通りかを集計するためのリスト
dp = [0] * (n+1)
#0段目は必ず1通りしかない
dp[0] = 1


#壊れている階段をマークする
for i in range(m):
    broken[int(input())] = 1

#1段目から壊れている可能性があるので場合分け
if broken[1] == 1:
    dp[1] = 0
else:
    #1段目が無事な場合は1通り
    dp[1] = 1

#2段目以降
for i in range(2, n+1):
    if broken[i] == 1:
        #壊れていた場合次の段を確認する
        continue
    dp[i] = dp[i-1] + dp[i-2]
    dp[i] = dp[i] % 1000000007

print(dp[n])

Submission status: Accepted

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

for i in range(2,N+1):
	if step[i] == 0:
		continue
	step[i] = (step[i-1] + step[i-2])%(10**9+7)

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

Submission status: Accepted

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

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

Submission status: Accepted

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

b = [0] * (n+1)

for i in a:
    b[i] = 1

dp = [0] * (n+1)

dp[0] = 1

if b[1] == 1:
    dp[1] = 0
else:
    dp[1] = 1

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

print(dp[n] % 1000000007)

Submission status: Accepted

Solution code:
def main():
    N, M = list(map(int, input().split()))
    A = set()
    for i in range(M):
        A.add(int(input()))

    mod = 1000000007

    dp = [0] * (N+1)
    dp[0] = 1
    for now in range(0, N):
        for next in range(now+1, min(N, now+2)+1):
            if next not in A:
                dp[next] += dp[now]
                dp[next] %= mod

    print(dp[N] % mod)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
a = set([int(input()) for _ in range(M)])
mod =  1000000007
ret = [0] * (N+1)
ret[0] = 1
for i in range(1,N+1):
    if i in a:
        continue
    elif i == 1:
        ret[1] = 1
    else:
        ret[i] = ret[i-2] + ret[i-1]

print(ret[len(ret)-1]%mod)

Submission status: Accepted

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 len(bro) == 0:
        dp[i]= (dp[i-1] + dp[i-2]) % mod
    elif bro[0] == i:
        del bro[0]
        continue
    else:
        dp[i]= (dp[i-1] + dp[i-2]) % mod
print(dp[-1] % mod)

Submission status: Accepted

Solution code:
a, b = map(int, input().split())
d = [0] * (a+1)

for i in range(b):
    d[int(input())] = -1
d[0] = 1 if d[0] != -1 else 0
d[1] = 1 if d[1] != -1 else 0
for i in range(2, a+1):
    if d[i] != -1:
        d[i] = (d[i-1] + d[i-2]) % 1000000007
    else:
        d[i] = 0
print(d[len(d)-1])

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
am = [int(input()) for i in range(M)]
safe = [True]*(N+1)
for i in am:
    safe[i] = False
dp = [0]*(N+1)
dp[0]=1
for i in range(N):
    if safe[i+1]:
        dp[i+1] += dp[i]
    if i+2<=N:
        if safe[i+2]:
            dp[i+2] += dp[i]
print(dp[N]%(10**9+7))

Submission status: Accepted

Solution code:
def fibonacci(n):
	if n==0:
		return 0
	a,b=1,1
	for i in range(0,int((n-1)/2)):
		a+=b
		b+=a
	if n%2!=0:
		return a
	return b

n=[int(i) for i in input().split()]
f=1
a=-1
for i in range(0,n[1]):
	b=int(input())
	f*=fibonacci(b-a-1)
	a=b
f*=fibonacci(n[0]-a)
print(f%1000000007)

Submission status: Accepted

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

# 壊れている床
a = [-1]
for i in range(M):
  a.append(int(input()))
  # 連続して壊れていたら辿り着けない
  if a[i + 1] - a[i] == 1:
    print(0)
    exit()

# フィボナッチ数列
def fib(n):
  a, b = 0, 1
  if n == 1:
    return a
  elif n == 2:
    return b
  else:
    for i in range(n-2):
      a, b = b, a + b
    return b

# 階段を登る組み合わせ
combi = 1

for i in range(len(a) - 1):
  # 次の穴との距離
  dis = a[i+1] - a[i]
  #print(dis)
  combi *= fib(dis)
  #print(a[i])
    
dis = N+1 - a[-1]
#print(dis)
combi *= fib(dis)
 
print(combi % 1000000007)

Submission status: Accepted

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

a.append(n+1)
mod=1000000007

b=[0]*(n+1)
b[0]=1
if a[0]==1:
    b[1]=0
    count=1
else:
    b[1]=1
    count=0

if n==1:
    if m==0:
        print("1")
    else:
        print("0")
else:
    for i in range(2,n+1):
        if i==a[count]:
            b[i]=0
            count += 1
        else:
            b[i]=b[i-1]+b[i-2]
    print(int(b[n]%mod))

Submission status: Accepted

Solution code:
# 再帰上限あげとく
import sys
sys.setrecursionlimit(10**6)

# 値入力
mod = 7+10**9
N,M = map(int, input().split())
a = [0]*M
for i in range(M):
    a[i] = int(input())

# メモ化フィボナッチ
# 参考:http://python-remrin.hatenadiary.jp/entry/2017/05/19/153228
memo = [0]*(N+2)
def fibonacci(n):
    if n < 3:
        return 1
    if memo[n] < 1:
        memo[n] = fibonacci(n-1) + fibonacci(n-2)
    return memo[n]

now = 0 # 今いる場所と考える
count = 1
for i in a:
    count *= fibonacci(i-now)
    count = count%mod
    if now == i:
        print(0)
        quit()
    now = i+1 # 穴を超えた次の段に移動する

# 最上段までを計算
count *= fibonacci(N-now+1)
print(count%mod)

Submission status: Accepted

Solution code:
# 再帰上限あげとく
import sys
sys.setrecursionlimit(10**6)

# 値入力
mod = 7+10**9
N,M = map(int, input().split())
a = [0]*M
for i in range(M):
    a[i] = int(input())

# メモ化フィボナッチ
# 参考:http://python-remrin.hatenadiary.jp/entry/2017/05/19/153228
fib_memo = {}
def fib(n):
    if n < 3: return 1
    if n not in fib_memo:
        fib_memo[n] = fib(n-1) + fib(n-2)
    return fib_memo[n]

now = 0 # 今いる場所と考える
count = 1
for i in a:
    count *= fib(i-now)
    count = count%mod
    if now == i:
        print(0)
        quit()
    now = i+1 # 穴を超えた次の段に移動する

# 最上段までを計算
count *= fib(N-now+1)
print(count%mod)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-

def solve():
    MOD = 1000000007
    N, M = list(map(int, input().split()))
    dp = [0 for i in range(0, N+1)]
    A = set()
    for i in range(M):
        A.add(int(input()))
    
    dp[0] = 1
    dp[1] = 0 if 1 in A else 1

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


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
# def LIST(): return list(map(str, input().split()))
# def LIST(): return list(input())

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
A = [INT() for _ in range(M)]

b = [0] * (N + 2)
# 壊れているところが1
for i in A:
    b[i] = 1

dp = [0] * (N + 2)
# for i in range():

dp[0] = 1

if b[1] == 1:
    # あなあいてるのでそのルートは考えられない
    dp[1] = 0
else:
    dp[1] = 1

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

ans = dp[N] % mod
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque, defaultdict
import copy
import bisect
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 9)

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

num = [0 for i in range(N)]
for i in range(M):
    num[a[i] - 1] = 1000000008
if num[0] == 0:
    num[0] = 1
if len(num) >= 2 and num[1] == 0:
    num[1] = 1 + min(1000000007, num[0])
    num[1] = num[1] % 1000000007
for i in range(2, N):
    if num[i] < 1000000008:
        num[i] = min(1000000007, num[i - 1]) + min(1000000007, num[i - 2])
        num[i] = num[i] % 1000000007
print(num[N - 1])

Submission status: Accepted

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

memo = [1]
cnt = 1
while cnt <= N:
  if len(broken) > 0 and cnt == broken[0]:
    del broken[0]
    memo.append(0)
  elif cnt == 1:
    memo.append(1)
  else:
    memo.append((memo[-1] + memo[-2])%MOD)
  cnt += 1
  
print(memo[-1])

Submission status: Accepted

Solution code:
import sys

N, M = map(int, input().split())
set_a = set([int(sys.stdin.readline()) for _ in range(M)])
MOD = 10**9 + 7

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

Submission status: Accepted

Solution code:
import sys

N, M = map(int, input().split())
# set_a = set([int(input()) for _ in range(M)])
if M > 0:
    set_a = set(map(int, sys.stdin))
else:
    set_a = set()
MOD = 10**9 + 7

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

Submission status: Accepted

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


for i in broken:
    num[i] = 0

for i in range(2, n):
    if num[i] == -1:
        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: Accepted

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

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

print(ans)

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

Solution code:
import logging
from math import factorial

logging.basicConfig(level=logging.INFO, format="%(message)s")
#logging.disable(logging.CRITICAL)

steps_memo =[0 for _ in range(150000)]
def cal_steps(num):
    steps_memo[0] = 1
    steps_memo[1] = 1

    for i in range(2, num):
        steps_memo[i] = steps_memo[i - 1] + steps_memo[i - 2]

    return steps_memo[num - 1]
    
def main():
    N, M = (int(x) for x in input().split())
    a_s = [int(input()) for _ in range(M)]

    logging.info(a_s)
    
    a_s.append(N + 1)
    a_s.insert(0, -1)
    diff_a = [a_s[i + 1] - a_s[i] - 1 for i in range(M + 1)]

    if diff_a[0] == 0:
        diff_a[0] = 1
    
    logging.info(diff_a)

    
    answer = 1
    for i in diff_a:
        answer *= int(cal_steps(i))

    print(answer % (10 ** 9 + 7))
        

if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n, m = (int(i) for i in input().split())
broken = [False]*(n+1)

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

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

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
MOD = 1000000007
a = [int(input()) for _ in range(M)]
dp_list = [-1] * (N+1)

#brokenのところを0に
for i in range(M):
  dp_list[a[i]] = 0

#最後の段の確定
if dp_list[N] != 0:
  dp_list[N] = 1
  
#最後の段の一段前の値を確定
if dp_list[N-1] != 0:
  dp_list[N-1] = 1

#漸化式で求める
for i in range(N-2,-1,-1):
  if dp_list[i] == 0:
    continue
  dp_list[i] = dp_list[i+1] + dp_list[i+2]

print(dp_list[0]%MOD)

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7

n, m = map(int, input().split())
a = tuple(int(input()) for _ in range(m))
b = [False] * (n + 1)
for aa in a:
    b[aa] = True

dp = [0] * (n + 5)
dp[0] = 1

for i in range(n):
    if not b[i]:
        dp[i + 1] += dp[i]
        dp[i + 1] %= mod
        dp[i + 2] += dp[i]
        dp[i + 2] %= mod
print(dp[n])

Submission status: Accepted

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

for i in range(N+1):
    if l[i] == "empty":
        l[i] = (l[i-1] + l[i-2]) % MOD

print(l[N])