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:


N, M = map(int, input().split())
a=[]
step=[0]*200000
total=1
count=0
num=0

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

for x in range(M):
    num=a[x]-a[x-1]
    if(num==1):
        print(0)
        exit(0)
    else:
        num=0

step[0]=1
for k in range(1,N+1):
    if M!=0:
        if k==a[count]:
            step[k]=0
            if count<M-1:
                    count +=1
        else:
            if k>0:
                step[k]+=step[k-1]
            if k>1:
                step[k]+=step[k-2]
    else:
        if k > 0:
            step[k] += step[k - 1]
        if k > 1:
            step[k] += step[k - 2]



print(step[N]%1000000007)

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
Num =  1000000007 
n,m = map(int,input().split())
a = [False] * (n+1)
for i in range(m):
    tmp = int(input())
    a[tmp] = True
dp = [1 for i in range(n+1)]
dp[0] = 1
if a[1]:
    dp[1] = 0

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

    else:
        dp[i] = dp[i-1] + dp[i-2]
print(dp[-1]%Num)

Submission status: Accepted

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

Submission status: Accepted

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

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

for _ in range(M):
    a = int(input())
    flag[a] = 1


dp[0] = 1
if flag[1] == 1:
    dp[1] = 0
else:
    dp[1] = 1;

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

print(dp[N])

Submission status: Accepted

Solution code:
#配列内の全ての数値の積を求める際に必要
from operator import mul
from functools import reduce

# リスト内包表記で入力を変数やリストに代入
n, m = [int(i) for i in input().split()]
arr = [int(input()) for i in range(m)]

#始点（0）と終点（n）をarrに追加するが、壊れた床間の差分をとる際にずれるので、視点は-1,終点は+1しておく
arr.append(n+1)
arr.insert(0, -1)
#壊れた床同士の差分をとる
div_arr = [arr[i+1]-arr[i]-1 for i in range(len(arr)-1)]


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

print(reduce(mul, [Fib(i+1) for i in div_arr])%1000000007)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
from operator import mul
from functools import reduce

n, m = [int(i) for i in input().split()]
arr = [int(input()) for i in range(m)]
arr.append(n+1)
arr.insert(0, -1)
div_arr = [arr[i+1]-arr[i]-1 for i in range(len(arr)-1)]


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

if 0 in div_arr:
  print(0)
else:
  print(reduce(mul, [Fib(i+1) for i in div_arr])%1000000007)

Submission status: Accepted

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

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

import math
import sys
import itertools
import queue

mod = 1000000007

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

    broken = [False for _ in range(N + 2)]
    for _ in range(M):
        broken[int(sys.stdin.readline())] = True

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

Submission status: Accepted

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

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

import math
import sys
import itertools
import queue

mod = 1000000007

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

    broken = [False for _ in range(N + 2)]
    for _ in range(M):
        broken[int(sys.stdin.readline())] = True

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

Submission status: Accepted

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

for i in range(M):
  d[a[i]] = 1

t[0]=t[1]=1
if M>0:
  t[1] = 0 if (a[0]==1) else 1

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

Submission status: Accepted

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

Submission status: Accepted

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

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

for i in range(1, N):
    if stairs[i+1] != 0:
        stairs[i+1] = stairs[i] + stairs[i-1]
print(stairs[N] % max_num)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
a = [int(input()) for i in range(M)]
Mod = 1000000007
dp = [1]*(N+1) #dp[i]...i番目にいる時の移動方法の数

count = 0
for i in a:
    if i+1 in a:
        print(0)
        exit()

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

print(dp[N])

Submission status: Accepted

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

now = 0
if 1 in a:
    prev1 = 0
else:
    now = 1
    prev1 = 1
prev2 = 1

for i in range(2,N+1):
    if i in a:
        now = 0
        prev2 = prev1
        prev1 = now 
    else:
        now = prev1 +prev2
        prev2 = prev1
        prev1 = now

print(now%Num)

Submission status: Accepted

Solution code:
mod = 10**9+7
n, m = map(int, input().split())
a = [0]*m
oks = [True]*(n+1)
for i in range(m):
    a = int(input())
    oks[a] = False
dp = [0]*(n+1)
dp[0] = 1
for now in range(n):
    for nex in range(now+1, min(n, now+2)+1):
        if oks[nex]:
            dp[nex] += dp[now]
            dp[nex] %= mod
print(dp[n])

Submission status: Accepted

Solution code:
#!/usr/bin/env python
import bisect
from collections import defaultdict

def main():
    N, M = map(int, input().split())
    As = set([int(input()) for i in range(M)])
    BIG_NUM = 1000000007

    current_step = 0
    prev_prev_step = 1
    if 1 in As:
        prev_step = 0
    else:
        prev_step = 1
        current_step = 1

    for i in range(2, N+1):
        if i in As:
            current_step = 0
        else:
            current_step = (prev_step + prev_prev_step) % BIG_NUM
        prev_prev_step = prev_step
        prev_step = current_step

    print(current_step)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, m = [int(x) for x in input().split()]
bad = [False for i in range(n + 1)]
for i in range(m):
  bad[int(input())] = True
mod = 10 ** 9 + 7
dp = [0 for i in range(n + 1)]
dp[0] = 1
for i in range(1, n + 1):
  if bad[i]: 
    continue
  x1 = dp[i - 1] if (i > 0) and not bad[i - 1] else 0
  x2 = dp[i - 2] if (i > 1) and not bad[i - 2] else 0
  dp[i] = x1 + x2
  if dp[i] >= mod:
    dp[i] -= mod
print(dp[n])

Submission status: Accepted

Solution code:
#coding:utf-8
#dp[i]:i段目に登るまでの組み合わせ総数
#dp[i] = dp[i-1] + dp[i-2] if dp[i] != B[i] else 0
N,M = list(map(int,input().split()))
B = [True] * N

for _ in range(M):
    B[int(input())-1] = False
dp = [0] * N
if B[0]:
    dp[0] = 1
if N >= 2 and B[1]:
    dp[1] = dp[0] + 1 
mod = 10**9 + 7
for i in range(2,N):
    if B[i] :
        dp[i] = dp[i-1] + dp[i-2]
        dp[i] %= mod
print(dp[-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from math import floor  
stairs_num, broken_num = tuple(int(i) for i in input().split(" "))
broken_list = []
for i in range(broken_num):
    broken_list.append(int(input()))
trance_num_list = []
if len(broken_list) >= 1 and broken_list[0] == 1:
    trance_num_list.append(0)
else:
    trance_num_list.append(1)
if (len(broken_list) >= 1 and broken_list[0] == 2) or \
 (len(broken_list) >= 2 and broken_list[1] == 2):
    trance_num_list.append(0)
else:
    if trance_num_list[0] == 0:
        trance_num_list.append(1)
    else:
        trance_num_list.append(2)
if stairs_num > 2:
    a = len(broken_list)
    for i in range(stairs_num - 2):
        key = 0
        left = 0
        right = a
        while left < right:
            midle = floor((left + right) / 2)
            if broken_list[midle] < i + 3:
                left = midle + 1
            elif broken_list[midle] == i + 3:
                key = 1
                break
            else:
                right = midle
        if key:
            trance_num_list.append(0)
        else:
            trance_num_list.\
             append((trance_num_list[-1] + trance_num_list[-2]) % 1000000007)
print(trance_num_list[stairs_num - 1])

Submission status: Accepted

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

Submission status: Accepted

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

n,m = list(map(int,input().split()))
a = [int(input()) for _ in range(m)]
dp = [0]*(n+1)
flg = [True]*(n+1)
mod = 1000000007
for i in a:
    flg[i] = False
dp[0] = 1
for i in range(1,n+1):
    if flg[i]:
        if i == 1:
            dp[i] += dp[i - 1]
        else:
            dp[i] += dp[i - 2] + dp[i - 1]

    dp[i] %= mod
print(dp[n])

Submission status: Accepted

Solution code:
n, m = list(map(int, input().split()))
a = [input() for i in range(m)]
b = []
c = []
total_act = 0
total_act2 = 1
total = 1
if m == 0:
    for i in range(n + 1):
        if str(i) in a:
            total *= total_act
            total_act = 0
            total_act2 = 1
        else:
            total_act3 = total_act2 + total_act
            total_act2 = total_act
            total_act = total_act3
    total *= total_act
    print(total % 1000000007)
else:
    b.append(int(a[0]))
    for i in range(len(a) - 1):
        b.append(int(a[i + 1]) - int(a[i]) - 1)
        if int(a[i + 1]) - int(a[i]) - 1 == 0:
            print(0)
            exit()
    b.append(n - int(a[-1]))

    for i in range(max(b)):
        total_act3 = total_act2 + total_act
        total_act2 = total_act
        total_act = total_act3
        c.append(total_act)

    for i in b:
        total *= c[i - 1]
    print(total % 1000000007)

Submission status: Accepted

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

counts = [1,1]+[0 for _ in range(10**6)]

for i in range(M):
    counts[L[i]-1] = -1

MOD = 10**9 + 7
for i in range(10**5+1):
    if counts[i] == -1:
        continue
    if counts[i+1] != -1:
        counts[i+1] += counts[i]
        counts[i+1] %= MOD
    if counts[i+2] != -1:
        counts[i+2] += counts[i]
        counts[i+2] %= MOD
print(counts[N-1]%MOD)

Submission status: Accepted

Solution code:
step = [int(i) for i in input().split()]
breaked_step = [int(input()) for i in range(step[1])]
dp = [1] * (step[0] + 1)
ans = 0
ans_ptn = 0
par = 1000000007

"""for i in range(len(breaked_step) - 1):
    if breaked_step[i + 1] - breaked_step[i] == 1:
        ans = 0
    else:
        ptn = breaked_step[i + 1] - breaked_step[i]
        ans_ptn += ptn * 2
        print("breaked_step[i + 1] - breaked_step[i]:{} - {}".format(breaked_step[i+1], breaked_step[i]))
        print("ans_ptn:{}".format(ans_ptn))

ans = ans_ptn % par"""
for i in breaked_step:
    dp[i] = 0

for j in range(1, step[0]):
    #print("dp[{}]:{}".format(j+1, dp[j+1]))
    if dp[j + 1] != 0:
        dp[j + 1] = (dp[j] + dp[j - 1]) % par
        #print("dp[{}] - dp[{}] = {}".format(j, j - 1, dp[j] - dp[j-1]))

print(dp[step[0]])

Submission status: Accepted

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

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


for i in range(2, n+1):
    if i != a[x]:
        dp.append((dp[-1] + dp[-2]) % 1000000007)
    else:
        dp.append(0)
        if x < len(a)-1:
            x += 1
# print(dp)
print(dp[-1])

Submission status: Accepted

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

# broken[i] : i段目が壊れていたらTrue
broken = [False] * 100100
for i in a:
	broken[i] = True

# dp[i] : i段目に行く通り数
dp = [0] * 100100

# 0段目に行く方法は1通り
dp[0] = 1

# 1段目からn段目について調べる
for i in range(1, n + 1):
	# 壊れてるなら
	if broken[i]:
		# その段には進めないので0通り
		dp[i] = 0
	# 壊れてないなら
	else:
		# i - 1段目から移動可能 (i - 1段目は, i == 0 のときにはないので分岐)
		if i > 0:
			dp[i] += dp[i - 1]
		# i - 2段目から移動可能 (i - 2段目は, i == 0, 1 のときにはないので分岐)
		if i > 1:
			dp[i] += dp[i - 2]
	dp[i] %= MOD

print(dp[n])

Submission status: Accepted

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

fib = [0, 1]
for i in range(100100):
	fib.append((fib[i] + fib[i + 1] % MOD))

res = 1
for i in range(m + 1):
	p, q = a[i], a[i + 1]
	res = (res * fib[q - p - 1]) % MOD

print(res)

Submission status: Accepted

Solution code:
#C問題
def fib(n):
    a, b = 0, 1
    for i in range(n-1):
        a, b = b, a + b
    return b

N, M = map(int,input().split())
break_step = []
step_list = [i for i in range(N+1)]
for i in range(M):
    break_step.append(int(input()))
count_list = []
count = 0
for i in break_step:
    count = i - count
    count_list.append(count)
    count = i + 1
count = N - count + 1
count_list.append(count)
ans = 1
for i in count_list:
    ans = ans * fib(i)
if 0 in  count_list:
    print(0)
else:
    print(ans%1000000007)

Submission status: Accepted

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

P = 10**9+7
dp = [1]*(N+1)

for i in List:
    dp[i]=0

for j in range(1, N):
    if dp[j+1]!=0:
        dp[j+1] = (dp[j]+dp[j-1])%P
        
print(dp[N])

Submission status: Accepted

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

P = 10**9+7
dp = [1]*(N+1)

for i in List:
    dp[i]=0

for j in range(1, N):
    if dp[j+1]!=0:
        dp[j+1] = dp[j]+dp[j-1]
        
print(dp[N]%P)

Submission status: Accepted

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

[N, M] = [int(i) for i in input().split()]
a_list = []
for m in range(M):
    a_list.append(int(input()))

stairs_status = [-1] * (N + 1)
stairs_status[0] = 1
for a in a_list:
    stairs_status[a] = 0

for n in range(1, N + 1):
    if n == 1:
        if stairs_status[n] == -1:
            stairs_status[n] = stairs_status[n - 1]
    else:
        if stairs_status[n] == -1:
            stairs_status[n] = stairs_status[n - 1] + stairs_status[n - 2]

#print(stairs_status)
print(stairs_status[-1] % 1000000007)

Submission status: Accepted

Solution code:
import sys
mod = 10**9+7
def main():
    n,m=map(int,input().split(' '))
    if m > 0:
        aaa = set(map(int,sys.stdin))
    else:
        aaa = set()

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

    print(dp[n])

main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Wed Jun 19 17:29:01 2019

@author: makigon
"""
mod = 10 ** 9 + 7
N, M = map(int, input().split())
a = [int(input()) for i in range(M)]

aset = set(a)
f = [0 for i in range(N)]
f[0] = 1
if 1 in a and N>=2 :
    f[1] = 0
elif 1 not in a and N>=2:
    f[1] = 1

for i in range(2,N):
    if i in aset:
        continue
    else:
        f[i] = f[i-1]+f[i-2]
    f[i] %= mod

if N == 1:
    print(f[N-1])
else:       
    print((f[N-1]+f[N-2]) % mod)

Submission status: Accepted

Solution code:
import sys
import numpy as np
MOD = 1000000007
def main():
    n, m = [int(x) for x in input().split()]
    pattern = [1]
    broken = -1
    brokencnt = 0
    if brokencnt < m:
        broken = int(input())
        brokencnt += 1
    for i in range(1, n + 1):
        if i == broken:
            pattern.append(0)
            if brokencnt < m:
                broken = int(input())
                brokencnt += 1
            continue
        if i == 1:
            pattern.append(pattern[i - 1])
        if i > 1:
            pattern.append((pattern[i - 1] + pattern[i - 2]) % MOD)
    print(pattern[n])
main()

Submission status: Accepted

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

LARGE = 10**9 + 7

r_arr = [0]*(N+1)
r_arr[0] = 1
if a_dict.get(1, 0) == 1:
    r_arr[1] = 0
else:
    r_arr[1] = 1

for i in range(2, N+1):
    if a_dict.get(i, 0) == 1:
        pass
    else:
        r_arr[i] = (r_arr[i-1] + r_arr[i-2]) % LARGE

print(r_arr[-1])

Submission status: Accepted

Solution code:
def solve(string):
    n, m, *a = map(int, string.split())
    ans = [0] * (n + 1)
    a = set(a)
    ans[0] = 1
    ans[1] = 0 if 1 in a else 1
    num = 1000000007
    for i in range(2, n + 1):
        if i in a:
            continue
        ans[i] = (ans[i - 2] + ans[i - 1]) % num
    return str(ans[-1])


if __name__ == '__main__':
    n, m = map(int, input().split())
    print(solve('{} {}\n'.format(n, m) + '\n'.join([input() for _ in range(m)])))

Submission status: Accepted

Solution code:
def solve(string):
    n, m, *a = map(int, string.split())
    ans = [0] * (n + 1)
    a = set(a)
    ans[0] = 1
    ans[1] = 0 if 1 in a else 1
    num = 1000000007
    for i in range(2, n + 1):
        if i in a:
            continue
        ans[i] += (ans[i - 2] + ans[i - 1]) % num
    return str(ans[-1])


if __name__ == '__main__':
    n, m = map(int, input().split())
    print(solve('{} {}\n'.format(n, m) + '\n'.join([input() for _ in range(m)])))

Submission status: Accepted

Solution code:
def solve(string):
    n, m, *a = map(int, string.split())
    ans = [0] * (n + 1)
    a = set(a)
    ans[0] = 1
    ans[1] = 0 if 1 in a else 1
    for i in range(2, n + 1):
        if i in a:
            continue
        ans[i] += (ans[i - 2] + ans[i - 1]) % 1000000007
    return str(ans[-1])


if __name__ == '__main__':
    n, m = map(int, input().split())
    print(solve('{} {}\n'.format(n, m) + '\n'.join([input() for _ in range(m)])))

Submission status: Accepted

Solution code:
def solve(string):
    n, m, *a = map(int, string.split())
    ans = [0] * (n + 1)
    for _a in a:
        ans[_a] = -1
    ans[0] = 1
    ans[1] = 1 if ans[1] == 0 else 0
    for i in range(2, n + 1):
        if ans[i] == -1:
            ans[i] = 0
            continue
        ans[i] += ans[i - 2] % 1000000007
        ans[i] += ans[i - 1] % 1000000007
    return str(ans[-1] % 1000000007)


if __name__ == '__main__':
    n, m = map(int, input().split())
    print(solve('{} {}\n'.format(n, m) + '\n'.join([input() for _ in range(m)])))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import numpy as np
import statistics
from statistics import mean, median,variance,stdev
import math

def main():
	N, M = map(int, input().split(" "))
	N += 1
	
	DP = [-1 for i in range(N)]
	DP[0] = 1
	DP[1] = 1
	
	for i in range(M):
		tmp = int(input())
		DP[tmp] = 0

	for i in range(2, N):
		if DP[i] == 0:
			continue
		else:
			DP[i] = (DP[i-1] + DP[i-2]) % 1000000007
		
	print(DP[-1])
	
	
if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
import sys

n, m = map(int, input().split())
aaa = set()
if m != 0:
    for _ in range(m):
        aaa.add(int(input()))
    
    
dp = [0] * (n + 1) # 0 array
dp[0] = 1
dp[1] = 1 if 1 not in aaa else 0 # 入ってはいけない段に1が存在した場合は0
MOD = int(1e9) + 7

for i in range(2, n + 1):
    if i in aaa:
        continue
    dp[i] = (dp[i-2] + dp[i-1]) % MOD # 入ってはいけないところからの遷移の場合0を加算
print(dp[n])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

lst = [0] * N
pre1 = 0
pre2 = 0
skips = set([int(input()) for _ in range(M)])
for x in range(N):
    if x in skips:
        lst[x] = 0
    elif x in [0, 1]:
        lst[x] = 1
    else:
        lst[x] = (lst[x - 1] + lst[x - 2]) % 1000000007

if N == 1:
    print(lst[-1])
else:
    print((lst[-1] + lst[-2]) % 1000000007)

Submission status: Accepted

Solution code:
#ABC129-C
N,M=map(int,input().split())
a=[]
broke={} #N段目が壊れているか
broke[0]=0
for i in range(1,N+1):
    broke[i]=0

f={}
f[0]=0 #番号を段数と一致させるため
num=0 #N段までの行き方
check=0 #行けるかどうか

for i in range(M):
    a.append(int(input()))
    n=a[i]
    broke[n]=1 #ｎ段目が壊れていることを記憶
    f[n]=0

for i in range(M-1): #壊れている階段同士の差が１の場所があるか調べる。
    dif=a[i+1]-a[i]
    if dif==1:
        check=1
        break
        
if (1 in a)==True: #１が壊れているとき
    f[1]=0
else:
    f[1]=1
if (2 in a)==True: #２が壊れているとき
    f[2]=0
elif f[1]==0: #１が壊れているとき
    f[2]=1
else:
    f[2]=2

if check==0:
    for i in range(1,N-1): #1~N-2
        if broke[i+2]==1:
            continue
        f[i+2]=f[i+1]+f[i]
    num=f[N]

#for i in range(N+1):
    #print(str(i)+":"+str(f[i]))
print(num%1000000007)
#print(broke)

Submission status: Accepted

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

da = max([a[i+1] - a[i] for i in range(len(a)-1)])
b = [0 for i in range(da+1)]
b[0] = 1
b[1] = 1
for i in range(2, da + 1):
    b[i] = b[i-1] + b[i-2]

ans = 1
MOD = 1000000007
for j in range(1, M+2):
    index = a[j] - a[j-1] - 2
    if index == -1:
        ans = 0
        break
    ans = ans * b[index]
    ans = ans % MOD
print(ans)

Submission status: Accepted

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

for _ in range(n):
    b.append(b[-1] + b[-2])

if m == 0:
    ans = b[n + 1]
else:
    c.append(a[0])
    for i in range(m - 1):
        c.append(a[i + 1] - a[i] - 1)
    c.append(n - a[m - 1])

    for i in c:
        ans *= b[i]

print(ans % 1000000007)

Submission status: Accepted

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

for i in range(1,N+1):
    if ret[i] == 0:
        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:
from collections import deque

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

A = deque()
dp = [0] * N
for i in range(M):
  A.append(int(input()))
A.append(N+1)

if N == 1:
  print(1)

elif N == 2:
  if 1 in A:
    print(1)
  else:
    print(2)
    
else:
  a = A.popleft()
  if a != 1:
    dp[0] = 1
  else:
    a = A.popleft()
    
  if a != 2:
    dp[1] = dp[0] + 1
  else:
    a = A.popleft()
    
  for i in range(2,N):
    if a != i+1:
      dp[i] = dp[i-1] + dp[i-2]
    else:
      a = A.popleft()
  print(dp[-1]%1000000007)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
fall=[0]*(n+1)
for i in range(m):
    fall[int(input())]=1
dp=[0]*100010
dp[0]=1
for now in range(n):
    for next in range(now+1,min(n,now+2)+1):
        if fall[next]==0:
            dp[next]+=dp[now]
            dp[next]%=1000000007
print(dp[n])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#abc129c

n,m=map(int,raw_input().split())
a={int(raw_input()) for i in xrange(m)}

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

Submission status: Accepted

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

INF = 10**9+7

def ri():
    return int(input())

def rl():
    return list(input().split())

def rli():
    return list(map(int, input().split()))

def main():
    n, m = rli()
    la = [False for _ in range(100001)]
    for _ in range(m):
        la[ri()] = True
    dp = [0 for _ in range(100001)]
    dp[0] = 1
    for i in range(1, n+1):
        if la[i]:
            dp[i] = 0
        else:
            dp[i] = (dp[i-1]+dp[i-2]) % INF
    print(dp[n])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)] 
mod = 10**9 + 7
X = [1 for _ in range(N+1)]
for i in a:
  X[i] = 0
for j in range(2,N+1):
  if X[j]:
    X[j] = X[j-1] + X[j-2]
ans = X[N] % mod
print(ans)

Submission status: Accepted

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

mod=10**9+7
dp=[0 for i in range(N+1)]
dp[0]=1
for i in range(N):
    j=i+1
    for j in range(j,min(N+1,j+2)):
        if a[j]==1:
            dp[j]+=dp[i]
            dp[j]%=mod

print(dp[N])

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
A = set()
for i in range(M):
    A.add(int(input()))
count = [0] * (N+1)
count[0] = 1
mod = 10 ** 9 + 7
if 1 in A:
    if 2 in A:
        print(0)
        exit()
    count[2] = 1
    start = 3
else:
    count[1] = 1
    start = 2
for i in range(start, N+1):
    if i in A:
        continue
    count[i] = count[i-1] + count[i-2]
    count[i] %= mod
print(count[N])

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
MOD = 10 ** 9 + 7
dp = [0] * (N+1)
dp[0] = 1
a = set()
for _ in range(M):
    a.add(int(input()))
if 1 in a:
    if 2 in a:
        print(0)
        exit()
    dp[2] = 1
    start = 3
else:
    dp[1] = 1
    start = 2
for i in range(start, N+1):
    if i in a:
        continue
    dp[i] = dp[i-1] + dp[i-2]
    dp[i] %= MOD
print(dp[N])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

if 1 in a:
    if 2 in a:
        print(0)
        exit()
    dp[2] = 1
    start = 3
else:
    dp[1] = 1
    start = 2
for i in range(start, N+1):
    if i in a:
        continue
    dp[i] = dp[i-1] + dp[i-2]
    dp[i] %= MOD

print(dp[N])

Submission status: Accepted

Solution code:
def fib(n):
    a, b = 1, 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

n,m = map(int,input().split())
if m != 0:
  a = [int(input()) for i in range(m)]
  ans = fib(a[0])
  for j in range(1,m):
    if m == 1:
        continue
    elif a[j] == a[j-1]+1:
        ans = 0
    else:
        ans *= fib(a[j]-a[j-1]-1)
  ans *= fib(n-a[m-1])
else:
  ans = fib(n+1)
print(ans%1000000007)