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:
nm=list(map(int,input().split()))
n=nm[0]
m=nm[1]

inp=[]
if m==0:
    inp=[n+1]
    dis=[n+1]
else:
    for inpset in range(m):
        inp.append(int(input()))
    

    dis=[max(inp[0],1)]
    p=0
    for i in inp[:-1]:
        dis.append(inp[p+1]-inp[p]-1)
        p+=1
    dis.append(max(n-inp[-1],1))
    #print (dis)

def fib(x):
    a=0
    b=1
    for step in range(x):
        c=a+b
        a=b
        b=c
    return a


def counting(x):
    if x==1:
        return 1
    else:
        
        res=0
        for a in range(x-1):
            if x-1-a>=a:
                res+=combinations_count(x-1-a,a)
                # print(x-1-a,a)
            else:
                break
        res=res%1000000007
        return res

if 0 in dis:
    print(0)
else:
    ans=1
    dis.sort()
    for d in dis:
        ans*=fib(d)%1000000007
        ans=ans%1000000007
    print(ans)

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    n,m = list(map(int, input().split()))
    a = []
    for i in range(m):
        a.append(int(input()))
    a.append(0)
    ac = 0

    step0 = 0
    step1 = 1
    for i in range(1, n+1):
        temp = step0 + step1
        step0 = step1
        step1 = temp
        if(i == a[ac]):
            step1 = 0
            ac += 1

    print(step1 % 1000000007)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
def main(N, M, a_list):
    div = 10**9 + 7

    a_set = set(a_list)
    
    dp = {}
    dp[0] = 1
    if 1 in a_set:
        dp[1] = 0
    else:
        dp[1] = 1

    for i in range(N):
        if i+2 in a_set:
            dp[i+2] = 0
        else:
            dp[i+2] = (dp[i+1] + dp[i])
    
    print(dp[N] % div)


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

    main(N, M, a_list)

Submission status: Accepted

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

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

print(dp[-1])

Submission status: Accepted

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

hole_count = 0
pattern = [0,1]

if m != 0:
    a = int(input())
    hole_count += 1
else:
    a = n+1
    
for i in range(n):
    index = i + 1
    if index == a:
        pattern.append(0)
        if hole_count < m:
            a = int(input())
            hole_count += 1
    else:
        pattern.append(pattern[-1] + pattern[-2])

print(pattern[-1] % 1000000007)

Submission status: Accepted

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


@lru_cache(maxsize=1000000)
def get_ways(n):
    if n == 1 or n == 2:
        return n
    elif n == 0:
        return 1
    elif n == -1:
        return 0
    else:
        return get_ways(n - 2) + get_ways(n - 1)


N, M = map(int, input().split())
ans = 1
tmp = 0
for i in range(M):
    a = int(input())
    ans *= get_ways(a - tmp - 1)
    tmp = a + 1
ans *= get_ways(N - tmp)
print(ans % 1000000007)

Submission status: Accepted

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

dp =[0]*(n+1)

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

for i in [0,1]:
    if dp[i] == -1:
        dp[i] =0
    else:
        dp[i] =1

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

print(dp[-1]%1000000007)

Submission status: Accepted

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

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

print(dp[N])

Submission status: Accepted

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

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

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

Submission status: Accepted

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

INF = 10 ** 9 + 7

memo = [None for _ in range(N + 1)]
memo[0] = 1
memo[1] = 0 if 1 in broken else 1
for i in range(2, N + 1):
    if i in broken:
        memo[i] = 0
    else:
        memo[i] = (memo[i - 2] + memo[i - 1]) % INF

print(memo[N])

Submission status: Accepted

Solution code:
from collections import defaultdict

N, M = map(int, input().split())
steps = [1 for _ in range(N + 1)]
for _ in range(M):
    i = int(input())
    steps[i] = 0
scores = defaultdict(int)
scores[0] = 1
scores[1] = steps[1]

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

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
b = [] 
for i in range(n+1):
  if i == 0 or i == 1:
    b.append(1)
  else:
    b.append(b[i-2]+b[i-1])

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
s = sys.stdin.readlines()
N, M = map(int, s[0].split())
if M > 0:
    a_set = set(map(int, s[1:]))
else:
    a_set = set()

# DP
dp = [0] * (N + 1)
# def case 0, 1
dp[0] = 1
dp[1] = 1 if 1 not in a_set else 0
divisor = 10 ** 9 + 7
 
for i in range(2, N + 1):
    if i in a_set:
        continue
    dp[i] = (dp[i - 2] + dp[i - 1]) % divisor
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)]
broken = [False] *(N+1)
for i in range(M):
    broken[a[i]] = True

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

for i in range(N):
    for j in range(i+1, min(N+1, i+3)):
        if not broken[j]:
            dp[j] += dp[i]


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 for i in range(N+1)]
dp[0] = 1

isbroken = [1 for _ in range(N+1)]

for i in range(M):
    isbroken[A[i]] = 0

for i in range(N):
    if i-1 >= 0:
        dp[i+1] = dp[i] * isbroken[i] + dp[i-1] * isbroken[i-1]
    else:
        dp[i+1] = dp[i] * isbroken[i]
    
    dp[i+1] %= mod
    
print(dp[N])

Submission status: Accepted

Solution code:
n, m = map(int,input().split())
lists = [1,2]
bag_step = [-1]
last = 0
conbi = 1
 
def conbination(num):
    if len(lists) >= num:
        return lists[num-1]
    for i in range(len(lists),num):
        lists.append(lists[i-1]+lists[i-2])
    return lists[num-1]
 
for i in range(m):
    bag_step.append(int(input())) #穴が空いているステップ
bag_step.append(n+1)
for i in range(1,len(bag_step)):
  if bag_step[i] == bag_step[i-1] + 1:
    conbi = 0
    break
  if bag_step[i] == bag_step[i-1] + 2:
    continue
  conbi = conbi * conbination(bag_step[i] - bag_step[i-1] - 2)%(1000000007)
print(conbi)

Submission status: Accepted

Solution code:
def Fib(n):
    a, b = 0, 1
    if n == 1:
        return a
    elif n == 2:
        return b
    else:
        for i in range(n-2):
            a, b = b, a + b
        return b
a,b=input().split()
a=int(a)
b=int(b)
ll=[]
y=-1
s=0
for i in range(b):
    x=input()
    x=int(x)
    ll.append(x)
    if x-y==1:
        s=1
        break
    y=x
ll.append(a+1)
l2=[]
if s==1:
    print(0)
else:
    x=-1
    for i in ll:
        l2.append(Fib(i-x))
        x=i
    ans=1
    for i in l2:
        ans*=i
    print(ans%1000000007)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import numpy as np

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

# a[i] = 0 の床は踏めない
a = np.ones(n+1, dtype=np.bool)
for _ in range(m):
    a[int(input())] = 0

mod = 1e9 + 7

# pos[i]はi段目まで登る場合の数
pos = np.zeros(n+1)
pos[0] = 1
for i in range(n-1):
    if a[i+1]:
        pos[i+1] += pos[i]
        pos[i+1] %= mod
    if a[i+2]:
        pos[i+2] += pos[i]
        pos[i+2] %= mod

pos[n] += pos[n-1]

print(int(pos[n] % mod))

Submission status: Accepted

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

def num_way(stair):
  memo = ["EMPTY"]*(stair+1)
  def _fib(stair):
    if stair == 1 or stair == 0:
      return 1
    elif stair == 2:
      return 2
    elif memo[stair] != "EMPTY":
      return memo[stair]
    else:
      memo[stair] = _fib(stair-1)+_fib(stair-2)
      return memo[stair]
  return _fib(stair)

N, M = map(int,input().split())
a = deque([0])
path_poss = 1
ans = 1
for m in range(M):
  start = a.popleft()
  buff = int(input())
  end = buff-1
  if (end-start) <= -1:
    path_poss = 0
    break
  a.append(buff+1)
  ans *= num_way(end-start)
  ans %= 1000000007

if path_poss == 0:
  print(0)
else:
  start = a.popleft()
  end = N
  if(end-start) <= -1:
    path_poss = 0
  if path_poss == 0:
    print(0)
  else:
    ans *= num_way(end-start)
    print(ans%1000000007)

Submission status: Accepted

Solution code:
from collections import defaultdict
N, M = map(int, input().split())
A = [int(input()) for i in range(M)]
dict = defaultdict(int)
for a in A:
    dict[a] += 1

mod = 10 ** 9 + 7
dp = [0 for _ in range(N+1)]
dp[0] = 1
if dict[1] == 0:
    dp[1] = 1

for i in range(1, N):
    if dict[i] == 0 and dict[i-1] == 0:
        dp[i+1] += ((dp[i-1] + dp[i]) % mod)
    elif dict[i] == 0:
        dp[i+1] += (dp[i] % mod)
    elif dict[i-1] == 0:
        dp[i+1] += (dp[i-1] % mod)

print(dp[-1])

Submission status: Accepted

Solution code:
from collections import defaultdict
N, M = map(int, input().split())
A = [int(input()) for i in range(M)]
dict = defaultdict(int)
for a in A:
    dict[a] += 1

mod = 10 ** 9 + 7
dp = [0 for _ in range(N+1)]
dp[0] = 1
dp[1] = 1
for i in range(1, N):
    if dict[i] == 0 and dict[i-1] == 0:
        dp[i+1] += ((dp[i-1] + dp[i]) % mod)
    elif dict[i] == 0:
        dp[i+1] += (dp[i] % mod)
    elif dict[i-1] == 0:
        dp[i+1] += (dp[i-1] % mod)

print(dp[-1])

Submission status: Accepted

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

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


for i in range(0, N-1):
    counter_arr[i+1] += counter_arr[i] * broken_lst[i+1]
    counter_arr[i+1] %= 10**9 + 7
    counter_arr[i+2] += counter_arr[i] * broken_lst[i+2]
    counter_arr[i+2] %= 10**9 + 7

counter_arr[-1] += counter_arr[-2] * broken_lst[-1]
counter_arr[-1] %= 10**9 + 7

print(counter_arr[-1])

Submission status: Accepted

Solution code:
def func(x, a, n):
    if a[n] == 1:
        x[n] = a[n-1] * x[n-1] + a[n-2] * x[n-2]
    else:
        x[n] = 0

def main():
    K = 1000000007
    line = input().split(' ')
    N = int(line[0])
    M = int(line[1])
    a = [1] * (N + 1)
    x = [0] * (N + 1)

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

    x[0] = 1
    if a[1] == 1:
        x[1] = 1
    else:
        x[1] = 0

    for i in range(2, N+1):
        func(x, a, i)
        
    print(x[N]%K)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
mod = 10**9 + 7
n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
ok = [True] * (n + 1)
for x in a:
    ok[x] = False
dp = [0] * (n + 1)
dp[0] = 1
for i in range(n + 1):
    if i > 0 and ok[i - 1]:
        dp[i] = (dp[i] + dp[i - 1])
    if i > 1 and ok[i - 2]:
        dp[i] = (dp[i] + dp[i - 2])
print(dp[n] % mod)

Submission status: Accepted

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

broken = [0 for _ in range(n+1)]
for i in range(m):
    a = int(input())
    broken[a] = True

    
mod = 1000000007
dp = [0 for _ in range(n+2)]

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:
import copy
n,m = map(int,input().split())
a00 = 0
a0 = 1
if m > 0:
    ann = 0
    for i in range(m):
        an = int(input())
        if an != ann:
            for x in range(an-ann-1):
                ak = copy.copy(a00 + a0)
                a00 = copy.copy(a0)
                a0 = copy.copy(ak)
            ann = copy.copy(an)
            a00 = copy.copy(a0)
            a0 = 0
        else:
            ann = copy.copy(an)
    for j in range(n-an):
        ak = copy.copy(a00+a0)
        a00 = copy.copy(a0)
        a0 = copy.copy(ak)
else:
    for i in range(n):
        ak = copy.copy(a00 + a0)
        a00 = copy.copy(a0)
        a0 = copy.copy(ak)
print(a0 % 1000000007)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
k = []
count_sub = 0
steps = []
j = 0
for i in range(m):
    k.append(int(input())) 
    if len(k)>1 and k[i]-k[i-1]==1:
        count_sub = 1
        
if count_sub ==1:
    steps = [0 for i in range(n)]  
else:
    for i in range(n+1):
        if k!=[] and k[j]==i:
            steps.append(0)
            if j < len(k)-1:
                j = j + 1
        elif i ==0:
            steps.append(1)
        elif i ==1:
            steps.append(1)  
        else:
            steps.append((steps[i-1]+steps[i-2])%1000000007)
 
print(steps[-1])

Submission status: Accepted

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

a.append(0)

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

print(dp[-1])

Submission status: Accepted

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

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

print(dp[-1])

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
k = []
count_sub = 0
steps = []
j = 0
for i in range(m):
    k.append(int(input())) 
    if len(k)>1 and k[i]-k[i-1]==1:
        count_sub = 1
        
if count_sub ==1:
    steps = [0 for i in range(n)]  
else:
    for i in range(n+1):
        if k!=[] and k[j]==i:
            steps.append(0)
            if j < len(k)-1:
                j = j + 1
        elif i ==0:
            steps.append(1)
        elif i ==1:
            steps.append(1)  
        else:
            steps.append(steps[i-1]+steps[i-2])
 
print(steps[-1]%(1000000007))

Submission status: Accepted

Solution code:
n,m = list(map(int, input().split()))
a=[]
a.append(-1)
for x in range(m):
  tmp=int(input())
  a.append(tmp)
a.append(n+1)
diff = []
for x in range(len(a)-1):
  diff.append(a[x+1]-a[x])
              
large = 0
small = 123456789012345
for x in diff:
  large=max(large,x)
  small=min(small,x)

num=[0,0,1]
for _ in range(large):
  num.append((num[-1]+num[-2])%1000000007)
    
answer=1
for x in diff:
  #print(x,num[x])
  answer *=num[x]
  answer%=1000000007
print(answer)

Submission status: Accepted

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

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

memo = [0]*(n+1)
memo[0]=1
if not(1 in a):
    memo[1]=1

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

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

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
a=[int(input()) for i in range(M)]
tf=[0]*(N+1)
for i in a:
  tf[i]=1
dp=[0]*(N+1)
dp[0]=1
dp[1]=0 if 1 in a else 1
mod=10**9+7
 
for i in range(2,N+1):
    if tf[i] == 1:
        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())
dp=[0]*(N+3)
dp[0]=1
a=[0]*(N+3)
for i in range(M):
    a[int(input())]=1
mod=10**9+7

for i in range(N+1):
    if a[i+1] != 1:
        dp[i+1]+=dp[i]
        dp[i+1]%=mod
    if a[i+2] != 1:
        dp[i+2]+=dp[i]
        dp[i+2]%=mod

print(dp[N])

Submission status: Accepted

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

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

a_set = {int(input()) for _ in range(m)}

ans_list = []

ans_list = [0] * (n + 1)

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:
import sys
input = sys.stdin.readline

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

a_set=set()

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

ans_list = []

ans_list = [0] * (n + 1)

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:
import sys
input = sys.stdin.readline

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

a_set=set()

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

ans_list=[0] * (n + 1)

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:
import sys
input = sys.stdin.readline

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:
import sys
n,m=map(int,input().split())
a=set(map(int,sys.stdin))
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
    if dp[i-1]==dp[i-2]==0:break
    dp[i]=(dp[i-1]+dp[i-2])%1000000007
print(dp[-1])

Submission status: Accepted

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

B = set(A)

X = [1, 1 if 1 not in B else 0]
for i in range(2, N + 1):
    x = (X[-1] + X[-2]) % 1000000007
    X.append(x if i not in B else 0)

print(X[N])

Submission status: Accepted

Solution code:
MOD = 10**9 + 7

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

path = [-1] * (N+1)
path[0] = 1
path[1] = 1
for a in A:
    path[a] = 0
for i, p in enumerate(path):
    if i < 2:
        continue
    if p == -1:
        path[i] = (path[i-1] + path[i-2]) % MOD
print(path[-1])

Submission status: Accepted

Solution code:
import sys
n,m=map(int,input().split())
a={int(input()) for i 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 in a:continue
    if dp[i-1]==dp[i-2]==0:break
    dp[i]=(dp[i-1]+dp[i-2])%1000000007
print(dp[-1])

Submission status: Accepted

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

MOD = 1000000007

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

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

for i in range(1,n+1):
    if count[i] == 0:
        continue
    
    if i == 1:
        count[i] = 1 
    elif i == 2:
        count[i] = count[i-1] + 1
    else:
        count[i] = (count[i-1] + count[i-2]) % MOD

print(count[n])

Submission status: Accepted

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

N, M = list(map(int, sys.stdin.readline().split()))
A = [int(sys.stdin.readline()) for _ in range(M)]
MOD = 10 ** 9 + 7

safe = [True for _ in range(N + 1)]
for a in A:
    safe[a] = False

dp = [0 for _ in range(N + 1)]
dp[0] = 1
for i in range(N + 1):
    if not safe[i]:
        continue
    if i + 1 < len(dp):
        dp[i + 1] += dp[i]
        dp[i + 1] %= MOD
    if i + 2 < len(dp):
        dp[i + 2] += dp[i]
        dp[i + 2] %= MOD
print(dp[-1])

Submission status: Accepted

Solution code:
import sys
# input = sys.stdin.readline
 
n, m = map(int, input().split())
s = set(map(int, [input() for _ in range(m)]))
MOD = 10 ** 9 + 7
a = 1 if not 0 in s else 0
b = 1 if not 1 in s else 0
for i in range(2, n + 1):
    if i in s:
        a, b = b, 0
    else:
        a, b = b, (a + b) % MOD
print(b)

Submission status: Accepted

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

for i in range(1,n+1):
  if x[i-1]==False:
    block=block[1:]+[0]
  else:
    block=block[1:]+[sum(block)%mod]
print(block[-1])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
 
n, m = map(int, input().split())
s = set(map(int, [input() for _ in range(m)]))
MOD = 10 ** 9 + 7
a = 1 if not 0 in s else 0
b = 1 if not 1 in s else 0
for i in range(2, n + 1):
    if i in s:
        a, b = b, 0
    else:
        a, b = b, (a + b) % MOD
print(b)

Submission status: Accepted

Solution code:
def org_fib(t):
    t1 = 1
    t2 = 2
    fib = 0
    if t == 1:
        return t1
    elif t == 2:
        return t2
    else:
        for _ in range(t-2):
            fib = t1+t2
            t1 = t2
            t2 = fib
    return fib % 1000000007

N,M = map(int,input().split())
if N == 1:
    print(1)
elif M == 0:
    print(org_fib(N))
else:
    pre_a = -1
    k = []
    ef = True
    for i in range(M):
        a = int(input())
        if (a-pre_a == 1):break
        k.append(a-pre_a-2)
        pre_a = a
    else:
        ef = False
        k.append(N-a-1)

    if ef:print(0)
    else:
        g = 1
        for kk in k:
            if kk == 0:pass
            else:g = (g * org_fib(kk)) % 1000000007
        print(g)

Submission status: Accepted

Solution code:
MOD = 1000000007

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

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

for i in range(1,n+1):
    if count[i] == 0:
        continue
    
    if i == 1:
        count[i] = 1 
    elif i == 2:
        count[i] = count[i-1] + 1
    else:
        count[i] = (count[i-1] + count[i-2]) % MOD

print(count[n])

Submission status: Accepted

Solution code:
OK = "O"
BRO = "B"

N,M=map(int, input().split())
Broken=[int(input()) for i in range(M)]
#K = "".join(list(BRO if i in Broken else OK for i in range(N+1)))
K = list(OK for i in range(N+1))
for i in range(M):
  K[Broken[i]] = BRO
  
if N == 1:
  print(1)
  exit()
  
c=[0 for i in range(N+1)]
if K[N-1]==OK:
  c[1]=1
if K[N-2]==OK and K[N-1]==OK:
  c[2]=2
if K[N-2]==OK and K[N-1]==BRO:
  c[2]=1

for i in range(3,N+1):
  if K[N-i]==OK:
    if K[N-i+1]==OK and K[N-i+2]==OK:
      c[i]=c[i-1]+c[i-2]
    if K[N-i+1]==OK and K[N-i+2]==BRO:
      c[i]=c[i-1]
    if K[N-i+1]==BRO and K[N-i+2]==OK:
      c[i]=c[i-2]
  c[i]%=1000000007
  
print(c[N] % 1000000007)

Submission status: Accepted

Solution code:
OK = 0
BRO = 1

N,M=map(int, input().split())
Broken=[int(input()) for i in range(M)]
#K = "".join(list(BRO if i in Broken else OK for i in range(N+1)))
K = list(0 for i in range(N+1))
for i in range(M):
  K[Broken[i]] = 1
  
if N == 1:
  print(1)
  exit()
  
c=[0 for i in range(N+1)]
if K[N-1]==OK:
  c[1]=1
if K[N-2]==OK and K[N-1]==OK:
  c[2]=2
if K[N-2]==OK and K[N-1]==BRO:
  c[2]=1

for i in range(3,N+1):
  if K[N-i]==OK:
    if K[N-i+1]==OK and K[N-i+2]==OK:
      c[i]=c[i-1]+c[i-2]
    if K[N-i+1]==OK and K[N-i+2]==BRO:
      c[i]=c[i-1]
    if K[N-i+1]==BRO and K[N-i+2]==OK:
      c[i]=c[i-2]
  c[i]%=1000000007
  
print(c[N] % 1000000007)

Submission status: Accepted

Solution code:
import sys
MOD = 1000000007

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

count = [0 for i in range(n+1)]
nxt = 0

def scount(s,e):
    #print(s,e,file=sys.stderr)
    global count
    for i in range(s,e):
        if i == 0:
            count[i] = 1 
        elif i == 1:
            count[i] = 1
        else:
            count[i] = (count[i-1] + count[i-2]) % MOD

for i in range(m):
    a = int(input())
    if nxt == a:
        print(0)
        exit(0)
    scount(nxt,a)
    nxt = a+1

scount(nxt,n+1)

#print(count,file=sys.stderr)
print(count[n])

Submission status: Accepted

Solution code:
OK = 0
BRO = 1
MOD = 1000000007

N,M=map(int, input().split())
Broken=[int(input()) for i in range(M)]
#K = "".join(list(BRO if i in Broken else OK for i in range(N+1)))
K = list(0 for i in range(N+1))
for i in range(M):
  K[Broken[i]] = 1
  
dp=[0 for i in range(N+1)]
dp[0]=1
for i in range(N):
  for j in range(i+1,min(i+2+1,N+1)):
    if K[j]==OK:
      dp[j]+=dp[i]
      dp[j]%=MOD
      
print(dp[N])

Submission status: Accepted

Solution code:
d = 1000000007
N, M = list(map(int, input().split()))
a = [int(input()) for i in range(M)]
safe = [True for i in range(N+1)]
for ai in a:
  safe[ai] = False
dp = [0 for i in range(N+1)]
dp[0] = 1
dp[1] = 1 if safe[1] else 0
for i in range(2, N+1):
  dp[i] = (dp[i-2]+dp[i-1]) % d if safe[i] else 0
print(dp[N])

Submission status: Accepted

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

N, M = map(int, input().split())
L = set([int(input()) - 1 for _ in range(M)])
ans = [0] * N

if 0 not in L:
    ans[0] = 1
    
if N > 1 and 1 not in L:
    ans[1] = ans[0] + 1

for i in range(2, N):
    if i in L:
        continue
    
    if ans[i - 2] != 0 or ans[i - 1] != 0:
        ans[i] = ans[i - 2] + ans[i - 1]
        
print(ans[-1] % (1000000007))

Submission status: Accepted

Solution code:
MOD = 1000000007
N = 100001

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

n, m = list(map(int, input().split(" ")))
a_list = [int(input()) for _ in range(m)]
is_ngs = [0] * (n + 2)
for a in a_list:
    is_ngs[a] = 1
for i in range(n):
    if is_ngs[i] and is_ngs[i + 1]:
        print(0)
        exit()
cnts = []
cnt = 0

for i in range(n + 1):
    if is_ngs[i]:
        cnts.append(cnt)
        cnt = 0
        continue
    cnt += 1
cnts.append(cnt)
ans = 1
for c in cnts:
    if c != 0:
        ans *= fibo[c - 1]
# print(is_ngs)
# print(cnts)
print(ans % MOD)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
num = 10**9+7
nots = [int(input()) for i in range(m)]
dp = [-1]*(n+1)
dp[0] = 1

for i in nots:
  dp[i] = 0

if dp[1] == -1:
  dp[1] = 1

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

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

Submission status: Accepted

Solution code:
import sys
import numpy as np

MOD = 1000000007

def main():
    n, m = [int(x) for x in 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])


main()