Problem:


Score : 300 points

Problem Statement

There is a staircase with N steps. Takahashi is now standing at the foot of the stairs, that is, on the 0-th step.
He can climb up one or two steps at a time.

However, the treads of the a_1-th, a_2-th, a_3-th, \ldots, a_M-th steps are broken, so it is dangerous to set foot on those steps.

How many are there to climb up to the top step, that is, the N-th step, without setting foot on the broken steps?
Find the count modulo 1\ 000\ 000\ 007.

Constraints

1 \leq N \leq 10^5

0 \leq M \leq N-1

1 \leq a_1 < a_2 <  ...  < a_M \leq N-1

Input

Input is given from Standard Input in the following format:

N M
a_1
a_2
 .
 .
 .
a_M

Output

Print the number of ways to climb up the stairs under the condition, modulo 1\ 000\ 000\ 007.

Sample Input 1

6 1
3

Sample Output 1

4

There are four ways to climb up the stairs, as follows:

0 \to 1 \to 2 \to 4 \to 5 \to 6

0 \to 1 \to 2 \to 4 \to 6

0 \to 2 \to 4 \to 5 \to 6

0 \to 2 \to 4 \to 6

Sample Input 2

10 2
4
5

Sample Output 2

0

There may be no way to climb up the stairs without setting foot on the broken steps.

Sample Input 3

100 5
1
23
45
67
89

Sample Output 3

608200469

Be sure to print the count modulo 1\ 000\ 000\ 007.



Sample input:
6 1
3


Sample output:
4

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-


MOD = 1000000007


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

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

Submission status: Accepted

Solution code:
import sys
import collections
ns = lambda: sys.stdin.readline().rstrip()
ni = lambda: int(ns())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
nsm = lambda: map(str, sys.stdin.readline().split())
nsl = lambda: list(nsm())

mod = 1000000007

n, m = nm()
dp = [0] * (n + 1)
for i in range(m):
    tmp = ni()
    dp[tmp] = -1
dp[0] = 1
for i in range(n):
    if i + 1 < n + 1:
        if dp[i + 1] != -1 and dp[i] != -1:
            dp[i + 1] += dp[i] % mod
            dp[i + 1] %= mod
    if i + 2 < n + 1:
        if dp[i + 2] != -1 and dp[i] != -1:
            dp[i + 2] += dp[i] % mod
            dp[i + 2] %= mod
print(dp[n] % mod)

Submission status: Accepted

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

if A and A[-1] == 1:
    dp = [1,0]
    while A and A[-1] == 1:
        A.pop()
else:
    dp = [1,1]


for i in range(2,N+1):
    if A and A[-1] == i:
        dp.append(0)
        while A and A[-1] == i:
            A.pop()
    else:
        dp.append((dp[-1]+dp[-2])%MOD)

print(dp[-1])

Submission status: Accepted

Solution code:
#import sys
#from collections import deque
#from collections import defaultdict
#import math
#sys.setrecursionlimit(20000000)
#input = sys.stdin.readline
n,m = map(int,input().split())
a = [int(input()) for i in range(m)]
a = set(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[i] = 1
                continue
        dp[i] = dp[i-1] + dp[i-2]
        dp[i] %= mod
print(dp[n]%mod)

Submission status: Accepted

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

Submission status: Accepted

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


dp = [0] * (N + 100)
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
mod = 10**9 + 7
n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
ok = [True] * (n + 1)
for x in a:
    ok[x] = False
dp = [0] * (n + 1)
dp[0] = 1
for i in range(n + 1):
    if i > 0 and ok[i - 1]:
        dp[i] = (dp[i] + dp[i - 1]) % mod
    if i > 1 and ok[i - 2]:
        dp[i] = (dp[i] + dp[i - 2]) % mod
print(dp[n])

Submission status: Accepted

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

Submission status: Accepted

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

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

next_a = a.pop(0)

for i in range(N):
    if next_a == i:
        dp[i] = 0
        next_a = a.pop(0)
    else:
        dp[i+1] += dp[i]
        dp[i+2] += dp[i]
print(dp[N]%1000000007)

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:
        if l[i+2]!=-1:l[i+2]=(l[i+2]+l[i])%mod
print(l[n])

Submission status: Accepted

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

def solve():
    n, m = map(int, input().split())
    am = set([int(input()) for i in range(m)])
    ans = [0] * (n + 1000)
    ans[0] = 1
    md = (10 ** 9) + 7
    for i in range(n):
        if (i + 1) not in am:
            ans[i + 1] = (ans[i] + ans[i + 1]) % md
        if (i + 2) not in am:
            ans[i + 2] = (ans[i] + ans[i + 2]) % md
    print(ans[n])

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import bisect
from operator import itemgetter
import math
import functools
import itertools
import numpy as np
import sys
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N,M = IL()
a = [I() for i in range(M)]

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

for i in a:
  dp[i] = -1

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

Submission status: Accepted

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

cache = dict()
def n_steps(n):
    if n not in cache:
        if n in As:
            value = 0
        
        elif n in {0, 1}:
            value = 1

        else:
            value = n_steps(n - 1) + n_steps(n - 2)
            value %= MOD

        cache[n] = value
    return cache[n]

for i in range(N):
    n_steps(i)
print(n_steps(N))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
if m > 0:
    a = {int(input()): None for i in range(m)}
else:
    a = {}
dp = [0] * (n + 1)
dp[0] = 1
MOD = 10 ** 9 + 7
if m == 0 or 1 not in a:
    dp[1] = 1
for i in range(2, n + 1):
    if i - 1 not in a:
        dp[i] += dp[i - 1]
    if i - 2 not in a:
        dp[i] += dp[i - 2]
    dp[i] %= MOD
print(dp[-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
a = set([int(input()) for _ in range(m)])
dp = [0] * (n + 100)
dp[0] = 1
for i in range(n):
    if i + 1 <= n and 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] % (10 ** 9 + 7))

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)}

dp = [0] * (N + 1000)
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())
judge = [True for i in range(n+1)]
for i in range(m):
    judge[int(input())] = False
dp = [0]*(n+1)
dp[0] = 1
for i in range(n):
    if judge[i + 1]:dp[i+1] += dp[i]
    if i + 2 > n:continue
    if judge[i + 2]:dp[i+2] += dp[i]
print(dp[-1]%1000000007)

Submission status: Accepted

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


MOD = 10**9 + 7

N, M = inpl()
A = [False for i in range(N + 1)]
for i in range(M):
    a = int(input())
    A[a] = True
p = 1
pp = 0
ans = 0

for i in range(1, N + 1):
    if A[i] is True:
        pp = p
        p = 0
    else:
        ans = (p + pp) % MOD
        pp = p
        p = ans
    # print(ans)

print(ans % MOD)

Submission status: Accepted

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

mod = 10 ** 9 + 7

dp = [0] * (N + 3)
dp[0] = 1
not_use = [False] * (N + 3)
for a in a_list:
    not_use[a] = True

for i in range(N+1):
    not_u = not_use[i]
    if not_u:
        continue
    else:
        if i < N:
            dp[i + 1] += dp[i]
            dp[i + 1] %= mod
        if i < N - 1:
            dp[i + 2] += dp[i]
            dp[i + 2] %= mod

print(dp[N] % mod)

Submission status: Accepted

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

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

for _ 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,raw_input().split())
a = {}
for i in xrange(m):
	step = int(raw_input())
	a[step] = 1
dp = [1]*(n+1)
mod = 10**9+7
for i in xrange(1,n+1):
	if i in a:
		dp[i] = 0
	elif i == 1:
		dp[i] = 1
	else:
		dp[i] = dp[i-1] + dp[i-2]
print dp[n]%mod

Submission status: Accepted

Solution code:
def gcd_core(a, b):
    if b == 0:
        return a
    else:
        return gcd_core(b, a % b)


def gcd(arr):
    g = gcd_core(arr[0], arr[1])
    for i in range(2, len(arr)):
        g = gcd_core(g, arr[i])
    return g




n,m = map(int,input().split())
a = {}
base = 1000000007
for i in range(m):
    a[int(input())] = 0
steps = [0 for i in range(n+2)]
steps[0] = 0
steps[1] = 1

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

#print(steps)
print(steps[-1])

Submission status: Accepted

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

import sys
sys.dont_write_bytecode = True
stdin = sys.stdin
input = stdin.readline
sys.setrecursionlimit(10000000)

#import numpy as np
#import scipy as sp

# Python 3 modules: https://docs.python.org/3/library/

import math, itertools, operator
from math import *
from math import factorial as fact
from operator import itemgetter, attrgetter
from itertools import permutations, combinations
from functools import reduce, lru_cache
# Use scipy for stats: https://docs.scipy.org/doc/scipy/reference/stats.html
# Before Python 3.5.  Import from math after it.
from fractions import gcd
from fractions import Fraction as Frac

inf = float('inf')

def lcm(a, b):
    return a * b // gcd(a,b)

def perm(a, b):
    import scipy.special
    return scipy.special.perm(a, b, exact = True)

def comb(a, b):
    import scipy.special
    return scipy.special.comb(a, b, exact = True)

def dfact(n):
    import scipy.special
    return scipy.special.factorial2(n, exact = True)

def prod(l):
    return reduce(operator.mul, l)

def input_ints(func = input, sep = None, conv = int):
    return list(map(conv, func().split(sep = sep)))

################################################################################

N, M = list(map(int, input().split()))
A = [None for i in range(M)]
for i in range(M):
    A[i] = int(input())
#A = list(map(int, stdin.read().split()))

BROKEN = [False for i in range(N)]
for a in A:
    BROKEN[a] = True

@lru_cache(maxsize = None)
def dp(cur):
    if cur > N:
        return 0
    if cur == N:
        return 1
    if BROKEN[cur]:
        return 0
    return dp(cur + 1) + dp(cur + 2)

print(dp(0) % 1000000007)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
b_list=[True]*(n+1)
for i in range(m):
    a=int(input())
    b_list[a]=False
dp=[0]*(n+1)
dp[0]=1
Mod=10**9+7
for i in range(1,n+1):
    if b_list[i]:
        if i>=2:
            if b_list[i-2]:
                dp[i]=(dp[i]+dp[i-2])%Mod
            if b_list[i-1]:
                dp[i]=(dp[i]+dp[i-1])%Mod
            if not b_list[i-2] and not b_list[i-1]:
                b_list[i]=False
        else:
            dp[i]=dp[0]
    else:
        pass
print(dp[n])

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
a = [True] * (N + 3)
a[N + 1] = False
a[N + 2] = False

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

MOD = 10 ** 9 + 7

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

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 + 5)]

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,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
Max = sys.maxsize
def l():
	return list(map(int,input().split()))
def m():
	return map(int,input().split())
def s(x):
	a = []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa == x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x):
	return " ".join(map(str,x))
n,p = m()


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

for i in range(p):
	k = int(input())
	dp[k] = -1

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

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7

N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
bl = [True] * (N + 10)
for aa in a:
    bl[aa] = False

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

for step_frm in range(N):
    if bl[step_frm]:
        dp[step_frm + 2] += dp[step_frm]
        dp[step_frm + 2] %= mod
        dp[step_frm + 1] += dp[step_frm]
        dp[step_frm + 1] %= 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 = [0] * (n + 1)
dp[0] = 1

j = 0
for i in range(1, n + 1):
    if j < m and i == arr[j]:
        dp[i] = 0
        j += 1
        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 = 1000000007
 

a = set()

for m in range(M):
    aa = int(input())
    a.add(aa)

x = [0 for n in range(N+1)]
x[0] = 1
for n in range(1,N+1):
    if n in a or (n-1 in a and n-2 in a):
        x[n] = 0
    elif n-1 in a:
        x[n] = x[n-2]%MOD
    elif n-2 in a:
        x[n] = x[n-1]%MOD
    else:
        x[n] = (x[n-1] + x[n-2])%MOD

print(x[N])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)


m = Mod(10**9 + 7)


@mt
def slv(N, M, A):
    dp = [0] * (N+3)
    b = [False] * (N+3)
    for a in A:
        b[a] = True

    dp[0] = 1
    for i in range(N):
        if not b[i+1]:
            dp[i+1] = m.add(dp[i+1], dp[i])
        if not b[i+2]:
            dp[i+2] = m.add(dp[i+2], dp[i])
    return dp[N]


def main():
    N, M = read_int_n()
    A = [read_int() for _ in range(M)]
    print(slv(N, M, A))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
A=[int(input()) for i in range(M)]
mod=10**9+7
dp=[0]*(N+1)
dp[0]=1
j=0
for i in range(1,N+1):
    if j<M and i==A[j] :
        j+=1
        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:
# -*- coding: utf-8 -*-
import heapq
import math
import sys

MOD = 1000000007

N, M = [int(a) for a in input().split()]
N += 1
a_s = []
for n in range(M):
    a = int(input())
    a_s.append(a)
    if a == N-1:
        print(0)
        exit()

a_set = set(a_s)

dp = [0 if i not in a_set else None for i in range(N)]
dp[0] = 1
for i in range(N):
    val = dp[i]
    if val is None:
        continue
    if i + 1 < N and dp[i+1] is not None:
        dp[i+1] += dp[i]
        dp[i+1] %= MOD
    if i + 2 < N and dp[i+2] is not None:
        dp[i+2] += dp[i]
        dp[i+2] %= MOD

print(dp[N-1])

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:

nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

N, M = nl()
A = set()
for i in range(M):
    A.add(n())

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

print(dp[N])

Submission status: Accepted

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

dp = [0 for i in range(n+5)]
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:
#!/usr/bin/env pypy
from __future__ import division, print_function

import os
import sys
from __builtin__ import xrange as range
from cStringIO import StringIO
from future_builtins import ascii, filter, hex, map, oct, zip
from io import IOBase

import __pypy__

MOD = 10**9 + 7


def main():
    n, m = map(int, input().split())
    broken = [False] * (n + 2)
    for _ in range(m):
        broken[int(input())] = True

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

    for x in reversed(range(n)):
        if not broken[x + 1]:
            dp[x] = (dp[x] + dp[x + 1]) % MOD
        if not broken[x + 2]:
            dp[x] = (dp[x] + dp[x + 2]) % MOD

    print(dp[0])


# region fastio

BUFSIZE = 8192


class FastI(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = StringIO()
        self.newlines = 0

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count("\n") + (not b)
            ptr = self._buffer.tell()
            self._buffer.seek(0, 2), self._buffer.write(b), self._buffer.seek(ptr)
        self.newlines -= 1
        return self._buffer.readline()


class FastO(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = __pypy__.builders.StringBuilder()
        self.write = lambda s: self._buffer.append(s)

    def flush(self):
        os.write(self._fd, self._buffer.build())
        self._buffer = __pypy__.builders.StringBuilder()


def print(*args, **kwargs):
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


sys.stdin, sys.stdout = FastI(sys.stdin), FastO(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
MOD = 10 ** 9 + 7
Broken = [0] * (N + 2)
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:
N, M = list(map(int, input().split(" ")))
A = {int(input()) for _ in range(M)}

memo = [0] * (N + 1)
memo[0] = 0 if 0 in A else 1
memo[1] = 0 if 1 in A else 1

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

print(memo[N] % 1000000007)

Submission status: Accepted

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

Submission status: Accepted

Solution code:

mod = 1000000007

n,m = map(int,input().split())
vals = [0 for i in range(n+2)]
for i in range(m):
	vals[int(input())] = 1

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

Submission status: Accepted

Solution code:
import numpy as np
words = lambda t : list(map(t, input().split()))
n,m = words(int)

ss = [True] * (n+1)
dp = [0] * (n+1)
MOD = 1000000007


for i in range(m):
    k = int(input())
    ss[k] = False

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

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

#print(dp)
print(dp[n])

Submission status: Accepted

Solution code:
#!/usr/bin/env pypy
from __future__ import division, print_function

import os
import sys
from __builtin__ import xrange as range
from cStringIO import StringIO
from future_builtins import ascii, filter, hex, map, oct, zip
from io import IOBase

import __pypy__


def main():
    MOD = 10**9 + 7
    N, M = read_int_array()
    dp = [0]*(N+1)
    dp[0] = dp[1] = 1

    for _ in range(M):
        dp[read_int()] = -1

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



# region fastio

BUFSIZE = 8192


class FastI(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = StringIO()
        self.newlines = 0

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count("\n") + (not b)
            ptr = self._buffer.tell()
            self._buffer.seek(0, 2), self._buffer.write(b), self._buffer.seek(ptr)
        self.newlines -= 1
        return self._buffer.readline()


class FastO(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = __pypy__.builders.StringBuilder()
        self.write = lambda s: self._buffer.append(s)

    def flush(self):
        os.write(self._fd, self._buffer.build())
        self._buffer = __pypy__.builders.StringBuilder()


def print(*args, **kwargs):
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


sys.stdin, sys.stdout = FastI(sys.stdin), FastO(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

read = input
read_int = lambda: int(input())
read_array = lambda sep=None, maxsplit=-1: input().split(sep, maxsplit)
read_int_array = lambda: [int(a) for a in read_array()]

# endregion

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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+9999) # sentinel
    pattern = [1]
    for i in range(1, N+10):
        pattern.append(0)
    pointer = 0
    for i in range(0, N+2):
        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 sys
input = sys.stdin.readline

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

ANSLIST=[0]*(N+4)
ANSLIST[0]=1

for i in range(N):
    if not(i+1 in A):
        ANSLIST[i+1]=(ANSLIST[i+1]+ANSLIST[i])%mod

    if not(i+2 in A):
        ANSLIST[i+2]=(ANSLIST[i+2]+ANSLIST[i])%mod

    #print(ANSLIST)
    #print()

print(ANSLIST[N])

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
for i in range(1,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 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:
N, M = map(int, input().split())
a = []
stair = [1 for i in range(N+1)]
for i in range(M):
    stair[int(input())] = 0

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

dp[0] = 1

MOD = 1000000007

for i in range(1, N+1):
    if stair[i] == 1:
        dp[i] = (dp[i-1] + dp[i-2]) % 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(100000 + 5)]

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

Submission status: Accepted

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

Submission status: Accepted

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

for i in range(N):
  if a[i]==-1:
    continue
  if a[i+1]!=-1:
    a[i+1]+=a[i]
    a[i+1]%=MOD
  if i+2<=N and a[i+2]!=-1:
    a[i+2]+=a[i]
    a[i+2]%=MOD
print(a[N])

Submission status: Accepted

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

dp[0] = 1
if 1 not in brokens:
    dp[1] = 1

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

print(dp[-1])

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
way = [1 for _ in range(n+1)]
for i in range(m):
  ai = int(input())
  way[ai] = 0
for i in range(2,n+1):
  if way[i] != 0:
    way[i] = (way[i-1]+way[i-2])%1000000007
print(way[n])