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())
dq = [1]*(n+1)
for _ in range(m):
  dq[int(input())]=0
mod = 10**9+7
x, y = 0, 1
for i in range(1, n+1):
  x,y = y, dq[i] * (x+y) % mod
print(y)

Submission status: Accepted

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

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

print(dp[n] % mod)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

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

def stepcmb(st):
    memo = [0]*(st+1)
    memo[0] = 1
    def _fib(st):
        if st <= 1:
            return 1
        if memo[st] != 0:
            return memo[st]
        memo[st] = _fib(st-1) + _fib(st-2)
        return memo[st]
    return _fib(st)

if m >= 2:
    for i in range(1, m):
        if steps[i] - steps[i-1] == 1:
            print(0)
            exit()

res = 1
nowstep = 0
for i in range(m):
    res *= stepcmb(steps[i]-nowstep-1) % (10**9+7)
    nowstep = steps[i] + 1
res = (res * stepcmb(n-nowstep)) % (10**9+7)

print(res)

Submission status: Accepted

Solution code:
N,M = (int(b) for b in input().split())
a = [0]*(N+1)
a[0] = 1
for i in range(M):
    x = int(input())
    a[x] = -1
for i in range(1,N+1):
    if a[i] == -1:
        continue
    a1 = max(a[i - 2], 0)
    a2 = max(a[i - 1], 0)
    a[i] = a1 + a2
print(a[N]%(1000000000+7))

Submission status: Accepted

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

s=[0]*n

for _ in range(m):
  s[int(input())-1]=""
  
#print(s)

if n==1:
  print(1)
  exit()
elif n==2:
  if s[0]=="":
    print(1)
  else:
    print(2)
  exit()
  
if s[0]=="":
  s[0]=0
else:
  s[0]=1
  
if s[1]=="":
  s[1]=0
else:
  s[1]=1+s[0]

i=2
while i<n:
  if s[i]=="":
    s[i]=0
  else:
    s[i]=s[i-1]+s[i-2]
  i+=1
print(s[-1]%1000000007)

Submission status: Accepted

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

Submission status: Accepted

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

N, M = map(int, readline().split())
ans = [0] * (N + 2)
ans[0] = 1
for _ in range(M):
    a = int(readline())
    ans[a] = -1

for i in range(1, N + 1):
    if ans[i] == -1:
        continue
    a1 = max(ans[i - 2], 0)
    a2 = max(ans[i - 1], 0)
    ans[i] = a1 + a2

print(ans[N] % (10 ** 9 + 7))

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
a = [-1]
flag = True
 
if m>0:
  for i in range(m):
    a.append(int(input()))
    if a[i+1]==a[i]+1:
      flag = False
      break
  if not flag:
    print(0)
  else:
    a.append(n+1)
    step = [a[i+1]-a[i]-1 for i in range(m+1)]
    onestep = [1,1]
    if max(step)>=3:
      for i in range(3,max(step)+1):
        onestep.append(onestep[-2]+onestep[-1])
  
    ans = 1
    for i in range(m+1):
      ans *= onestep[step[i]-1]
    print(ans%1000000007)
else:
  onestep=[1,1]
  if n==1:
    print(1)
  else:
    for i in range(2,n+1):
      onestep.append(onestep[-2]+onestep[-1])
    print(onestep[-1]%1000000007)

Submission status: Accepted

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

MOD = 1000000007  # type: int

def solve(N: int, M: int, a: "List[int]"):
    p = [0] * (N+1)
    p[0] = 1

    for m in range(M-1):
        if a[m] + 1 == a[m + 1]:
            print(0)
            return

    a += [999999, 1999999]
    watch = 0
    if a[watch] == 1:
        watch += 1
        p[1] = 0
    else:
        p[1] = 1
    for n in range(2, N+1):
        if a[watch] == n:
            p[n] = 0
        elif a[watch] == n - 1:
            p[n] = p[n-2]
        elif a[watch] == n - 2:
            if a[watch+1] != n:
                p[n] = p[n-1]
            else:
                p[n] = 0
            watch += 1
        else:
            p[n] = p[n-1] + p[n-2]
    print(p[N] % MOD)
    return


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:
def Fib(n):
    a=[0,1,1]
    if n<=2:
    	return a[n]
    else:
    	for i in range(n-2):
    		a.append(a[i+1]+a[i+2])
    	return a[n]
n,m=map(int,input().split())
if m==0:
	print(Fib(n+1)%(10**9+7))
	exit()
a=[]
for i in range(m):
	a.append(int(input()))
if a[0]!=1:
	a.insert(0,-1)
if a[-1]!=n-1:
	a.append(n+1)
b=[]
for i in range(len(a)-1):
	b.append(a[i+1]-a[i]-1)
	if a[i+1]-a[i]==1:
		print(0)
		exit()
ans=1
for i in range(len(b)):
	ans*=Fib(b[i])
	ans%=10**9+7
print(ans)

Submission status: Accepted

Solution code:
import math
import copy
import fractions
import numpy as np

# ===FUNCTION===

def getInputNum():
    inputNum = int(input())
    return inputNum

def getInputListInt():
    outputoData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData

def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList

def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList

# ===CODE===

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

broken = getSomeInputInt(m)

mod = 1000000007

dp = np.zeros(n+1)
dp[0] = 1

brokenArray = np.ones(n+1)
for i in range(len(broken)):
    brokenArray[broken[i]] = 0


for i in range(n+1):
    if brokenArray[i] == 1 and i+1 < n+1:
        dp[i+1] += dp[i]
        dp[i+1] %= mod

    if brokenArray[i] == 1 and i+2 < n+1:
        dp[i + 2] += dp[i]
        dp[i + 2] %= mod

print(int(dp[n]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
MOD=10**9+7
N,M = [int(s) for s in input().split()]
ans=[1 for s in range(N+2)]
ans[N+1]=0
for i in range(M):
  ans[int(input())]=0
for i in range(1,N+1):
  if(ans[i]!=0):
    ans[i]=(ans[i-1]+ans[i-2])%MOD
print(ans[N])

Submission status: Accepted

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

a.insert(0, -1)
a.append(n + 1)
total = 1

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

for i in range(1, m + 2):
    interim = a[i] - a[i - 1] - 1
    if interim <= 0:
        total = total * 0
    else:
        total = total * Fib(interim)

ans = total % 1000000007
print(ans)

Submission status: Accepted

Solution code:
import sys

mod = 1000000007

"""
# 標準入力取得
## 文字列
    = sys.stdin.readline().rstrip()
    = list(sys.stdin.readline().rstrip())

## 数値
    = int(sys.stdin.readline())
    = map(int, sys.stdin.readline().split())
    = list(map(int, sys.stdin.readline().split()))
    = [list(map(int,list(sys.stdin.readline().split()))) for i in range(N)]
"""

if __name__ == "__main__":
    N , M = map(int, sys.stdin.readline().split())

    broken = [False for _ in range(N + 1)]
    for _ in range(M):
        broken[int(sys.stdin.readline())] = True

    L = [0] * (N + 1)
    L[0] = 1
    if not broken[1]:
        L[1] = 1
    for i in range(2, N + 1):
        if not broken[i]:
            L[i] = L[i - 1] + L[i - 2]
    print(L[N] % mod)

Submission status: Accepted

Solution code:
def dp(n):
    d=[0]*(n+1)
    if n==1:
        return 1
    else:
         d[0]=1
         if a[1]==0:
            d[1]=1
         else:
            d[1]=0
         for i in range(2,n+1):
            if a[i]==0:
                d[i]=(d[i-1]+d[i-2])%1000000007
            else:
                d[i]=0
         return d[n]

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

Submission status: Accepted

Solution code:
def dp(n):
    d=[0]*(n+1)
    if n==1:
        return 1
    else:
         d[0]=1
         if a[1]==0:
            d[1]=1
         else:
            d[1]=0
         for i in range(2,n+1):
            if a[i]==0:
                d[i]=d[i-1]+d[i-2]
            else:
                d[i]=0
         return d[n]

n,m=map(int, input().split())
a=[0]*(n+1)
for i in range(0,m):
    k=int(input())
    a[k]=1
print(dp(n)%1000000007)

Submission status: Accepted

Solution code:
def main():
    n, m = map(int, input().split())
    a = [0] * n
    step = [0] * (n + 1)
    for i in range(m):
        step[int(input())] = -1
    step[0] = 1
    step[1] = 1 if step[1] != -1 else -1
    for i in range(2, n + 1):
        if step[i - 2] == -1 and step[i - 1] == -1:
            print(0)
            return
        if step[i] == -1:
            continue
        step[i] = (step[i - 2] if step[i - 2] != -1 else 0) + \
            (step[i - 1] if step[i - 1] != -1 else 0)
        step[i] %= 1000000007
    print(step[n])


if __name__ == '__main__':
    main()

Submission status: Accepted

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

  if a[0]==1:
    way=[1, 0]
    a.remove(1)
  else:
    way=[1, 1]
else:
  a=[]
  way=[1, 1]
  
for i in range(2, N+1):
  if len(a)>0:
    if i==a[0]:
      a.remove(i)
      way=[way[1], 0]
    else:
      way=[way[1], sum(way)]
  else:
    way=[way[1], sum(way)]
    
print(way[1]%1000000007)

Submission status: Accepted

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

mod = 10**9+7
n, m = map(int, input().split())
broken = set(int(input()) for i in range(m))

pattern = [0]*(n+1)
pattern[0] = 1
if 1 in broken:
    pattern[1] = 0
else:
    pattern[1] = 1

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

print(pattern[n])

Submission status: Accepted

Solution code:
import sys


input = sys.stdin.readline

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

pattern = [0]*(n+1)
pattern[0] = 1
if 1 in broken:
    pattern[1] = 0
else:
    pattern[1] = 1

for i in range(2, n+1):
    if i in broken:
        pattern[i] = 0
    else:
        pattern[i] = pattern[i-1] + pattern[i-2]

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

Submission status: Accepted

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

dp=[-1]*(N+1)
idx=0
dp[0]=1
if idx<M:
    if A[idx]==1:
        dp[1]=0
        idx+=1
if dp[1]==-1:dp[1]=1

for i in range(2,N+1):
    if idx<M:
        if A[idx]==i:
            dp[i]=0
            idx+=1
    if dp[i]==-1:
        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

def main(): 
    N,M=map(int,input().split())
    a=[int(input()) for _ in range(M)]
    a.sort(reverse=True)
    ans=[0]*(N+1)
    ans[0]=1
    if not(len(a) != 0 and a[-1] == 1):
        ans[1]=1
    else:
        a.pop()
    for i in range(2,N+1):
        if len(a) != 0 and a[-1] == i:
            a.pop()
        else:
            ans[i] = ans[i-1]+ans[i-2]
            #ans[i]%=1000000007
    print(ans[N]%1000000007)
if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

f = [0 for i in range(n)]
f[-2:] = [1, 1]
for i in range(m):
  f[int(input())-1] = -1

div_num = 1000000007

for i in range(n-2)[::-1]:
  if f[i] == -1:
    continue
  if f[i+1] == -1 and f[i+2] == -1:
    print(0)
    exit()
  elif f[i+1] == -1 and f[i+2] != -1:
    f[i] = f[i+2]
  elif f[i+1] != -1 and f[i+2] == -1:
    f[i] = f[i+1]
  else:
    f[i] = f[i+1]+f[i+2]

if f[0] != -1 and f[1] != -1:
  print(int((f[0]+f[1])%div_num))
elif f[0] == -1 and f[1] != -1:
  print(int(f[1]%div_num))
elif f[0] != -1 and f[1] == -1:
  print(int(f[0]%div_num))
else:
  print(0)

Submission status: Accepted

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

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

f = [0 for i in range(n)]
f[-2:] = [1, 1]
for i in range(m):
  f[int(input())-1] = -1

div_num = 1000000007

for i in range(n-2)[::-1]:
  if f[i] == -1:
    continue
  if f[i+1] == -1 and f[i+2] == -1:
    print(0)
    exit()
  elif f[i+1] == -1 and f[i+2] != -1:
    f[i] = f[i+2]
  elif f[i+1] != -1 and f[i+2] == -1:
    f[i] = f[i+1]
  else:
    f[i] = f[i+1]+f[i+2]

if f[0] != -1 and f[1] != -1:
  print(int((f[0]+f[1])%div_num))
elif f[0] == -1 and f[1] != -1:
  print(int(f[1]%div_num))
elif f[0] != -1 and f[1] == -1:
  print(int(f[0]%div_num))
else:
  print(0)

Submission status: Accepted

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

m = [0] * n
m[0] = 1 if 1 not in a else 0

if n == 1:
    print(m[0])
    exit()

m[1] = 2 if 2 not in a else 0

if m[0] == 0 and m[1] == 2:
    m[1] = 1

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

print(m[-1] % 1000000007)

Submission status: Accepted

Solution code:
mod = 10**9+7
n,m = map(int,input().split())

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

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

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

print(dp[n]%mod)

Submission status: Accepted

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

for _ in range(m):
    idx = int(input())
    dp[idx] = 0
for i in range(2,n+1):
    if dp[i] != 0:
        dp[i] = dp[i-1] + dp[i-2]
print(dp[-1]%1000000007)

Submission status: Accepted

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

a = [-1] + a + [N+1] #add beginning and end

# list of steps between broken steps
s1=[]
for i in range(len(a)-1):
    if a[i+1]-a[i]-2<0:
        flag = False
        break
    s1.append(a[i+1]-a[i]-2) 

if flag==False:
    print(0)    
else:     
    # possibile ways for steps
    s2 = [1, 1, 2]
    while len(s2) < max(s1)+1:
        s2.append(s2[-2]+s2[-1])
    
    # possible ways for all
    s3 = 1 
    for j in s1:
        s3 = s3 * s2[j] 
        
    s4 = s3 % 1000000007 
    print(s4)

Submission status: Accepted

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

a = [-1] + a + [N+1] #add beginning and end

# list of steps between broken steps
s1=[]
for i in range(len(a)-1):
    if a[i+1]-a[i]-2<0:
        flag = False
        break
    s1.append(a[i+1]-a[i]-2) 

if flag==False:
    print(0)    
else:     
    # possibile ways for steps
    s2 = [1, 1, 2]
    while len(s2) < N+1:
        s2.append(s2[-2]+s2[-1])
    
    # possible ways for all
    s3 = 1 
    for j in s1:
        s3 = s3 * s2[j] 
        
    s4 = s3 % 1000000007 
    print(s4)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
dp=[1]*(N+1)
for _ in range(M):
  i=int(input())
  dp[i]=0
for i in range(2,N+1):
  if dp[i]!=0:
      dp[i]=dp[i-1]+dp[i-2]
  dp[i]%=1000000007
print(dp[N])

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc129/tasks/abc129_c
# C - Typical Stairs

n, m = list(map(int, input().split()))
a_list = []

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

steps_list = [dict(fx1=True, fx2=True) for _ in range(n + 1)]

for step_index in a_list:
    steps_list[step_index] = dict(fx1=False, fx2=False)

    if step_index < n - 1:
        steps_list[step_index + 1]['fx1'] = False
    if step_index < n - 2:
        steps_list[step_index + 2]['fx2'] = False

steps_list[1]['fx2'] = False
p_count_list = [0] * (n + 1)

# fx段目に登る方法は、（fx-1 + fx-2）方法ある
# ただし、x-1が壊れている場合はfx-2通り
# x-2が壊れている場合はfx-1通り
for i, op in enumerate(steps_list):
    if i == 0:
        p_count_list[i] = 1
        continue

    p_count = 0
    if steps_list[i]['fx1']:
        p_count += p_count_list[i-1]
    if steps_list[i]['fx2']:
        p_count += p_count_list[i-2]

    p_count_list[i] = p_count % 1000000007

# print(p_count_list)
ans = p_count_list[-1]
print(ans)

Submission status: Accepted

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

if m > 0:
  As = set(map(int, sys.stdin))
else:
  As = set()

nums = [0] * (n + 1)
nums[0] = 1
if 1 in As:
  pass
else:
  nums[1] = 1
  
for i in range(2, n + 1):
  if i in As:
    continue
  else:
    nums[i] = (nums[i-1] + nums[i-2]) % 1000000007
    
print(nums[-1])

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

n, m = map(int, input().split())
mod = 10 ** 9 + 7
broken_steps = [False for _ in range(n + 1)]

for _ in range(m):
    broken_steps[int(input())] = True

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

for now in range(n):
    next = now + 1
    if not broken_steps[next]:
        steps[next] = (steps[now] + steps[now - 1]) % mod

print(steps[n])

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

n, m = map(int, input().split())
mod = 10 ** 9 + 7
broken_steps = [False for _ in range(n)]

for _ in range(m):
    a = int(input())
    broken_steps[a - 1] = True

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

for i in range(n):
    if not broken_steps[i]:
        steps[i + 1] = (steps[i] + steps[i - 1]) % mod

print(steps[n])

Submission status: Accepted

Solution code:
n,m = map(int,input().split(" "))
s = [0]*(n+1)
flag = 0
for i in range(m):
    s[int(input())] = 1
    if i>=1 and s[i-1] == 1 and s[i] == 1:
        flag = 1
i = 0
counter = 1
dp = [0 for i in range(n+1)]
dp[0] = 1
for i in range(0,n+1):
    for j in range(i+1,min(i+3,n+1)):
        if s[j] ==0:
            dp[j] += dp[i]
if flag == 1:
    print(0)
else: 
    print(dp[n] % 1000000007)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
MOD = 10**9 + 7

def main():
    N, M = map(int, input().split())
    broken_floors = set(int(input()) for _ in range(M))
    dp = [0]*(N+2)
    dp[1] = 1

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

    print(dp[-1])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
MOD = 10**9 + 7

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

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

print(dp[-1])

Submission status: Accepted

Solution code:
big = 10**9 + 7

def typical_stairs(n,m,a):

    flag = [True]*(n+1)
    for i in range(m):
        tmp = a[i]
        flag[tmp] = False

    route = [0]*(n+1)
    route[0] = 1
    ans = route[0]
    if flag[1]:
        route[1] = 1
    else:
        route[1] = 0

    for i in range(2,n+1):
        if flag[i]:
            route[i] = route[i-1] + route[i-2]

        ans = route[i]

    return ans%big
if __name__ == '__main__':
    n,m = map(int,raw_input().split())
    a = [int(raw_input()) for _ in range(m)]
    print typical_stairs(n,m,a)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    N, M = map(int, input().split())
    A = {}
    mod = 10**9+7
    for _ in range(M):
        k = int(input())
        l = int(k)
        A[k] = 1
    answer = [0] * (N+1)
    answer[0] = 1
    if 1 in A:
        answer[1] = 0
    else:
        answer[1] = answer[0]
    
    for i in range(2,N+1):
        if i in A:
            answer[i] = 0
        else:
            answer[i] = (answer[i-1] + answer[i-2])%mod
    print(answer[-1])
    
    
    
main()

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
N, M = map(int,input().split())
a = 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 a and i > 1:
        dp[i] = (dp[i-1] + dp[i-2]) % MOD
    elif i not in a and i == 1:
        dp[i] = dp[i-1]
print(dp[-1])

Submission status: Accepted

Solution code:
def main():
    N, M = map(int, input().split())
    a = set()
    for _ in range(M):
        a.add(int(input()))

    mod = pow(10, 9) + 7
    dp = [0 for _ in range(N+1)]
    dp[0] = 1
    for i in range(1, N+1):
        if i in a:
            dp[i] = 0
        else:
            if i == 1:
                dp[i] = dp[i-1]
            else:
                dp[i] = dp[i-1] + dp[i-2]
        dp[i] %= mod
    return dp[N]

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

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
a = list(int(input()) for i in range(M))
a.append(N+1)
a.insert(0,-1)
if a[0] == 0:
  print(0)
  exit()
#パターン数はフィボナッチ数列で通り数が増える
def Fib(n):
    a, b = 1, 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
#aとa+1の間の距離nに対して、フィボナッチ数列n+1番目数のパターンが有る
ans = 1
if M > 1:
    for i in range(len(a)-1):
        n = a[i+1]-a[i]-1
        if n == 0:
            print(0)
            exit()
        ans = ans*Fib(n)%1000000007
        i += 1
    print(ans)
elif M == 1:
    print(Fib(a[1])%1000000007 * Fib(N-a[1])%1000000007)
elif M == 0:
    print(Fib(N+1)%1000000007)

Submission status: Accepted

Solution code:
from functools import lru_cache
from sys import setrecursionlimit

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

mod = 10**9+7
setrecursionlimit(mod)

@lru_cache(maxsize=n)
def stairway(i) :
    if i in a :
        return 0
    elif i == 0 :
        return 1
    elif i == 1 :
        return stairway(0)
    else :
        return (stairway(i-1)+stairway(i-2))%mod
    
print(stairway(n))

Submission status: Accepted

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

MOD = 10 ** 9 + 7
n,m = map(int,input().split())
A = set(int(input()) for _ in range(m)) #壊れた階段

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

for i in range(1,n+1):
    if i in A:
        continue
    x = dp[i-1]
    if i > 1:
        x += dp[i-2]
    dp[i] = x%MOD

print(dp[n])

Submission status: Accepted

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

Bs = []
if len(As) == 0:
    Bs.append(N + 1)
else:
    Bs.append(As[0])
    for i in range(M-1):
        Bs.append(As[i+1] - As[i] - 1)
    Bs.append(N - As[-1])

count = [0, 1, 1]
for i in range(3, max(Bs)+1):
    count.append(count[i - 1] + count[i - 2])

res = 1
for b in Bs:
    res *= count[b]
    res %= 1000000007

print(res)

Submission status: Accepted

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

b=[]
num=0
if len(a)>1:
    b.append(a[1]-a[0]-1)
    for i in range(1,M):
            b.append(a[i+1]-a[i]-2)
    b.append(N-a[M]-1)
else:
    b.append(N)

num=max(b)

mod=1000000007

fib=[0 for i in range(num+10)]
fib[0]=1
fib[1]=1
for i in range(2,num+1):
    fib[i]=fib[i-1]+fib[i-2]

if -1 in b:
    print(0)
else:
    p=1
    for j in range(M+1):
        p*=fib[b[j]]
    print(p%mod)

Submission status: Accepted

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

# print(a)

mod = 10**9 + 7

d = [0]*(n+1)
# print(len(d))
# print(d)
d[0] = 1
d[1] = 1
for i in a:
    d[i] = -1

# print(d)


for i in range(2,n+1):
    if d[i]==0 and d[i-1]==-1 and d[i-2]==-1:
        print(0)
        exit()
    elif d[i]==0 and d[i-1]==-1 and d[i-2]!=-1:
        d[i] = d[i-2]
    elif d[i]==0 and d[i-1]!=-1 and d[i-2]==-1:
        d[i] = d[i-1]
    elif d[i]==0 and d[i-1]!=-1 and d[i-2]!=-1:
        d[i] = d[i-1] + d[i-2]
# print(d)
print(d[n]%mod)

Submission status: Accepted

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

DENOMINATOR = 1000000007

pos = 0
route = 1
before = 0

for i in range(1, N+1):
    route, before = route+before, route
    if pos < M:
        if A[pos] == i:
            route = 0
            pos+=1

print(route%DENOMINATOR)

Submission status: Accepted

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

b=[]
num=0
if len(a)>1:
    b.append(a[1]-a[0]-1)
    for i in range(1,M):
            b.append(a[i+1]-a[i]-2)
    b.append(N-a[M]-1)
else:
    b.append(N)

num=max(b)


mod=1000000007

def fib(n,num):
    fib=[0 for i in range(num+10)]
    fib[0]=1
    fib[1]=1
    for i in range(2,num+1):
        fib[i]=fib[i-1]+fib[i-2]
    return fib[n]

if -1 in b:
    print(0)
else:
    p=1
    for j in range(M+1):
        p*=fib(b[j],num)
    print(p%mod)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
a = set(int(input()) for i in range(M)) 

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

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

print (A[-1])

Submission status: Accepted

Solution code:
def resolve():
    n, m = list(map(int, input().split()))
    mod = 10 ** 9 + 7
    is_safe = [True] * (n + 1)
    broken = list(int(input()) for _ in range(m))
    for b in broken:
        is_safe[b] = False

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


if __name__ == "__main__":
    resolve()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,M = (int(i) for i in input().split())
ban=[False]*(N+1)
for i in range(M):
    a=int(input())
    ban[a]='True'
    
dp=[0]*(N+1)
dp[0]=1
if ban[1]=='True':
    dp[1]=0
else:
    dp[1]=1

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

Submission status: Accepted

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

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

print(dp[n]%1000000007)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = set([int(input()) for _ in range(M)])
 
dp = [0, 1]
for i in range(N):
    if i+1 in A: dp.append(0)
    else: dp.append(dp[i]+dp[i+1])
print(dp[N+1]%1000000007)

Submission status: Accepted

Solution code:
dp = [1] * (10**5 + 1)
dp[2] = 2
for i in range(3, 10**5+1):
    dp[i] = (dp[i-1] + dp[i-2]) % 1000000007

n, m = map(int, input().split())
start = 0
res = 1
for i in range(m):
    nex = int(input())
    if nex == start:
        res = 0
        break
    res = (res * dp[(nex-1)-start]) % 1000000007
    #print('res :', res)
    start = nex + 1
else:
    res = (res * dp[n - start]) % 1000000007
    #print('res :', res)
print(res)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, M = map(lambda x: int(x), input().split())
a = [int(input()) for _ in range(M)]
mod = 1e9+7

is_broken = [False]*(N+1)
for aa in a:
    is_broken[aa] = True

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

for now in range(N):
    for next in range(now+1, min(N, now+2)+1):
        if not is_broken[next]:
            dp[next] += dp[now]
            dp[next] %= mod
print(int(dp[N]))

Submission status: Accepted

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

mod = 10**9+7

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

Submission status: Accepted

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

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

print(dp[-1])

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(110000)

d = {}


def calc_step_combination(num):
    if num == 0:
        return 0
    if num == 1 or num == 2:
        return 1
    if num in d:
        return d[num]
    res = calc_step_combination(num - 1) + calc_step_combination(num - 2)
    d[num] = res
    return res


def sol(n, a_list):
    step_batch = []
    batch_start = 0
    for a in a_list:
        step_batch.append(a - batch_start)
        batch_start = a + 1
    step_batch.append(n - batch_start + 1)

    result = 1
    for i, steps in enumerate(step_batch):
        result *= calc_step_combination(steps)
    print(result % 1000000007)


def main():
    n, m = map(int, input().split())
    a_list = []
    for i in range(0, m):
        a_list.append(int(input()))
    sol(n, a_list)


main()