Problem:


Score : 300 points

Problem Statement

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

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

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

Constraints

1 \leq N \leq 10^5

0 \leq M \leq N-1

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

Input

Input is given from Standard Input in the following format:

N M
a_1
a_2
 .
 .
 .
a_M

Output

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

Sample Input 1

6 1
3

Sample Output 1

4

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

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

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

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

0 \to 2 \to 4 \to 6

Sample Input 2

10 2
4
5

Sample Output 2

0

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

Sample Input 3

100 5
1
23
45
67
89

Sample Output 3

608200469

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



Sample input:
6 1
3


Sample output:
4

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
#
# Created: Jul, 12, 2020 18:27:48 by Nobody
# $Author$
# $Date$
# $URL$
__giturl__ = "$URL$"


from sys import stdin
input = stdin.readline


def main():
  N, M = list(map(int, input().split()))
  A = set([int(input()) for _ in range(M)])

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

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

  print(dp[N] % 1_000_000_007)


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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
broken = [0]*(n+1)
#m個階段が壊れているからそれをbrokenに入れる
for i in range(m):
    a = int(input())
    broken[a] = 1
dp = [0]*(n+1)
dp[0] = 1
mod = 1000000007
for i in range(1, n+1):
    if broken[i]:
        continue
    #dp[-1]は0だから上手く回る
    dp[i] = (dp[i-1] + dp[i-2]) % mod
print(dp[n])

Submission status: Accepted

Solution code:
import sys
from operator import itemgetter

sys.setrecursionlimit(10**9)
input = sys.stdin.readline

def ii(): return int(input())
def mi(): return map(int, input().split())
def lmi(): return list(map(int, input().split()))
def iif(n): return [int(input()) for _ in range(n)]
def lmif(n): return [list(map(int, input().split())) for _ in range(n)]
def ss(): return input().split()

def main():
    mod = 1000000007

    F = [1, 1]
    for i in range(100000):
        F.append(F[i] + F[i+1])

    N, M = mi()

    if M == 0:
        print(F[N] % mod)
        return

    A = iif(M)
    DA = []
    left = 0
    for i in range(M):
        da = A[i] - left
        if da == 0 and left != 0:
            print(0)
            return
        else:
            DA.append(da-1)
        left = A[i] + 1
    if A[-1] != N:
        DA.append(N - A[-1] - 1)


    ans = 1
    for i in DA:
        ans *= F[i]

    print(ans % mod)

    return

main()

Submission status: Accepted

Solution code:
import sys

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

for k in range(K-1):
    if broken[k] +1 == broken[k+1]:
        print(0)
        sys.exit(0)
broken_set = set(broken)

# N段連続したら何通りあるか表を作る
P = {0: 1, 1: 1, 2: 2}
for i in range(3, N+1):
    P[i] = P[i-1] + P[i-2]

total = 1
low = 0
for i in range(1, N+1):
    if i in broken_set:
        seq = (i - 1) - low
        total *= P[seq]
        total %= 1000000007
        low = i + 1
else:
    seq = N - low
    total *= P[seq]
    total %= 1000000007

print(total)

Submission status: Accepted

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

dp = [[0]*2 for i in range(n+1)]
dp[0][0] = 1

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

ans = (dp[-1][0]+dp[-1][1])%mod

print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
broken = {int(input()) for _ in range(m)}

mod = 10 ** 9 + 7

dp = [0] * (n + 1)
dp[0] = 1
if 1 not in broken:
    dp[1] = 1

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
N,M = (int(x) for x in input().split())
Broken = [True]*(N+1)
for TM in range(0,M):
    Broken[int(input())] = False
DP = [1]+[0]*N
for Now in range(0,N):
    for Next in range(Now+1,min(N+1,Now+3)):
        if Broken[Next]==True:
            DP[Next] = (DP[Next]+DP[Now])%1000000007
print(DP[N])

Submission status: Accepted

Solution code:
N,M = (int(x) for x in input().split())
Broken = [True]*(N+1)
for TM in range(0,M):
    Broken[int(input())] = False

DP = [1]+[0]*N
for Now in range(0,N):
    for Next in range(Now+1,min(N+1,Now+3)):
        if Broken[Next]==True: DP[Next] += DP[Now]
print(DP[N]%1000000007)

Submission status: Accepted

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

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

for i in range(m):
    ans[int(input())] = 0
for i in range(n-2, -1, -1):
    if ans[i]==0:
        continue
    ans[i] = (ans[i+1]+ans[i+2])%(10**9 + 7)

print(ans[0])

Submission status: Accepted

Solution code:
def resolve():
    import sys
    
    read = sys.stdin.read
    readline = sys.stdin.readline

    N, M = map(int, readline().split())
    a = set(int(x) for x in read().split())
    
    dp = [0] * (N + 2)
    dp[0] = 1

    for i in range(N):
        now = dp[i]
        if i + 1 not in a:
            dp[i + 1] += now
        if i + 2 not in a:
            dp[i + 2] += now

    print(dp[N] % 1_000_000_007)


resolve()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
bad = []
for i in range(m):
    bad.append(int(input()))
dp = [0 for x in range(n+1)]
dp[0] = 1
idx = 0
if m > 0 and bad[0] == 1:
    dp[1] = 0
    idx = 1
else:
    dp[1] = 1

for i in range(2, n+1):
    if idx < m and i == bad[idx]:
        dp[i] = 0
        idx+=1
    else:
        dp[i] = (dp[i-1] + dp[i-2]) % 1000000007

print(dp[n])

Submission status: Accepted

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

for i in a:
  lis[i]=-1
lis[1] += 1
for i in range(n-1):
  if lis[i+2]<0:
    lis[i+2]= 0
  else:
    lis[i+2] = (lis[i+1] + lis[i])%M
print(lis[n])

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
a = [0]*(N+2)
pass_list = [0]*(N+2)

for i in range(M):
    b = int(input())
    a[b] = 1
if(a[1] !=1):
    pass_list[1]=1
if(a[2] !=1):
    pass_list[2]=1
for i in range(2,N+1):
    if(a[i] != 1):
        pass_list[i] += pass_list[i-1]+pass_list[i-2]
print(pass_list[N]%1000000007)

Submission status: Accepted

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

ok = [True] * (n+1)
for i in range(m):
    a = int(input())
    ok[a] = False

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

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

print(dp[n])

Submission status: Accepted

Solution code:
import sys


def read():
    return sys.stdin.readline().rstrip()


def main():
    n, m = map(int, read().split())
    a = {int(read()) - 1 for _ in range(m)}
    if n == 1:
        print(1)
        return
    mod = 10**9 + 7
    dp = [0] * n
    if 0 not in a:
        dp[0] = 1
    if 1 not in a:
        dp[1] = 1 + dp[0]
    for i in range(2, n):
        if i in a:
            continue
        dp[i] = (dp[i - 1] + dp[i - 2]) % mod
    print(dp[-1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
def gcd(*numbers): reduce(math.gcd, numbers)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
count = 0
ans = 0
inf = float("inf")

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

N,M = I()
a = [1]*(N +1)
for i in range(M):
    x = k()
    a[x] = 0

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

print(dpp(N) % mod)

Submission status: Accepted

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

dp = [0] * (N + 1)

dp[0] = 1
for i in range(N):
    for j in range(i + 1, min(N, i + 2) + 1):
        if A[j] is True:
            dp[j] += dp[i]
            dp[j] %= 10 ** 9 + 7

print(dp[N])

Submission status: Accepted

Solution code:

def solve():
    dp = [0] * (N+1)
    dp[0] = 1
    for i in range(N):
        for j in range(i+1, min(N,i+2)+1):
            if broken[j]:
                dp[j] += dp[i]
                dp[j] %=  1000000007
    print(dp[-1])

if __name__ == "__main__":
    N,M = list(map(int, input().split()))
    broken = [True] * (N+1)
    for i in range(M):
        a = int(input())
        broken[a] = False
    solve()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
DIVZ = 10**9+7

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

steps[0] = 1
for i in range(N):
    if steps[i] > 0:
        if steps[i+1] >= 0:
            steps[i+1] += steps[i]
            steps[i + 1] %= DIVZ
        if steps[i+2] >= 0:
            steps[i+2] += steps[i]
            steps[i+2] %= DIVZ

print(steps[N])

Submission status: Accepted

Solution code:
def route_num(stairs):
    if stairs <= 1:
        return 1
    else:
        return route_num(stairs - 1) + route_num(stairs - 2)

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

broken = {i:False for i in range(n + 1)}
for a_i in a:
    broken[a_i] = True

route_num = {}
for i in range(n + 1):
    if broken[i]:
        route_num[i] = 0
    elif i <= 1:
        route_num[i] = 1
    else:
        route_num[i] = (route_num[i-1] + route_num[i-2]) % 1000000007

print(route_num[n])

Submission status: Accepted

Solution code:
def route_num(stairs):
    if stairs <= 1:
        return 1
    else:
        return route_num(stairs - 1) + route_num(stairs - 2)

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

broken = {i:False for i in range(n + 1)}
for a_i in a:
    broken[a_i] = True

route_num = {}
for i in range(n + 1):
    if broken[i]:
        route_num[i] = 0
    elif i <= 1:
        route_num[i] = 1
    else:
        route_num[i] = route_num[i-1] + route_num[i-2]

print(route_num[n] % 1000000007)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

def main():
    n, m = map(int, input().split())
    a = [0] * n
    MOD = 10 ** 9 + 7
    for _ in range(m):
        a[int(input())] = 1
    dp = [0] * (n+1)
    dp[0] = 1
    for i in range(n):
        dp[i] %= MOD
        if a[i]:
            dp[i] = 0
        if i + 1 <= n:
            dp[i+1] += dp[i]
        if i + 2 <= n:
            dp[i+2] += dp[i]
    print(dp[-1]%MOD)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

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

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

print(dp[N])

Submission status: Accepted

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

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

if 1 not 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]
	dp[i] %= INF

print(dp[N])

Submission status: Accepted

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

Submission status: Accepted

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

dp = [0 for _ in range(n+1)]
dp[0] = 1
mod = 10**9 + 7

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

if an[0] == 1:
    dp[1] = 0
    a = 1
    if len(an) == 1:
        a = 0
else:
    dp[1] = 1
    a = 0

for i in range(2, n+1):
    if i == an[a]:
        dp[i] = 0
        a += 1
        if a == len(an):
            a -= 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())

stairs = ["o"] * (n + 1)

for _ in range(m):
  stairs[int(input())] = "x"

c = [0] * (n + 1)
c[0] = 1
if stairs[1] == "x":
  c[1] = 0
else:
  c[1] = 1

for i in range(2, n + 1):
  if stairs[i] == "x":
    c[i] = 0
  else:
    c[i] = c[i - 1] + c[i - 2]

print(c[n] % 1000000007)

Submission status: Accepted

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

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

print(A[-1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("## ",*x,file=sys.stderr)
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    #N = int(input())
    N, M = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    A = tuple(int(input()) for i in range(M)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    aset=set(A)
    dp=[0]*(N+1)
    dp[0]=1
    for i in range(1,N+1):
        if i in aset:
            continue
        if i>=2:
            dp[i]=(dp[i-1]+dp[i-2])%mod
        else:
            dp[i]=(dp[i-1])%mod

    #printe(dp)
    print(dp[-1])



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
if m>0:
    a=[int(input()) for i in range(m)]

dp=[None]*(n+1)
dp[0]=1
for i in range(m):
    dp[a[i]]=0
if dp[1]==None:
    dp[1]=1

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

print(dp[-1])

Submission status: Accepted

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

sys.setrecursionlimit(1000000)
n, m, *a = map(int, open(0).read().split())
dp = [1] + [-1] * n
dp[1] = 1
for i in a:
    dp[i] = 0

def count(n):
    if dp[n] != -1:
        return dp[n]
    dp[n] = (count(n - 1) + count(n - 2)) % (10**9 + 7)
    return dp[n]


print(count(n))

Submission status: Accepted

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

sys.setrecursionlimit(1000000)


memo = [0]*(10**5+1)
def count(n):
    if n < 2:
        return 1
    if memo[n] != 0:
        return memo[n]
    memo[n] = count(n-1) + count(n-2)
    return memo[n]


n, m, *a = map(int, open(0).read().split())
if sum(a[i + 1] == a[i] + 1 for i in range(m - 1)) > 0:
    print(0)
    exit()

a.append(n + 1)
c = -1
ans = 1
for i in a:
    ans = ans * count(i - c - 2) % (10**9 + 7)
    c = i
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[0] = 1

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

print(dp[-1])

Submission status: Accepted

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

Submission status: Accepted

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

dp = [0] * (n+1)
if 1 not in a:
  dp[1] = 1
if 2 not in a and n != 1:
  dp[2] = dp[1] + 1
for i in range(3, n+1):
  if i not in a:
    dp[i] = dp[i-1] + dp[i-2]

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

Submission status: Accepted

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

nums = [1, 2]
for i in range(2, N+1):
  plus = nums[i-2] + nums[i-1]
  nums.append(plus)
  
stairs = [0]*N
stairs[0] = 1
stairs.append(1)
flag = True
for i in range(M):
  m = int(input())
  if stairs[m] == 1:
    flag = False
    break
  else:
    stairs[m-1], stairs[m], stairs[m+1] = 1, 1, 1
  
ans = 1
mode = False
left = -1
right = -1
for i in range(N+1):
  if stairs[i] == 0:
    if not mode:
      left = i
      mode = True
  else:
    if mode:
      right = i
      n = right - left
      ans *= nums[n]
      mode = False
      
if flag:
  print(ans%(10**9+7))
else:
  print(0)

Submission status: Accepted

Solution code:
# ANSHUL GAUTAM
# IIIT-D

from math import *
from copy import *					# ll = deepcopy(l)
from heapq import *					# heappush(hp,x)
from string import *				# alpha = ascii_lowercase
from random import *				# l.sort(key=lambda l1:l1[0]-l1[1]) => ex: sort on the basis difference
from bisect import *				# bisect_left(arr,x,start,end)  => start and end parameters are temporary
from sys import stdin				# bisect_left return leftmost position where x should be inserted to keep sorted
from sys import maxsize				# minn = -maxsize
from operator import *				# d = sorted(d.items(), key=itemgetter(1))
from itertools import *				# pre = [0] + list(accumulate(l))
from decimal import Decimal 		# a = Decimal(a)	# use this for math questions
from collections import Counter		# d = dict(Counter(l))
from collections import defaultdict # d = defaultdict(list)

'''
3
1 2 3
'''

def solve(l,n):
	m = len(l)
	d = dict(Counter(l))
	dp = [0]*(n+1)
	dp[0] = 1
	mod = 10**9 + 7
	if(1 not in d):
		dp[1] = 1
	for i in range(2,n+1):
		if(i not in d):
			dp[i] = dp[i-1] + dp[i-2]
			dp[i] %= mod
	return dp[n]

N,M = list(map(int, stdin.readline().rstrip().split()))
l = []
for m in range(M):
	l.append(int(input()))
ans = solve(l,N)
print(ans)

Submission status: Accepted

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

A = []

for i in range (0, M):
	A.append(int(input()))


if N == 1:
	print(1)
	exit()
elif N ==2:
	if len(A) ==1:
		print(1)
	else:
		print(2)
	exit()

DP = [0]*N

if A.count(1)==0:
	DP[0] = 1

if A.count(2)==0:
	if A.count(1)==0:
		DP[1] = 2
	else:
		DP[1] = 1

for i in range (0, M):
	DP[A[i]-1] = -1

for i in range (0, 2):
	if DP[i] == -1:
		DP[i] = 0

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

print(DP[-1]%(1000000007))

Submission status: Accepted

Solution code:
import sys
INFTY=sys.maxsize

def readinput():
    n,m=list(map(int,input().split()))
    a=[]
    for _ in range(m):
        a.append(int(input()))
    return n,m,a

def main(n,m,a):
    MOD=10**9+7
    dp=[0]*(n+3)
    dp[0]=1
    ia=0
    for i in range(n+1):
        if ia<m and i==a[ia]:
            ia+=1
            #print(ia)
            continue
        dp[i+1]=(dp[i+1]+dp[i])%MOD
        dp[i+2]=(dp[i+2]+dp[i])%MOD
        #print(dp)
    return dp[n]

if __name__=='__main__':
    n,m,a=readinput()
    ans=main(n,m,a)
    print(ans)

Submission status: Accepted

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

print(dp[n+1])

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
set_A = set()
dp = [0]*n
mod = pow(10, 9) + 7

for _ in range(m):
    set_A.add(int(input()))

if 1 not in set_A:
    dp[0] = 1
if 2 not in set_A and n != 1:
    dp[1] = 1 + dp[0]

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

print(dp[n-1])

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
INF = 10 ** 9 + 7

# map(int, input().split())
# list(map(int, input().split()))

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


dp = [0] * (N + 1)
dp[0] = 1
if not 1 in A:
    dp[1] = 1
for i in range(2, N + 1):
    dp[i] = (dp[i - 1] + dp[i - 2]) % INF
    if i in A:
        dp[i] = 0
print(dp[N])
# ans = 1
# cur = 0
# for a in A:
#     steps = (a - 1) - cur
#     cur = a + 1

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
mod = 10**9+7
ans = [1,1]
for i in range(2,100001):
  ans.append((ans[i-1]+ans[i-2])%mod)
num = 1
s = 0
for i in range(m):
  e = int(input())
  if e-1 < s:
    print(0)
    exit(0)
  num*=ans[e-1-s]
  num%=mod
  s = e+1
num*=ans[n-s]
print(num%mod)

Submission status: Accepted

Solution code:
N,M=list(map(int,input().split()))
 
S=[]
s=0
for m in range(M):
    e = int(input())
    S.append(list(range(s,e)))
    s = e+1

e = int(N+1)
S.append(list(range(s,e)))
 
fibo=[0,1]
for n in range(2,N+2):
    fibo.append(fibo[n-2]+fibo[n-1])
    
ans=1
for s in S:
    ans=ans*fibo[len(s)]
print(ans%1000000007)

Submission status: Accepted

Solution code:
MOD = 10**9+7

n,m = map(int, input().split())
al = [True]*(n+1)
for _ in range(m):
    al[int(input())] = False

dp = [0]*(n+1) 
dp[0] = 1
for i in range(n):
    if i+2 <= n and al[i+2]:
        dp[i+2] += dp[i]
    if i+1 <= n and al[i+1]:
        dp[i+1] += dp[i]

print(dp[n]%MOD)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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)
ng = [False]*(n+1)
for i in a:
    ng[i] = True
    
dp[0] = 1
if not ng[1]:
    dp[1] = 1
for i in range(2, n+1):
    if ng[i]:
        continue
    else:
        dp[i] = (dp[i-1] + dp[i-2]) % MOD
print(dp[n])

Submission status: Accepted

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

for a in A:
    oks[a] = False

for now in range(N + 1):
    next1 = now + 1
    next2 = now + 2
    if N < next1:
        break
    if oks[next1]:
        dp[next1] += dp[now]
        dp[next1] %= mod

    if N < next2:
        break
    if oks[next2]:
        dp[next2] += dp[now]
        dp[next2] %= mod

print(dp[N])

Submission status: Accepted

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

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

judge = (N+1)*[True]
for i in a:
    judge[i]=False

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


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

#print(judge)
#print(dp)
print(dp[N]%(10**9+7))

Submission status: Accepted

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

def main(n,a):
    MOD=10**9+7

    nroute=[0]*(n+2)
    nroute[0]=0
    nroute[1]=1
    nroute[2]=1
    for i in range(3,n+2):
        nroute[i]=(nroute[i-1]+nroute[i-2])%MOD
    #print(nroute)
    
    subn=[]
    i=0
    for j in a:
        subn.append((i,j-1))
        i=j+1
    subn.append((i,n))
    #print(subn)

    nways=1
    for i,j in subn:
        l=j-i+1
        nways=nways*nroute[l]%MOD

    return nways

if __name__=='__main__':
    n,a=readinput()
    ans=main(n,a)
    print(ans)

Submission status: Accepted

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

aa=[0]*(N+1)
for j in range(M):
    aa[a[j]] = 1

dp = [0]*(N+1)
dp[0]=1
if 1 not in a:
    dp[1]=1
else:
    dp[1]=0

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

print(dp[-1] % 1000000007)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from itertools import product
n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
mod = 10**9+7


def mat2_mul(X, Y):
    z = [[0, 0], [0, 0]]
    for (i, j, k) in product(range(2), range(2), range(2)):
        z[i][j] += X[i][k] * Y[k][j]
    return z


def mat2_pow(X, n):
    if n == 0:
        return [[1, 0], [0, 1]]
    elif n % 2:
        return mat2_mul(X, mat2_pow(X, n - 1))
    else:
        half_pow = mat2_pow(X, n / 2)
        return mat2_mul(half_pow, half_pow)


def fib(n):
    if n == 0:
        return 0
    else:
        f = [[0, 1], [1, 1]]
    return mat2_pow(f, n - 1)[1][1]


ans, start = 1, 0

for i in a:
    ans *= fib(i - start)
    ans %= mod
    start = i + 1

ans *= fib(n - start + 1)
print(ans % mod)

Submission status: Accepted

Solution code:
N,M = list(map(int,input().split()))
p=10**9+7
A = [0]*(N+1)
flag = 0
for i in range(M):
    tmp = int(input())
    A[tmp]=1
    if A[tmp]*A[tmp-1]>0:
        flag=1
        break
if flag==1:
    print(0)
else:
    dp = [0]*(N+1)
    dp[0] = 1
    dp[1] = 1-A[1]
    for i in range(2,N+1):
        if A[i]==1:
            continue
        dp[i]=(dp[i-1]+dp[i-2])%p
    print(dp[-1])

Submission status: Accepted

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

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

for i in range(n):
    for j in range(i+1, min(n+1, i+3)):
        if a[j]:
            dp[j] += dp[i]
            dp[j] %= 10**9+7

print(dp[n])

Submission status: Accepted

Solution code:
def main():
    N, M = map(int, input().split())
    A = set([int(input()) for _ in range(M)])
    ways = [0] * (N+1)
    ways[0] = 1
    for i in range(1, N+1):
        if i not in A:
            ways[i] = ways[i-1] + ways[i-2]

    print(ways[N] % 1000000007)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
M=10**9+7
n,m,*l=map(int,open(0).read().split())
dp=[1]+[0]*n
for i in l: dp[i]=-1
dp[1]+=1
for i in range(n-1):
  if dp[i+2]<0: dp[i+2]=0
  else: dp[i+2]=(dp[i]+dp[i+1])%M
print(dp[n])

Submission status: Accepted

Solution code:
def m():
    MOD = 10 ** 9 + 7
    N, M = map(int, input().split())
    A = [int(input()) for _ in range(M)]
    dp = [0] * (N + 1)
    for a in A: dp[a] = -1
    if N == 1:
        if dp[1] != -1:
            return 1
        else:
            return 0
    if dp[1] != -1 and dp[2] != -1:
        dp[1] = 1
        dp[2] = 2
    elif dp[1] != -1 and dp[2] == -1:
        dp[1] = 1
    elif dp[1] == -1 and dp[2] != -1:
        dp[2] = 1
    else:
        return 0

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


print(m())