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:
def main():
    n, m = map(int, input().split())
    dp = [0] * (n + 1)
    dp[0] = 1
    for _ in range(m):
        a = int(input())
        dp[a] = -1
    mod = 10 ** 9 + 7

    for i in range(n + 1):
        if dp[i] == 0:
            if i - 1 >= 0 and dp[i - 1] != -1:
                dp[i] += dp[i - 1]
            if i - 2 >= 0 and dp[i - 2] != -1:
                dp[i] += dp[i - 2]

    print(dp[-1] % mod)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

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

mod = 10**9 + 7

dp = [1] * (N+1)

for i in A:
    dp[i] = 0

for i in range(2, N+1):
        dp[i] *= (dp[i-1] + dp[i-2]) % mod

print(dp[-1])

Submission status: Accepted

Solution code:
def main():
    N,M = map(int,input().split())
    mod = 10**9 + 7
    a = [0]*(N+1)
    a[0] = 1
    banned = [False]*(N+1)
    for x in range(M):
        n = int(input())
        banned[n] = True
    for i in range(1,N+1):
        res = 0
        if not banned[i-1]:
            res += a[i-1]
        if not banned[i-2]:
            res += a[i-2]
        a[i] = res
    print(a[-1]%mod)
    return

main()

Submission status: Accepted

Solution code:
n,m=map(int, input().split())
a=[False]*(n+1)
for i in range(m):
    A=int(input())
    a[A]=True
mod=10**9+7
dp=[0]*(n+1)

if not a[1]:
    dp[1]=1

if n>1:
    if not a[2]:
        dp[2]=dp[1]+1

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

print(dp[n]%mod)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
oks = [True]*(N+1)
for i in range(M):
   a = int(input())
   oks[a] = False
dp = [0]*(N+1)
dp[0] = 1
mod = 1000000007
for now in range(N):
    for next in range(now+1,min(N,now+2)+1): #1段または2段すすむ。際集団を超えないように
        if oks[next]: #階段が壊れていなければ
            dp[next] += dp[now]
            dp[next] %= mod
print(dp[N])

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
 
# issafe => 0段目からN段目まで, 安全ならTrue, 壊れているならFalse
issafe = [1] * (N+1)
for i in range(M):
  a = int(input())
  issafe[a] = 0

# 動的計画法（漸化式）
# dp => 0段目からN段目まで, その移動方法の数
dp = [0] * (N+1)
dp[0] = 1
if issafe[1]: dp[1] = 1
for i in range(2, N+1):
  if issafe[i-1]: dp[i] += dp[i-1]
  if issafe[i-2]: dp[i] += dp[i-2]
  dp[i] %= 10**9+7
    
print(dp[N])

Submission status: Accepted

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

# issafe => 0段目からN段目まで, 安全ならTrue, 壊れているならFalse
issafe = [1] * (N+1)
for i in range(M):
  a = int(input())
  issafe[a] = 0

# dp => 0段目からN段目まで, その移動方法の数
dp = [0] * (N+1)
dp[0] = 1
if issafe[1]: dp[1] = 1
for i in range(2, N+1):
  if issafe[i-1]: dp[i] += dp[i-1]
  if issafe[i-2]: dp[i] += dp[i-2]
  dp[i] %= 10**9+7
    
print(dp[N])

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
# 0段目からN段目まで、壊れているか否かを表す flag
issafe = [1] * (N+1)
for i in range(M):
  a = int(input())
  issafe[a] = 0

mod = 10**9 + 7

# 0段目からN段目までの移動方法の数
dp = [0] * (N + 1)
dp[0] = 1
if issafe[1]: dp[1] = 1
# 漸化式に従って計算する
for i in range(2, N + 1):
  if issafe[i-1]: dp[i] += dp[i-1]
  if issafe[i-2]: dp[i] += dp[i-2]
  dp[i] %= mod
  
print(dp[N])

Submission status: Accepted

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

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

broken = set([int(readline()) for i in range(M)])

dp = [0] * (N + 1)
dp[0] = 1
if 1 not in broken:
  dp[1] = 1
  
DIV = 10 ** 9 + 7

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

Submission status: Accepted

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

Submission status: Accepted

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

dp=[0]*(n+1)
dp[0]=1
dp[1]=1
for i in range(2,n+1):
    dp[i]=dp[i-1]+dp[i-2]
    dp[i]%=mod
if m==0:
    ans=dp[n]
else:
    begin=0
    end=a[0]-1
    for i in range(m):
        end=a[i]-1
        ans*=dp[end-begin]
        
        if(i+1<m and a[i+1]==a[i]+1):
            ans=0
            break
            
        else:
            begin=end+2

    ans*=dp[n-a[m-1]-1]

print(ans%mod)

Submission status: Accepted

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


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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
MOD = 10 ** 9 + 7
s = 0

def comb(n, k):
  if k > n - k:
    k = n - k
  de = 1
  nu = 1
  for i in range(k):
    de *= (n - i)
    de = de % MOD
    nu *= (i + 1)
    nu = nu % MOD
  nu = pow(nu, -1, MOD)
  return (de * nu) % MOD

def calc_from_step(step):
  temp = 0
  for i in range(1 + (step // 2)):
    temp += comb(step-i, i)
  return temp


arr = [1, 1]
steps = []
step = 0
s = 0
for i in range(M):
  l = int(input()) - 1
  steps.append(l-s)
  if s > l:
    print(0)
    exit()
  if step < l - s:
    step = l - s
  s = l + 2
l = N
steps.append(l-s)
if step < l - s:
  step = l - s

for i in range(step - 1):
  arr.append((arr[i] + arr[i+1])%MOD)
ans = 1

for i in steps:
  ans *= arr[i]
  ans = ans % MOD
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=[int(input()) for i in range(m)]
a=set(a)
mod=10**9+7
dp=[0]*(n+7)
dp[0]=1
for i in range(n+1):
    if i+2 not in a: #2段先が壊れていない
        dp[i+2]+=dp[i]
    if i+1 not in a: #1段先が壊れていない
        dp[i+1]+=dp[i]
    dp[i+2]%=mod
    dp[i+1]%=mod
print(dp[n]%mod)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a1=0
ans=1
for i in range(m+1):
    if i==m:
        a2=n+1
    else:
        a2=int(input())
    l=a2-a1
    if l==0:
        print(0)
        exit()
    if l>2:
        fst=1
        snd=1
        for _ in range(l-2):
            nfst=snd
            snd=fst+nfst
            fst=nfst
        ans*=snd
    a1=a2+1
print(ans%(10**9+7))

Submission status: Accepted

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    n, m = map(int, input().split())
    S = set(int(input()) for _ in range(m))

    a, b = 0, 1 # a[-1], a[0]
    for i in range(1, n + 1):
        if i in S:
            a, b = b, 0
        else:
            a, b = b, (a + b) % MOD

    print(b)
resolve()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = [True]*N
for _ in range(M):
  a = int(input())
  A[a-1] = False # 壊れてるところはfalse

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

dp[0], dp[1] = 1, 1 # 初期条件
if not A[0]: # 1段目が壊れてたら
  dp[1] = 0

for i in range(2,N+1):
  # 壊れてるところはdp=0にする
  if not A[i-1]:
    dp[i] = 0
  else:
    dp[i] = (dp[i-1] + dp[i-2])%waru
print(dp[-1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Sep 13 12:37:37 2020

@author: liang
"""

"""
フィボナッチ数列生成
【DP(?)】　: 配列を使用することで計算量が爆発するのを防ぐ
【小さいものから計算する】の原則

【方針】
　通常の配列を用いたフィボナッチ数列の生成方法の応用版
 壊れた階段のフィボナッチ数列の値を　0 にすることで、実質遷移を止めることが出来る。
"""
key = 10**9 + 7
N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]+[-1]

fibs = [0]*(N+1)
index = 0
for i in range(N+1):
    #壊れたところの値を0にすれば良い
    if i == A[index]:
        fibs[i] = 0
        index += 1
    elif i == 0 or i == 1:
        fibs[i] = 1
    else:
        fibs[i] = (fibs[i-1] + fibs[i-2])%key
        

print(fibs[N])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Sep 13 12:06:59 2020

@author: liang
"""


key = 10**9 + 7
N, M = map(int, input().split())

A = [int(input()) for _ in range(M)]
A.sort()
A += [-1]

def solve():
    steps = list()
    count = 0
    index = 0
    #段差数え
    for i in range(N+1):
        if i == A[index]:
            if count == 0:
                return 0
            else:
                steps.append(count)
                count = 0
                if index < M:
                    index += 1
        else:
            count += 1
    else:
         steps.append(count)
         count = 0
        
    smax = max(steps)
    fibs = [0] * smax
    #fibテーブル生成 O(n)
    for i in range(smax):
        if i == 0 or i == 1:
            fibs[i] = 1
        else:
            fibs[i] = fibs[i-1] + fibs[i-2]  
    else:
        ans = 1
        for s in steps:
            #print(s)
            ans *= fibs[s-1]
            #print(ans)
            ans %= key
    #print(A)
    #print(steps)
    #print(fibs)
    return ans

ans = solve()        
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

mod = 10**9+7
a.append(float('INF'))
a = a[::-1]
dp = [0] * (n+1)
dp[0] = 1
if a[-1] != 1:
    dp[1] = 1
else:
    a.pop()
for i in range(2, n+1):
    if i == a[-1]:
        a.pop()
        continue
    dp[i] = dp[i-1] + dp[i-2]
    dp[i] %= mod
print(dp[n])

Submission status: Accepted

Solution code:
MOD = 10**9+7

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

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

dp = [0]*(n+1)
dp[0] = 1
if not A[1]:
    dp[1] = 1

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

print(dp[n])

Submission status: Accepted

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

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

Submission status: Accepted

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

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


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

print(memo[-1]%mod)

Submission status: Accepted

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

mod = 1000000007

memo = [-1]*(n+1)
memo[0] = 0

for k in range(m):
    memo[a[k]] = 0

for i in range(1, n+1):
    if memo[i] != -1:
        pass 
    elif i <= 2:
        memo[i] = memo[i-1] + 1
    else:
        memo[i] = memo[i-1] + memo[i-2]
print(memo[-1]%mod)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = set(list(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[-1])

Submission status: Accepted

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

lst[0] = 1
for i in range(1, n + 1):
    if (i == 1):
        if(lst[1] == -1):
            lst[1] = 1
    elif (lst[i] == 0):
        pass
    else:
        lst[i] = (lst[i - 1] + lst[i - 2])%(1000000007)

print(lst[n])

Submission status: Accepted

Solution code:
#入力:N,M(int:整数)
def input2():
	return map(int,input().split())

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

n,m=input2()
A=[int(input()) for _ in range(m)]
INF = 1000000007

start=0 #階段の開始点
ans=1 #
for a in A:
	tmp=a-start
	if tmp>1:
		fib=Fib(tmp+1)
		ans*=fib
		ans%=INF
	elif tmp==0:
		ans=0
		break
	start=a+1

if n-start>1:
	ans*=Fib(n-start+2)
	ans%=INF
print(ans)

Submission status: Accepted

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

p = 10**9+7
dp = [0]*(n+1)
dp[0] = 1

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

Submission status: Accepted

Solution code:
import sys
from sys import exit
from collections import deque
from bisect import bisect_left, bisect_right, insort_left, insort_right #func(リスト,値)
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import sin, cos, tan, asin, acos, atan, degrees, radians

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def powmod(n,i,mod):
    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)
def div2(x):
    return x.bit_length()
def div10(x):
    return len(str(x))-(x==0)
def perm(n,mod=None):
    ans = 1
    for i in range(1,n+1):
        ans *= i
        if mod!=None:
            ans %= mod
    return ans
def intput():
    return int(input())
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x,d=1):
        self.setdefault(x,0)
        self[x] += d
class comb():
    def __init__(self, n, mod=None):
        self.l = [1]
        self.n = n
        self.mod = mod
    def get(self,k):
        l,n,mod = self.l, self.n, self.mod
        k = n-k if k>n//2 else k
        while len(l)<=k:
            i = len(l)
            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)
        return l[k]

N,M = mint()
A = set()
for _ in range(M):
    A.add(intput())
dp = [1]+[0]*N
for i in range(N):
    if i+1 not in A:
        dp[i+1] += dp[i]
    if i+2<=N and i+2 not in A:
        dp[i+2] += dp[i]
print(dp[N]%MOD)

Submission status: Accepted

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

Submission status: Accepted

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

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

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

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

if __name__ == "__main__":
    main3()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
pin=sys.stdin.readline
sys.setrecursionlimit(10000000)

def f(n):
  if n==0:
    return 1
  if n==1:
    if dp[n]==0:
      return 0
    return 1
  if dp[n]==0:
    return 0
  if dp[n-1]==-1:
    dp[n-1]=f(n-1)
  if dp[n-2]==-1:
    dp[n-2]=f(n-2)
  return dp[n-1]+dp[n-2]


N,M=map(int,pin().split())
mod=1000000007
dp=[-1]*(N+1)
dp[0]=1
for i in range(M):
  dp[int(pin())]=0
print(f(N)%mod)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
step = [True] * n
r = [0,1]
MOD = 10**9 + 7
for _ in range(m):
    broken = int(input())
    step[broken - 1] = False
for i, tf in enumerate(step):
    if tf:
        r += [(r[i] + r[i+1]) % MOD]
    else:
        r += [0]
print(r[-1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
def main():
    N, M = map(int, input().split())
    A = set([int(input()) for x in range(M)])

    mod = 10 ** 9 + 7
    dp = [0] * 10 ** 6
    dp[0] = 1
    for i in range(N + 1):
        if i in A:
            continue
        dp[i + 1] += dp[i] % mod
        dp[i + 2] += dp[i] % 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)])
step = [0] * (N+1)
step[0] = 1
if 1 not in A:
    step[1] = 1
else:
    step[1] = 0
for i in range(2,N+1):
    if i in A:
        continue
    step[i] = (step[i-1] + step[i-2]) % 1000000007
print(step[-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
# INF =  float("inf")
INF = 10**18
import bisect
import statistics
mod = 10**9+7
# mod = 998244353

N, M = map(int, input().split())
a = set()
for i in range(M):
    a.add(int(input()))

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

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

print(dp[N] % mod)

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
# INF =  float("inf")
INF = 10**18
import bisect
import statistics
mod = 10**9+7
# mod = 998244353

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

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

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

ans = 1
a = -1
for i in range(M):
    b = int(input())
    c = b - a - 2
    if c < 0:
        print (0)
        sys.exit()
    else:
        ans = (ans * dp[c]) % mod
        a = b

ans = (ans * dp[N-a-1]) % mod

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
mod=10**9+7 ; inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict #すべてのkeyが用意されてる defaultdict(int)で初期化
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  #変換後の末尾桁を0や0.01で指定
  #Decimal((str(0.5)).quantize(Decimal('0'), rounding=ROUND_HALF_UP))
from functools import lru_cache
from bisect import bisect_left as bileft, bisect_right as biright
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########
n,m=map(int,input().split())
A=[int(input()) for i in range(m)]
NG=[0]*(10**5+10)
for i in A:
    NG[i]=1


@lru_cache(maxsize=10**10)
def qwe(x):
    if x==n:return 1
    if x>n:return 0
    if NG[x+1] and NG[x+2]: print(0);exit()
    if NG[x+1]:return qwe(x+2)%mod
    if NG[x+2]:return qwe(x+1)%mod
    return (qwe(x+2)+qwe(x+1))%mod
print(qwe(0))

Submission status: Accepted

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

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

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

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

print(dp[n])

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
A = [int(input()) for i in range(M)]
n = 0
if M != 0:
    a = b = A[0]
else:
    a = b = -2
c = 0
ans = [0,1]
for i in range(1,N+1):
    if  i == a:
        c = 0
        n += 1
        b = a
        if n <= M-1:
            a = A[n]
    elif i-2 == b:
        c = ans[-1]
    elif i-1 == b :
        c = ans[-2]
    else:
        c  = ans[-1] + ans[-2]
    c %= 10**9 + 7
    ans.append(c)
print(ans[-1])

Submission status: Accepted

Solution code:
P = 10**9 + 7

class UnionFind():
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * n

    def root(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.root(self.par[x])
            return self.par[x]

    def union(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                self.par[x] = y
            else:
                self.par[y] = x
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1

    def samegrp(self, x, y):
        return self.root(x) == self.root(y)

N, M = [int(x) for x in input().split()]
X = UnionFind(N + 1)
for i in range(M):
    X.union(0, int(input()))

dp = [0]*(N + 1)
dp[0] = 1
if X.samegrp(0, 1):
    dp[1] = 0
else:
    dp[1] = 1
for i in range(2, N + 1):
    if X.samegrp(0, i):
        dp[i] = 0
    else:
        dp[i] = (dp[i - 1] + dp[i - 2]) % P

ans = dp[N]
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

MOD=10**9+7

if N>1:
    dp=[0]*(N+1)
    dp[0]=1
    dp[1]=1

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

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

        if dp[i-2]!=-1:
            dp[i]+=dp[i-2]
        
        if dp[i-1]!=-1:
            dp[i]+=dp[i-1]
        
        dp[i]=dp[i]%MOD

    print(dp[N])

else:
    if M==0:
        print(1)
    else:
        print(0)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
isBroken = [0] * (N+1)

for i in range(M):
    a = int(input())
    isBroken[a] = 1

dp = [0 for _ in range(N+2)]
#幻のN+1段目まで生やして、そこの組み合わせをゼロにする

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

Submission status: Accepted

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

Submission status: Accepted

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

mod=10**9+7

dp=np.zeros(N+1)
dp[0]=1
if 1 not in A:
    dp[1]=1
else:
    dp[1]=0

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

print(int(dp[N]))

Submission status: Accepted

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

for _ in range(m):
  a = int(input())
  dp[a] = -1

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

print(dp[n]%(10**9+7) if dp[n]!=-1 else 0)

Submission status: Accepted

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

# dp[i]: i 段目まで来た時の移動方法の総数
dp = [0]*(N+1)

# 初期条件
dp[0] = 1

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

mod = 10**9+7
ans = [0]*(n+1)
ans [0] = 1
if 1 not in a: ans[1] = 1

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

Submission status: Accepted

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

step = [0]*(N+1)
last = -1
for a in A:
    if a == last + 1 or a == last - 1:
        print(0)
        exit()
    step[a] = 1
    last = a

ans = [0] + [1] + [0]*N

chk = 0
for i in range(1, N+1):
    if step[i] == 0 and chk <= 0:
        ans[i+1] = ans[i] + ans[i-1]
        chk = 0
    elif step[i] == 1:
        ans[i+1] = ans[i]
        chk = 2
    elif step[i] == 0 and chk > 0:
        ans[i+1] = ans[i]
        chk -= 1
        
print(ans[-1]%(10**9 + 7))

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
A = []
MOD = 1000000007
for _ in range(M):
  a = int(input())
  A.append(a)
DP = [1]*(N+1)
for i in A:
  DP[i] = 0
for i in range(2,N+1):
  DP[i] = (DP[i-1]+DP[i-2])%MOD*DP[i]
print(DP[-1])

Submission status: Accepted

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

dp = [1] * (n+1)
dp[0] = 1
if 1 not in a_l:
    dp[1] = 1
else:
    dp[1] = 0
if n > 1:
    for i in a_l:
        dp[i] = 0
    if 2 not in a_l:
        dp[2] = dp[0] + dp[1]
    else:
        dp[2] = 0
    for i in range(2,n+1):
        if dp[i] != 0:
            dp[i] = (dp[i-1] + dp[i-2])%1000000007
print(dp[-1])

Submission status: Accepted

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

now = 0
for i in range(m):
  next = int(input()) - 1
  step.append(next - now)
  now = next + 2

step.append(n-now)  
step.sort()

def fibo():
  s = []
  a = 1
  b = 1
  s.append(a)
  s.append(b)
  for i in range(n):
    c = a+b
    a = b
    b = c
    s.append(c)
  return s

ans = 1

if step[0] < 0:
  ans = 0

else:
  f = fibo()
  for i in step:
    ans *= f[i]

print(ans % 1000000007)

Submission status: Accepted

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

Submission status: Accepted

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

mod = 10**9+7
dp = [-1]*(n+1)
dp[0]= 0
dp[1] = 1
for i in range(m):
    a = int(input())
    dp[a] = 0

for i in range(2,n+1):
    if dp[i] == -1:
        if i <= 2:
            dp[i] = dp[i-1]+1
        elif i>=3 :
            dp[i] = (dp[i-1]+ dp[i-2])%mod

print(dp[n])

Submission status: Accepted

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

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