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/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 = read_int_array()
    nums = []
    for _ in range(M):
        nums.append(read_int())
    print(solve(N, nums))


def solve(N, nums):
    dp = [0] * (N + 1)
    dp[0] = 1
    broken = set(nums)
    for i in range(1, N + 1):
        if i in broken:
            dp[i] = 0
            continue
        dp[i] = dp[i - 1]
        if i > 1:
            dp[i] = (dp[i] + dp[i - 2]) % MOD
    return dp[N]


import math
import random


def always_true(*args, **kwargs):
    return True


def generate_nums(n, min, max, check_if_good=always_true):
    while True:
        numSet = set()
        nums = []
        for _ in range(n):
            while True:
                x = random.randint(min, max)
                if x not in numSet:
                    numSet.add(x)
                    nums.append(x)
                    break
        if check_if_good(nums):
            return nums


def main2():
    for _ in range(1000000):
        N = random.randint(1, 10**5)
        M = random.randint(0, min(3, N-1))
        nums = generate_nums(M, 1, N-1, lambda nums: len(nums) == len(set(nums)))
        print(solve(N, nums), flush=True)


# 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  = [int(x)for x in input().split()]

a = [0 for i in range(N+8)]

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

DP = [0 for i in range(N+8)]
DP[0] = 1
DP[1] = 1
if a[1] == 1:
    DP[1] = 0
for i in range(2,N+1):
    if a[i] == 0:
        DP[i] = (DP[i-2]+DP[i-1])
        if DP[i] >1000000007:
            DP[i] %=1000000007
    else:
        pass
#print(DP)
print(DP[N])

Submission status: Accepted

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

Submission status: Accepted

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

mod = int(1e9+7)

if N == 1:
  print(1)
  exit()

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

## 調べるべき階段のみ取り出す
stairs = set(range(2,N+1)) - set(A)

## 1段目の処理
if len(A) > 0 and A[0] == 1:
  solver[1] = 0
else:
  solver[1] = 1

for i in stairs: ## i段目の処理
    var = (solver[i-2] + solver[i-1]) % mod
    solver[i] = var
    
print(solver[-1])

Submission status: Accepted

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

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

waru=1000000007

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

ans=1
now=0
for i in range(m):
    ans*=Fib(a[i]-now+1)
    now=a[i]+1
ans*=Fib(n-now+2)
print(ans%waru)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
a_set = set()
for i in range(M):
    a_set.add(int(input()))
mod = 1000000007

ways = [0] * (N + 1)
if N not in a_set:
    ways[N] = 1
if N - 1 not in a_set:
    ways[N - 1] = 1

for n in reversed(range(N - 1)):
    if n in a_set:
        continue
    ways[n] = (ways[n + 1] + ways[n + 2]) % mod
print(ways[0])

Submission status: Accepted

Solution code:
from collections import defaultdict

N, M = map(int, input().split())
aList = [int(input()) for _ in range(M)]
mod = 1000000007

dp = defaultdict(int)
dp[0] = 1
for i, a in enumerate(aList):
    dp[a] = None

for i in range(1, N + 1):
    if dp[i] != None:
        if i >= 1 and dp[i - 1] != None:
            dp[i] += dp[i - 1]
        if i >= 2 and dp[i - 2] != None:
            dp[i] += dp[i - 2]

        dp[i] %= mod

if dp[N] == None:
    dp[N] = 0
print(dp[N])

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:
N, M = map(int, input().split())
a = {}
for i in range(M):
    a[int(input())] = True

comb = [0] * (N + 1)
comb[0] = 1
comb[1] = 0 if 1 in a else 1

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

print(comb[N])

Submission status: Accepted

Solution code:
import collections

BIGINT = int(1e9 + 7)

N, M = map(int, input().split())
invalid = {int(input()) for _ in range(M)}
dp = collections.defaultdict(int)
dp[0] = 1
for i in range(1, N + 1):
    if i in invalid:
        dp[i] = 0
    else:
        dp[i] = (dp[i - 1] + dp[i - 2]) % BIGINT

print(dp[N])

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

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

print(dp[N] % mod)

Submission status: Accepted

Solution code:
import sys

def main():
    input = sys.stdin.readline
    MOD = 10**9 + 7
    N, M = map(int, input().split())
    A = [int(input()) for _ in range(M)]
    is_safe = [True] * (N+1)
    for a in A:
        is_safe[a] = False

    dp = [0] * (N+2)
    dp[1] = 1
    for i in range(N):
        step = i+2
        if is_safe[i+1]:
            dp[step] = dp[step-1] + dp[step-2]
            dp[step] %= MOD
        else:
            dp[step] = 0

    return dp[N+1]


if __name__ == '__main__':
    print(main())

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())
	if b > a + 1:
		x = (x * F[b - a - 1]) % mod
		a = b
	elif b == a + 1:
		x = 0
x = (x * F[N - a]) % mod
print(x)

Submission status: Accepted

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

broken = [N+1]*(M+1)
ans = [0]*(N+1)
broken_pointer = 0
for i in range(M):
    a = int(input())
    broken[i] = a

ans[0] = 1
if(broken[0] == 1):
    ans[1] = 0
    broken_pointer += 1
else:
    ans[1] = 1

for i in range(2,N+1):
    if (broken[broken_pointer] == i):
        ans[i] = 0
        broken_pointer += 1
    else:
        ans[i] = ans[i-1] + ans[i-2]
    

print(ans[N]%1000000007)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
ans = 1
a = -1
if M > 0:
    a = int(input())
    ans = 1
    b = 0
    for i in range(a-1):
        c = ans
        ans = ans + b
        b = c
for i in range(M-1):
    new_ans = 1
    b = 0
    new_a = int(input())
    if new_a == a + 1:
        ans = 0
        break
    k = new_a - a - 2
    for j in range(k):
        c = new_ans
        new_ans = new_ans + b
        b = c
    ans = ans * new_ans % 1000000007
    a = new_a
new_ans = 1
b = 0
for j in range(N - a - 1):
    c = new_ans
    new_ans = new_ans + b
    b = c
ans = ans * new_ans % 1000000007
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
a_array = [int(input()) for x in range(m)]
res = [1 for x in range(n + 1)]
res[1] = 1
for i in a_array:
    res[i] = -1
if n <= 2:
    print(n if m == 0 else 1)
    exit()
for i in range(2, n + 1):
    if res[i] == -1:
        continue
    if res[i - 1] != -1 and res[i - 2] != -1:
        res[i] = (res[i - 1] + res[i - 2])%1000000007
    elif res[i - 1] != -1 or res[i - 2] != -1:
        res[i] = max(res[i - 1], res[i - 2])%1000000007
    else:
        res[i] = 0
print(res[-1])

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)

# print(a)



x = [0 for n in range(N+1)]
x[0] = 1
x[1] = 1 if 1 not in a else 0
for n in range(2,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)
print(x[N])

Submission status: Accepted

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

for i in range(m):
    a.add(int(input()))

p = [0 for i in range(n)]

if 1 not in a:
    p[0] = 1

if n >= 2 and 2 not in a:
    p[1] = p[0] + 1

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

print(p[n - 1] % 1000000007)

Submission status: Accepted

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

MOD =  1000000007

def f(N, A):
    c0 = 0
    c1 = 1

    for i in range(1, N+1):
        c0, c1 = c1, (c0+c1)%MOD

        if i in A:
            c1 = 0

    return c1
            


def main():
    N,M = map(int, input().split())
    A = set(int(input()) for i in range(M))
    print(f(N, A))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M = map(int, raw_input().split(" "))
A = {int(raw_input()) for _ in range(M)}

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

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

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from collections import deque


MOD = 1000000007 


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

dp = [1 for _ in range(N+1)]
for a in An:
  dp[a] = 0


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

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+1)
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:
        if not broken[i+2]:
            dp[i+2]+=dp[i]
            dp[i+2]%=MOD
print(dp[N])

Submission status: Accepted

Solution code:
mod=10**9+7
N,M=map(int,input().split())
alist = [True]*(N+1)
for i in range(M):
  alist[int(input())] = False

#print(alist)
reslist = [0]*(N+1)
reslist[0] = 1
if alist[1]:
  reslist[1] = 1

for i in range(2,N+1):
  if alist[i]:
    reslist[i] = (reslist[i-2]+reslist[i-1])%mod
  else:
    reslist[i] = 0
    
#print(reslist)
print(reslist[N])

Submission status: Accepted

Solution code:
Q = 1000000007
n, m = map(int, input().split())
a = set(int(input()) for _ in range(m))
dp = {
    0: 1,
    1: 0 if 1 in a else 1,
}

for k in range(2, n + 1):
    dp[k] = (0 if k in a else (dp[k - 1] + dp[k - 2])) % Q

print(dp[n])

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

if M != 0:
    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:
def li():
    return list(map(int, input().split()))


if __name__ == "__main__":
    [n, m] = li()
    broken = [int(input()) for _ in range(m)]
    mod = 10 ** 9 + 7

    pattern = [0] * (n + 1)
    pattern[0] = 1
    broken_index = 0
    checking = broken[broken_index] if len(broken) > broken_index else -1
    if checking != 1:
        pattern[1] = 1
    else:
        pattern[1] = 0
        broken_index = broken_index + 1
        checking = broken[broken_index] if len(broken) > broken_index else -1

    for i in range(2, n + 1):
        if checking != i:
            pattern[i] = (pattern[i - 2] + pattern[i - 1]) % mod
        else:
            pattern[i] = 0
            broken_index = broken_index + 1
            checking = broken[broken_index] if len(broken) > broken_index else -1
    print(pattern[n])

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
arr = []
MOD = 1000000007
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]) % MOD

print(dp[N])

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
judge = [True for i in range(n+5)]
for i in range(m):
    judge[int(input())] = False
dp = [0]*(n+5)
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[n]%1000000007)

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(1, N + 1):
        if i in a:
            continue
        if i - 1 >= 0:
            stairs[i] += stairs[i - 1]
            stairs[i] %= MOD
        if i - 2 >= 0:
            stairs[i] += stairs[i - 2]
            stairs[i] %= MOD
    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:
mod = int(1e9) + 7
def solve():
    n, m = map(int, input().split())
    li = [1, 1] + [-1] * n
    for a in (int(input()) for _ in range(m)):
        li[a] = 0
    for i in range(2, n + 1):
        if li[i]:
            li[i] = (li[i - 2] + li[i - 1]) % mod
    print(li[n])
solve()

Submission status: Accepted

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

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

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


print(dp[-1])

Submission status: Accepted

Solution code:
N,M  = [int(x)for x in input().split()]

a = [0 for i in range(N+8)]

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

DP = [0 for i in range(N+8)]
DP[0] = 1
DP[1] = 1
if a[1] == 1:
    DP[1] = 0
for i in range(2,N+1):
    if a[i] == 0:
        DP[i] = (DP[i-2]+DP[i-1])%1000000007
    else:
        pass
#print(DP)
print(DP[N])

Submission status: Accepted

Solution code:
import sys
import math
# from itertools import permutations
input = sys.stdin.readline
p=1000000007
N,M=map(int,input().split())
fib=[1,1]
for i in range(N):
	fib.append(fib[-1]+fib[-2])

cur=0
ans=1
flag=False
for i in range(M):
	x=int(input())
	if x==cur:
		flag=True
		print(0)
		break
	ans*=fib[x-cur-1]
	ans%=p
	cur=x+1
ans*=fib[N-cur]
ans%=p
if not flag:
	print(ans%p)

Submission status: Accepted

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

for i in range(0,n+1):
    if a[i]<0:
        continue
    if i+1>n:
        continue
    if (not a[i+1]<0):
        a[i+1]+=a[i]
        a[i+1]%=1000000007
    if i+2>n:
        continue
    if (not a[i+2]<0):
        a[i+2]+=a[i]
        a[i+2]%=1000000007

print(a[n])

Submission status: Accepted

Solution code:
import sys

mod = 10**9 + 7
N, M = map(int,input().split())
A = []
#次が壊れている段目...k
#その段までの行き方a_kとする
#a_k = a_(k-2) + a_(k-1)
#フィボナッチ数やんけ！！
pos = 0 #現在地

fib = [1, 1]
for i in range(N-1):
    fib.append(fib[i] + fib[i+1])

ans = 1
#各ステップでは壊れている段の直後にいる
for i in range(M):
    a = int(input())
    step = a-1 - pos
    if step >= 0:
        ans = (ans * (fib[step] % mod)) % mod
        pos = a+1
    else:
        print("0")
        sys.exit()
step = N - pos
ans = (ans * (fib[step] % mod)) % mod
print(str(ans))

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
if dp[n] == -1:
    print(0)
else:
    print(dp[n] % mod)

Submission status: Accepted

Solution code:
mod = 1000000007

N,M = list(map(int,input().split()))
a = [int(input()) for i in range(M)]

dp = [0]*(N+2)
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]%mod
  if i+2 <= N:
    if dp[i+2] != -1:
      dp[i+2] += dp[i]%mod

print(dp[N]%mod)

Submission status: Accepted

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

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

print(dp[N] % mod)

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行の数をリストに
if m > 0:
    a = [int(input()) for i in range(m)]
else:
    a = []
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:
import sys
MOD=10**9+7
N,M=map(int,input().split())

if N==1:
    print(1)
    sys.exit()

a=[0]*(N+1)
for i in range(M):
  a[int(input())]=-1

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

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

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = set()
MOD = 1000000007
for _ in range(M):
    A.add(int(input()))

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

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

print(ans[N])

Submission status: Accepted

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

A = []
if len(A_pre)>0:
    A.append(A_pre[0])
    for i in range(1,M):
        if A[-1] != A_pre[i]:
            A.append(A_pre[i])

ans = [0] * (N+1)
ans[0] = 1
break_floor_count = 0
if break_floor_count < len(A) and A[break_floor_count] == 1:
    break_floor_count += 1
else:
    ans[1] = 1

for i in range(2,N+1):
    if break_floor_count < len(A) and A[break_floor_count] == i:
        break_floor_count += 1
    else:
        ans[i] = (ans[i-2]+ans[i-1])%mod_num 

print(ans[N])

Submission status: Accepted

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

N, M = map(int, input().split())
hsh = {}
for i in range(M):
    hsh[int(input())] = True

acc = [0 for _ in range(N+1)]
acc[0] = 1

for i in range(1,N+1):
    if i > 1 and i-2 in hsh:  # 2段前が穴
        if i-1 in hsh: # 1段前が穴
            d = 0
        else:
            d = acc[i-1]
    else:  # 2段前が穴ではない
        s = acc[i-2] if i > 1 else 0
        if i-1 in hsh:  # 1段前が穴
            d = s
        else: 
            d = acc[i-1] + s
    acc[i] = d

# print(hsh)
# print(acc)
print(acc[-1]%1000000007)

Submission status: Accepted

Solution code:
mod = 10**9+7
import sys
sys.setrecursionlimit(10000000)

N,M = [int(x) for x in input().split()]
a = [int(input()) for _ in range(M)]
di = {}
for i in a:
    di[i]=1
dp = [0 for _ in range(N+1)]
dp[0] = 1
for i in range(N+1):
    if(i in di):
        continue
    if(i<N-1):
        if(i+2 not in di):
            dp[i+2]+=dp[i]
            dp[i+2]%=mod
    if(i<N):
        if(i+1 not in di):
            dp[i+1]+=dp[i]
            dp[i+1]%=mod
print(dp[N])

Submission status: Accepted

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

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

if N == 1:
    print(1)
elif N == 2:
    if dp[1] == -1:
        print(1)
    else:
        print(2)
else:
    dp[0] = 1
    if dp[1] != -1 and dp[2] != -1:
        dp[1] = 1
        dp[2] = dp[0] + dp[1]
    elif dp[1] == -1 and dp[2] != -1:
        dp[2] = 1
    elif dp[1] != -1 and dp[2] == -1:
        dp[1] = 1
    else:
        print(0)
        exit()
    
    
    for i in range(3, N+1):
        if dp[i] == -1:
            continue
        elif dp[i-1] == -1 and dp[i-2] != -1:
            dp[i] = dp[i-2]
        elif dp[i-1] != -1 and dp[i-2] == -1:
            dp[i] = dp[i-1]
        elif dp[i-1] != -1 and dp[i-2] != -1:
            dp[i] = dp[i-1] + dp[i-2]
        else:
            print(0)
            exit()
    
    print(dp[N] % mod)

Submission status: Accepted

Solution code:
import sys
N,M = map(int, input().strip().split(' '))
if M > 0:
  broken = set(int(line.strip()) for line in sys.stdin)
else:
  broken = set()
p = [0]*(N+2)
p[0] = 1
for i in range(N):
  # 今i段目にいる
  if i in broken:
    continue
  p[i+1] += p[i]
  p[i+2] += p[i]
print(p[N]%1000000007)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
l=[0]*(n+1)
mod=10**9+7
M=set([int(input()) for _ in range(m)])
for i in M:
    l[i]=-1
l[0]=1
for i in range(n):
    if l[i]!=-1:
        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:
MOD = 1000000007

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

Submission status: Accepted

Solution code:
import sys,heapq
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True # and False
def ddprint(x):
  if DBG:
    print(x)

R = 1000000007

n,m = inm()
b = [0] * (n+2)
b[0] = 1
bad = [False] * (n+2)
for i in range(m):
    bad[inn()] = True

for i in range(1,n+1):
    if bad[i]:
        if bad[i-1]:
            print(0)
            exit()
        else:
            continue
    else:
        b[i] = (b[i-1] + b[i-2]) % R

print(b[n])

Submission status: Accepted

Solution code:
###template###
import sys
def input(): return sys.stdin.readline().rstrip()
def mi(): return map(int, input().split())
###template###

N, M = mi()

#Nが1段なら、絶対に1通り
if N == 1:
  print(1)
  exit()

As = [int(input()) for _ in range(M)]
#0段目を含めて、階段を配列にする stairs[n]でアクセスする
stairs = ['.'] * (N+1)

#壊れた床を#に変え、1行の文字列にする
for a in As:
  stairs[a] = '#'
stairs = ''.join(stairs)

#そもそも無理なパターン。無理なパターンはこの場合だけ
if '##' in stairs:
  print(0)
  exit()


#n段目までの来方をDP[n]に格納していく
DP = [0]*(N+1)
#初期化
DP[0] = 1
#ループを楽にするため、DP[1]は求めておく ※1段しかない場合は排除済み
DP[1] = 1 if stairs[1] == '.' else 0

#Nに辿り着くまでループを回す
for i in range(2,N+1):
  DP[i] = (DP[i-2]+DP[i-1])%1000000007 if stairs[i] == '.' else 0

print(DP[N])

Submission status: Accepted

Solution code:
MAX = 1000000007

def solve():
    N, M = [int(_) for _ in raw_input().split()]
    a = [None] * M
    for i in range(M):
        a[i] = int(raw_input())
    ok = [1] * (N+1)
    for i in range(M):
        ok[a[i]] = 0
    ret = [1] * (N+1)
    ret[N-1] = ok[N-1]
    for i in range (N-2,-1,-1):
        ret[i] = (ret[i+1] * ok[i+1] + ret[i+2] * ok[i+2]) % MAX
    print ret[0]

if __name__ == '__main__':
    solve()

Submission status: Accepted

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

A=[]
for i in range(M):
    A.append(int(input()))

P=10**9+7
index=0

if 1 in A:
    num[1]=0
    index+=1


if N>=2:
    for i in range(2,N+1):
        num[i]=(num[i-1]+num[i-2])%P
        if index<=M-1 and i==A[index]:
            num[i]=0
            index+=1

print(num[N])

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(200000, 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 = (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:
    if x-pre == 1:
        print(0)
        exit()
    l.append(Fib(x-pre-1 +1))
    pre = x

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

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

print(res % 1000000007)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
A = []
B = [0] * (N + 5)

for i in range(M):
  A.append(int(input()))
  B[A[-1]] = -1
  
B[0] = 1
for i in range(N + 1):
  if B[i] == -1:
    continue
  if B[i + 1] != -1:
    B[i + 1] += B[i]
    B[i + 1] %= 1000000007
  if B[i + 2] != -1:
    B[i + 2] += B[i]
    B[i + 2] %= 1000000007
print(B[N])

Submission status: Accepted

Solution code:

MOD =  1000000007

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

a_list = set()
for _ in range(M):
	a_list.add(int(input()))

#print(a_list)

counts = [0] * (N + 10)
counts[0] = 1
for i in range(N):
	if not i in a_list:
		counts[i + 1] = (counts[i + 1] + counts[i]) % MOD
		counts[i + 2] = (counts[i + 2] + counts[i]) % MOD

#print(counts)
print(counts[N])