Problem:


Score : 300 points

Problem Statement

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

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

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

Constraints

1 \leq N \leq 10^5

0 \leq M \leq N-1

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

Input

Input is given from Standard Input in the following format:

N M
a_1
a_2
 .
 .
 .
a_M

Output

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

Sample Input 1

6 1
3

Sample Output 1

4

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

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

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

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

0 \to 2 \to 4 \to 6

Sample Input 2

10 2
4
5

Sample Output 2

0

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

Sample Input 3

100 5
1
23
45
67
89

Sample Output 3

608200469

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



Sample input:
6 1
3


Sample output:
4

Submission status: Accepted

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

MOD = 1000000007
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

for i in range(1, n+1):
    if hole[i]: dp[i] = 0
    else:
        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 i in range(M)]
MOD = 10**9+7
A = set(A)
dp = [0]*(N+1)
dp[0] = 1
for i in range(1,N+1):
    if i in A:
        continue
    if i == 1:
        dp[1] = dp[0]
    else:
        dp[i] = (dp[i-1]+dp[i-2])%MOD
print(dp[N])

Submission status: Accepted

Solution code:
n,m = (int(i) for i in input().split())
a = [int(input()) for i in range(m)]
mod = 1000000007
oks = [True for _ in range(n+1)]
for i in a:
    oks[i] = False
dp = [1,0]
dp[1] = 1 if oks[1] is True else 0
for i in range(2,n+1):
    if oks[i] is True:
        dp.append((dp[i-1]+dp[i-2])%mod)
    else:
        dp.append(0)
print(dp[n])

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
mods = 1000000007
n, m = [int(x) for x in input().split()]
bads = [True] * (n + 1)
for i in range(m):
    bads[int(input())] = False
dp = [0] * (n + 1)
dp[0] = 1
for curr in range(n):
    for next in range(curr + 1, min(n, curr + 2) + 1):
        if bads[next]:
            dp[next] += dp[curr]
            dp[next] %= mods
print(dp[n])

Submission status: Accepted

Solution code:
def reads():
    return list(map(int, input().split()))

MOD = 10**9 + 7

N, M = reads()
proh = set()
for _ in range(M):
    a, = reads()
    proh.add(a)

res = [0] * (N + 2)
res[0] = 1
for i in range(1, N+1):
    if i not in proh:
        res[i] = (res[i-1] + res[i-2]) % MOD
print(res[N])

Submission status: Accepted

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


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

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

Submission status: Accepted

Solution code:
N,M = (int(i) for i in input().split())
a = set([int(input()) for i in range(M)])
hoge = [0] * N
if 1 not in a:
    hoge[0] = 1
if 2 not in a and N >= 2:
    hoge[1] = hoge[0] + 1

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

print(hoge[N-1] % (10**9 + 7))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=[int(input()) for i in range(m)]
rd=[True for i in range(n+1)]
mod=1000000007
for i in a:
    rd[i]=False
dp=[1]+[0 for i in range(n)]
for i in range(n):
    for j in range(i+1,min(i+3,n+1)):
        if rd[j]:
            dp[j]+=dp[i]
            dp[j]%=mod
print(dp[n])

Submission status: Accepted

Solution code:
N,M = (int(i) for i in input().split())
a = set([int(input()) for i in range(M)])
hoge = [0] * N
if 1 not in a:
    hoge[0] = 1
if 2 not in a and N >= 2:
    hoge[1] = hoge[0] + 1

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

print(hoge[N-1] % (10**9 + 7))

Submission status: Accepted

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

res = 1
for i in range(1, len(a)):
    steps = a[i] - a[i-1] - 2
    if steps < 0:
        patern_nmu = 0
    elif steps <= 1:
        patern_nmu = 1
    elif steps <= 2:
        patern_nmu = 2
    else:
        p, q = 2, 1
        for j in range(1, steps-1):
            p, q = p+q, p
        patern_nmu = p
    res *= patern_nmu
    res %= 1000000007

print(res)

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

print(dp[N] % mod)

Submission status: Accepted

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

res = 1
for i in range(1, len(a)):
    if a[i] == 1:
        continue
    tmp = a[i] - a[i-1] - 2
    if tmp < 0:
        tmp2 = 0
    elif tmp <= 1:
        tmp2 = 1
    elif tmp <= 2:
        tmp2 = 2
    else:
        p, q = 2, 1
        for j in range(1, tmp-1):
            p, q = p+q, p
        tmp2 = p
    res *= tmp2
    res %= 1000000007

print(res)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
a = []
ans = -1
MOD = 10 ** 9 + 7
if N == 1:
    ans = 1
else:
    if M > 0:
        a += [int(input())]
    for i in range(M - 1):
        a += [int(input())]
        if a[i + 1] - a[i] == 1:
            ans = 0
            break
    a.append([-1])
if not ans in [0, 1]:
    memo = [0] * (N + 1)
    memo[0] = 1
    if a[0] == 1:
        memo[1] = 0
        j = 1
    else:
        memo[1] = 1
        j = 0
    for i in range(N - 1):
        if i + 2 == a[j]:
            j += 1
            continue
        memo[i + 2] = memo[i] + memo[i + 1]
        memo[i + 2] = memo[i + 2] % MOD
    else:
        ans = memo[i + 2]
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
a = []
ans = -1
MOD = 10 ** 9 + 7
if N == 1:
    ans = 1
else:
    if M > 0:
        a += [int(input())]
    for i in range(M - 1):
        a += [int(input())]
        if a[i + 1] - a[i] == 1:
            ans = 0
            break
    a.append([-1])
if not ans in [0, 1]:
    memo = [0] * (N + 1)
    memo[0] = 1
    memo[1] = 1
    try:
        if a[0] == 1:
            a.pop(0)
            memo[1] = 0
    except:
        pass
    j = 0
    for i in range(N - 1):
        if i + 2 == a[j]:
            j += 1
            continue
        memo[i + 2] = memo[i] + memo[i + 1]
        memo[i + 2] = memo[i + 2] % MOD
    else:
        ans = memo[i + 2]
print(ans)

Submission status: Accepted

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

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

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

print(dp[n])

Submission status: Accepted

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

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

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

print(dp[n])

Submission status: Accepted

Solution code:
N,M = list(map(int,input().split()))
A = set(int(input())-1 for i in range(M))

S = []
for i in range(N):
  if i not in A: 
    if i == 0 :
      S += [1]
    elif i == 1:
      S += [S[0] + 1]
    else:
      S += [(S[i-1] + S[i-2]) % int(1e9+7)]
  else:
    S += [0]

print(S[-1])

Submission status: Accepted

Solution code:
from functools import lru_cache
import sys

sys.setrecursionlimit(1000000)

mod = 10 ** 9 + 7

@lru_cache(maxsize=1000000)
def saiki(i):
    if ok[i]:
        if i == 0:
            return 1
        if i == 1:
            return 1
        return saiki(i - 1) % mod + saiki(i - 2) % mod
    else:
        return 0


n, m = map(int, input().split())
a = [int(input()) for i in range(m)]
ok = [True] * (n + 1)
for i in a:
    ok[i] = False
print(saiki(n) % mod)

Submission status: Accepted

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

MOD = int(1e9 + 7)
N, M = map(int, input().split())

broken = [False] * (N + 1)
for i in range(M):
    broken[int(input())] = True

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

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

print(dp[N] % MOD)

Submission status: Accepted

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


s = [0] * (n + 1)
s[0] = 1
for i in range(n):
    j = i + 1
    while(j <= min(n, i + 2)):
        if j not in a:
            s[j] += s[i]
            s[j] = int(s[j] % 1000000007)
        j += 1

print(s[n])

Submission status: Accepted

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

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

wa = (10**9) + 7

#dpを使う

dp = [0]*(N+1)
dp[0]=1
now_a = 0
if len(a)==0:
    now_a = -1
if len(a)!=0:
    a.reverse()
    now_a = a.pop()

for i in range(1,N+1):
    # print(now_a)
    if i==1:
        dp[i]=dp[i-1]
    else:
        dp[i]=dp[i-1] + dp[i-2]
    if i == now_a:
        dp[i]=0
        if len(a)!=0:
            now_a = a.pop()
        else:
            now_a = -1

# print(dp)

print(dp[N]%wa)

Submission status: Accepted

Solution code:
N, M = map(int, input().split(" "))
mod = 1000000007
aList = 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]
    if i in aList :
        dp[i] = 0
print(dp[N]%mod)

Submission status: Accepted

Solution code:
def fib(n):
    if n == 1 or n == 2:
        return 1
    else:
        a = 1
        b = 0
        for _ in range(n-1):
            (a, b) = (a+b, a)
        return a % (10 ** 9 + 7)


def counter(n):
    if n == 0:
        return 0
    else:
#        f = round(phi**(n) / math.sqrt(5)) % (10**9+7)
        return fib(n)


N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
if M == 0:
    print(counter(N+1))
    exit()
a.append(N+1)
ans = counter(a[0])
for i in range(1,M+1):
    ans = (ans * counter(a[i]-a[i-1]-1)) % (10**9+7)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
a=list(int(input())for _ in range(M))
L=[1 for i in range(N+1)]
dp=[0 for _ in range(N+1)]
#L[0]=0
dp[0]=1
mod=1000000007
for j in a:
    L[j]=0
for i in range(1,N+1):
    if i>=2:
        dp[i]=(dp[i-1]*L[i-1]+dp[i-2]*L[i-2])*L[i]

    elif i==1:
        dp[i]=1
    dp[i]%=mod

print(dp[N])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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


num=[1,1,2]


mod=1000000007

count=0
jud=1
ans=1
for i in range(n+1):
	
	if i>2:
		num.append(1)
		num[i]=(num[i-1]+num[i-2])%mod

	if(jud==0 and a[i]==1):
		print("0")
		break
	elif a[i]==1:
		ans=(ans%mod)*(num[count-1]%mod)
		count=0
		jud=0
	elif(i==n):
		count+=1
		ans=(ans%mod)*(num[count-1]%mod)
		print(ans%mod)
	else:
		jud=1
		count+=1

Submission status: Accepted

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

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

aa = [] #aの差を取ったもののリスト
if M >= 2:
    for k in range(M-1):
        aa.append(a[k+1] - a[k] - 1)
#print(aa)
#aa.append(N - a(M))

    if 0 in aa:
        ans = 0

    else:
        ans = 1
        ans_list = []
        for i in range(M-1):
            ans_list.append(fibo(aa[i]))

        ans_list.append(fibo(a[0]))
        ans_list.append(fibo(N - a[M-1]))
    #print(ans_list)
    
        for i in range (len(ans_list)):
            ans = (ans * ans_list[i]) % (10**9 + 7)

elif M == 1:
    ans_list = []
    ans_list.append(fibo(a[0]))
    ans_list.append(fibo(N - a[0]))
    ans = (ans_list[0] * ans_list[1]) % (10**9 + 7)

elif M == 0:
    ans = fibo(N+1) % (10**9 + 7)

print(ans)

Submission status: Accepted

Solution code:
#C

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

p = 0
num = [1]
if p>=m:
    num.append(1)
elif a[p] == 1:
    num.append(0)
    p += 1
else:
    num.append(1)

for i in range(2,n+1):
    if p>=m:
        temp = num[-2]+num[-1]
        num.append(temp)
    elif a[p] == i:
        num.append(0)
        p += 1
    else:
        temp = num[-2]+num[-1]
        num.append(temp)

print(num[-1]%1000000007)

Submission status: Accepted

Solution code:
def main():
    n, m = map(int, input().split())
    if m != 0:
        a = [int(input()) for _ in range(m)]
        a = set(a)
    else:
        a = set()
    
    s = [0] * (n+1)
    s[0] = 1
    s[1] = 1 if 1 not in a else 0

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

    print(s[n])

main()

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
a=[]
b=[0]*N
for i in range(M):
    a.append(int(input()))
if M==0:
    j=-1
else:
    j=0
if N==1:
    b[0]=1
elif M>0 and a[0]==1:
    b[0]=0
    b[1]=1
elif M>0 and a[0]==2:
    b[0]=1
    b[1]=1
else:
    b[0]=1
    b[1]=2
for i in range(N-2):
    if j==M-1 or (j>=0 and (i+2)!=a[j] and (i+1)!=a[j]):
        b[i+2]=b[i+1]+b[i]
    if j>0 and a[j]==a[j-1]+1:
        b[N-1]=0
    if j+1<M and a[j+1]==a[j]+1:
        b[N-1]=0
    elif j>=0 and (i+2)==a[j]:
        b[i+2]=b[i]
    elif j>=0 and j+1<M and (i+1)==a[j]:
        j+=1
        b[i+2]=b[i+1]
    elif j>=0 and (i+1)==a[j]:
        b[i+2]=b[i+1]
print(b[N-1]%1000000007)

Submission status: Accepted

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
mod = 10**9+7
n, m = map(int, input().split())
broken = {int(input()) for _ in range(m)}

dp = [0]*(n+1)
dp[0] = 1
for i in range(n+1):
    for j in (1, 2):
        nex = i+j
        if nex <= n and not nex in broken:
            dp[nex] += dp[i]
            dp[nex] %= mod
print(dp[-1])

Submission status: Accepted

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
MOD = 10**9+7
N, M = map(int, input().split())
broken = {int(input()) for _ in range(M)}

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

Submission status: Accepted

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

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

# all element of stairs
for i in range(N, -1, -1):
	# last is always 1
	if i == N:
		stairs[i] = 1
	# if stair[N - 1] is not broken 
	elif i == N - 1 and stairs[i] != -1:
		stairs[i] = stairs[i + 1]
	# if stairs[i] is not broken
	elif stairs[i] != -1:
		if stairs[i + 1] != -1:
			stairs[i] += stairs[i + 1]
		if stairs[i + 2] != -1:
			stairs[i] += stairs[i + 2]
print(int(stairs[0]) % 1000000007)

Submission status: Accepted

Solution code:
n, m = list(map(int, input().split() ))
broken = [int(input()) for _ in range(m)]
broken.append(-1) #番兵
broken_idx = 0

mod = 10**9+7

num_way = [0] * (n+1)
num_way[0] = 1
if broken[broken_idx] == 1:
	num_way[1] = 0
	broken_idx += 1
else:
	num_way[1] = 1

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

print (num_way[n])

Submission status: Accepted

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

dp = [0] * (n+1)
for j in range(n+1):
    if a[j] == 1:
        dp[j] = 0
    elif j == 1 or j == 0:
        dp[j] = 1
    else:
        dp[j] = (dp[j-1] + dp[j-2]) % mod

print(dp[n])

Submission status: Accepted

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

mod = 10 ** 9 + 7

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

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

print(dp[n] % mod)

Submission status: Accepted

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

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

S = [0] * (N+1)
S[0] = 1
for n in range(1, N+1):
    if a[n]==False:
        S[n] = 0
    elif n==1:
        S[n] = 1
    else:
        S[n] = (S[n-1] + S[n-2])%1000000007

print(S[n])

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(1000000)

N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
MOD = 1000000007
dp = [-1] * (N + 1)
dp[0] = 1
dp[1] = 1
for a in A:
    dp[a] = 0


def rec(n):
    if n < 0:
        return 0
    if dp[n] != -1:
        return dp[n]
    num = rec(n - 1) + rec(n - 2)
    dp[n] = num
    return num


print(rec(N) % MOD)

Submission status: Accepted

Solution code:
import sys

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

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

    return dp[N+1]


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

Submission status: Accepted

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

cs = [0] * (N + 1)

cs[0] = 1

M = 10**9+7

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

result = cs[N]

print(result)

Submission status: Accepted

Solution code:
def c_typical_stairs(N, M, A, MOD=10**9 + 7):
    a = set(A)
    way_go_up_the_stairs = [1] + [0] * (N)
    for i in range(1, N + 1):
        if i not in a:
            way_go_up_the_stairs[i] += sum([way_go_up_the_stairs[i - j - 1]
                                            for j in range(2) if i - j >= 0])
            way_go_up_the_stairs[i] %= MOD
    return way_go_up_the_stairs[N]

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

Submission status: Accepted

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

dp=[0 for _ in range(N+1)]
dp[0]=1
for i in range(N+1):
    if broken[i]==False:
        continue
    else:
        if i==0:
            continue
        elif i==1:
            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())
P = 10**9+7

dp = [-1 for _ in range(n+1)]
dp[0] = 1
dp[1] = 1
for _ in range(m):
  dp[int(input())] = 0

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

print(dp[-1])

Submission status: Accepted

Solution code:
import sys
N, M = map(int, input().split())
if N == 1:
    print(1)
    sys.exit()
ana = [0] * M
ans = [0] * N
mod = 10 ** 9 + 7
if M != 0:
    for i in range(M):
      ans[int(input())-1] = -1
if ans[0] == -1 and ans[1] == -1:
    print(0)
    sys.exit()
elif ans[0] == -1:
    ans[0] = 0
    ans[1] = 1
elif ans[1] == -1:
    ans[0] = 1
    ans[1] = 0
else:
    ans[0] = 1
    ans[1] = 2

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

Submission status: Accepted

Solution code:
from sys import stdin
N, M = [int(_) for _ in stdin.readline().rstrip().split()]
dp = [1 for i in range(N+1)]
MOD = 1000000007
for _ in range(M):
  a = int(stdin.readline().rstrip())
  dp[a] = 0
for i in range(2, N+1):
    if dp[i] == 0:
        continue
    dp[i] = dp[i-1]+dp[i-2]
print(dp[N] % MOD)

Submission status: Accepted

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

past = 1
past_past = 0
mod = 10**9 + 7

for is_broken in is_broken_array:
    if is_broken:
        now = 0
        # print(past_past, past, now)
    else:
        now = past + past_past
        # print(past_past, past, now)
        now = now % mod
    past_past = past
    past = now

print(now)

Submission status: Accepted

Solution code:
import sys
mod = 10**9+7
def main():
    n,m=map(int,input().split(' '))
    if m > 0:
        aaa = set(map(int,sys.stdin))
    else:
        aaa = set()

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

    print(dp[n])

main()

Submission status: Accepted

Solution code:
import sys
mod = 10**9+7
def main():
    n,m=map(int,input().split(' '))
    if m > 0:
        aaa = set(map(int,sys.stdin))
    else:
        aaa = set()

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

    print(dp[n]%mod)

main()

Submission status: Accepted

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

dp[0] = 1

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

print(dp[N])

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

print(dp[N] % mod)

Submission status: Accepted

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

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

for _ in range(M):
  i = int(input()) + 1
  step[i] = -1

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

print (step[-1] % 1000000007)

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

print(dp[N] % mod)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
try:
  a = int(input())
except EOFError:
  a = 0
P = [0]*(N+1)
P[0] = 1
if a == 1:
  P[1] = 0
  try:
    a = int(input())
  except EOFError:
    pass
    
else:
  P[1] = 1

for i in range(2,N+1):
  if i == a:
    P[i] = 0
    try:
      a = int(input())
    except EOFError:
      continue
  else:
    P[i] = P[i-1] + P[i-2]
print(P[-1]%1000000007)

Submission status: Accepted

Solution code:
import sys

n1, n2 = [int(i) for i in input().split()]

na1 = []

for i1 in range(n2):
    na1.append(int(input()))

for i3 in range(n2):
    if i3 == 0:
        continue
    else:
        if na1[i3] == na1[i3 - 1] + 1:
            print("0")
            sys.exit()

n3 = 0
n4 = 0
n5 = 0
n6 = 0
n7 = 0
r1 = 1
r2 = []
f1 = False
for i2 in range(n1):
    if len(na1) > n7 and (na1[n7] == i2 + 1 ):
        n3 = 0
        n4 = 0
        n6 = 0
        n7 += 1
        r2.append(r1)
        r1 = 1
        f1 = True

    else:
        if f1 == True:
            f1 = False
            continue
        if n4 == 0 :
            n4 = 1
            r1 = 1
        elif n3 == 0 :
            n3 = 1
            n4 = 2
            r1 = 2
        else:
            n6 = n3 + n4
            r1 = n6
            n3 = n4
            n4 = n6
    if i2 == (n1 - 1) :
        r2.append(r1)

r3 = 1
for i6 in range(len(r2)):
    r3 *= r2[i6]

print(r3 % 1000000007)

Submission status: Accepted

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

print(d[-1])

Submission status: Accepted

Solution code:
from collections import Counter
from collections import deque
from functools import reduce
from pprint import pprint
import bisect
import copy
import fractions
import itertools
import math
import queue
import random
import sys
import time
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def MI(): return map(int, sys.stdin.readline().split())
def II(): return int(sys.stdin.readline())
def IS(): return input()
def C(x): return Counter(x)
def GCD_LIST(numbers): return reduce(fractions.gcd, numbers)
def LCM_LIST(numbers): return reduce(LCM, numbers)
def LCM(m, n): return (m * n // fractions.gcd(m, n))


n, m = MI()
a = [II() for _ in range(m)]

tmp = [0] * (n+1)
ok = [True] * (n+1)
for num in a:
    ok[num] = False
tmp[0] = 1
for i in range(n):
    for j in range(i+1, min(n, i+2)+1):
        if ok[j]:
            tmp[j] += tmp[i]
print(tmp[n] % MOD)

Submission status: Accepted

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

Submission status: Accepted

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

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

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

print(l[-1] % 1000000007)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
steps = [True] * (N + 1)
for _ in range(M):
    steps[int(input())] = False
dp = [0] * (N + 1)
dp[0] = 1
for prev in range(N):
    for now in range(prev + 1, min(N, prev + 2) + 1):
        if steps[now]:
            dp[now] += dp[prev]
            dp[now] %= 10 ** 9 + 7
print(dp[N])

Submission status: Accepted

Solution code:
from collections import deque

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

before1 = 1
before2 = 0
ai = a.popleft() if len(a) else 0

for i in range(1, N+1):
    if i == ai:
        before2 = before1
        before1 = 0
        ai = a.popleft() if len(a) else ai
    else:
        current = divmod(before1 + before2, 10**9+7)[1]
        before2 = before1
        before1 = current

print(before1)

Submission status: Accepted

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


def main():
    n, m = map(int, input().split())
    mod = 10 ** 9 + 7
    broken = [False for _ in range(n + 1)]
    dp = [0 for _ in range(n + 2)]
    dp[n] = 1

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

    # See:
    # https://www.youtube.com/watch?v=L8grWxBlIZ4
    for j in range(n - 1, -1, -1):
        if broken[j]:
            continue

        dp[j] = dp[j + 1] + dp[j + 2]
        dp[j] %= mod

    print(dp[0])


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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):
    if i in a:
        dp[i] = 0
        continue
    dp[i] = (dp[i-1] + dp[i-2]) % 1000000007

print(dp[N])

Submission status: Accepted

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

def main(N, M, a_list):
    div = 10**9 + 7
    a_set = set(a_list)
    @lru_cache(maxsize=None)
    def fib(n):
        if n in a_set:
            return 0
        else:
            if n == -1:
                return 0
            elif n == 0 or n == 1:
                return 1
            else:
                return fib(n-2) % div + fib(n-1)
    
    
    print(fib(N) % div )


if __name__ == "__main__":
    N, M = [int(x) for x in input().split()]
    a_list = []
    for _ in range(M):
        a_list.append(int(input()))

    main(N, M, a_list)

Submission status: Accepted

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

# DP
dp = [1] * (N + 1)
for A in AL:
    dp[A] = 0

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

Submission status: Accepted

Solution code:
import numpy as np

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

step0 = 1
step1 = A[1]

ans = [step0, step1]
for i in range(2, N+1):
    now = (ans[-1] + ans[-2]) * A[i]
    ans.append(now)
print(ans[-1] % 1000000007)