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:
def main():
    n, m = map(int, input().split())
    a = [int(input()) for _ in range(m)]
    s = [True for _ in range(n + 1)]

    for ai in a:
        s[ai] = False

    print(solve(n, s))

def solve(n, s):
    M = 10 ** 9 + 7

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

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


main()

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
displace = {}
for _ in range(m):
    displace[int(input())] = 1
dp = {0:1}
if 1 in displace:
    dp[1] = 0
else:
    dp[1] = 1

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

Submission status: Accepted

Solution code:
import sys,collections,math,random;sys.setrecursionlimit(10**7)
def Is(): return [int(x) for x in sys.stdin.readline().split()]
def Ss(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

MOD = 10**9 + 7
n,m = Is()
ns = [0] * (n+1)
ns[0] = 1
for i in range(m):
    ns[I()] = -1
for i in range(n):
    if ns[i] >= 0 and i+1 <= n and ns[i+1] >= 0:
        ns[i+1] = (ns[i+1] + ns[i]) % MOD
    if ns[i] >= 0 and i+2 <= n and ns[i+2] >= 0:
        ns[i+2] = (ns[i+2] + ns[i]) % MOD
print(ns[n])

Submission status: Accepted

Solution code:
import fractions as fr
import itertools as it
import collections as col
import heapq as hq
import sys
sys.setrecursionlimit(10**9)

"""
N=int(input())
W=list(map(int, input().split()))
ans=10**100
for T in range(1,N):
        S1=sum(W[:T])
        S2=sum(W[T:])
        ans = min(ans, abs(S1-S2))
print(ans)
"""
"""
P,Q,R=map(int, input().split())
print(min([P+Q, P+R, Q+R]))
"""
MOD=1000000007
N,M=map(int, input().split())
A=set()
for i in range(M):
        A.add(int(input()))

dp=dict()
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
        else:
                m1=0 if (i-1) in A else dp[i-1]
                m2=0 if (i-2) in A else dp[i-2]
                dp[i]=(m1+m2) % MOD
print(dp[N])
"""

        print(i)
        if i in A: return 0
        if i in dp: return dp[i]
        m1=0 if (i-1) in A else f(i-1)
        m2=0 if (i-2) in A else f(i-2)
        dp[i]=(m1+m2) % MOD
        return dp[i]

print(f(N))
"""

Submission status: Accepted

Solution code:
import sys

inp = input().split(" ")
n,m = int(inp[0]),int(inp[1])
brokens = []
for i in range (m):
    brokens.append(int(input()))

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


dp = []
for i in range(n+1):
    dp.append(0)

for i in brokens:
    dp[i]= -1

if dp[1] == -1 and dp[2] == -1:
    dp[1] = 0
    dp[2] = 0
elif dp[1] == -1:
    dp[1] = 0
    dp[2] = 1
elif dp[2] == -1 :
    dp[1] = 1
    dp[2] = 0
else:
    dp[1] = 1
    dp[2] = 2


if n <= 2:
    print(dp[n])
    sys.exit(0)


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

print(dp[n] % 1000000007)

Submission status: Accepted

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

broken = [False for it in range(n)]
for it in a:
    broken[it] = True

how_many = [0 for it in range(n)]
for i in range(0, n)[::-1]:
    if broken[i]:
        continue
        
    if i==n-1:
        how_many[i] = 1
    elif i==n-2:
        how_many[i] =  how_many[i+1] + 1
    else:
        how_many[i] = (how_many[i+1] + how_many[i+2])% 1000000007
print(how_many[0])

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
S = []
tmp = -1
for _ in range(m):
  a = int(input())
  S.append(a-tmp-2)
  tmp = a
S.append(n-tmp-1)

fib = [1 for _ in range(n+1)]
for i in range(n-1):
  fib[i+2] = fib[i] + fib[i+1]

total = 1
for x in S:
  if x == -1:
    print(0)
    exit()
  total *= fib[x]

#print(S)
print(total%1000000007)

Submission status: Accepted

Solution code:
from collections import defaultdict
from collections import deque
from string import ascii_uppercase
import sys, bisect, math
stdin = sys.stdin
read_int = lambda : list(map(int,stdin.readline().split()))
read_str = lambda : stdin.readline().rstrip()

N, M = read_int()
num_array = [read_int()[0] for _ in range(M)]

BIG = 1000000007

dp = [0 for _ in range(N + 2)]
for i in range(M):
    dp[num_array[i]] = -1

def solve():
    ans = 0
    dp[0] = 1
    for i in range(N):
        if dp[i] == -1:
            if dp[i + 1] == -1:
                return 0
            continue
        if dp[i + 1] != -1:
            dp[i + 1] += dp[i] % BIG if dp[i + 1] == 0 else dp[i]
        if dp[i + 2] != -1:
            dp[i + 2] += dp[i] % BIG if dp[i + 2] == 0 else dp[i]
    return dp[N] % BIG

if __name__ == "__main__":
    print(solve())

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
def lmi(): return list(map(int, input().split()))

n, m = lmi()

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

a = 0
if m != 0:
    a = int(input())
k = 1
for i in range(n+1):

    if i != a:
        if i == 1:
            l[i] = 1
        elif i >= 2:
            l[i] = l[i-1] + l[i-2]
            l[i] %= 1000000007
    else:
        k += 1
        if k <= m:
            a = int(input())



#print(l)
print(l[n] % 1000000007)

Submission status: Accepted

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

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

    if (stair[i + 1] != -1):
        stair[i + 1] = (stair[i] + stair[i + 1]) % mod

print(stair[n])

Submission status: Accepted

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

fib = [0]*(n + 1)
fib[0] = 1
fib[1] = 1
for x in range(2, n+1):
    fib[x] = fib[x-1] + fib[x-2]

mod = 10**9+7
ans = 1
prev_a = -1
a = 0
for i in range(m):
    a = int(input())
    if a - 1 == prev_a:
        ans = 0
        break
    else:
        ans = (ans * fib[a - prev_a - 2]) % mod
    prev_a = a

if m == 0:
    ans = fib[n] % mod
else:
    ans = (ans * fib[n - a - 1]) % mod
print(ans)

Submission status: Accepted

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

if m == 0:
    print(list[n - 1] % 1000000007)
else:
    ans = 1
    o = 0
    for i in range(m):
        a = int(input())
        if a == o:
            ans = 0
            break
        if a > o + 1:
            ans = (ans * list[a - o - 2]) % 1000000007
        o = a + 1

    if a + 1 < n:
        ans = (ans * list[n - a - 2]) % 1000000007
    print(ans)

Submission status: Accepted

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

C = [0] * 100001
C[1] = 1
C[2] = 2

for i in range(3, 100001, 1):
    C[i] = C[i-1] + C[i-2]

start = 0

result = 1

for i in range(M):
    a = int(input())
    next = a - 1
    if next == start:
        start = a + 1
        continue
    if next < start:
        print(0)
        exit(0)
    range = a - 1 - start
    pattern = C[range]
    result *= pattern
    start = a + 1

if start < N:
    range = N - start
    pattern = C[range]
    result *= pattern

print(result % 1000000007)

Submission status: Accepted

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

ax = [1]*(N+1)
for m in range(M):
    ai = int(input()) - 1
    ax[ai+1] = None
# maybe ax[k] = ax[k-1] + ax[k-2]
#print(ax)

chunk_num = []
num = 0
for i in range(len(ax)):
    if ax[i] is not None:
        num += 1
    else:
        chunk_num.append(num)
        num = 0
chunk_num.append(num)

#print(chunk_num)
bu = {0:1, 1:1}
for i in range(1, max(chunk_num)):
    if bu.get(i) is None:
        bu[i] = bu[i-1] + bu[i-2]

rs = 1
for num in chunk_num:
    #print('l', num, bu[num-1])
    try:
        rs *= bu[num-1]
    except:
        rs = 0
    rs %= 1000000007
print(rs%1000000007)

Submission status: Accepted

Solution code:
import bisect

def find_bisect(a, x):
    i = bisect.bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return True
    return False

val = list(map(int, input().strip().split()))
n = val[0]
m = val[1]
a = []

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

pastpast_result = 0
past_result = 1
result = 0

for i in range(n):
    result = 0
    if not find_bisect(a, i):
        result += past_result
    if not find_bisect(a, i-1):
        result += pastpast_result

    if result > 1000000007:
        result = result % 1000000007
    
    if result == 0:
        break
    
    pastpast_result = past_result
    past_result = result

print(result % 1000000007)

Submission status: Accepted

Solution code:
import sys

from collections import deque
# q = deque(); q.append(x); q.appendleft(x); q.pop() -> x; q.popleft() -> x
from collections import defaultdict
# d = defaultdict(lambda: []); d[key] -> []
import heapq
# hq = []; heapq.heappush(hq, x); heapq.heappop(hq) -> x; heapq.heappushpop(hq, x) -> x
import bisect
# i = bisect.bisect_left([1,2,3,4], 1.5); i = bisect.bisect_right([4,3,2,1], 1.5)

#import numpy as np
#from scipy.misc import comb

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def fib_memo(n):
    memo = [0] * (n+1)
    memo[0] = 1
    if n < 1:
        return memo
    memo[1] = 1
    for i in range(2, n+1):
        memo[i] = memo[i-1] + memo[i-2]
    return memo

def main():
    N, M = i2nn()
    A = ii2nn(M)
    MOD = int(1e+9) + 7
    D = [0] * (M+1)
    if M == 0:
        D[0] = N
    else:
        D[0] = A[0] - 1
        for i in range(1, M):
            t = A[i] - A[i-1] - 2
            if t <= -1:
                print(0)
                return
            D[i] = t
        D[M] = N - A[M-1] - 1
    n = 1
    memo = fib_memo(max(D))
    for d in D:
        n = (n * memo[d]) % MOD
    print(n)

main()

Submission status: Accepted

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

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

inf = 1000000007
index = 0
n_way = [0 for i in range(N+2)]
n_way[0] = 1

for i in range(N):
    if a[index] == i:
        index += 1
        index = min(index,len(a)-1)
    else:
        n_way[i+1] += n_way[i]
        n_way[i+1] = n_way[i+1]%inf
        n_way[i+2] += n_way[i]
        n_way[i+2] = n_way[i+2]%inf

print(n_way[N])

Submission status: Accepted

Solution code:
from sys import stdin

MOD = 1000000007

n, m = map(int, raw_input().strip().split())
inp = stdin.readlines()
broken = [0] * n

for line in inp:
    a = int(line.strip())
    broken[a] = 1

dp = [0] * (n + 1)

dp[n] = 1
if not broken[n - 1]: dp[n - 1] = 1
for i in xrange(n - 2, -1, -1):
    if broken[i]: continue
    dp[i] = dp[i + 1] + dp[i + 2]
    if dp[i] >= MOD: dp[i] -= MOD

print dp[0] % MOD

Submission status: Accepted

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

dan=[]

for i in range(m):
    b=list(map(int, input().split()))
    dan.append(b[0])

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

for ii in range(n-1):
    i=ii+3
    fib[i]=(fib[i-1]+fib[i-2])%1000000007
    
#print(fib,dan)

eachans=[]

if(m==0):
    print(fib[n])

if(m>=1):
    if(dan[0]!=1):
        eachans.append(fib[dan[0]-1])

    for i in range(m-1):
        if(dan[i+1]-dan[i]-2 == 0):
            eachans.append(1)
        elif(dan[i+1]-dan[i]-2 == -1):
            eachans.append(0)
        else:
            eachans.append(fib[dan[i+1]-dan[i]-2])
        #print(dan[i+1]-dan[i]-1)

if(m>=1):
    if(dan[-1]!=n-1):
        eachans.append(fib[n-dan[-1]-1])
    
if(m>=1):
    #print(eachans)
    ans=1
    for i in range(len(eachans)):
        ans = ans*eachans[i]%1000000007

    print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

MOD = 10**9+7
memo = {}
def steps(n):
  if not(n in memo):
    if n == 0:
      memo[n] = 1
    elif n == 1:
      memo[n] = 1
    else:
      memo[n] = (steps(n-1)+steps(n-2))%MOD
  return memo[n]

N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
nowstep = 0
ans = 1
for a in A:
  if nowstep == a:
    ans = 0
    break
  ans = (ans * steps(a-1-nowstep))%MOD
  nowstep = a+1
ans = (ans * steps(N-nowstep))%MOD
print(ans)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
def add(a, b):
  return (a + b) % MOD
def sub(a, b):
  return (a - b) % MOD
def mul(a, b):
  return ((a % MOD) * (b % MOD)) % MOD
def div(a, b):
  return ( (a % MOD) * (power(b, MOD)) ) % MOD
def power(a, b):
  return pow(a, b, MOD)

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

n, m = map(int, input().split())
an = []
for _ in range(m):
  an.append(int(input()))
an.append(n+1)

now = 0
pattern = 1
for a in an:
  if now >= a:
    pattern = 0
    break
  steps = a - now - 1
  pattern = mul(pattern, fn[steps])
  now = a + 1

print(pattern)

Submission status: Accepted

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

ans = [0]*(n+1)
ans[0] = 1
for i in range(m):
  ans[a[i]] = -1
for i in range(1,n+1):
  if i > 1:
    if ans[i] != -1:
      if ans[i-2] != -1:
        ans[i] += ans[i-2]
      if ans[i-1] != -1:
        ans[i] += ans[i-1]
  else:
    if ans[i] != -1:
      ans[i] = ans[i-1]
#print(ans)
print(ans[n]%1000000007)

Submission status: Accepted

Solution code:
flag=0
N,M=map(int,input().split())
A=[-1]+[int(input()) for _ in range(M)]+[N+1]
mod=10**9+7
    
fib=[1,1]
for i in range(10**5):
    fib.append((fib[i]+fib[i+1])%mod)
    
for i in range(1,M):
    if A[i+1]==A[i]+1:
        flag=1

if flag==0:
    B=[A[i+1]-A[i]-2 for i in range(M+1)]
    ans=1
    for i in range(M+1):
        ans=(ans*fib[B[i]])%mod
    print(ans)
else:
    print(0)

Submission status: Accepted

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

if M == 0:
    if N == 1:
        print(1)
        exit(0)
    dp[0] = 1
    dp[1] = 1
    dp[2] = 1
    for k in range(2,N+1):
        dp[k] = dp[k-1] + dp[k-2]
        dp[k] %= MOD
    print(dp[N])
else:
    A = [int(input()) for k in range(M)]
    dp[0] = 1
    dp[1] = 1
    dp[2] = 1
    if N == 1:
        if M == 1:
            print(0)
        exit(0)
    else:
        t = 0
        if A[0] == 1:
            t += 1
            dp[1] = 0
        for k in range(2,N+1):
            if t < len(A) and A[t] == k:
                dp[k] = 0
                t += 1
            else:
                dp[k] = dp[k-1] + dp[k-2]
                dp[k] %= 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)}
dp = {}
for step in range(1,n+1):
    if step in a:
        dp[step] = 0
        continue
    if step == 1:
        if step in a:
            dp[1] = 0
        else:
            dp[1] = 1
        continue
    if step == 2:
        if step in a:
            dp[2] = dp[1]
        else:
            dp[2] = dp[1] + 1
        continue
    dp[step] = dp[step-1] + dp[step-2]
print(int(dp[n]%1000000007))

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
M = 1000000007


def main():
  n, m = map(int, input().split())
  a = [int(input()) for _ in range(m)]
  a.sort()
  a += [-1, -1]
  b = 0
  w = [0] * (n + 2)
  w[0] = 1

  for i in range(n):
    if a[b] == i:
      b += 1
      continue
    elif a[b] == i + 1 and a[b + 1] == i + 2:
      print(0)
      return

    if a[b] != i + 1:
      w[i + 1] = (w[i] + w[i + 1]) % M

    if a[b] != i + 2:
      w[i + 2] = (w[i] + w[i + 2]) % M

  print(w[-2])


if __name__ == '__main__':
  main()

Submission status: Accepted

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

table = [0] * (n + 2)
table[0] = 1
for i in range(m):
    a = int(input())
    table[a] = -2

for i in range(1, n + 1):
    if table[i-1] == -2 and table[i-2] == -2:
        print(0)
        exit()


    if table[i] != -2:
        if table[i-1] != -2:
            table[i] += table[i-1]
        if table[i-2] != -2:
            table[i] += table[i-2]

        table[i] %= (10**9+7)

print(table[n])

Submission status: Accepted

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

if N == 1:  print(1)
elif N == 2:
    if 1 == M:  print(1)
    else:   print(2)
else:
    temp, temp1, temp2 = 0,0,0
    if 1 not in a:  temp1 = 1
    if 2 not in a:  temp2 = 1 + temp1
    
    for i in range(2,N-1):
        temp = 0
        if i+1 not in a:    temp = temp1 + temp2
        temp1 = temp2
        temp2 = temp

    print( int((temp1+temp2) % 1000000007) )

Submission status: Accepted

Solution code:
def solve():
    N, M = map(int, input().split())
    A = []
    if M != 0:
        A = [int(input()) for _ in range(M)]
    A.sort(reverse=True)
    mm = 10 ** 9 + 7
    dp = [0] * (N + 1)
    dp[0] = 1  # 0段目に行くパターンは1とする
    tag = -1
    if len(A) != 0:
        tag = A.pop()
    # 1段目のパターンを設定
    if tag == 1:
        dp[1] = 0
        if len(A) == 0:
            tag = -1
        else:
            tag = A.pop()
    else:
        dp[1] = 1
    for i in range(2, N + 1):
        if i == tag:
            if len(A) == 0:
                tag = -1
            else:
                tag = A.pop()
            continue
        dp[i] = (dp[i - 1] + dp[i - 2]) % mm
    print(dp[N])


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
N,M=map(int,input().split())#N段、m-broken
cango=[True]*(N+1) #x段目が安全か
mod=10 ** 9 + 7
for i in range(M):
    cango[int(input())]=False
dp=[0]*(N+1) #dp[x]=x段目まで行く総数
dp[0]=1 #地上
dp[1]=int(cango[1])
for x,ok in enumerate(cango):#もらうdp
    if x==0 or x==1 :continue
    if ok:
        dp[x] += (dp[x - 1] + dp[x - 2])%mod
print(dp[N])

Submission status: Accepted

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

a=[1,1]
for i in range(2,100001):
    a.append((a[i-1]+a[i-2])%1000000007)

bad=[]
for i in range(m):
    bad.append(int(input()))
num=[]
before=0
bad_flag=0

if m!=0:
    for i in range(len(bad)):
        nxt=bad[i]-before-1
        if nxt==-1:
            bad_flag=1
            break
        num.append(nxt)
        before=bad[i]+1
    num.append(n-bad[len(bad)-1]-1)
else:
    num.append(n)
if bad_flag:
    print(0)
else:
    ans=0
    last=1
    for i in num:
        ans=a[i]*last
        last=ans%1000000007
    print(last)

Submission status: Accepted

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

if M == 0:
    A = [-1]
else:
    A = [-1] * M
    for i in range(M):
        A[i] = int(input())
A = set(A)

root = [0] * (N+1)  # N danme madeno root
root[0] = 1  # start is 1

if N == 1:
    if 1 in A:
        print(0)
    else:
        print(1)
    exit()

if N == 2:
    if 2 in A:
        print(0)
    else:
        if 1 in A:
            print(1)
        else:
            print(2)
    exit()

root[1] = 0 if 1 in A else 1
root[2] = 0 if 2 in A else (root[0] + root[1])

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

print(root[N] % 1000000007)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=[]
for i in range(m):
    x=int(input())
    if a:
        if x!=a[-1]:
            a.append(x)
    else:
        a.append(x)
count=[0]*(n+2)
count[1]=2
count[0]=1
i=0
s=0
if a:
    s=a.pop(0)
if s==1:
    count[1]=1
    count[0]=0
    if a:
        s=a.pop(0)
if s==2:
    count[1]=0
    if a:
        s=a.pop(0)

while i<n:        
    if (i+2==s-1):
        i=i+1
        if a:
            s=a.pop(0)
    else:
        count[i+2]=(count[i]+count[i+1])%1000000007
        i=i+1
#print(count)
print(count[n-1])

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
 
a_set=set()
 
for index in range(m):
    a_set.add(int(input()))
 
ans_list=[]
 
for index in range(n + 1):
    ans_list.append(0)
 
for index in range(n + 1):
    if index == 0:
        ans_list[index] += 1
        continue
    if index == 1 and (index not in a_set):
        ans_list[index] += ans_list[index - 1]
        continue
    
    if index not in a_set:
        if (index - 1) not in a_set:
            ans_list[index] += ans_list[index - 1]
            ans_list[index] %= 1000000007
        if (index - 2) not in a_set:
            ans_list[index] += ans_list[index - 2]
            ans_list[index] %= 1000000007
 
print(ans_list[n])

Submission status: Accepted

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

s = [0] * (n + 1)
s[-1] = 1
for _ in range(m):
    a = int(input())
    s[a] = None

if s[0] is None and s[1] is None:
    print(0)
    exit()

for i in range(n - 1, -1, -1):
    if s[i] is None:
        continue
    if i + 1 < len(s) and s[i + 1] is not None:
        s[i] += s[i + 1]
    if i + 2 < len(s) and s[i + 2] is not None:
        s[i] += s[i + 2]

print(s[0] % 1000000007)

Submission status: Accepted

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


def binary_search(l, value):
    low = 0
    high = len(l) - 1
    while low <= high:
        mid = (low + high) // 2
        if l[mid] == value:
            return True
        elif l[mid] < value:
            low = mid + 1
        else:
            high = mid - 1
    return False


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

A.append(10**6)
A.append(10**6)
B = [0] * (N + 1)
B[0] = 1
if binary_search(A, 1) is True:
    B[1] = 0
else:
    B[1] = 1
mod = 10**9 + 7

for i in range(2, N + 1):
    if i != 2 and binary_search(A, i - 1) is True and binary_search(
            A, i - 2) is True:
        print(0)
        exit()
    elif binary_search(A, i - 2) is True:
        B[i] = B[i - 1]
    elif binary_search(A, i - 1) is True:
        B[i] = B[i - 2]
    else:
        B[i] = B[i - 1] + B[i - 2]
    B[i] %= mod
print(B[N] % mod)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
lis = [int(input()) for i in range(m)]
dp = [0 for i in range(n+2)]
lis.append(0)
dp[0] = 1
cou = 0
co = 0
if lis[0] == 1:co += 1
for i in range(n):
  if i+1 != lis[cou]:
    dp[i+1] += dp[i]
    dp[i+1] %= 10 ** 9+7
  else:
    cou +=1
  if i+2 != lis[co]:
    dp[i+2] += dp[i]
    dp[i+2] %= 10 ** 9 + 7
  else:
    co += 1
print(dp[n])

Submission status: Accepted

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

a_set=set()

for index in range(m):
    a_set.add(int(input()))

ans_list=[]

for index in range(n + 1):
    ans_list.append(0)

for index in range(n + 1):
    if index == 0:
        ans_list[index] += 1
        continue
    if index == 1 and (index not in a_set):
        ans_list[index] += ans_list[index - 1]
        continue
    
    if index not in a_set:
        if (index - 1) not in a_set:
            ans_list[index] += ans_list[index - 1]
            ans_list[index] %= 1000000007
        if (index - 2) not in a_set:
            ans_list[index] += ans_list[index - 2]
            ans_list[index] %= 1000000007

print(ans_list[n])

Submission status: Accepted

Solution code:
from sys import stdin

N, M = [int(x) for x in stdin.readline().rstrip().split()]
a = [int(stdin.readline().rstrip()) for _ in range(M)]
fib = [1, 1]
for k in range(N):
    fib.append((fib[-1] + fib[-2]) % 1000000007)
if M == 0:
    print(fib[N])
    exit()
ans = fib[a[0] - 1]
for l in range(M - 1):
    if a[l + 1] - a[l] == 1:
        print(0)
        exit()
    ans = ans * fib[a[l + 1] - a[l] - 2]
ans = ans * fib[N - a[-1] - 1]
print(ans % 1000000007)

Submission status: Accepted

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


#debug = True
debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)

def solve():
    memo = {}

    def fib(n):
        if n in memo.keys():
            return memo[n]
        else:
            if n >= 4:
                ans = fib(n - 1) + fib(n - 2)
                memo[n] = ans
                return ans
            elif n == 3:
                return 2
            elif n == 2:
                return 1
            elif n == 1:
                return 1
            else:
                return 1

    n, m = map(int, input().split())
    w_list = []
    last = -1
    dead = False
    for i in range(m):
        a = int(input())
        w = a-last-1
        dprint(i, a, w)
        if w == 0:
            dead = True
            break
        w_list.append(w)
        last = a

    w_list.append((n+1)-last-1)

    dprint(w_list)

    mx = 10**9 + 7
    if dead == True:
        ans = 0
    else:
        ans = 1
        for w in w_list:
            fibw = fib(w)
            ans *= fibw
            dprint(w, fibw, ans)
            ans %= mx

    print(ans)

solve()

Submission status: Accepted

Solution code:
N,M  = map(int, input().split())
A = {}
mod = 10**9+7
for i in range(M):
    a = int(input())
    A[a] = 1
    if a-1 in A:
        print(0)
        exit()

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

for i in range(N):
    if i+1 not in A:
        stairs[i+1] = (stairs[i] + stairs[i+1]) % mod
    if i+2 not in A:
        stairs[i+2] = (stairs[i] + stairs[i+2]) % mod
        
print(stairs[N])

Submission status: Accepted

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

Submission status: Accepted

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

a = [0 for i in range(0, m)]
b = [True for i in range(0, n + 1)]
dp = [0 for i in range(0, n + 1)]

for i in range(0, m):
    a[i] = int(input())

for i in range(0, m):
    b[a[i]] = False

dp[0] = 1

if b[1]:
    dp[1] = 1
else:
    dp[1] = 0

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

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

Submission status: Accepted

Solution code:
mod = 1000000007

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

for i in range(len(A) - 1):
    if A[i] + 1 == A[i + 1]:
        print(0)
        quit()

fib = [-1] * (N + 1)
fib[0] = 1
fib[1] = 1
for i in range(2, len(fib)):
    fib[i] = fib[i - 1] + fib[i - 2]


ans = 1
pre = -1
lo = 0
for a in A:
    f = fib[a - 1 - lo]
    ans = (ans * f) % mod

    lo = a + 1
    pre = a

print(ans)

Submission status: Accepted

Solution code:
import sys
import heapq

N, M = map(int,input().split())
a_lists = []

if N == 1:
    if M == 0:
        print (1)
        sys.exit()
    else:
        print(0)
        sys.exit()

for m in range (M):
    temp = int(input())
    a_lists.append(temp-1)

a_lists.append(10**6)

datas = [0]*N
if 0 in a_lists:
    datas[0] = 0
    heapq.heappop(a_lists) 
    
else:
    datas[0]=1

if 1 in a_lists:
    datas[1] = 0
    heapq.heappop(a_lists) 
else:
    datas[1]= datas[0]+1
    
heapq.heapify(a_lists)
    
for i in range (2,N):
    if i == a_lists[0]:
        datas[i] =0
        heapq.heappop(a_lists) 
    else:
        datas[i] = datas[i-1] + datas[i -2]

print(datas[-1]%1000000007)

Submission status: Accepted

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

def SINGLE_INT(): return int(INPUT())
def MULTIPLE_INT_LIST(): return list(map(int, INPUT().split()))
def MULTIPLE_INT_MAP(): return map(int, INPUT().split())
def SINGLE_STRING(): return INPUT()
def MULTIPLE_STRING(): return INPUT().split()

def solve(n, m):
    floors = [0] * (n + 1)
    floors[0] = 1
    floors[1] = 1

    last, current = 0,0

    for i in range(m):
        if i == 0:
            current = SINGLE_INT()
            floors[current] = -1

        else:
            last = current
            current = SINGLE_INT()
            floors[current] = -1
            if current == last + 1:
                return 0

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

        floors[i] %= MOD

    return(floors[-1])


N, M = MULTIPLE_INT_MAP()

if N == 1:
    print(1)

elif N > 1:
    print(solve(N,M))

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify, heapreplace
from collections import defaultdict


class Solution:
    def main_old(self):
        N, M = map(int, input().split())
        self.memo = {}
        for _ in range(M):
            a = int(input())
            self.memo[a] = 0
        res = self.rec(N)
        print(res)

    def main(self):
        N, M = map(int, input().split())
        A = set()
        for _ in range(M):
            A.add(int(input()))
        dp = [0] * (N+1)
        dp[0] = 1
        for i in range(0, N+1):
            # print(dp)
            if i+1 <= N and i+1 not in A:
                dp[i+1] += dp[i]
                dp[i + 1] %= 1000000007
            if i+2 <= N and i+2 not in A:
                dp[i+2] += dp[i]
                dp[i + 2] %= 1000000007
        print(dp[N])

    def rec(self, n):
        if n < 0:
            return 0
        elif n == 0:
            return 1
        elif n in self.memo:
            return self.memo[n]
        else:
            val = (self.rec(n-1) + self.rec(n-2)) %1000000007
            self.memo[n] = val
            return val


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