Problem:


Score : 300 points

Problem Statement

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

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

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

Constraints

1 \leq N \leq 10^5

0 \leq M \leq N-1

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

Input

Input is given from Standard Input in the following format:

N M
a_1
a_2
 .
 .
 .
a_M

Output

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

Sample Input 1

6 1
3

Sample Output 1

4

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

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

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

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

0 \to 2 \to 4 \to 6

Sample Input 2

10 2
4
5

Sample Output 2

0

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

Sample Input 3

100 5
1
23
45
67
89

Sample Output 3

608200469

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



Sample input:
6 1
3


Sample output:
4

Submission status: Accepted

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

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

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

for now in range(N):
    for next in range(now+1, min(N, now+2)+1):
        if oks[next]:
            dp[next] += dp[now]
            dp[next] %= 10**9 + 7

print(dp[N])

Submission status: Accepted

Solution code:
# coding: utf-8
# hello worldと表示
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

n,m=MI()
brs=[]
for i in range(m):
    brs.append(int(input()))
brs.append(0)
dp=[0 for i in range(n+2)]
dp[0]=0
dp[1]=1
i=2
while i<n+2:
    if i==brs[0]+1:
        dp[i]==0
        brs.remove(brs[0])
        #print(brs[0])
        i=i+1
    else:
        dp[i]=dp[i-1]+dp[i-2]
        i=i+1
print(dp[-1]%(10**9+7))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
IS = lambda: sys.stdin.readline().rstrip()
II = lambda: int(IS())
MII = lambda: list(map(int, IS().split()))

def main():
    n, m = MII()
    a_lst = [II() for _ in range(m)]
    DIV = 10**9+7
    stairs = [1]*2 + [0]*(n-1)
    for a in a_lst:
        stairs[a] = 'NG'
    cnt = 0
    for i in range(2, n+1):
        if cnt == 2:
            print(0)
            exit(0)
        if stairs[i] == 'NG': cnt += 1; continue
        cnt = 0
        a = stairs[i-1] if stairs[i-1] != 'NG' else 0
        b = stairs[i-2] if stairs[i-2] != 'NG' else 0
        stairs[i] = a + b
    print(stairs[n]%DIV)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

for i in range(M):
    broken[int(input())] = True

dp[0] = 1
for i in range(N + 1):
    if broken[i]:
        continue
    if i - 2 >= 0 and not broken[i - 2]:
        dp[i] += dp[i - 2] % MOD
    if i - 1 >= 0 and not broken[i - 1]:
        dp[i] += dp[i - 1] % MOD
# print(dp[:10])
print(dp[N] % MOD)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
A = set([int(input()) for _ in range(M)])
Div = 10**9+7
#dp[i]:i段目にたどり着く移動方法のパターン数
dp = [0 for _ in range(N+1)]
dp[0] = 1
if 1 not in A:
    dp[1] = 1

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

print(dp[N])

Submission status: Accepted

Solution code:
def fib(n):
    if n == 1:
        return 1
    if n == 2:
        return 2
    else:
        a,b = 0,1
        for i in range(n):
            a,b = b,a+b
        return b

n,m = map(int,input().split())
mod = 10**9+7
ans = 1
a = -1
for i in range(m):
    b = int(input())
    if a != -1 and b-a == 1:
        print(0)
        break
    ans *= fib(b-a-2)
    a = b
else:
    ans *= fib(n-a-1)
    print(ans%mod)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
now=0
a=0
MOD=10**9+7
p=[1,0]#0 humu  1 humazu
A=[int(input()) for i in range(M)]+[-1]
while now<N:
  if now==A[a]-1:
    p=[0,p[0]]
    a+=1
  else:
    p=[(p[0]+p[1])%MOD, p[0]%MOD]
  now+=1
print(p[0]%MOD)

Submission status: Accepted

Solution code:
# coding: utf-8

import sys
import math
import collections
import itertools
INF = 10 ** 13
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def gcd(x, y) : return y if x % y == 0 else gcd(y, x % y)
def lcm(x, y) : return (x * y) // gcd(x, y)
def I() : return int(input())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def LS() : return input().split()
def RS(N) : return [input() for _ in range(N)]
def LRS(N) : return [input().split() for _ in range(N)]
def PL(L) : print(*L, sep="\n")

N, M = LI()
A = RI(M)

dp = [0] * (N+10)
dp[0] = 1
j = 0
for i in range(N):
    if j < M and i == A[j]:
        j += 1
        continue

    dp[i+1] = ((dp[i] % MOD) + (dp[i+1] % MOD)) % MOD
    dp[i+2] = ((dp[i] % MOD) + (dp[i+2] % MOD)) % MOD

print(dp[N])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
a = set([int(input()) for _ in range(m)])
mod = 10**9+7
dp = [0]*(n+1)
dp[0] = 1
dp[1] = 0 if 1 in a else 1
for i in range(2, n+1):
    dp[i] = (dp[i-1]+dp[i-2])%mod if i not in a else 0 #かけたところは0にしとこう、ってことか…
print(dp[n])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)

n, m = [int(i) for i in input().split()]
fibo_l = [1] + [None] * n
a = set([int(input()) for i in range(m)])

def fibo(x):
    if x not in a and x >= 0:
            if fibo_l[x] is None:
                fibo_l[x] = fibo(x-1) % 1000000007 + fibo(x-2) % 1000000007
            return fibo_l[x]
    else: return 0
    
print(fibo(n) % 1000000007)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n , m = map(int,input().split())
u = 1000000007
p = {i for i in range(n)}
y = [0 for i in range(n)]
q = {int(input()) - 1 for i in range(m)}
f = list(p - q)
for i in f:
    if i == 0:
        y[0] = 1
    elif i == 1:
        y[1] = y[0] + 1
    else:
        y[i] = (y[i-1] + y[i-2])%u

print(y[n-1])

Submission status: Accepted

Solution code:
# python 3.4.3
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# function
# -------------------------------------------------------------


# -------------------------------------------------------------
# main
# -------------------------------------------------------------
N,M = map(int,input().split())
A = list(int(input()) for _ in range(M))

mod = 10**9+7

# 床が壊れてる階段を高速に判別できるように
B = [True]*(N+1)
for a in A:
    B[a] = False

# dp[i] : i番目の階段までの場合の数
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 B[i]:
        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())
a=set([int(input()) for i in range(m)])
dp=[0]*(n+1)
dp[0]=1
for i in range(1,n+1):
    dp[i]=(dp[i-1]+dp[i-2])%(10**9+7)
    if i in a:dp[i]=0
print(dp[n])

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
nums = [0, 1]
broken = set()
for i in range(m):
    broken.add(int(input()))
def fib(n):
    for i in range(n):
        if i+1 in broken:
            nums.append(0)
        else:
            a = nums[i]
            b = nums[i+1]
            nums.append((a+b)%1000000007)
    return nums[-1]
print(fib(n))

Submission status: Accepted

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

Submission status: Accepted

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

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

ret_list = [0] * (n + 1)

ret_list[0] = 1
ret_list[1] = 0 if 1 in a_set else 1

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

print(ret_list[-1])

Submission status: Accepted

Solution code:
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 10 ** 9 + 7
N, M = lr()
A = set(ir() for _ in range(M))
dp = [0] * (N+1)
dp[0] = 1
for i in range(N):
    if i+2 not in A and i+2 <= N:
        dp[i+2] += dp[i]
    if i+1 not in A:
        dp[i+1] += dp[i]

print(dp[-1]%MOD)

Submission status: Accepted

Solution code:
import collections
import itertools
import numpy as np
import sys
sys.setrecursionlimit(100000000)
MOD = 10**9+7

def binary_search(a,val):
    n = len(a)
    low = 0
    high = n-1
    mid =(low+high)//2
    cnt = 1
    while low < high + 1:
        if a[mid] == val:
            return True
        elif a[mid]>val:
            high = mid - 1
        else:
            low = mid + 1
        mid =(low+high)//2
        cnt += 1
    return False
#入力
n,m = map(int,input().split())
a = [int(input()) for i in range(m)]
dp = [0]*(n+2)
dp[n] = 1
broke = [0]*(n+1)
for i in range(m):
    broke[a[i]] = 1
for i in range(n-1,-1,-1):
    if broke[i]:
        dp[i] = 0
        continue
    dp[i] = dp[i+1] + dp[i+2]
    dp[i]%=MOD
print(dp[0])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,M = map(int,readline().split())
A = [True] * (N+10)
MOD = 10 ** 9 + 7
for _ in range(M):
  x = int(readline())
  A[x] = False


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

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

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7
mod2 = 2**61+1
from collections import deque
import heapq
from bisect import bisect_left, insort_left, bisect_right

def iip(listed=True):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def iip_ord():
    return [ord(i) - ord("a") for i in input()]


def main():
    ans = solve()
    if ans is not None:
        print(ans)

def solve():
    N, M = iip(False)
    A = [iip(False) for i in range(M)]

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

    for i in A:
        dp[i] = False

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

        if dp[i] is False:
            continue

        if a is False:
            a = 0
        if b is False:
            b = 0

        dp[i] = (a+b) % mod

        #print(dp)
    print(dp[-1] % mod)


#####################################################ライブラリ集ここから

def YesNo(s):
    if s:
        print("Yes")
    else:
        print("No")


def fprint(s):
    for i in s:
        print(i)

def split_print_space(s):
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        # print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p, mod_= mod):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


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+2)
for i in a:
    dp[i]=-1

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

print(dp[-2])
#print(dp)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n,m = list(map(int,input().split()))
a = [int(input()) for i in range(m)]

from collections import deque
stack_deque = deque(a)

def pl():
    try:
        return stack_deque.popleft()
    except:
        return -1

MOD = 10**9+7
#i段目への移動方法
dp = [0] * (n+1)
dp[0]=1
min_a = pl()
if min_a!=1:
    dp[1]=1
else:
    min_a = pl()
for i in range(2,n+1):
    if i == min_a:
        dp[i]=0
        min_a = pl()
    else:
        dp[i]=(dp[i-1]%MOD+dp[i-2]%MOD) % MOD
print(dp[-1])

Submission status: Accepted

Solution code:
def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))
def ism():return map(str,input().split())
def isl():return list(map(str,input().split()))

n,m = iim()
broke = []
for j in range(m):
    broke.append(ii())
if n > 1:
    num = [1]
    if len(broke) and broke[0] == 1:
        num.append(0)
        broke.pop(0)
    else:
        num.append(1)

    for i in range(2,n+1):
        if len(broke) and broke[0] == i:
            num.append(0)
            broke.pop(0)
        else:
            num.append((num[-1]+num[-2])%1000000007)
    print(num[-1])
else:
    print(1)

Submission status: Accepted

Solution code:
def main():
    n, m = map(int, input().split())
    a = set([int(input()) for _ in range(m)])
    if 1 < n:
        dp = [0 for _ in range(n + 1)]
        dp[1] = 0 if 1 in a else 1
        dp[2] = 0 if 2 in a else 1
        dp[2] += dp[1]
        for i in range(3, n + 1):
            if i - 1 not in a:
                dp[i] += dp[i - 1]
            if i - 2 not in a:
                dp[i] += dp[i - 2]
        print(dp[-1] % (10 ** 9 + 7))
    else:
        print(1 if 1 not in a else 0)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import math

from collections import defaultdict
from collections import deque
def load(vtype=int):
    return vtype(input().strip())
def load_list(seplator=" ", vtype=int):
    return [vtype(v) for v in input().strip().split(seplator)]
def exit():
    import sys
    sys.exit(0)
def perm_sub(li, used):
    if len(li) == len(used):
        return [deque()]
    k = []
    for i in range(len(li)):
        if i in used:
            continue
        used.add(i)
        sub_list = perm_sub(li, used)
        for sub in sub_list:
            sub.appendleft(li[i])
        k.extend(sub_list)
        used.discard(i)
    return k
def perm_li(li):
    return perm_sub(li, set())
def perm_n(n):
    return perm_sub(list(range(n)), set())
def join_i(li, sep=""):
    return sep.join([str(e) for e in li])
def li2n(li):
    n, base = 0, 1
    for i in range(len(li)-1, -1, -1):
        n += li[i] * base
        base *= 10
    return n
def sli2ili(li):
    return [int(s) for s in li] 
def prime_list(n):
    li = [i for i in range(2, n+1)]
    for i in range(len(li)):
        if li[i] >= int(math.sqrt(n)):
            break
        if li[i] == -1:
            continue
        for j in range(i+1, len(li)):
            if li[j] % li[i] == 0:
                li[j] = -1
    return [n for n in li if n != -1]
def gcd(a, b):
    a, b = max(a, b), min(a, b)
    while True:
        r = a % b
        if r == 0: return b
        a, b = b, r
def lcm(a, b):
    return int(a * b / gcd(a,b))
def all_subset(li):
    s = []
    n = len(li)
    for bit in range(0, (1<<(n+1))):
        ss = set()
        for i in range(0, n):
            if (bit & (1 << i)):
                ss.add(li[i])
        s.append(ss)
    return s
def factorial(n):
    if n == 1:
        return 1
    return n * factorial(n-1)
def mCn(m, n):
    def factorial_ntimes(m, n):
        r = 1
        while n:
            r *= m
            m -= 1
            n -= 1
        return r
    return int(factorial_ntimes(m, n) / factorial(n))


n, m = load_list()
A = []
for _ in range(m):
    A.append(load())
A = set(A)

dp = dict()

s = list()
s.append(0)

def f(now, goal, A):
    if now > goal:
        return 0
    if now == goal:
        return 1
    
    cnt = 0
    if now + 1 in A:
        pass
    elif now + 1 in dp:
        cnt += dp[now+1]
    else: 
        dp[now+1] = f(now+1, goal, A) 
        cnt += dp[now+1]

    if now + 2 in A:
        pass
    elif now + 2 in dp:
        cnt += dp[now+2]
    else:
        dp[now+2] = f(now+2, goal, A) 
        cnt += dp[now+2]
    return cnt
sys.setrecursionlimit(1000000) 
cnt = f(0, n, A)
print(cnt % 1000000007)

Submission status: Accepted

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

if m>=2:
    pre = A[0]
    for i in range(1,m):
        if pre+1 == A[i]:
            print(0)
            exit()
        pre = A[i]
if m==0:
    for i in range(1,n+1):
        if i==1:
            dp[i]=1
        else:
            dp[i] = (dp[i-1]+dp[i-2])%mod
    print(dp[-1])
    exit()


idx = 0
a = A[idx]
for i in range(1,n+1):
    if i==a:
        dp[i]=0
        idx+=1
        if idx <m:
            a =A[idx]
    else:
        if i==1:
            dp[i]=1
        else:
            dp[i] = (dp[i-1]+dp[i-2])%mod
print(dp[-1])

Submission status: Accepted

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

mod = 10**9+7

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

for i in range(1,n+1):
    #print(i)
    if m == 0:
        if i == 1:
            dp[i] = dp[i-1] % mod
        else:
            dp[i] = (dp[i-1] + dp[i-2])%mod
    else:
        if i == ai[num]:
            dp[i] = 0
            num += 1
            num = min(num,m-1)
        else:
            if i == 1:
                dp[i] = dp[i-1] % mod
            else:
                dp[i] = (dp[i-1] + dp[i-2])%mod
    #    dp[i+1] = dp[i-1] + dp[i]
            
print(dp[n]%mod)

Submission status: Accepted

Solution code:
from collections import deque
from collections import Counter
from itertools import product, permutations,combinations
from operator import itemgetter
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right, bisect
#pypyではscipy, numpyは使えない
#from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, minimum_spanning_tree
#from scipy.sparse import csr_matrix, coo_matrix, lil_matrix
#import numpy as np
from fractions import gcd
from math import ceil,floor, sqrt, cos, sin, pi, factorial
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7

def main():
  n, m = map(int, readline().split())
  A = list(int(readline()) for i in range(m))
  A.append(INF)
  dp = [0]*(n+1)
  dp[0] = 0
  j = 0
  if A[j] == 1:
    dp[1] = 0
    j += 1
  else:
    dp[1] = 1
  
  if n>=2:
    if A[j] == 2:
      dp[2] = 0
      j += 1
    else:
      dp[2] = dp[1] + 1
  
  if n>=3:
    for i in range(3, n+1):
      if A[j] == i:
        dp[i] = 0
        j += 1
      else:
        dp[i] = (dp[i-1]+dp[i-2])%MOD
  print(dp[n])
  
if __name__ == '__main__':
  main()

Submission status: Accepted

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

dp = [0] * (N+2)
dp[N] = 1
mod = 1000000007

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

print(dp[0])

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
a = set(a)
mod = 1000000007
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])%mod
print (dp[N])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
import sys
sys.setrecursionlimit(100000)
f = math.factorial
n, m = map(int, input().split())
a = [-1] + [int(input()) for i in range(m)] + [n+1]
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10 ** 9 + 7
N = 10 ** 5  # N は必要分だけ用意する
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]
 
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)


count = 1
for i in range(m+1):
    k = a[i+1] - a[i] - 2
    if k == -1:
        count = 0
        break
    else:
        work = 0
        for b in range(k//2+1):
            work += cmb(k-b, b, p)
        count *= work
print(count%p)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
#a = [int(input()) for _ in range(M)]
issafe = [True] * (N + 1)
for i in range(M):
    issafe[int(input())] = False

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

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

print(dp[N])

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
#a = [int(input()) for _ in range(M)]
issafe = [True] * (N + 1)
for i in range(M):
    issafe[int(input())] = False

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

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

mod = 1000000007
print(dp[N] % mod)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
p=10**9+7
a=[int(input()) for i in range(m)]
a.append(n+1)
b=[a[0]-1]
for i in range(m):
  b.append(a[i+1]-a[i]-2)
x=[1]*(max(b)+1)
for i in range(2,max(b)+1):
  x[i]=(x[i-1]+x[i-2])%p

ans=1
if min(b)==-1:
  ans=0
else:
  for i in range(m+1):
    ans=(ans*x[b[i]])%p
print(ans)

Submission status: Accepted

Solution code:
import sys

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

a = []
for _ in range(m):
    a.append(int(input()))

if n == 1:
    print(1)
    sys.exit()
dp = [0 for _ in range(n+1)]
dp[0] = 1
dp[1] = 1
dp[2] = 2
if m == 0:
    for i in range(2,n+1):
        dp[i] = dp[i-1] + dp[i-2]
    print(dp[n]%(10**9+7))
else:
    c = 0
    for i in range(1,n+1):
        if i == a[c]:
            dp[i] = 0
            if c < m-1:
                c += 1
        else:
            dp[i] = dp[i-1] + dp[i-2]

    print(dp[n]%(10**9+7))

Submission status: Accepted

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

a.sort()
for i in range(1,n+1):
        if dp[i] == 0:
                continue
        if i == 1:
                dp[i] = 1
                continue
        if i == 2:
                if dp[i-1] == 0:
                        dp[i] = 1
                else:
                        dp[i] = 2
                continue
        if dp[i-1] == 0:
                dp[i] = dp[i-2]
                continue
        if dp[i-2] == 0:
                dp[i] = dp[i-1]
                continue
        dp[i] = (dp[i-1]+dp[i-2])%(10**9+7)
        #print (dp[i])
print (dp[-1]%(10**9+7))

Submission status: Accepted

Solution code:
#C
n, m = map(int, input().split())
a = [1] * (n + 1)
mod=1e9+7
for i in range(m):
    a[int(input())] = 0
b = [1] * (n + 1)
if a[1] == 0:
    b[1] = 0
for i in range(2, n + 1):
    b[i] = int(a[i] * (b[i - 2] + b[i - 1]) % mod)
print(b[n])

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
break_stair = [False for i in range(n)]
for i in range(m):
    break_stair[int(input())-1] = True
mod = 10**9+7
# i番目にたどり着く総数
dp = [0 for i in range(n+1)]
dp[0] = 1
if break_stair[0]:
    dp[1] = 0
else:
    dp[1] = 1
for i in range(n-1):
    if break_stair[i+1]:
        dp[i+2] = 0
    else:
        dp[i+2] = (dp[i] + dp[i+1])%mod
print(dp[n])

Submission status: Accepted

Solution code:
import sys


input = sys.stdin.readline

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

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

print(dp[N]%MOD)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

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

lst=[None]*(N+1)
def func(n):
    #if n in a:
    #    return 0
    if n<=1:
        return 1
    else:
        if lst[n]:
            return lst[n]
        else:
            temp=(func(n-1)+func(n-2))%(10**9+7)
            lst[n]=temp
            return temp



a=[-1]+a+[N+1]
answer=1
for i in range(M+1):
    if a[i+1]-a[i]==1:
        print(0)
        break
    answer=( func(a[i+1]-a[i]-2)*answer )%(10**9+7)
else:
    print(answer)

Submission status: Accepted

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

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

for i in range(1, N + 1):
    if i in a_s:
        continue
    elif i >= 2:
        dp[i] = (dp[i - 1] + dp[i - 2]) % mod
    else:
        dp[i] = (dp[i - 1]) % mod
print(dp[-1])

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
a=[int(input()) for _ in range(M)]
dp=[0]*N
id=0
p=10**9+7
id=0
for i in range(N):
    if (i==0):
        dp[i]=1
    elif (i==1):
        dp[i]=dp[i-1]+1
    else:
        dp[i]=dp[i-1]+dp[i-2]
    if len(a)>0:
        if a[id]==i+1:
            dp[i]=0
            if id<len(a)-1:
                id=id+1
print(dp[N-1]%p)

Submission status: Accepted

Solution code:
#どっちで出すか注意, rstrip注意
#提出前に見返すこと！
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    mod = 10**9 + 7

    N,M = map(int, input().split())
    a = [int(input()) for _ in range(M)]
    res = [0]*(N+1)
    res[0] = 1
    k = 0
    for i in range(1,N+1):
        if k<M:
            if i==a[k]:
                k += 1
                continue
        res[i] = (res[i-1]+res[i-2]) % mod
    print(res[-1])


if __name__ == '__main__':
    main()