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:
# solution
import io

nim,mike = map(int,input().split())

sets={int(input()) for _ in range(mike)}

modulous=10**9+7

array=[0]*(nim+1)
array[0]=1
array[1]=1
if 1 in sets:
  array[1]=0

for i in range(2,nim+1):
  if i in sets:
    continue
  array[i]=(array[i-1]+array[i-2])%modulous
print(array[nim])

Submission status: Accepted

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

# dp[i] = (i段目に辿り着くルートの総数)

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

# DP
for i in range(N):
  if not is_broken[i+1]:
    dp[i+1] += dp[i]
    dp[i+1] %= MOD
  if i+2 <= N:
    if not is_broken[i+2]:
      dp[i+2] += dp[i]
      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)]
MOD = int(1e9) + 7

tf = [True for _ in range(N)]
for i in a:
    tf[i-1] = False

if N <= 2:
    if N == 1:
        if tf[0]:
            print(1)
        else:
            print(0)
    else:
        if tf[0] and tf[1]:
            print(2)
        elif tf[0] or tf[1]:
            print(1)
        else:
            print(0)
    exit()


# DP
dp = []
if tf[0]:
    dp.append(1)
else:
    dp.append(0)
if tf[1]:
    dp.append(dp[0] + 1)
else:
    dp.append(0)
for i in range(N):
    if i == 0 or i == 1:
        continue
    else:
        if tf[i]:
            dp.append((dp[i-1] + dp[i-2])%MOD)
        else:
            dp.append(0)
print(dp[N-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# 初期入力
N,M = (int(x) for x in input().split())
A = set([int(input()) for i in range(M)])


#
mod_9 = 10**9 +7
dp =[0]*(N +1)
dp[0] = 1
if 1 not in A:
    dp[1] =1
for i in range(N-1):
    if i+2 in A:
        dp[i+2] = 0
    else:
        dp[i+2] = dp[i+1] + dp[i] 
        dp[i+2] %= mod_9
kotae =dp[N] # % mod_9
print(kotae )

Submission status: Accepted

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

broken = [False] * (N + 1)
for i in range(M):
    broken[int(input())] = True
dp = [0] * (N + 2)
mod = 1000000007
dp[N] = 1
for i in range(N-1,-1,-1):
    if broken[i]:
        dp[i] == 0
        continue
    dp[i] = (dp[i+1]+ dp[i+2]) % mod
    
print(dp[0])

Submission status: Accepted

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

mod = 1000000007

DP = [-1] * (N + 1) 
DP[0] = 1 
DP[1] = 1 

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

ans = 1
x = 0

for a in a_list:
    if a == x:
        ans = 0
        break
    
    ans = (ans * fib((a-1)-x)) % mod
    x = a+1
else:
    ans = (ans * fib(N-x)) % mod
    
print(ans)

Submission status: Accepted

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

oks = [True for i in range(N+1)]
for i in range(M):
    x = int(input())
    a.append(x)
    oks[x] = False

dp = [0 for i in range(N+1)]
dp[0] = 1

now = 0
while now < N:
    next = now+1
    while next <= min([N, now+2]):
        if oks[next]:
            dp[next] += dp[now]
            dp[next] %= 1000000007 
        next += 1
    now += 1

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

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

for i in a:
    dp[i] = 0

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

Submission status: Accepted

Solution code:
import sys
MOD = 10 ** 9 + 7

n, m, *broken = map(int, sys.stdin.read().split())
broken = set(broken)

def main():
    ways = [0] * (n + 1)
    ways[0] = 1
    ways[1] = int(not 1 in broken)
    for i in range(2, n + 1):
        ways[i] = (not i in broken) * (ways[i-1] + ways[i-2]) % MOD
    print(ways[n])

if __name__ ==  '__main__':
    main()

Submission status: Accepted

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

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

is_ok = [True] * (N+1)
for a in A:
  is_ok[a] = False

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

print(dp[N])

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
N, M, *A = map(int, read().split())
 
MOD = 10**9 + 7
 
dp = [0] * (N + 10)
dp[0] = 1
is_broken = [False] * (N + 1)
 
for x in A:
    is_broken[x] = True
 
for n in range(1, N + 1):
    if is_broken[n]:
        continue
    x = dp[n - 1] + dp[n - 2]
    if x >= MOD:
        x -= MOD
    dp[n] = x
 
answer = dp[N]
print(answer)

Submission status: Accepted

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

a = [int(input())-1 for _ in range(M)]
T = 1
for i in range(M-1):
    if a[i]+1 == a[i+1]:
        T = 0
        break
if T == 0:
    print(0)
else:
    if N == 1:
        if M==0:
            print(1)
        else:
            print(0)
    else:
        L = [0 for _ in range(N)]
        for i in range(M):
            L[a[i]] = -1
        if L[0] == -1:
            L[1] = 1
        else:
            L[0] = 1
            if L[1] != -1:
                L[1] = 2
        for i in range(2,N):
            if L[i] != -1:
                if L[i-2] == -1:
                    L[i] = L[i-1]%1000000007
                elif L[i-1] == -1:
                    L[i] = L[i-2]%1000000007
                else:
                    L[i] = (L[i-1]+L[i-2])%1000000007
        print(L[-1])

Submission status: Accepted

Solution code:
#3問目
NM = input().split()
N,M = int(NM[0]), int(NM[1])
A = set([int(input()) for _ in range(M)])
dp = [0] * (N+1)
dp[0] = 1
dp[1] = 1
MOD = 1000000007
    
if(1 in A):
    dp[1] = 0

for i in range(2, N+1):
    #貰うdp
    if(i in A):
        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 j in range(M)]

#dp[i]:i段目までの上がり方

div = 1000000007

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

def stairs():
    for i in range(N-1):
        if dp[i+1] == 0 and dp[i] == 0:
            break
        if a:
            if i+2 == a[0]:
                del a[0]
                continue
        dp[i+2] = (dp[i+1] + dp[i]) % div
    print(dp[N])

stairs()

Submission status: Accepted

Solution code:
fib = [1,1,1,2]
def fibonacci(n):
    if n<len(fib):
        return fib[n]
    x = len(fib)
    a = fib[len(fib)-2]
    b = fib[len(fib)-1]
    while x<=n:
        c = b
        b = a+b
        a = c
        x+=1
    return b

h = input().split(" ")
n = int(h[0])
a = []
for i in range(n+1):
    a.append(1)

m = int(h[1])
for i in range(m):
    an = int(input())
    a[an]=0

prod=1
ck = 0
sum = 0

for i in range(n+1):
    if a[i]==0:
        if ck==1:
            prod =0
            break
        prod*=fibonacci(sum)
        sum=0
        ck=1
    else:
        sum+=1
        ck=0
prod*=fibonacci(sum)
print(prod%1000000007)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def Fibonacci(n):
  if n==1 or n==2:
    return 1
  a,b=1,1
  for i in range (3,1+n):
    a,b=a+b,a
  return a

n,m=map(int,input().split())
bk=-1
ans=1
for i in range(m):
  a=int(input())
  if bk==-1 and a==2:
    ans*=2
  elif bk+1==a:
    print(0)
    exit()
  ans*=Fibonacci(a-bk-1)
  bk=a
if bk!=m:
  ans*=Fibonacci(n-bk)
print(ans%(10**9+7))

Submission status: Accepted

Solution code:
mod = pow(10,9)+7
N,M = map(int,input().split())
A = [int(input()) for i in range(M)]+[mod]
DP = [1]
k = 0
for i in range(1,N+1):
    if i==A[k]:
        DP.append(0)
        k+=1
    else:
        a = DP[i-1]
        b = DP[i-2] if i>1 else 0
        DP.append((a+b)%mod)
print(DP[N]%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)
dp[0] = 1
for a in A:
    dp[a] = -1

for i in range(N):
    if dp[i] >= 0:
        if dp[i + 1] >= 0:
            dp[i + 1] += dp[i]
        if i + 2 <= N and dp[i + 2] >= 0:
            dp[i + 2] += dp[i]

print(dp[N] % mod)
# print(dp)

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

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

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7

n, m = map(int, input().split())
pattern = [1]
broken = -1
brokencnt = 0
if brokencnt < m:
    broken = int(input())
    brokencnt += 1
for i in range(1, n+1):
    if i == broken:
        pattern.append(0)
        if brokencnt < m:
            broken = int(input())
            brokencnt += 1
        continue

    if i == 1:
        pattern.append(pattern[i-1])
    if i > 1:
        pattern.append((pattern[i-1]+pattern[i-2]) % mod)

print(pattern[n])

Submission status: Accepted

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

for i in range(m):
    dp[int(input())-1] = 10**12
    
if dp[0] == 10**12:
    dp[0] = 0
else:
    dp[0] = 1

if n == 1:
    print(dp[0])
else:
    if dp[1] == 10**12:
        dp[1] = 0
    else:
        dp[1] = 1+ dp[0]

    mod = 1000000007

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

mod = 1000000007

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

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

for i in range(n):
    # 出発点になれるなら、のみでOK
        # Falseの部分が更新されることはあっても、出発点になれないから
    if good[i]:
        if i+1 <= n:
            dp[i+1] += dp[i]
            dp[i+1]%= mod
        if i+2 <= n:
            dp[i+2] += dp[i]
            dp[i+2] %= mod

print(dp[n])

Submission status: Accepted

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


mod=10**9+7

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

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

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

print(t[n])

Submission status: Accepted

Solution code:
div = 1000000007

n, m, *b = map(int, open(0).read().split())
a = set(b)
 
f = [0] * (n + 1)
f[0] = 1

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

Submission status: Accepted

Solution code:
n, m = (int(x) for x in input().split())
MOD = 10 ** 9 + 7
INF = 10 ** 12
dp = [INF] * (n + 1)
for i in range(m):
  dp[int(input())] = 0
dp[0] = 1
for i in range(1, n+1):
  if dp[i] == INF:
    dp[i] = dp[i-1] % MOD
    if i > 1:
      dp[i] += dp[i-2] % MOD
    dp[i] %= MOD
print(dp[n])

Submission status: Accepted

Solution code:
N, M=map(int, input().split())
mod=10**9+7
pre=-1
hole=[]
for i in range(M):
  a=int(input())
  hole.append(a-1-pre)
  pre=a
hole.append(N-pre)

  

dp=[0]*(N+3)
dp[1]=1
dp[2]=1
for i in range(3,N+3):
  dp[i]=(dp[i-1]+dp[i-2])%mod
if len(hole)==1:
  print(dp[N+1])
  exit()
#print(dp)
#print(hole)
ans=1
for h in hole:
  ans*=dp[h]
  ans%=mod
  
print(ans)

Submission status: Accepted

Solution code:
N, M=map(int, input().split())
mod=10**9+7
pre=-1
hole=[]
for i in range(M):
  a=int(input())
  hole.append(a-1-pre)
  pre=a
hole.append(N-pre)

  

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

  
#print(dp)
#print(hole)
ans=1
for h in hole:
  ans*=dp[h]
  ans%=mod
  
print(ans)

Submission status: Accepted

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

MOD = 1000000007
MAX = 200000           #適当な数を入力
fac, finv, inv = [[0]*MAX for i in range(3)]
def combinit():     #MAXまでの下準備
  fac[0] = fac[1] = 1
  finv[0] = finv[1] = 1
  inv[1] = 1
  for i in range(2, MAX):
    fac[i] = fac[i - 1] * i % MOD
    inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i - 1] * inv[i] % MOD

def modcomb(n, k):      #mod(nCk)を計算、ただしn<MAX
  if (n < k):
    return 0
  if (n < 0 or k < 0):
    return 0
  return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD
combinit()          #下準備の実行 O(MAX)

def poss(n):
  n -= 1
  k = n//2
  ans = 0
  for i in range(k+1):
    ans += modcomb(n-i, i) % MOD
  return ans % MOD
if m == 0:
  print(poss(n+1))
  sys.exit()
ans = poss(danger[0])
for i in range(1, m):
  if danger[i] - danger[i-1] == 1:
    print(0)
    sys.exit()
  ans *= poss(danger[i] - danger[i-1] - 1)
  ans = ans % MOD
ans *= poss(n - danger[m-1])

print(ans % MOD)

Submission status: Accepted

Solution code:
# import fractions
# import sys
from sys import stdin

n, m = map(int, stdin.readline().rstrip().split())
a = [int(stdin.readline().rstrip()) for i in range(m)]
oks = []
mod = 1e+9 + 7
for i in range(n + 1):
    oks.append(True)
for ai in a:
    oks[ai] = False
dp = [0] * (n + 1)
dp[0] = 1
for now in range(n):
    for next in range(now + 1, min(n, now + 2) + 1):
        if oks[next]:
            dp[next] += dp[now]
            dp[next] %= mod

print(int(dp[n]))

Submission status: Accepted

Solution code:
from functools import lru_cache

def main():
    n,m = map(int,input().split())
    import numpy as np
    ans = np.ones(n+1,dtype=int)*-1
    ans[0] = 1
    mod = 10**9+7
    for _ in range(m):
        a = int(input())
        ans[a]=0
    if ans[1]!=0:
        ans[1]=1
    for i in range(2,n+1):
        if ans[i]!=0:
            ans[i] = (ans[i-1]+ans[i-2])%mod
    print(ans[-1])
        

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
line = input()
X, Y = [int(n) for n in line.split()]

broken_steps = set()
for _ in range(Y):
    line = input()
    broken_steps.add(int(line))

if 1 not in broken_steps:
    if 2 not in broken_steps:
        stairs = [1, 2]
    else:
        stairs = [1, 0]
elif 2 not in broken_steps:
    stairs = [0, 1]
else:
    stairs = [0, 0]

for i in range(2, X):
    number_of_steps = 0
    if i+1 not in broken_steps:
        number_of_steps = stairs[i - 1] + stairs[i-2]
    stairs.append(number_of_steps)
predicted_value = stairs[X-1]
print(predicted_value % 1000000007)

Submission status: Accepted

Solution code:
def fib(n, broken):
    a = 1
    b = 1
    for i in range(n-2):
        # if i in broken:

        a, b = b, a + b
    print(b)


# t = int(input())
t = 1

for _ in range(t):
    n, m = [int(x) for x in input().split()]
    broken = set()
    for _ in range(m):
        broken.add(int(input()))

    x = 0
    y = 1
    i = 1
    impossible = False
    c = 0
    while i <= n:
        # print(f'degrau: {i}')
        # print(f'main loop: i: {i}')
        if i in broken:
            # print('broken')
            x = y
            if i + 1 in broken:
                impossible = True
                break
            while not ((i + 1) not in broken and (i + 2) not in broken and (i + 3) not in broken):

                if i + 1 in broken and i + 2 in broken:
                    impossible = True
                if i + 2 in broken and i + 3 in broken:
                    impossible = True

                i += 1
            i += 2
            # while True:
            #     print('entrei')

            #     if not ((i + 1) not in broken and (i + 2) not in broken and (i + 3) not in broken):
            #         print('aqui')

            #         i += 1
            #         print(f'i: {i}')
            #         break
            #     i += 3
            #     break

            #     c = 0
            #     for x in range(i + 1, i + 4):
            #         if x in broken:
            #             c += 1
            #     if c >= 2:
            #         impossible = True

            #     print(f'i: {i}')
            # if i + 1 not in broken and i + 2 not in broken and i + 3 not in broken:
            #     i += 1

            # print('broken')
            # x = y
            # # y = x
            # print(f'x: {x}, y: {y}')
            # previous_broken = False
            # while i not in broken and (i + 1) not in broken and (i + 2) not in broken:
            #     i += 1
            # while c < 2:
            #     i += 1
            #     if i in broken:
            #         if previous_broken:
            #             impossible = True
            #         previous_broken = True
            #         continue
            #     else:
            #         previous_broken = False
            #         c += 1
            # i += 2
            # c = 0
        else:
            y, x = (x + y) % 1000000007, y % 1000000007
            # print(f'x: {x}, y: {y}')
            c = 0
        i += 1
        # print(y)
    print(0) if impossible else print(y % 1000000007)

Submission status: Accepted

Solution code:
n, m, *a = map(int, open(0).read().split())
div = 1000000007
broken = set(a)
 
f = [0] * (n + 1)
f[0] = 1
if 1 not in broken:
    f[1] = 1
 
for i in range(2, n + 1):
    if i in broken:
        continue
    f[i] = (f[i - 1] + f[i - 2]) % div
 
print(f[-1])

Submission status: Accepted

Solution code:
def main():
    N, M, *a = map(int, open(0).read().split())
    div = 1000000007
    broken = set(a)
 
    comb_list = [0] * (N + 1)
    comb_list[0] = 1
    if 1 not in broken:
        comb_list[1] = 1
 
    for i in range(2, N + 1):
        if i in broken:
            continue
        comb_list[i] = (comb_list[i - 1] + comb_list[i - 2]) % div
 
    print(comb_list[-1])
 
 
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    N, M, *a = map(int, open(0).read().split())
    div = 1000000007
    broken = set(a)

    comb_list = [0] * (N + 1)
    comb_list[0] = 1
    if 1 not in broken:
        comb_list[1] = 1

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

    print(comb_list[-1])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import functools
import operator

n,m= map(int,input().split())
def fib(n):
  x,y=1,2
  if n==1 or n==0:
    return x
  elif n==2:
    return y
  else:
    for i in range(n-2):
      x, y = y,x+y
    return y
if m==0:
  print(fib(n)%1000000007)
else:
  li=[int(input()) for i in range(m)]
  l=len(li)
  a=0
  b=0
  c=[]
  for i in range(l):
    b=li[i]-1
    c.append(b-a)
    a=li[i]+1
  c.append(n-(li[-1]+1))
  c2=[i for i in c if i<0]
  if sum(c2)<0:
    print(0)
  else:
    ans=list(map(fib,c))
    result = functools.reduce(operator.mul, ans)
    print(result%1000000007)

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7

N, M = map(int, input().split())
_is_ok = [True for i in range(N + 1)]
for i in range(M):
    _is_ok[int(input())] = False
ways = [0 for i in range(N + 1)]
ways[0] = 1
if _is_ok[1]:
    ways[1] = 1
for i in range(N - 1):
    if _is_ok[i + 2]:
        ways[i + 2] = ways[i + 1] + ways[i]
    ways[i + 2] %= mod
print(ways[N])

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
stair = []
mod = int(1e9+7)
for i in range(m):
    stair.append(int(input()))
dp = [0] * (n+1)
dp[0] = 1
stair.append(int(1e10))
k = 0
for i in range(1, n+1):
    if i == stair[k]:
        dp[i] = 0
        k += 1
    elif i == 1:
        dp[1] = 1
    else:
        dp[i] = (dp[i-1] + dp[i-2])%mod
print(dp[-1])

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
stair = []
mod = int(1e9+7)
ans = 1
for i in range(m):
    stair.append(int(input()))
dp = [0] * (n+1)
dp[0] = dp[1] = 1
stair.append(int(1e10))
if n == 1:
    print(1)
    exit()
k = 0
for i in range(1, n+1):
    if i == stair[k]:
        dp[i] = 0
        k += 1
    elif i == 1:
        dp[1] = 1
    else:
        dp[i] = (dp[i-1] + dp[i-2])%mod
print(dp[-1])

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=set([int(input()) for 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])%(10**9+7)
    if i in a:dp[i]=0
print(dp[n])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

count = [-1]*(n+1)
for stair in num:
  count[stair] = 0
  
count[0] = 1
count[1] = 1 if 1 not in num else 0

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

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
dp=[1 for _ in range(n+1)]
for i in range(m):
    a = int(input())
    dp[a] = 0
for i in range(2,n+1):
    if dp[i]==0:
        continue
    else:
        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())
alis = list(int(input()) for _ in range(m))
dp = [-1]*(n+1)
mod = 10**9 + 7
for i in alis:
    dp[i] = 0
dp[0] = 1
dp[1] = 1 if 1 not in alis else 0
for i in range(2,n+1):
    if dp[i] == -1:
        dp[i] = (dp[i-1] + dp[i-2]) % mod
print(dp[n])

Submission status: Accepted

Solution code:
import math
import string
import collections
from collections import Counter
from collections import deque
import sys
sys.setrecursionlimit(2*10**5)
INF = 2**60


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


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


def has_duplicates2(seq):
    seen = []
    for item in seq:
        if not(item in seen):
            seen.append(item)
    return len(seq) != len(seen)


def divisor(n):
    divisor = []
    for i in range(1, n+1):
        if n % i == 0:
            divisor.append(i)
    return divisor


# coordinates
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]

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

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

# print(a)
dp = [0]*(N+2)
#print('safe', safe)
dp[0] = 1
for i in range(0, N):
    if safe[i]:
        dp[i+1] = dp[i+1]+dp[i]
        dp[i+2] = dp[i+2]+dp[i]

    if not(safe[i]):
        dp[i] = 0
#print('dp', dp)
print(dp[N] % 1000000007)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
#import fractions
#import math
#import collections
#from collections import deque
#from bisect import bisect_left
#N = int(input())
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = list(map(int,input().split()))
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
N,M = map(int,input().split())
dicti = {i:True for i in range(N+2)}
for i in range(M):
    a = int(input())
    dicti[a] = False
ans = [0] * (N+3)
ans[0] = 1
for i in range(N):
    if dicti[i]:
        ans[i+1] += ans[i]
        ans[i+1] = ans[i+1] % 1000000007
        ans[i+2] += ans[i]
        ans[i+2] = ans[i+2] % 1000000007
    else:
        ans[i] = 0
print(ans[N])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
A =[int(input()) for _ in range(m)]
dict = {i:False for i in range(n)}
for a in A:
    dict[a]=True
dp = [0 for _ in range(n+2)]
dp[0] = 1
MOD = 1000000007
for i in range(n):
    if not dict[i]:
        dp[i+1] = (dp[i]+dp[i+1])%MOD
        dp[i+2] = (dp[i]+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)]
a=[-1]+a+[n+1]
d=[a[i+1]-a[i]-2 for i in range(m+1)]
def fib(x):
    if x==1:
        return [1,1]
    else:
        ans=[1,1]
        for i in range(2,x+1):
            ans.append(ans[-1]+ans[-2])
        return ans
md=max(d)
l=fib(md)
ans=1
for i in range(m+1):
    if d[i]==-1:
        ans=0
        break
    else:
        ans=ans*l[d[i]]
print(ans%1000000007)

Submission status: Accepted

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

f=[True]*(n+1)
for _ in range(m):
    f[int(input())]=False

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

print(dp[-1]%1000000007)

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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

print(dp[n])

Submission status: Accepted

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

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

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

Submission status: Accepted

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

for i in range(M):
    broken[a[i]-1]=0

for i in range(N):
    if i == 0:
        ans.append(broken[0])
    else:
        ans.append(ans[i] * broken[i-1] + ans[i-1] * broken[i-2])
        
print((ans[N]) % mod)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
def steps(N,M):
	a=[]
	b=[1,1]
	for j in range(N):
		b.append(b[-1]+b[-2])
	if M==0:
		return print(b[N]%1000000007)
	else:
		for i in range(M):
			a.append(int(input()))
		for i in range(M-1):
			if a[i+1]-a[i]==1:
				return print(0)
		ans=1
		a.append(N+1)
		a.insert(0,-1)
		for i in range(M+1):
				c=a[i+1]-a[i]-2
				ans*=(b[c])
		return print(ans%1000000007)
steps(N,M)

Submission status: Accepted

Solution code:
import math
import string
import collections
from collections import Counter
from collections import deque


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


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


def has_duplicates2(seq):
    seen = []
    for item in seq:
        if not(item in seen):
            seen.append(item)
    return len(seq) != len(seen)


def divisor(n):
    divisor = []
    for i in range(1, n+1):
        if n % i == 0:
            divisor.append(i)
    return divisor


# coordinates
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]

N, M = map(int, input().split())
a = []
for _ in range(M):
    a.append(int(input()))
# print(a)
dp = [0]*(N+1)
#dp[0] = 1
#dp[1] = 1
# for i in range(2, N):
#    dp[i] = dp[i-1]+dp[i-2]
safe = [True]*(N+1)
for i in range(M):
    safe[(a[i])] = False
#print('safe', safe)
dp[0] = 1
if safe[1]:
    dp[1] = 1
for i in range(2, N+1):
    if safe[i]:
        dp[i] = dp[i-1]+dp[i-2]
    if not(safe[i]):
        dp[i] = 0
#print('dp', dp)
print(dp[N] % 1000000007)