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 = list(map(int, input().split()))
MOD = 1000000007

dp = [0 for i in range(n+2)]
dp[0] = 1
a = set()
for i in range(m):
  t = int(input())
  a.add(t)

for i in range(n):
  if i+2 not in a:
    dp[i+2] = (dp[i+2]+dp[i])%MOD
  if i+1 not in a:
    dp[i+1] = (dp[i+1]+dp[i])%MOD

print(dp[n])

Submission status: Accepted

Solution code:
N, M = map(int, raw_input().split())
S = [True]*(N+1)
for _ in range(M):
  a = input()
  S[a] = False
T = [0]*(N+1)
T[0] = 1
T[1] = 1 if S[1] else 0
for i in range(2, N+1):
  if S[i]:
    T[i] = (T[i-1]+T[i-2])%1000000007
print T[N]

Submission status: Accepted

Solution code:
def c_typical_stairs(N, M, A, MOD=10**9 + 7):
    a = set(A)
    stairs = [0] * (N + 1)
    stairs[0] = 1
    for i in range(N):
        if i + 1 <= N and (i + 1) not in a:
            stairs[i + 1] += stairs[i]
        if i + 2 <= N and (i + 2) not in a:
            stairs[i + 2] += stairs[i]
    return stairs[N] % MOD

N, M = [int(i) for i in input().split()]
A = [int(input()) for _ in range(M)]
print(c_typical_stairs(N, M, A))

Submission status: Accepted

Solution code:
def getlist():
	return list(map(int, input().split()))

N, M = getlist()
L = [0 for i in range(N + 100)]
L[0] = 1
L[1] = 1

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

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

print(L[N] % 1000000007)

Submission status: Accepted

Solution code:
MOD = int(1e9+7)

def main():
    N, M = map(int, input().split())
    A = [int(input()) for _ in range(M)]
    broken = [False] * (N+1)
    for a in A:
        broken[a] = True
    dp = [0] * (N+1)
    dp[0] = 1
    if not broken[1]:
        dp[1] = 1
    for i in range(2, N+1):
        if not broken[i]:
            dp[i] = (dp[i-2] + dp[i-1]) % MOD
    print(dp[N])

if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    p,q,r = LI()
    print(p+q+r-max(p,q,r))
    return

#B
def B():
    n = I()
    w = LI()
    ans = float("inf")
    for i in range(n):
        m = sum(w[:i])
        l = sum(w[i:])
        ans = min(ans,abs(m-l))
    print(ans)
    return

#C
def C():
    n,m = LI()
    f = [1 for i in range(n+1)]
    for i in range(m):
        a = I()
        f[a] = 0
    dp = [0 for i in range(n+1)]
    dp[0] = 1
    for i in range(1,n+1):
        if f[i]:
            dp[i] = dp[i-1]+dp[i-2]
            dp[i] %= mod
    print(dp[n])
    return

#D
def D():
    h,w = LI()
    s = SR(h)

    return

#E
def E():
    n = I()

    return

#F
def F():
    n = I()

    return

#Solve
if __name__ == "__main__":
    C()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")

MOD = 1000000007  # type: int


def solve(N: int, M: int, a: "List[int]"):

    # 0段目一通り
    dp = [None]*(N+1)
    dp[0] = 1
    for i in a:
        dp[i] = 0
    for i in range(1, N+1):
        # print(i, dp)
        if dp[i] == None:
            b = dp[i-1]
            if i-2 >= 0:
                b += dp[i-2]
                b %= MOD
            dp[i] = b
    print(dp[N])
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(M)]  # type: "List[int]"
    solve(N, M, a)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

for a in A:
    T[a] = -1

T[0] = 1
for i in range(0, N):
    if i + 1 <= N and T[i + 1] != -1 and T[i] != -1:
        T[i + 1] = (T[i + 1] + T[i]) % MOD
    if i + 2 <= N and T[i + 2] != -1 and T[i] != -1:
        T[i + 2] = (T[i + 2] + T[i]) % MOD

print(T[N])

Submission status: Accepted

Solution code:
import sys
N, M = map(int, input().split())
dp = [0]*(N + 1)
dp[0] = 1
A = [int(sys.stdin.readline()) for _ in range(M)]
D = set(A)
mod = 10**9 + 7
for i in range(1, N+1):
    res = 0
    if i - 1 >= 0 and i - 1 not in D:
        res += dp[i-1]
    if i - 2 >= 0 and i - 2 not in D:
        res += dp[i-2]
    dp[i] = res % mod
print(dp[-1])

Submission status: Accepted

Solution code:
def makelist(n, m):
    return [[0 for _ in range(m)] for _ in range(n)]

MOD = int(1e9) + 7

N, M = map(int, input().split())
a = [True]*(N+1)

for i in range(1, M+1):
    n = int(input())
    a[n] = False

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
mod=10**9+7
isbroken=[1 for i in range(N+1)]
dp=[0 for i in range(N+1)]
dp[0]=1
for i in range(M):
    ai=int(input())
    isbroken[ai]=0
for i in range(N):
    dp[i+1]=isbroken[i]*dp[i]+isbroken[i-1]*dp[i-1]
    dp[i+1]%=mod
print(dp[N])

Submission status: Accepted

Solution code:

MOD = int(1e9) + 7

def main():
    buf = input()
    buflist = buf.split()
    N = int(buflist[0])
    M = int(buflist[1])
    a = []
    for i in range(M):
        buf = input()
        a.append(int(buf))
    a.append(N+1) # sentinel
    pattern = [1]
    for i in range(1, N+3):
        pattern.append(0)
    pointer = 0
    for i in range(0, N+1):
        if a[pointer] == i:
            pattern[i] = 0
            pointer += 1
        pattern[i+1] = (pattern[i+1] + pattern[i]) % MOD
        pattern[i+2] = (pattern[i+2] + pattern[i]) % MOD
    print(pattern[N])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
from collections import defaultdict
from functools import reduce

MOD = 1000000007

A = set()

# s = input()
# n = int(input())
# A = list(map(int, input().split()))
n, m = map(int, input().split())

for _ in range(m):
    a = int(input())
    A.add(a)

res = [0]*(n+1)

res[0] = 1
if 1 not in A:
    res[1] = 1

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

print(res[n])



class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res

Submission status: Accepted

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

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, log2
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

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()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, M = MAP()
a = [INT() for _ 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])%MOD

print(dp[N])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from operator import itemgetter
# gcd
# from fractions import gcd
# 切り上げ，切り捨て
# from math import ceil, floor
# リストの真のコピー（変更が伝播しない）
# from copy import deepcopy
# 累積和。list(accumulate(A))としてAの累積和
# from itertools import accumulate
# l = ['a', 'b', 'b', 'c', 'b', 'a', 'c', 'c', 'b', 'c', 'b', 'a']
# S = Counter(l)  # カウンタークラスが作られる。S=Counter({'b': 5, 'c': 4, 'a': 3})
# print(S.most_common(2))  # [('b', 5), ('c', 4)]
# print(S.keys())  # dict_keys(['a', 'b', 'c'])
# print(S.values())  # dict_values([3, 5, 4])
# print(S.items())  # dict_items([('a', 3), ('b', 5), ('c', 4)])
# from collections import Counter
# import math
# from functools import reduce
#
# input関係の定義
# fin = open('in_2.txt', 'r')
# sys.stdin = fin
# 提出時はコメントアウト+上のshebangを有効にする
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
# template

MOD = 1000000007  # type: int

def iterate_tokens():
    for line in sys.stdin:
        for word in line.split():
            yield word


if __name__ == '__main__':

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [ int(next(tokens)) for _ in range(M) ]  # type: "List[int]"
    setA = set(a)
    # write code
    dp = [0 for i in range(N + 10)]
    dp[0] = 1
    if 1 not in setA:
        dp[1] = 1
    else:
        dp[1] = 0
    if 2 not in setA:
        dp[2] = dp[1]+1
    else:
        dp[2]=0
    for i in range(3,N+1):
        if i-1 in setA and i-2 in setA:
            dp[i] = 0
        elif i - 1 in setA:
            dp[i] = dp[i - 2] % MOD
        elif i - 2 in setA:
            dp[i] = dp[i-1]%MOD
        else:
            dp[i] = (dp[i - 1] + dp[i - 2]) % MOD

    print(dp[N])

Submission status: Accepted

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

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

j = 0
for i in range(1, n + 1):
    if j < m and i == arr[j]:
        dp[i] = 0
        j += 1
        continue

    dp[i] = dp[i - 1] + dp[i - 2]
    dp[i] %= mod

print(dp[n])

Submission status: Accepted

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

for i in range(M):
    dp[int(input())]=0
for i in range(1,1+N):
    if dp[i]==0:
        continue
    else:
        if i==1:
            dp[i]=dp[i-1]%mod
        else:
            dp[i]=(dp[i-1]+dp[i-2])%mod
if dp[N]==-1:
    print(0)
else:
    print(dp[N])

Submission status: Accepted

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

A = [True for i in range(N + 1)]

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

for i in range(M):
    a = int(input())
    A[a] = False

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

print(dp[N])

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
n, m = map(int, input().split())

ban = [False] * (n + 1)

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

dp = [0] * (n+1)
dp[0] = 1
for i in range(n):
    dp[i] %= MOD
    if(ban[i]):dp[i] = 0
    if i + 1 <= n:
        dp[i+1] += dp[i]
    if i + 2 <= n:
        dp[i+2] += dp[i]

print(dp[n] % MOD)

Submission status: Accepted

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

from collections import deque
import itertools as ite
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18
MOD = 10 ** 9 + 7

N, M = map(int, raw_input().split())
flag = [False] * (N + 1)
for i in range(M):
    num = input()
    flag[num] = True

DP = [0, 1] + [0] * N
for i in range(1, N + 1):
    if not flag[i]:
        DP[i + 1] = DP[i] + DP[i - 1]
        DP[i + 1] %= MOD
print DP[N + 1]

Submission status: Accepted

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

Submission status: Accepted

Solution code:

N,M = list(map(int,input().split()))
V = 10**9 + 7
a = [int(input()) for _ in range(M)]
A =set(a)
ANS = [0 for _ in range(N+2)]

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

print(ANS[N]% V)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    p,q,r = LI()
    print(p+q+r-max(p,q,r))
    return

#B
def B():
    n = I()
    w = LI()
    ans = float("inf")
    for i in range(n):
        m = sum(w[:i])
        l = sum(w[i:])
        ans = min(ans,abs(m-l))
    print(ans)
    return

#C
def C():
    n,m = LI()
    f = defaultdict(lambda : 1)
    for i in range(m):
        a = I()
        f[a] = 0
    dp = defaultdict(lambda : 0)
    dp[0] = 1

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

#D
def D():
    h,w = LI()
    s = SR(h)

    return

#E
def E():
    n = I()

    return

#F
def F():
    n = I()

    return

#Solve
if __name__ == "__main__":
    C()

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N, M = MI()
    A = set(LIN(M))
    #print(A)
    dp = [0] * (N + 1)
    dp[0]=1
    if 1 not in A:
        dp[1] = 1
    
    for i in range(2,N+1):
        if i in A:
            continue
        else:
            dp[i] = dp[i - 1] + dp[i - 2]
            dp[i]%=mod
    print(dp[-1])

if __name__ == '__main__':
    main()

Submission status: Accepted

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

MOD = 1000000007  # type: int

def solve(N: int, M: int, a: "List[int]"):
    a = set(a)
    res = [0 for _ in range(N+1)]
    res[0] = 1
    if 1 in a:
        res[1] = 0
    else:
        res[1] = 1
    
    for i in range(2, N+1):
        if i in a:
            continue
        
        res[i] = (res[i-1] + res[i-2]) % MOD

    print(res[N])

    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [ int(next(tokens)) for _ in range(M) ]  # type: "List[int]"
    solve(N, M, a)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def getN():
    return int(input())

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

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

MOD = 1000000007
n,m = getlist()

broken = [0 for i in range(n+1)]
for i in range(m):
    broken[getN()] = 1

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

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

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

print(dp[n])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
from collections import Counter, deque, defaultdict
from itertools import accumulate, permutations, combinations, takewhile, compress, cycle
from functools import reduce
from math import ceil, floor, log10, log2, factorial
from pprint import pprint

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
# N = int(input())
# A,B,C = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# A = [int(input()) for _ in range(N)]

N, M = [int(x) for x in input().split()]
A = [int(input()) for _ in range(M)]
A = set(A)

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

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

print(dp[N] % MOD)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import bisect
n,m = map(int,input().split())
p = [0]*(n+1)
mod = 10**9+7

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

p[0]=1

for i in range(1,n+1):
  k = bisect.bisect_left(a,i)
  k2 = bisect.bisect_right(a,i)
  if k == k2:
    p[i] += p[i-1]
    if i >= 2:
      p[i] += p[i-2]
    p[i] = p[i]%mod
#print(p)
print(p[-1]%mod)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    p,q,r = LI()
    print(p+q+r-max(p,q,r))
    return

#B
def B():
    n = I()
    w = LI()
    ans = float("inf")
    for i in range(n):
        m = sum(w[:i])
        l = sum(w[i:])
        ans = min(ans,abs(m-l))
    print(ans)
    return

#C
def C():
    n,m = LI()
    f = defaultdict(lambda : 1)
    for i in range(m):
        a = I()
        f[a] = 0
    dp = defaultdict(lambda : 0)
    dp[0] = 1

    for i in range(1,n+1):
        if f[i]:
            dp[i] = dp[i-1]+dp[i-2]
            dp[i] %= mod
    print(dp[n])
    return

#D
def D():
    h,w = LI()
    s = SR(h)

    return

#E
def E():
    n = I()

    return

#F
def F():
    n = I()

    return

#Solve
if __name__ == "__main__":
    C()

Submission status: Accepted

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

X = [1] + [0] * N
for i in range(1, N+1):
    if NG[i]:
        continue
    X[i] = (X[i-1] + (X[i-2] if i > 1 else 0)) % P

print(X[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 for _ in range(N + 1)]
for A in a:
    dp[A] = 0
for i in range(2, N + 1):
    if dp[i]:
        dp[i] = (dp[i - 1] + dp[i - 2]) % MOD
ans = dp[N]
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
ri = lambda: int(input())
#rl = lambda: [int(x) if x.isdecimal() else x for x in input().split()]
#rl = lambda: list(input().split()))
rl = lambda: map(int,input().split())
rr = lambda N: [list(l) for l in zip(*[rl() for _ in range(N)])]
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')
OE = lambda x: print('Odd') if x%2 else print('Even')
INF = 10**18
MOD = 10**9+7

N,M=rl()
A=[0]*M
for i in range(M):
    A[i] = ri()

dp = [0]*(N+4)
dp[0] = 1
for a in A:
    dp[a] = -1

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

print(dp[N])

Submission status: Accepted

Solution code:
p = 1000000007

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

u = [0]*(n+1)
F = [0]*(n+1)
for i in range(m):
	x = int(input())
	u[x] = 1

F[0] = 1
for i in range(1, n+1):
	F[i] = (F[i-1]+F[i-2])%p if i > 1 else F[i-1]
	if u[i] == 1: F[i] = 0

print(F[n])

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
kaidan = [True] * (N+2)
for i in range(M):
    kaidan[int(input())] = False

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

print(dp[N])

Submission status: Accepted

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

if 0 in A:
    print(0)
    exit()

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

Submission status: Accepted

Solution code:
import sys, math, collections, heapq, itertools
def gcd(a, b):
    a, b = max(a, b), min(a, b)
    while a % b > 0: a, b = b, a % b
    return b
  
def solve():
    file = sys.stdin.readline #single: int(file()), line: map(int, file().split())
    INF = 10 ** 25
    mod = 7 + 10 ** 9
    N, M = map(int, file().split())
    broken = set()
    for i in range(M): broken |= {int(file())}

    DP = [0] * (N + 1)
    DP[0] = 1
    for i in range(N):
        if i + 1 not in broken: 
            DP[i+1] += DP[i]
            DP[i+1] %= mod
        if i + 2 <= N:
            if i + 2 not in broken:
                DP[i+2] += DP[i]
                DP[i+2] %= mod
    print(DP[N])
    return 0
  
if __name__ == "__main__":
    solve()

Submission status: Accepted

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


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

for i in range(N):
    if (Broken[i + 1]) == 0 and (i + 1) <= N:
        dp[i + 1] += dp[i]
        dp[i + 1] %= MOD

    if (Broken[i + 2]) == 0 and (i + 2) <= N:
        dp[i + 2] += dp[i]
        dp[i + 2] %= MOD

print(dp[N] % MOD)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    p,q,r = LI()
    print(p+q+r-max(p,q,r))
    return

#B
def B():
    n = I()
    w = LI()
    ans = float("inf")
    for i in range(n):
        m = sum(w[:i])
        l = sum(w[i:])
        ans = min(ans,abs(m-l))
    print(ans)
    return

#C
def C():
    n,m = LI()
    f = defaultdict(lambda : 1)
    for i in range(m):
        a = I()
        f[a] = 0
    dp = defaultdict(int)
    dp[0] = 1
    for i in range(1,n+1):
        if f[i]:
            dp[i] = dp[i-1]+dp[i-2]
            dp[i] %= mod
    print(dp[n])
    return

#D
def D():
    h,w = LI()
    s = SR(h)

    return

#E
def E():
    n = I()

    return

#F
def F():
    n = I()

    return

#Solve
if __name__ == "__main__":
    C()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

def main():
    N, M = LI()
    A = [0] * (N + 1)
    for _ in range(M):
        A[II()] = 1
    dp = [0] * (N + 1)
    dp[0] = 1
    for i in range(1, N + 1):
        if A[i] == 1:
            dp[i] = 0
        else:
            dp[i] = (dp[i - 1] + dp[i - 2]) % MOD
    ans = dp[N]
    return ans

print(main())

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N,M=map(int,input().split())
#A=[int(input()) for i in range(M)]
A=set()
for i in range(M):
    a=int(input())
    A.add(a)
mod=10**9+7
dp=[0]*(N+1)
dp[0]=1
for i in range(1,N+1):
    if i in A:
        continue
    if i==1:
        dp[1]=dp[0]
        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())
MOD = 10**9 + 7
F = [0]*(N+1)
for i in range(M):
    F[int(input())-1] = 1

a = 1; b = 0
for i in range(N):
    if F[i]:
        a, b = 0, a
    else:
        a, b = (a+b) % MOD, a
print(a)

Submission status: Accepted

Solution code:
p = 1000000007

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

u = [0]*(n+1)
F = [0]*(n+1)
for i in range(m):
	x = int(input())
	u[x] = 1

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

print(F[n])

Submission status: Accepted

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

MOD = 1000000007  # type: int

def solve(N: int, M: int, a: "List[int]"):
    dp = [0] * (N + 1)
    dp[0] = 1
    j = 0
    for i in range(N):
        if j < M and i == a[j]:
            dp[i] = 0
            j += 1
        if i + 1 <= N:
            dp[i + 1] += dp[i]
        if i + 2 <= N:
            #print(i + 2)
            dp[i + 2] += dp[i]
    ret = dp[N] % MOD
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [ int(next(tokens)) for _ in range(M) ]  # type: "List[int]"
    solve(N, M, a)

if __name__ == '__main__':
    main()