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:
import sys
INPUT = sys.stdin.readline

def SINGLE_INT(): return int(INPUT())
def MULTIPLE_INT_LIST(): return list(map(int, INPUT().split()))
def MULTIPLE_INT_MAP(): return map(int, INPUT().split())
def SINGLE_STRING(): return INPUT()
def MULTIPLE_STRING(): return INPUT().split()

MOD = 10 ** 9 + 7

N, M = MULTIPLE_INT_MAP()

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

for _ in range(M):
    floors[SINGLE_INT()] = -1

for i in range(2, N+1):

    if floors[i] == -1:
        continue

    if floors[i-2] == floors[i-1] == -1:
        floors[-1] = 0
        break

    if floors[i-2] > 0:
        floors[i] += floors[i-2]
    if floors[i-1] > 0:
        floors[i] += floors[i-1]

    floors[i] %= MOD

print(floors[-1])

Submission status: Accepted

Solution code:
MODULO = 1000000007


def solve(n, xs):
    dp = [0] * (n + 1)
    dp[0] = 1
    dp[1] = 1 if 1 not in xs else 0
    for i in range(2, n + 1):
        if i in xs:
            dp[i] = 0
        else:
            if i - 1 not in xs:
                dp[i] += dp[i - 1]
            if i - 2 not in xs:
                dp[i] += dp[i - 2]
        dp[i] %= MODULO
    return dp[n]
         


def main():
    n, m = (int(z) for z in input().split())
    xs = {int(input()) for _ in range(m)}
    res = solve(n, xs)
    print(res)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict


def read_input():
    n, m = map(int, input().split())

    d = defaultdict(lambda : True)
    for i in range(m):
        d[int(input())] = False

    return n, m, d


def submit():
    n, m, d = read_input()

    prev = 1
    prev_prev = 0
    curr = 1
    for i in range(1, n + 1):
        curr = 0
        if d[i - 1]:
            curr += prev
        if d[i - 2]:
            curr += prev_prev

        curr %= 1000000007

        prev_prev = prev
        prev = curr

    print(curr)


if __name__ == '__main__':
    submit()

Submission status: Accepted

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

memo = [None] * (N + 1)
memo[0] = 1

idx = 0
for pos in range(1, N + 1):
    if a[idx] == pos:
        memo[pos] = 0
        idx += 1
        continue
    else:
        if pos > a[idx]:
            idx += 1
        #
        if pos == 1:
            memo[1] = (memo[0]) % (10 ** 9 + 7)
        else:
            memo[pos] = (memo[pos - 2] + memo[pos - 1]) % (10 ** 9 + 7)

# print("#", memo)
print(memo[-1])

Submission status: Accepted

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N,M=MAP()
broken=[False]*(N+1)
for i in range(M):
    a=INT()
    broken[a]=True

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

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 i + 1 > n:continue
    if judge[i + 1]:dp[i+1] = (dp[i] +dp[i+1]) %1000000007
    if i + 2 > n:continue
    if judge[i + 2]:dp[i+2] = (dp[i] + dp[i+2]) %1000000007
print(dp[-1]%1000000007)

Submission status: Accepted

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

mod = 10**9+7
stair_set = set(range(0, N)[::-1])
stair_set = stair_set - set(a)
stair_list = list(stair_set)
stair_list.sort(reverse=True)

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

print(dp[0])

Submission status: Accepted

Solution code:

N,M=map(int,input().split())
dp=[0]*(10**5+1)
table=[0]*(10**5+1)
for i in range(M):
    a=int(input())
    table[i]=a

dp[0]=1

count=0
if table[count]==1:
    dp[1]=0
    count+=1
else:
    dp[1]=1

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


print(dp[N]%1000000007)

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 + 100)
dp[0] = 1
a_set = set(a_list)

for i in range(N):
    if i in a_set:
        continue
    else:
        dp[i + 1] += dp[i]
        dp[i + 1] %= mod
        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 = [int(input()) for i in range(M)]
B = [1]*(N+2)
for a in A:
    B[a] = 0
MOD = 10**9+7

if not B[0]:
    print(0)
    exit()

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
mod = 10**9 + 7
n, m = map(int, input().split())
ok = [True] * (n + 1)
if m > 0:
    a = [int(input()) for _ in range(m)]
    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:
import collections as c
ip = lambda : map(int, input().split())
# ##############
mod = 1e9+7
N,M = ip()
a = set()
for i in range(M):
    a.add(int(input()))
dp = [0]*(N+1)
dp[0] = 1
if 1 in a:
    pass
else:
    dp[1] = dp[0]
if N>1:
    for i in range(2,N+1):
        if i in a:
            continue
        dp[i] += (dp[i-2] + dp[i-1])%mod
        dp[i] = int(dp[i] % mod)
print(dp[N])

Submission status: Accepted

Solution code:
def solve():
    mod = 10**9+7
    N, M = map(int, input().split())
    k = [0]*(N+1)
    if M==0:
        k[0]=1
        k[1]=1
        for i in range(2, N+1):
            k[i]=(k[i-1]+k[i-2])%mod
        print(k[N]%mod)
        return
    a = [int(input()) for _ in range(M)]
    k[0]=1
    cnt = 0
    if a[0]!=1:
        k[1]=1
    else:
        cnt+=1
    for i in range(2, N+1):
        if cnt<M and i ==a[cnt]:
            cnt+=1
            continue
        else:   
            k[i]=(k[i-1]+k[i-2])%mod
    print(k[N]%mod)
    return
solve()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
br = [False] * (n+1)
for _ in range(m):
    x = int(input())
    br[x] = True

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

Submission status: Accepted

Solution code:
N, M = [int(c) for c in input().split()]
a = [int(input()) for _ in range(M)]+[-1]
j=0

dp = [0, 1]

for i in range(N):
    if i+1 == a[j]:
        dp.append(0)
        while i+1==a[j]:
            j+=1
    else:
        dp.append((dp[i]+dp[i+1]) % 1000000007)

print(dp[-1])

Submission status: Accepted

Solution code:
ll = lambda: list(map(int, input().split()))
testcases = 1
def abs(x):
    if x<0:
        return -x
    return x
# testcases = int(input())
for testcase in range(testcases):
    [n,m]=ll()
    broken=[1]*(n+1)
    for i in range(m):
        [ai]=ll()
        broken[ai]=0
    ans=[0]*(n+1)
    ans[0]=1
    ans[1]=1*broken[1]
    for i in range(2,n+1):
        ans[i] = (ans[i-1]*broken[i] + ans[i-2]*broken[i])%(10**9+7)
    # print(ans)
    print(ans[n])

Submission status: Accepted

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

tmp = [0 for _ in range(n + 1)]
tmp[0] = 1

for i in range(1, n + 1):
    if a[i] == 1:
        tmp[i] = 0
    else:
        if i - 2 >= 0:
            tmp[i] += tmp[i - 2]
        if i - 1 >= 0:
            tmp[i] += tmp[i - 1]
        tmp[i] %= 1000000007

print(tmp[n] % 1000000007)

Submission status: Accepted

Solution code:

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

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-2]
    dp[i] %= 1000000007


print(dp[N])

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
a = [int(input()) for i in range(m)]
MOD = 10**9 + 7
memo = {}
for i in range(n+1):
    memo[i] = 1
for i in range(m):
    memo[a[i]] = 0

dp = [0] * (n+1)

dp[0] = 1
dp[1] = memo[1]

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

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7
N, M = map(int, input().split())
F = [0, 1]
fib_minus1 = 1
fib_minus2 = 0
for i in range(N):
	fib = (fib_minus1 + fib_minus2) % mod
	F.append(fib)
	fib_minus2 = fib_minus1
	fib_minus1 = fib
x = 1
a = -1
for i in range(M):
	b = int(input())
	x = (x * F[b - a - 1]) % mod
	a = b
x = (x * F[N - a]) % mod
print(x)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# coding: utf-8

import sys
def input(): return sys.stdin.readline().strip()

MOD = 10**9 + 7
# N = int(input())
# L = [int(x) for x in input().split()]
N, M = map(int, input().split())
# S = input()

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

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

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

print(dp[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)


def slv(N, M, A):
    dp = [0] * (N+10)
    b = [False] * (N+10)
    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:

def ispossible(a):
    d = [a[i] - a[i-1] for i in range(1, len(a))]
    return not 1 in d


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

    MOD = 10**9+7

    if not ispossible(a):
        print(0)
        return

    s = [1] * (N+1)

    a = set(a)

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

    for i in range(2, N+1):
        if i in a:
            continue

        s[i] = 0
        if i-1 not in a:
            s[i] += s[i-1]
            s[i] %= MOD
        if i-2 not in a:
            s[i] += s[i-2]
            s[i] %= MOD

    print(s[N] % MOD)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M = list(map(int,input().split()))
A = []
S = [0 for i in range(N+1)]
S[0] = 1
for i in range(M):
  s = int(input())
  A.append(s)
  S[s] = -1
for i in range(N+1):
  if S[i] == -1:
    continue
  if i+1 <= N:
    if S[i+1] == 0:
      S[i+1] = S[i]
    elif S[i+1] > 0:
      S[i+1] += S[i]
  if i+2 <= N:
    if S[i+2] == 0:
      S[i+2] = S[i]
    elif S[i+2] > 0:
      S[i+2] += S[i]
print (S[-1]%1000000007)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
div = 10**9+7
A = [0 for i in range(N+1)]
A[0] = 1
for i in range(M):
    a = int(input())
    A[a] = -1
for i in range(N):
    if A[i] == -1:
        continue
    now = A[i]
    if A[i+1] != -1:
        A[i+1] += now * 1
    if i < N-1 and A[i+2] != -1:
        A[i+2] += now * 1
# print(A)
print(A[-1] % div)

Submission status: Accepted

Solution code:
#

import itertools
from collections import Counter
from collections import defaultdict
import bisect
from heapq import heappush, heappop

def main():
    MOD = 1000000007

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

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

    # print(dp)
    print(dp[N] % MOD)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,M = map(int,input().split(' '))
MOD = 1000000007
a = [int(input()) for i in [0]*M]

a.append(-1)
a.append(N+1)

a.sort()

ds = [a[i+1] - a[i] - 1 for i in range(0,M+1)]

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

k = max(ds)

a = [0,1]
for i in range(2,k+1):
	a.append((a[i-2]+a[i-1]) % MOD)

ans = 1

for d in ds:
	ans = (ans * a[d] ) % MOD

print(ans)

Submission status: Accepted

Solution code:
N,M = (int(x) for x in input().split())
a_arr = [-1]
for _ in range(M):
    a_arr.append(int(input()))
a_arr.append(N+1)

n_dp_size = N+3
n_dp = [0]*(n_dp_size)
n_dp[0] = 1
n_dp[1] = 0
n_dp[2] = 1
for i in range(3,n_dp_size):
    n_dp[i] = (n_dp[i-2]+n_dp[i-1]) % 1000000007

ans = 1
for i in range(1,len(a_arr)):
    a_diff = a_arr[i]-a_arr[i-1]
    ans *= n_dp[a_diff]
    ans = ans % 1000000007

print(ans)

Submission status: Accepted

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

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

l = []
pre = -1
for x in a:
    l.append(Fib(x-pre-1 +1))
    pre = x

l.append(Fib(n-pre +1))

if l.count(0) > 0:
    print(0)
    exit()

res = 1
for x in l:
    res *= x

print(res % 1000000007)

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

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


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


print(L[N] % 1000000007)

Submission status: Accepted

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

import sys

class bigint:
    def __init__(self,n,mod=10**9+7):
        self.n = n % mod
        self.mod = mod
        return
    #
    def __str__(self):
        return str(self.n)
    #
    def __add__(self,other):
        assert self.mod==other.mod, "modulos of the two not match"
        return bigint(self.n+other.n,self.mod)
    #
    def __iadd__(self,other):
        assert self.mod==other.mod, "modulos of the two not match"
        self.n = (self.n + other.n) % self.mod
        return self
    #
    def __sub__(self,other):
        assert self.mod==other.mod, "modulos of the two not match"
        return bigint(self.n-other.n,self.mod)
    #
    def __isub__(self,other):
        assert self.mod==other.mod, "modulos of the two not match"
        self.n = (self.n - other.n) % self.mod
        return self
#
#::::::::::::::::::::::::::::::::::::::::::::::::::
n,m = [ int(x) for x in sys.stdin.readline().split() ]
step= [bigint(0)] * (n+1)
wall= [False] * (n+1)
for i in range(m):
    am = int( sys.stdin.readline() )
    wall[am] = True
#
step[0]= bigint(1)
if not wall[1]: step[1]= bigint(1)
#
for i in range(2,n+1):
    if wall[i]: continue
    s1= step[i-1]
    s2= step[i-2]
    if s1==s2==0: break
    step[i] = s1 + s2
#
print( step.pop() )

Submission status: Accepted

Solution code:
MOD = 1000000007

N, M = map(int, input().split())
A = [int(input()) for _ in range(M)] + [N + 10]

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

print(dp[-1] % MOD)

Submission status: Accepted

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

class comb():
  F = [1, 1]
  Fi = [1, 1]
  I = [0, 1]
  def __init__(self, num, mod):
    self.MOD = mod
    for i in range(2, num + 1):
      self.F.append((self.F[-1] * i) % mod)
      self.I.append(mod - self.I[mod % i] * (mod // i) % mod)
      self.Fi.append(self.Fi[-1] * self.I[i] % mod)
  def com(self, n, k):
    if n < k: return 0
    if n < 0 or k < 0: return 0
    return self.F[n] * (self.Fi[k] * self.Fi[n - k] % self.MOD) % self.MOD


MOD = 10 ** 9 + 7

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

com = comb(N, MOD)
ans = 1
x = 0
a = a + [N + 1]

for i in a:
  t = i - 1 - x
  at = 0
  for j in range(t // 2 + 1):
    k = t - j
    at = at + com.com(k, j) % MOD
  ans = ans * at % MOD
  x = i + 1
  

print(ans)

Submission status: Accepted

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

a = [0] * (n+1)
for i in x:
    a[i] = 1

dp = [1]

if a[1] == 1:
    dp.append(0)
else :
    dp.append(1)

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

print(dp[n])

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):
    temp = int(input())
    a[temp] = 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[-1])

Submission status: Accepted

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

aa = {}
for _ in range(m):
  aa[int(input())] = True

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

if n == 0:
  print(1)
  exit(0)

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

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

Submission status: Accepted

Solution code:
n, m = list(map(int, input().split(' ')))
arr  = set()
for _ in range(m):
    x = int(input())
    arr.add(x)

MOD = int(1e9) + 7

w = [0 for _ in range(n + 1)]

if 0 not in arr:
    w[0] = 1

for i in range(n + 1):
    if i in arr:
        continue

    if i - 1 >= 0 and i - 1 not in arr:
        w[i] += w[i-1]

    if i - 2 >= 0 and i - 2 not in arr:
        w[i] += w[i-2]
    
    w[i] %= MOD


print(w[n])

Submission status: Accepted

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

for i in range(1, N + 1):
    if i == a[a_flag]:
        dp.append(0)
        a_flag += 1
        continue
    dp.append(dp[i - 1] + dp[i])

print(dp[N + 1] % 1000000007)

Submission status: Accepted

Solution code:
#
import sys
import math
import numpy as np
import itertools

MOD = 1000000007
# いくつか入力
n,m = (int(i) for i in input().split())  

# n行の数をリストに
a = [int(input()) for i in range(m)] 
a.append(9999999) # sentinel
dame=0

b=[1]
if a[dame]==1:
    dame += 1
    b.append(0)
else:
    b.append(1)

for i in range(2,n+1):
    if i==a[dame]:
        dame += 1
        b.append(0)
    else:
        c=(b[i-1]+b[i-2]) % MOD
        b.append(c)

#print(a,b)
print(b[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+1]+dp[i])%1000000007
    if ((i+2)<(n+1)) and a[i+2]:
        dp[i+2]+=(dp[i+2]+dp[i])%1000000007
print(dp[n])

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]%=1000000007
print(L[n])

Submission status: Accepted

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

arr.append(10**10)

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

tmp = 0

if arr[0] == 1:
    dp[1] = 0
    tmp += 1
else:
    dp[1] = 1

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

print(dp[N]%(1000000007))

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 + 100)
dp[0] = 1
a_set = set(a_list)

for i in range(N+10):
    if i in a_set:
        continue
    else:
        dp[i + 1] += dp[i]
        dp[i + 1] %= mod
        dp[i + 2] += dp[i]
        dp[i + 2] %= mod

print(dp[N] % mod)

Submission status: Accepted

Solution code:
from collections import defaultdict


def read_input():
    n, m = map(int, input().split())

    d = defaultdict(lambda : True)
    for i in range(m):
        d[int(input())] = False

    return n, m, d




def submit():
    n, m, d = read_input()

    prev = 1
    prev_prev = 0
    for i in range(1, n + 1):
        curr = 0
        if d[i - 1]:
            curr += prev
        if d[i - 2]:
            curr += prev_prev

        curr %= 1000000007

        prev_prev = prev
        prev = curr

    print(curr)


if __name__ == '__main__':
    submit()

Submission status: Accepted

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

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

dp[1] = 1

MOD = 1000000007

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

print(dp[N+1])

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]
print(dp[n]%1000000007)

Submission status: Accepted

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

if not B[0]:
    print(0)
    exit()

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

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


n, m = li()
a = [ni() for _ in range(m)]
aset = set(a)

MOD = 10**9+7

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

for i in range(n):
    if i+1 in aset:
        continue

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

    else:
        dp[i+1] = dp[i] + dp[i-1]
        dp[i+1] %= MOD

print(dp[n])

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 + 2)
for i in range(m):
    tmp = ni()
    dp[tmp] = -1
dp[0] = 1
for i in range(n):
    if i + 1 <= n:
        if dp[i + 1] != -1 and dp[i] != -1:
            dp[i + 1] += dp[i] % mod
            dp[i + 1] %= mod
    if i + 2 <= n:
        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:
import sys
input = sys.stdin.readline
from sys import setrecursionlimit
setrecursionlimit(10**9)

def inpl(): return list(map(int, input().split()))
N, M = inpl()
MOD = 10**9 + 7
A = [1]*(N+3)
A[N+2] = 0
A[N+1] = 0
for _ in range(M):
    a = int(input())
    A[a] = 0

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

Submission status: Accepted

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

MOD = 1000000007
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1 if 1 not in a else 0
for i in range(2, n + 1):
    if i in a:
        dp[i] = 0
        continue
    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())
A=[]
for i in range(M):
    a=int(input())
    if i!=0 and a==A[-1]:
        continue
    if i!=0 and a==A[-1]+1:
        print(0)
        quit()
    A.append(a)
INF=10**9+7
B=[]
tmp=0
A.append(N+1)
for i in A:
    B.append(i-tmp)
    tmp=i+1
dp=[0]*(N+3)
dp[0]=1
dp[1]=1
dp[2]=1
for i in range(2,N+2):
    dp[i+1]=dp[i]+dp[i-1]
    dp[i+1]%=INF
ans=1
for i in B:

    ans*=dp[i]
    ans%=INF
print(ans)

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+10000)]
    for i in range(m):
        a = I()
        f[a] = 0
    dp = [0 for i in range(n+10000)]
    dp[0] = 1
    for i in range(n):
        if f[i+1]:
            dp[i+1] += dp[i]
            dp[i+1] %= mod
        if f[i+2]:
            dp[i+2] += dp[i]
            dp[i+2] %= mod
    print(dp[n])
    return

#D
def D():
    h,w = LI()
    s = SR(h)
    vi = [[0 for j in range(w)] for i in range(h)]
    ho = [[0 for j in range(w)] for i in range(h)]
    q = deque()
    for y in range(h):
        for x in range(w):
            if s[y][x] == "#":
                l = len(q)
                while q:
                    i,j = q.pop()
                    vi[i][j] = l
            else:
                q.append((y,x))
        l = len(q)
        while q:
            i,j = q.pop()
            vi[i][j] = l
    for x in range(w):
        for y in range(h):
            if s[y][x] == "#":
                l = len(q)
                while q:
                    i,j = q.pop()
                    ho[i][j] = l
            else:
                q.append((y,x))
        l = len(q)
        while q:
            i,j = q.pop()
            ho[i][j] = l
    ans = 0
    for y in range(h):
        for x in range(w):
            ans = max(ans,vi[y][x]+ho[y][x]-1)
    print(ans)
    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 = 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 + 5)]

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