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 math
mod = 10**9 + 7

# http://cav-inet.hateblo.jp/entry/2017/02/18/165141
def binary_search(list,target): 

	result = -1
	left = 0
	right = len(list) - 1

	while left <= right:
		center = (left + right)//2
		if list[center] == target:
			result = center
			break
		elif list[center] < target:
			left = center + 1
		elif list[center] > target:
			right = center - 1

	if result == -1:
		return False
	else:
		return True

n,m = map(int,input().split())
a = [int(input()) for _ in range(m)]

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

print(dp[n])

Submission status: Accepted

Solution code:
#import collections
import sys
input = sys.stdin.readline

#n = int(input())
#l = list(map(int, input().split()))

'''
A=[]
B=[]
for i in range():
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)'''

fibo = [1, 1]
for i in range(1, 10**5+2):
    fibo.append(fibo[i]+fibo[i-1])

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

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

flg=True
for i in range(m-1):
    if a[i]+1==a[i+1]:
        flg=False
        break

if not flg:
    print(0)

else:
    ans=1
    if m==1:
        print(fibo[a[0]-1]*fibo[n-a[0]-1] % (10**9+7))

    elif m==0:
        print((fibo[n]) % (10**9+7))

    else:
        for i in range(1,m):
            ans*=fibo[a[i]-a[i-1]-2]   
        print(ans*fibo[a[0]-1]*fibo[n-a[m-1]-1]%(10**9+7))

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline

n,m=map(int,input().split())
S=[]
now=0
for i in range(m):
    a=int(input())
    if i==0 and a==1:
        now=a
        continue
    elif i==0:
        S.append(a-now)
        now=a
        continue
    elif i!=0 and a-now==1:
        print(0)
        sys.exit()
    S.append(a-now-1)
    now=a

if m==0:
    S.append(n-now+1)
else:
    S.append(n-now)

mod=10**9+7
N=10**5+10
g1=[1,1]
g2=[1,1]
inverse=[0,1]

for i in range(2,N+1):
    g1.append((g1[-1]*i)%mod)
    inverse.append((-inverse[mod%i]*(mod//i))%mod)
    g2.append((g2[-1]*inverse[-1])%mod)

def cmb(n,r):
    if (r<0 or r>n):
        return 0
    r=min(r,n-r)
    return g1[n]*g2[r]*g2[n-r]%mod


ans=1

for s in S:
    cnt=0
    for i in range((s-1)//2+1):
        cnt+=cmb(s-i-1,i)
        cnt%=mod
    ans=ans*cnt%mod

print(ans%mod)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
l = {int(input()) for _ in range(m)}
if (n == 1):
    print(1)
else:
    p = 10**9+7
    f = [0] * (n + 1)
    f[0], f[1] = 1, 0 if 1 in l else 1
    for i in range(1, n+1):
        if not i in l:
            f[i] = (f[i - 1] + f[i - 2]) % p

    print(f[n])

Submission status: Accepted

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

mod = 1000000007

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

for n in range(N):
    if broken_step[n+1] == 0:
        dp[n+1] += dp[n]*1
    else:
        dp[n+1] = 0
    if broken_step[n+2] == 0:
        dp[n+2] += dp[n]*1
    else:
        dp[n+2] = 0
print(dp[N]%mod)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,m = map(int, input().split())
a = set(map(int, [input() for _ in range(m)]))
dp = [0] * (n+1)

#`dp[i] = i段目にいる通り数`
if not 0 in a:
    dp[0] = 1
if not 1 in a:
    dp[1] = 1
    
for i in range(2,n+1):
    if i in a:
        dp[i] = 0
    else: 
        dp[i] += (dp[i-1] + dp[i-2]) % (10 ** 9 + 7)

print(dp[-1])

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
arr=[1,2]
arr=arr+[0]*(n-2)
danger=[int(input()) for _ in range(m)]
if danger==[]:
  pass
elif danger[0]==1:
  arr[0]=0
  arr[1]=1
for i in range(m):
  arr[danger[i]-1]=-1
for i in range(n):
  if arr[i]==-1:
    arr[i]=0
  elif i==0 or i==1:
    continue 
  else:
    arr[i]=(arr[i-1]+arr[i-2])%(10**9+7)
print(arr[n-1]%(10**9+7))

Submission status: Accepted

Solution code:
N,M =map(int,input().rstrip().split(" "))
ans = [0 for _ in range(N + 3)]
ans[0] = 1
m = []
mc = 0
for _ in range(M):
  m.append(int(input()))
m.append(0)
for i in range(1,N + 1):
  if m[mc] != i:
    ans[i] += ans[i - 1]
    ans[i] += ans[i - 2]
    ans[i] %= 1000000007
  else:
    mc += 1
print(ans[N])

Submission status: Accepted

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

unreachable = False
for i in range(M-1):
    if A[i+1] - A[i] == 1:
        unreachable = True
        break

pat = [0]*(N+2)
pat[0] = 1
if unreachable:
    print(0)
else:
    for i in range(N):
        if i in broken:
            continue
        pat[i+1] = (pat[i+1] + pat[i]) % mod
        pat[i+2] = (pat[i+2] + pat[i]) % mod
    print(pat[N])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

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

check = set(a)
if 1 in check:
    dp = [0, 0, 1]
elif 2 in check:
    dp = [0, 1, 0]
else:
    dp = [0, 1, 2]
if N < 3:
    print(dp[N])
    exit()
for i in range(3, N+1):
    if i in check:
        dp.append(0)
    else:
        dp.append((dp[-1] + dp[-2])%1000000007)

print(dp[-1])

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
n,m=[int(i) for i in input().split()]
dp=[1,1] ;a=set() ; mod=(10**9+7)
for i in range(m):
    a.add(int(input()))
if 1 in a: dp[1]=0
for i in range(2,n+1):
    if i not in a:
        dp.append((dp[-1]+dp[-2])%mod)
    else:
        dp.append(0)
print(dp[-1])

Submission status: Accepted

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

Submission status: Accepted

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

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

print(dp[N] % MOD)

Submission status: Accepted

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

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

for i in range(N+1):
    if i==0 or i==1:
        if i in A:
            step[i] = 0
    else:
        step[i] = step[i-1]+step[i-2]
        if i in A:
            step[i] = 0
        step[i] %= mod

print(step[-1])

Submission status: Accepted

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

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

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

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

print(dp[-1])

Submission status: Accepted

Solution code:
def count_section_by_zero(data):
  count = 0
  flg = False
  start = 0
  for i, d in enumerate(data):
    if flg is False and d != 0:
      count += 1
      flg = True
      
    if d == 0:
      flg = False
  return count

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

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

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

# 2で割り切れる回数
def divide_two(arg):
  c = 0
  while True:
    if c >= 2:
      break
    if arg % 2 != 0:
      break
    arg //= 2
    c += 1
  return c

# 素因数分解
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

def main():
  n, m = input_list()
  falls = [False]*(n+1)
  for i in range(m):
    falls[int(input())] = True
  
  if n == 1:
    print(1)
    exit(0)

  dp = [0]*(n+1)
  dp[0] = 1
  dp[1] = 0 if falls[1] else 1
  for i in range(2, n+1):
    if falls[i]:
      continue
    dp[i] = dp[i-1] + dp[i-2]
  
  mod = 1000000007
  print(dp[-1]%mod)
import math
import fractions
import collections
import itertools
from functools import reduce
main()

Submission status: Accepted

Solution code:
import sys
n,m=map(int,input().split())
a=[]
for i in range(m):
  a.append(int(input()))
a.sort()
for i in range(m-1):
  if a[i+1]-a[i]==1:
    print(0)
    sys.exit()
p=10**9+7  
dp=[0]*(n+1)
dp[0]=1
if 1 not in a:
  dp[1]=1
lst=set(list(range(1,n+1)))
A=set(a)
Lst=lst-A
Lst=list(Lst)
if 1 in Lst:
  Lst.remove(1)
for i in Lst:
  dp[i]=dp[i-1]+dp[i-2]
  if p<=dp[i]:
    dp[i]=dp[i]%p
print(dp[n]%p)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=list(int(input()) for _ in range(m))
a.append(n+1)
key=0
ways = list(0 for _ in range(n))
if a[key] == 1:
    key += 1
else:
    ways[0] = 1

if a[key] == 2:
    key += 1
else:
    ways[1] = ways[0] + 1

for i in range(3, n+1, 1):
    if a[key] == i:
        key += 1
    else:
        ways[i-1] = (ways[i-2] + ways[i-3])%1000000007

print(ways[-1])

Submission status: Accepted

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

# F[N+1]: 0 ~ N 段目にたどり着く移動方法の場合の数
F = [None] * (N+1)
F[0] = 1
F[1] = 1
for i in range(2, N+1):
  if i-1 in a:
    tmp1 = 0
  else:
    tmp1 = F[i-1]
    
  if i-2 in a:
    tmp2 = 0
  else:
    tmp2 = F[i-2]
    
  F[i] = (tmp1 + tmp2) % p

# 基本的なDPの問題
# dp[v] = dp[v-1] + dp[v-2]だが、
# v-1, v-2は壊れていたら加算しない
print(F[N])

Submission status: Accepted

Solution code:
I=lambda : list(map(int,input().split()))

n,m = I();md=10**9+7;p=0;a=1
dp=[0,1];l=[0]*(10**5+2)
for _ in range(m):
    x=int(input())
    l[x]=1
for i in range(1,n+1):
    if l[i]:
        dp.append(0)
    else:
        dp.append((dp[-1]+dp[-2])%md)
print(dp[-1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
N,m=map(int,input().split())
s = set()
for i in range(m):
    s.add(int(input()))
memo={0:1}
mod=1000000007
def climb_stairs(n):
    if memo.__contains__(n):
        return memo[n]
    else:
        if s.__contains__(n):
            return 0
        elif n==1:
            return 1
        else:
            memo[n]=(climb_stairs(n-1)%mod + climb_stairs(n-2)%mod)%mod
            return memo[n]
print(climb_stairs(N))

Submission status: Accepted

Solution code:
I=lambda:list(map(int,input().split()))
n,m=I()
b=[int(input()) for i in range(m)]
b=list(set(b))
f={}
for i in b:
    f[i]=1
dp=[0]*(n+1)
dp[0]=1
for i in range(1,n+1):
    if not f.get(i,0):
        dp[i]=(dp[i-1]+dp[i-2])%(10**9+7)
print(dp[n])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
def fastio():
    from io import StringIO
    from atexit import register
    global input
    sys.stdin = StringIO(sys.stdin.read())
    input = lambda : sys.stdin.readline().rstrip('\r\n')
    sys.stdout = StringIO()
    register(lambda : sys.__stdout__.write(sys.stdout.getvalue()))
fastio()

INF = 10**20
MOD = 10**9 + 7
I = lambda:list(map(int,input().split()))
# from math import gcd
from math import ceil
from collections import defaultdict as dd, Counter
from bisect import bisect_left as bl, bisect_right as br

n, m = I()
broken = [0] * (n + 1)
for i in range(m):
    x, = I()
    broken[x] = 1

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

for i in range(1, n + 1):
    if not broken[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 = [int(input()) for _ in range(m)]
b = [1 for i in range(n+1)]
for i in a:
  b[i] = 0
for i in range(2,n+1):
  cnt = b[i-1] + b[i-2]
  if b[i] != 0:
    b[i] = cnt
print(b[-1]%1000000007)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
a = []
mod = int(1e9 +7)

def Fib(n):
    a, b = 1, 1
    if n == 1:
        return a
    elif n == 2:
        return b
    else:
        for _ in range(n-2):
            a, b = b, a + b
        return b

def main():
    is_no_ans = False
    for i in range(M):
        a_i = int(input())
        a.append(a_i)
        if i != 0 and a[i-1]+1 == a_i:
            is_no_ans = True
    if is_no_ans:
        print(0)
        return

    ans = 1
    left = 0
    a.append(N+1)
    for x in a:
        ans = ans* Fib(x - left) %mod
        left = x + 1
    print(ans)
main()

Submission status: Accepted

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

if M == 0:
    a = [-1]

fib = [1, 1] + [None] * (N - 1)
for i in range(2, N + 1):
    fib[i] = (fib[i - 1] + fib[i - 2]) % p

ans = 1
for j in range(M):
    if a[j] == N or (j + 1 < M and a[j] + 1 == a[j + 1]):
        ans = 0
        break

    if j == 0:
        ans = fib[a[j] - 1]
    else:
        ans *= fib[a[j] - 1 - (a[j - 1] + 1)]
        ans %= p
else:
    ans *= fib[N - a[M - 1] - 1]
    ans %= p

print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
steps = [1,1,2]
for i in range(3,N+1):
    steps.append(steps[i-1]+steps[i-2])
ans = 1
a = 0
mod = 10**9+7
for i in range(M):
    b = int(input())
    b -=1
    if(b<a):
        print(0)
        exit()
    else:
        ans = ans*steps[b-a]%mod
    a = b+2
ans = ans*steps[N-a]%mod
print(ans)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7

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

ban = [False] * (n + 1)

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

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

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

print(dp[n] % MOD)

Submission status: Accepted

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
mod=1000000007
f=[False]*(N+1)
for _ in range(M):
    i=int(input())
    f[i]=True
dp=[0 for _ in range(N+1)]

if N==1:
    if f[1]:
        print(0)
    else:
        print(1)
else:
    if f[1] and f[2]:
        print(0)
        exit()
    elif f[1]:
        dp[1]=0;dp[2]=1
    elif f[2]:
        dp[1]=1;dp[2]=0
    else:
        dp[1]=1;dp[2]=2

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

Submission status: Accepted

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

MOD = 1000000007

d = [0] * (N+1)
OK = [True]*(N+1)
d[0] = 1

for i in range(M):
    OK[a[i]] = False

#print(OK)

if(OK[1]):
    d[1] = 1
else:
    d[1] = 0

for i in range(2,N+1):
    if(OK[i-1]):
        d[i] += d[i-1]
    if(OK[i-2]):
        d[i] += d[i-2]
    d[i] %= MOD
    '''
    if(i in a):
        d[i] = 0
    else:
        d[i] = d[i-1] + d[i-2]
    d[i] %= MOD
    '''

print(d[-1])

Submission status: Accepted

Solution code:

n,m=map(int,input().split())
a = [int(input()) for _ in range(m)]

mod=10**9+7
dp=[0]*(n+1)
dp[0]=1
NG=[False]*n
for i in range(m):
    NG[a[i]-1]=True

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

"""
#DP問題
"""

Submission status: Accepted

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

MOD = 1000000007  # type: int


def solve(N: int, M: int, a: "List[int]"):
    dp = [0]*(N+1)
    dp[0] = 1
    B = set(a)
    for i in range(1, N+1):
        if i in B:
            continue
        if i > 1:
            dp[i] = (dp[i-1] + dp[i-2]) % MOD
        else:
            dp[i] = dp[i-1] % MOD
    print(dp[N])
    return


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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
A=[]
for i in range(M):
    a=int(input())
    A.append(a)
DP=[0]*(1+N)
DP[0]=1
DP[1]=1
damage=[0]*(N+1)
kotae=0
for m in A:
    damage[m]=-1
if N==1:
    print(1)
elif N==2:
    if M==1:
        print(1)
    else:
        print(2)
else:
    for a in range(2,N+1):
        if damage[a-1]==-1 and damage[a-2]==-1:
            print(0)
            kotae+=1
            break
        if damage[a]==-1:
            continue
        elif damage[a-1]==-1:
            DP[a]=DP[a-2]
        elif damage[a-2]==-1:
            DP[a]=DP[a-1]
        else:
            DP[a]=DP[a-2]+DP[a-1]
    if kotae==0:
        print(DP[-1]%(pow(10,9)+7))

Submission status: Accepted

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

mod=10**9+7
dp=[0]*(n+1)
dp[0]=1
NG=[False]*n
for i in range(m):
    NG[a[i]-1]=True

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

Submission status: Accepted

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

for i in broken_stairs:
    stairs[i] = False

dp = [0]*(n+1)

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


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

print(dp[-1])

Submission status: Accepted

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

for i in range(m):
    buf = int(input())
    is_Broken[buf] = True

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

print(dp[n])

Submission status: Accepted

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

dp = [0]*(n+1)
if m == 0:
  base = [n+1]

if 1 == base[j]:
  dp[1] = 0
  if j < m-1:
    j = j + 1
else:
  dp[1] = 1

dp[0] = 1

for i in range(2,n+1):
  if not (i == base[j]):
    dp[i] = dp[i-1] + dp[i-2]
  elif i == base[j]:
    if j < m-1:
      j = j + 1
  
  
print(int(dp[n]%1000000007))

Submission status: Accepted

Solution code:
# from math import factorial,sqrt
# from itertools import permutations as permus
# from fractions import gcd
# from collections import deque,Counter
# from decimal import Decimal, getcontext
# # getcontext().prec = 1000
# # eps = Decimal(10) ** (-100)

# import numpy as np
# import scipy as scp

# 入力の受け取り
n,m = map(int,input().split())
stair = [True for _ in range(n+1)]
for _ in range(m):
    broken = int(input())
    stair[broken] = False

mod = 1000000007

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

dp[0]=1
for now in range(n):
    for next in range(now+1,min(n,now+2)+1):
        if stair[next]:
            dp[next] += dp[now]
            dp[next] %= mod

print(dp[n])
# print("{:.10f}".format(ans))
# print(*ans)   # unpackして出力。間にスペースが入る
# for row in board:
#     print(*row,sep="")    #unpackして間にスペース入れずに出力する

Submission status: Accepted

Solution code:
import sys
N,M = map(int,input().split())
intact = [True for _ in range(N)]
dp = [0 for _ in range(N+1)]
MOD = 1000000007
for i in range(M):
  a = int(input())
  intact[a] = False
if N == 1:
  print(1)
  sys.exit(0)
dp[0] = 1
if (intact[1]):
  dp[1] = 1
for i in range(2,N+1):
  if intact[i-2]:
    dp[i] += dp[i-2]
  if intact[i-1]:
    dp[i] += dp[i-1]
  dp[i] %= MOD
print(dp[N])

Submission status: Accepted

Solution code:
import sys
import os

MOD = 10 ** 9 + 7


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, M = list(map(int, sys.stdin.buffer.readline().split()))
    A = set([int(sys.stdin.buffer.readline().rstrip()) for _ in range(M)])

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

    print(ret[-1] % MOD)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,_,*l=map(int,open(0).read().split());l=set(l);s=i=0;t=1
while i<n:i+=1;s,t=t,(s+t)%(10**9+7)*(not{i}&l)
print(t)

Submission status: Accepted

Solution code:
n,_,*l=map(int,open(0).read().split());l=set(l);s,t=0,1
for i in range(n):s,t=t,(s+t)%(10**9+7)*(not{i+1}&l)
print(t)

Submission status: Accepted

Solution code:
import sys
f=sys.stdin.readline
n,m=map(int,f().split())
l=set(int(f())-1 for _ in range(m))
s,t=0,1
for i in range(n): s,t=t,(s+t)%(10**9+7)*(1-(i in l))
print(t)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
l=set(int(input())-1 for _ in range(m))
s,t=0,1
for i in range(n): s,t=t,(s+t)%(10**9+7)*(1-(i in l))
print(t)

Submission status: Accepted

Solution code:
M=10**9+7
import sys
f=sys.stdin.readline
n,m=map(int,f().split())
s,t=0,1
u=0 if m<1 else int(f())
for i in range(n):
  if i==u-1:
    s,t=t,0
    try: u=int(f())
    except: pass
  else: s,t=t,(s+t)%M
print(t)

Submission status: Accepted

Solution code:
M=10**9+7
f=input
n,m=map(int,f().split())
s,t=0,1
u=0 if m<1 else int(f())
for i in range(n):
  if i==u-1:
    s,t=t,0
    try: u=int(f())
    except: pass
  else: s,t=t,(s+t)%M
print(t)

Submission status: Accepted

Solution code:
import bisect
N, M = map(int, input().split())
A = [0]*M
for i in range(M):
  A[i] = int(input())

def index(a, x):
  i = bisect.bisect_left(a, x)
  if i != len(a) and a[i] == x:
    return i
  else:
    return -1

def dp(a,n):
  if n==N:
    return 1
  if n>N:
    return 0
  if index(a,n)!=-1:
    return 0
  else:
    return (DP[n+1]+DP[n+2])%(10**9+7)
    
DP=[0]*(N+3)

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

ans=DP[0]
print(ans)

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[:2]= 1, 1 if 1 not in A else 0 # 最初の2つめは1だが、壊れている場合は0にする
for i in range(2, N+1):
    if i not in A: # 壊れている時はスキップする
        dp[i] = (dp[i-1]+dp[i-2])%mod
print(dp[-1])

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[:2]= 1, 1 if 1 not in A else 0
for i in range(2, N+1):
    if i not in A:
        dp[i] = (dp[i-1]+dp[i-2])%mod
print(dp[-1])

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7

def solve():
    N, M = map(int, input().split())
    A = [int(input()) for _ in range(M)]
    
    if N == 1 and M == 0:
        return 1
    elif N == 1 and M == 1 and A[0] == 0:
        return 0

    l = [1 for _ in range(N+1)]
    for a in A:
        l[a] = 0
        
    dp = [0 for i in range(N+1)]
    dp[1] = 0 if 1 in A else 1
    dp[2] = 0 if 2 in A else dp[1] + 1

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

    return dp[N] % MOD

print(solve())

Submission status: Accepted

Solution code:
import sys
from bisect import *
from heapq import *
from collections import *
from itertools import *
from functools import *
from math import *

sys.setrecursionlimit(100000000)
input = lambda: sys.stdin.readline().rstrip()

N, M = map(int, input().split())
broken = set(int(input()) for _ in range(M))

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

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

print(dp[-1])

Submission status: Accepted

Solution code:
from collections import deque
N, M = map(int, input().split())
broken = [int(input())-1 for i in range(M)] #indexは0からなので、-1
broken = set(broken)

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

if 0 in broken:
    if 1 in broken:
        stairs=deque([0,0])
    else:
        stairs=deque([0,1])
else:
    if 1 in broken:
        stairs=deque([1,0])
    else:
        stairs=deque([1,2])

for i in range(2,N):
    if i in broken:
        stairs.append(0)
    else:
        stairs.append((stairs[i-1]+stairs[i-2])%(10**9 + 7))
print(stairs[-1])

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7
N,M = map(int,input().split())
X = [1,1]
for i in range(N):
    X.append((X[i]+X[i+1]) % mod)
if M == 0:
    print(X[N])
else:
    a = int(input())
    ans = X[a - 1]
    #print(ans)
    tmp = a
    check = 0
    for _ in range(M-1):
        a = int(input())
        if a - tmp == 1:
            check = 1
        y = a - tmp - 2
        ans *= X[y]
        ans %= mod
        tmp = a
        #print(ans)
    y = N - tmp - 1
    ans *= X[y]
    ans %= mod 
    if check == 1:
        print(0)
    else:
        print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# import bisect
# import copy
# import fractions
# import math
# import numpy as np
# from collections import Counter, deque
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product

def resolve():

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


    dp=[1]*(N+1)
    for i in A:
        dp[i]=0

    for i in range(2,N+1):
        dp[i]=(dp[i-1]+dp[i-2])%(10**9+7)*dp[i]

    print(dp[N])

resolve()

Submission status: Accepted

Solution code:
import sys


n, m = [int(_) for _ in input().split()]
l = {}
for i in range(m):
    l[int(input())] = 1

d = [0] * (n + 2)
d[0] = 1
if 1 not in l:
    d[1] = 1
for i in range(n):
    if i in l and i + 1 in l:
        print(0)
        sys.exit()
    elif i in l:
        d[i + 2] = d[i + 1]
    elif i + 1 in l:
        d[i + 2] = d[i]
    else:
        d[i + 2] = d[i] + d[i + 1]
    d[i + 2] = d[i + 2] % (10 ** 9 + 7)
print(d[-2])

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
a = [0]*M
mod = 10**9+7

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

a = set(a)
DP = [0]*(N+1)
DP[0] = 1
if 1 in a:
    DP[1] = 0
else:
    DP[1] = 1

for i in range(2, N+1):
    if(i not in a):
        DP[i] = (DP[i-1]+DP[i-2])%mod
        
print(DP[-1])

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


n, m = map(int, input().split())
a = [0] * m
dp = [0] * (n + 1)
mod = 10 ** 9 + 7
for i in range(m):
    a[i] = int(input())
a = set(a)
dp[:2] = 1, 1 if 1 not in a else 0

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

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
broken = [int(input()) for i in range(m)]
broken.sort()
broken += [0] * (n-m)
index = 0
mod = 10**9 + 7
for i in range(1,n+1):
  if i==1:
    if i != broken[index]:
      a=1
      b=1
    else:
      a=1
      b=0
      index += 1
  else:
    if i == broken[index]:
      a,b=b,0
      index += 1
    else:
      a,b=b,(a+b)%mod
print(b)