Problem:


Score : 300 points

Problem Statement

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

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

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

Constraints

1 \leq N \leq 10^5

0 \leq M \leq N-1

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

Input

Input is given from Standard Input in the following format:

N M
a_1
a_2
 .
 .
 .
a_M

Output

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

Sample Input 1

6 1
3

Sample Output 1

4

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

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

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

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

0 \to 2 \to 4 \to 6

Sample Input 2

10 2
4
5

Sample Output 2

0

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

Sample Input 3

100 5
1
23
45
67
89

Sample Output 3

608200469

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



Sample input:
6 1
3


Sample output:
4

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
n,m = list(map(int, input().split()))
s = [0 for i in range(n+1)]
t = [-1 for i in range(n+1)]
for i in range(m):
    x = int(input())
    s[x] = 1

def dx(r):
    global t
    if t[r]>=0:
        return t[r]
    x=0
    y=0
    #print(i)
    if s[r+1]==0 and r==n-2:
        return 2
    if s[r+1]==1 and r==n-2:
        return 1
    if r==n-1:
        return 1
    if r==n:
        return 0
    if s[r+1] == 0:
        x=dx(r+1)
    if s[r+2] == 0:
        y=dx(r+2)
    #print([i,x,y])
    t[r]=(x+y)%1000000007
    return (x+y)%1000000007

ans=dx(0)

print(ans)

Submission status: Accepted

Solution code:
def fibonacci(n):
    dp = [1 for i in range(n)]
    for i in range(2,n):
        dp[i] = dp[i-2]+dp[i-1]
    return dp[n-1]

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

b = -1

ans = 1
for i in range(m+1):
    a = b
    if i==m:
        b = n+1
    else:
        b = int(input())
    c = b-a-2
    if c == -1:
        print(0)
        exit()
    ans *=fibonacci(c+1)
    ans %= 10**9+7

print(ans)

Submission status: Accepted

Solution code:
import sys
N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
mod = 10 ** 9 + 7

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

B = ['.'] * (N + 1) 
for a in A:
    B[a] = '#'
    
dp = [0] * (N + 1)
if B[1] == '.' and B[2] == '.':
    dp[1] = 1
    dp[2] = 2
elif B[1] == '#' and B[2] == '.':
    dp[2] = 1
elif B[1] == '.' and B[2] == '#':
    dp[1] = 1
    
for i in range(3, N + 1):
    if B[i] == '.':
        dp[i] = (dp[i - 2] + dp[i - 1]) % mod
    
print(dp[N])

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

mm = 1000000007
n, m = na()
ai = [-1]
for i in range(m):
    ai.append(int(input()))
ai.append(n+1)
li = [1, 1]
for i in range(n+4):
    li.append(li[i] + li[i+1])
ans = 1
#print(li)
if m == 0:
    print(li[n] % mm)
else:
    for i in range(len(ai) - 1):
        if ai[i+1] - ai[i] == 1:
            ans = 0
            break
        else:
            ans *= li[(ai[i+1] - ai[i]) - 2]
            ans = ans % mm
    print(ans)

Submission status: Accepted

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

M = 1000000007

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

Submission status: Accepted

Solution code:
inpl = lambda: list(map(int,input().split()))
MOD = 10**9 + 7
N, M = inpl()
A = []
for _ in range(M):
    A.append(int(input()))
A.append(0)

prev = 1
prev_prev = 0
m = 0
for i in range(1,N+1):
    if A[m] == i:
        prev, prev_prev = 0, prev
        m += 1
    else:
        prev, prev_prev = (prev + prev_prev) % MOD, prev
print(prev)

Submission status: Accepted

Solution code:
NM = list(map(int,input().split()))
N = NM[0]
M = NM[1]

A =[]
while True:
    try:
        A.append(int(input()))
    except:
        break;

countlist = [1,1,2]
if N >3:
    for i in range(3,N+1):
        a = countlist[i-2]+countlist[i-1]
        if a>1000000007:
            a = a%1000000007
        countlist.append(a)

t = 0
count = 0
out = []

if N >1:
    for i in range(1,N+1):
        count+=1
        if ((t<len(A))and(i==A[t])):
            t+= 1
            while ((t<len(A))and(i==A[t])):
                t+=1
            if count > 0:
                out.append(countlist[count-1])
            else:
                out.append(0)
                break
            count = -1


if count>=0:
    out.append(countlist[count])

output = 1

for i in range(len(out)):
    output = output*out[i]
    if output > 1000000007:
        output = output%1000000007

print(output)

Submission status: Accepted

Solution code:
def Fib(n):
    a, b = 1, 2
    if n == 1:
        return a
    elif n == 2:
        return b
    else:
        for i in range(n - 2):
            a, b = b, a + b
        return b

now_step = 0
ans = 1
N, M = map(int, input().split(" "))
for i in range(M):
    a = int(input())
    if now_step == a:
        ans *= 0
        break
    elif now_step == (a - 1):
        now_step = a + 1
        continue
    else:
        ans *= Fib((a - 1) - now_step)
        now_step = a + 1
if now_step != N:
    ans *= Fib(N - now_step)
print(ans % 1000000007)

Submission status: Accepted

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

mod=1000000007

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


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

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

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



a_i2=0
a_i1=0
a_i=0

for i in range(n-1):
  if i+2 == a[a_i2]:
      a_i2 += 1
      if a_i2 == m:
        a_i2 -= 1
  else:
    if i+1 == a[a_i1]:
      if i == a[a_i]:
        dp[i+2]=0
        a_i += 1
        if a_i == m:
          a_i -= 1
      else:
        dp[i+2]=dp[i]
      a_i1 += 1
      if a_i1 == m:
        a_i1 -= 1
    else:
      if i == a[a_i]:
        dp[i+2]=dp[i+1]
        a_i += 1
        if a_i == m:
          a_i -= 1
      else:
        dp[i+2]=dp[i+1]+dp[i]

  dp[i+2] = dp[i+2] % mod
  #print(dp)

print(dp[n])

Submission status: Accepted

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

def convi(li):
    m=max(li)
    a=[1,1]
    if m>2:
        for i in range(2,m+1):
            a.append(a[i-2]+a[i-1])
            
    ans=1    
    for j in li:
        ans=ans*a[j-1]%1000000007
    return ans

def count(li,n):
    t=1
    ans=1
    li2=[]
    li.append(n+1)
    if len(li)>0:
        for i in range(len(li)):
            
            if i>0:
                li2.append(li[i]-li[i-1]-1)
                if li[i]-li[i-1]==1 and i<len(li):
                    return 0
            else:
                li2.append(li[i])
                
    #print(li2)      
    return convi(li2)
                

print(count(li,n)%1000000007)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
MOD = 10**9 + 7
A = [int(input()) for _ in range(M)]
pat = [0] * (N+3)
pat[1] = 1
pat[2] = 2
for i in range(3, N+1):
    pat[i] = (pat[i-1] + pat[i-2]) % MOD
if M == 0:
    print(pat[N] % MOD)
else:
    steps = []
    if len(A) > 1:
        for i in range(M-1):
            d = A[i+1] - A[i]
            if d > 2:
                steps.append(d-2)
            elif d == 1:
                steps.append(0)
    if A[0] != 1:
        steps = [A[0] - 1] + steps
    if A[-1] != N-1:
        steps += [N - A[-1] - 1]
    ans = 1
    for s in steps:
        ans = (ans * pat[s]) % MOD
    print(ans)

Submission status: Accepted

Solution code:
patterns_dictionary = {}
patterns_dictionary[1] = 1
patterns_dictionary[2] = 1


def patterns(start_n, broken_n):
    # start;自分がいる場所，こわれていない．一つ前はこわれている
    diff = broken_n - start_n
    if diff in patterns_dictionary:
        return patterns_dictionary[diff]
    for ii in range(len(patterns_dictionary)+1, diff+1):
        patterns_dictionary[ii] = patterns_dictionary[ii-1] + patterns_dictionary[ii-2]
    ans = patterns(start_n, broken_n - 1) + patterns(start_n, broken_n - 2)
    patterns_dictionary[diff] = ans
    return ans


inp = input()
split_input = inp.split()
n = int(split_input[0])
m = int(split_input[1])
start = 0
patterns_count = 1
# broken_number = -1
for i in range(m+1):
    if i == m:
        broken = n + 1
    else:
        inp = input()
        broken = int(inp)
    if broken == start:
        # 二つ連続で通れない
        print(0)
        exit()
    # print(start, broken)
    p = patterns(start, broken)
    patterns_count = (patterns_count * p) % 1000000007
    start = broken + 1

print(patterns_count)

Submission status: Accepted

Solution code:
mod=1000000007
n,m=map(int,input().split())
d=set([])
w=[0]*(n+2)

for i in range(m):
    a=int(input())
    d.add(a)
for i in range(n):
    if i==0 and 1 not in d:
        w[1]=1
    elif i==0 and 1 in d:
        w[1]=0
    if i==0 and 2 not in d:
        w[2]=1
    elif i==0 and 2 in d:
        w[2]=0
    if i>0:
        if i+1 not in d:
            w[i+1]=(w[i+1]+w[i])%mod
        if i+2 not in d:
            w[i+2]=w[i]
print(w[-2]%mod)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000000)

def dfs(x):
  if x == N:
    return 1
  if x > N:
    return 0
  if memo[x] >= 0:
    return memo[x]
  memo[x] = dfs(x+1) + dfs(x+2)
  return memo[x]

N, M = map(lambda x: int(x), input().split())
a = [int(input()) for i in range(M)]
#print(N)
#print(M)
#print(a)
memo = [-1]*(N+1)
for ai in a:
  memo[ai] = 0
count = dfs(0)
print(count%1000000007)

Submission status: Accepted

Solution code:
# coding:utf-8

import math

base = 1000000007

def main():
    n,m = map(int,raw_input().split())
    ms = []
    for i in range(m):
        ms.append(int(raw_input()))
    prev = -1
    for i in ms:
        if i - prev <= 1:
            print 0
            return
        prev = i
    prev = 0
    fib = 1
    fib1 = 0
    fib2 = 1
    cur = 0
    total = 1
    for i in range(0,n+1):
        if len(ms) > cur:
            curM = ms[cur]
            if i < curM:
                if cur >= 1 and i == ms[cur-1]:
                    continue
                fib = fib1 + fib2
                fib1 = fib2
                fib2 = fib
            else:
                total = (total * fib1) % base
                fib = 1
                fib1 = 0
                fib2 = 1
                cur += 1
        else:
            if cur >= 1 and i == ms[cur-1]:
                continue
            if i != n:
                fib = fib1 + fib2
                fib1 = fib2
                fib2 = fib
            else:
                total = (total * fib) % base
    print total

if __name__ == "__main__":
    main()

Submission status: Accepted

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

for i in a:
    res_arr[i] = 0

for i in range(1, n):
    if res_arr[i] == 0:
        next
    elif i == 1:
        res_arr[i] = 1
    elif i == 2:
        res_arr[i] = 1 + res_arr[i-1]
    else:
        res_arr[i] = res_arr[i-1] + res_arr[i-2]

if n == 1:
    res = 1
elif n == 2:
    res = 1 + res_arr[1]
else:
    res = res_arr[-1]+res_arr[-2]
amari = res % 1000000007
print(amari)

Submission status: Accepted

Solution code:
def fib(n):
    a,b = 0,1
    for i in range(n):
        a, b = b, a+b
    return int(b)

N, M = map(int,input().split())

if M == 0:
    print(fib(N) % (10**9 + 7))
    exit()

A = [int(input()) for _ in range(M)]
L = [0] * (M+1)

ans = 1

L[0] = fib(A[0]-1) % (10**9 + 7)
L[M] = fib(N-(A[M-1]+1)) % (10**9 + 7)

for i in range(1,M):
    if A[i]-A[i-1] == 1:
        print(0)
        exit()
    L[i] = fib((A[i]-1)-(A[i-1]+1)) % (10**9 + 7)

for j in range(M+1):
    ans = (ans * L[j]) % (10**9 + 7)

print(ans)

Submission status: Accepted

Solution code:
def resolve():
    (N, M) = list(map(int, input().split(" ")))
    As = [int(input()) for i in range(M)]
    As.sort()

    cnts = [False] * (N+1)
    ptr = 0
    for i in range(N+1):
        c = 0
        if ptr < len(As) and i == As[ptr]:
            c = 0
            ptr = ptr + 1
        elif i == 0:
            c = 1
        elif i == 1:
            c = 1
        elif i == 2:
            c = 2 if 1 not in As else 1
        else:
            c = (cnts[i-2] + cnts[i-1])%1000000007
        cnts[i] = c

    print(cnts[N])

if '__main__' == __name__:
    resolve()

Submission status: Accepted

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

a = 1
b = 1

i = 2

for j in range(m):
  ind = int(input())
  if ind == 1:
    b = 0
    continue
  while i < ind:
    a, b = b, a+b
    i += 1
  else:
    a, b = b, 0
    i += 1
    
while i < n+1:
  a, b = b, a+b
  i += 1
  
  
print(b%1000000007)

Submission status: Accepted

Solution code:
from collections import Counter

N,M = map(int,input().split())
a = [0]*M
for i in range(M):
    a[i] = int(input())

c = Counter(a).keys()

b = [(-1 if x in c else 0) for x in range(N+1)]

b[0] = 1

mod = 10**9+7
for i in range(1,N+1):
    if b[i] == -1:
        continue
    if i == 1:
        b[i] = b[0]
    else:
        b[i] = max(b[i-1],0) + max(b[i-2],0)
    b[i] %= mod

print(b[N])

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

N,M = map(int,input().split())
if M == 0:
  P = Fib(N+2)
  print(P%1000000007)
else:
  S = []
  for _ in range(M):
    S.append(int(input()))
  S.append(-1)
  S.append(N+1)
  S.sort()  
  P = 1

  for i in range(M+1):
    P *= Fib(S[i+1]-S[i]) 

  print(P%1000000007)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)
INF = 1000000007
n,m= map(int,input().split())
a = [0]*m
for i in range(m):
    a[i] = int(input())

step = [0]*(n+10)
step[0] =1
step[1] =1
step[2] =2
for i in range(3,n+10):
    step[i] = step[i-1] + step[i-2]
if m != 0:
    l = [a[0]-1]
    for i in range(1,m):
        l.append(a[i]-a[i-1]-2)
    l.append(n-a[m-1]-1)

    ans = 1

    for i in range(m+1):
        if l[i] < 0:
            ans = 0
            break
        ans = ans*step[l[i]]
        if ans >= INF:
            ans = ans % INF
if m == 0:
    ans = step[n] % INF
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = []
for i in range(M):
    a = int(input())
    A.append(a)
def step(n):
    steps = [0 for i in range(n + 1)]
    ind = 0
    steps[0] = 1
    steps[1] = 1
    if M != 0:
        if 1 == A[ind]:
            steps[1] = 0
            if ind < M-1:
                ind += 1
    for i in range(2, n + 1):
        steps[i] = steps[i - 1] + steps[i - 2]
        if M != 0:
            if i == A[ind]:
                steps[i] = 0
                if ind < M-1:
                    ind += 1
    return steps[n] % 1000000007
print(step(N))

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
li = [int(input()) for i in range(m)]
p = 1000000007
ans = 0

steps = [0]*(max(10,n+1))
steps[1] = 1
steps[2] = 2
for i in range(3,n+1):
  steps[i] = (steps[i-1] + steps[i-2])%p
if m == 0:
  print(steps[n])
else:
  if li[0] == 1:
    ans += 1
  else:
    ans += steps[li[0]-1]%p

  for i in range(m-1):
    if li[i+1] == li[i]:
      continue
    elif li[i+1] - li[i] == 1:
      ans = 0
    elif li[i+1] - li[i] == 2:
      continue
    else:
      ans *= steps[li[i+1]-li[i]-2]
      ans %= p

  if li[m-1] == n-1: 
    print(ans)
  else:
    print((ans*steps[n-li[m-1]-1])%p)

Submission status: Accepted

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

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

dp[0] = 1
# 一段目確定
if ngs[1]:
    # 一通りだけ
    dp[1] = 1

for i in range(2, n+1):
    if ngs[i] == False:
        # たどりついてはいけない
        dp[i] = 0
    else:
        dp[i] = dp[i-1] + dp[i-2]
print(dp[n] % 1000000007)

Submission status: Accepted

Solution code:

import sys
imput =sys.stdin.readline

p = 10**9 + 7

N,M =map(int,input().split())
lis = [0]*N

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


if lis[0]!=-1:
    lis[0] =1
if N != 1:
    if lis[1]!=-1:
        lis[1] =1 + max(0,lis[0])

for i in range(N-2):
    i += 2
    if lis[i]!=-1:
        lis[i]= (max(0,lis[i-1])+max(0,lis[i-2]))%p

print(max(0,lis[-1]))

Submission status: Accepted

Solution code:
def fibon(n):
    a, b = 0, 1
    while n>=0:
        if n==0:return a
        b += a
        n -= 1
        if n==0: return b
        a += b
        n -= 1

n, m = map(int, input().split())
a = [-1] + [int(input()) for i in range(m)] + [n+1]
ans = 1
for i in range(m+1):
    ans *= fibon(a[i+1]-a[i]-1)
print(ans%1000000007)

Submission status: Accepted

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

for i in range(m):
#    s = input()
    an[i] = int( input() )
#an[-1] = n

#an.sort()
disjoint = False
for i in range(len(an)-1):
    if an[i] + 1 == an[i+1]:
        disjoint = True


if disjoint:
    print(0)

else:

    mod = 10**9+7
    tab = [0]*(10**5+10)
    tab[0] = 0
    tab[1] = tab[2]= 1

    for i in range(3, len(tab)):
        tab[i] = tab[i-1]+tab[i-2]
#        if i<100:
#            print(tab[i])

    an.append(n)
    prev = 0
    ans = 1
    for a in an:
        index = a-prev + (1 if a == n else 0)
#        print(a,prev,index,tab[index])
        ans *= tab[index]
        ans %= mod
        prev = a+1

    #ans *= tab[n - prev]
    #ans %= 1000000007

    print(ans)

Submission status: Accepted

Solution code:
number = 1000000007
fib = [1,1,2,3,5,8,13]
def fibon(n):
  if(n+1> len(fib)):
    while(len(fib) < n+1):
      fib.append(fib[-1]+ fib[-2])
  return fib[n]
n,m = map(int,input().split())
start = 0
ans = 1
for i in range(m):
  broken = int(input())
  if broken - start == 0:
    print(0)
    exit(0)
  ans *= fibon(broken-start-1)
  ans = ans % number
  start = broken + 1
else:
  ans *= fibon(n-start)
  ans = ans % number
print(ans)

Submission status: Accepted

Solution code:
def fb(num):
    """num番目のフィボナッチ数を返す
    """
    a, b = 1, 0
    for _ in range(num):
        a, b = a + b, a
    return b

import functools
import operator

import sys
n, m = map(int, input().split())
a = sorted(list(set(map(int, sys.stdin.readlines()))))
m = len(a)

s = 0
e = n
xs = [0] * (m + 1)
for i, j in enumerate(a):
  xs[i] = fb(j - s)
  s = j + 1
xs[m] = fb(n - s + 1)
if 0 in xs:
  print(0)
else:
  result = functools.reduce(operator.mul, xs)
  print(result % 1000000007)

Submission status: Accepted

Solution code:
N,M = list(map(int,input().split()))
a = [int(input()) for i in range(M)]
dekai = 1000000007
"""
import sympy as sym

def Fib(n):
	x = sym.symbols('x',nonnegative=True,integer=True)
	Fib=1/sym.sqrt(5)*(((1+sym.sqrt(5))/2)**(n-1)-((1-sym.sqrt(5))/2)**(n-1))
	result=Fib.subs(x,n)
	result=result.evalf(int(n*3/14)+1)
	return int(result)


"""
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
ans = 1

if M == 0:
	print(Fib(N+1-(-1))%dekai)
	exit()

for i in range(M+1):
	if i == 0:
		ans = (ans*(Fib(a[0]-(-1))%dekai))%dekai
	elif i == M:
		ans = (ans*(Fib(N+1-a[M-1])%dekai))%dekai
	else:
		ans = (ans*(Fib(a[i]-a[i-1])%dekai))%dekai
print(ans)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

n, m = map(int, input().split())
a_list = []
comb_list = [0, 1, 2, 3]
n_2, n_1 = 2, 3
for i in range(3, n):
    n_2, n_1 = n_1, (n_2+n_1)%(10**9+7)
    comb_list.append(n_1)
for _ in range(m):
    a = int(input())
    a_list.append(a)
start = 0
ans = 1
if m == 0:
    ans = comb_list[n]
else:
    for a in a_list+[n+1]:
        if a == 1:
            start = a + 1
            continue
        else:
            if start == a:
                ans = 0
                break
            elif start == a - 1:
                start = a + 1
            else:
                tmp = a - start - 1
                ans = (ans * comb_list[tmp])%(10**9+7)
                if a == n-1:
                    break
                else:
                    start = a + 1
print(ans)

Submission status: Accepted

Solution code:
import math
def cmb(n, r, mod, g1, g2):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

def main():
    N, M = map(int, input().split())
    A = [-1] + [int(input()) for i in range(M)] + [N + 1]

    mod = 10**9+7 #出力の制限
    N = 10**5
    g1 = [1, 1] # 元テーブル
    g2 = [1, 1] #逆元テーブル
    inverse = [0, 1] #逆元テーブル計算用テーブル
    for i in range( 2, N + 1 ):
        g1.append( ( g1[-1] * i ) % mod )
        inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
        g2.append( (g2[-1] * inverse[-1]) % mod )

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

    ans = 1
    for dd in d:
        if dd > 1:
            tmp = 0
            for j in range(dd//2 + 1):
                tmp += cmb(dd - j, j, mod, g1, g2)
            ans *= tmp

    print(ans % 1000000007)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

import sys


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



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

## 散弾未満の時
if n == 1:
    if not steps[1]:
        print(0)
    else:
        print(1)
    exit()
elif n == 2:
    if not steps[2]:
        print(0)
        exit()
    else:
        if not steps[1]:
            print(1)
        else:
            print(2)
        exit()


ans = 1

l = 0
r = 0
idx = 0
finished = 2
while l < len(steps):

    if idx >= len(steps):
        if r-l > finished:
            for i in range(finished+1, r-l+1):
                dp[i] = dp[i-2] + dp[i-1]
                finished = i
        ans *= dp[r-l]
        break

    if steps[idx]:
        r = idx
    else:
        # idx段目が壊れてる
        #次も壊れてるなら終わり
        if steps[idx+1] == False:
            print(0)
            exit()
        else: 
            if r-l > finished:
                for i in range(finished+1, r-l+1):
                    dp[i] = dp[i-2] + dp[i-1]
                    finished = i
            ans *= dp[r-l]
            l = idx+1
            r = idx+1
    idx += 1

print(ans%(10**9+7))

Submission status: Accepted

Solution code:
n, m = list(map(int, input().split()))
if m > 0:
  a = set([int(input()) for i in range(m)])
else:
  a = set([])

if n == 1:
  pat = 1
else:
  pt = [1]
  if (1 in a):
    pt.append(0)
  else:
    pt.append(1)

  for i in range(2, n + 1):
    if (i in a):
      pt.append(0)
    else:
      if (i-1 in a):
        pt.append(pt[i-2])
      else:
        pt.append(pt[i-1] + pt[i-2])

  pat = (pt[-1] % 1000000007)
print(pat)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
n, m = map(int, input().split())
a = []
for _ in range(m):
    _a = int(input())
    try:
        if _a == a[-1]:
            continue
    except:
        pass
    a.append(_a)
a.append(n + 1)
m = len(a)

memo = {0: 1, 1: 1, 2: 2}
def chk(n):
    if n in memo:
        return memo[n]
    else:
        make(n)
        return memo[n]

def make(n):
    if n in memo:
        return
    make(n - 1)
    make(n - 2)
    memo[n] = (memo[n-1] + memo[n-2]) % 1000000007

for i in range(m - 1):
    if a[i] + 1 == a[i + 1]:
        print(0)
        exit()

cur = 0
tot = 1
#from sys import stderr
#for k in range(100):
#    print(f'0-{k}: {chk(k)}', file=stderr)

for i in range(m):
    nxt = a[i] - 1
    add = chk(nxt - cur)
    #print(f'{cur}-{nxt}: {add}', file=stderr)
    tot *= add
    tot %= 1000000007
    cur = nxt + 2
print(tot % 1000000007)

Submission status: Accepted

Solution code:
n, m = map(int,input().split())
dangerList = [int(input()) for i in range(m)]
answerList = [0] * (n+2)
answerList[0] = 1
nextDanger = n + 2
if len(dangerList) > 0:
  nextDanger = dangerList.pop(0)
for i in range(n):
  if i == nextDanger:
    if len(dangerList) > 0:
    	nextDanger = dangerList.pop(0)
  else:
    answerList[i+1] = (answerList[i+1] + answerList[i]) % 1000000007
    answerList[i+2] = (answerList[i+2] + answerList[i]) % 1000000007
print(answerList[n])

Submission status: Accepted

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

inf=1000000007

l=[1,1]
for i in range(n+2):
    l.append((l[i]+l[i+1])%inf)



if m!=0:
    k=[a[0]]
    for i in range(m-1):
        k.append(a[i+1]-a[i]-1)
    k.append(n-a[m-1])

    flag=True
    for i in range(1,len(k)):
       if k[i]==0:
            flag=False
    ans=1

    for j in range(len(k)):
        ans=(ans*l[k[j]-1])%inf

    if flag:
        print(ans%inf)
    else:
        print(0)
else:
    print(l[n])

Submission status: Accepted

Solution code:
import sys

fin = sys.stdin.readline

MOD = 10 ** 9 + 7
N, M = [int(elem) for elem in fin().split()]
a_list = set([int(fin()) for _ in range(M)])


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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
def Fib(num):
    """num番目のフィボナッチ数を返す
    """
    a, b = 1, 0
    for _ in range(num):
        a, b = a + b, a
    return b

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

before = 0
total = 1
flag = False
for a in a_i:
    if a == before:
        flag = True
        break
    x = a - 1 - before
    fib = Fib(x+1)
    total = total*fib
    before = a + 1
if flag:
    print("0")
else:
    x = n - before
    total = total*Fib(x+1)
    print(total%1000000007)

Submission status: Accepted

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

if m > 0:
    for i in range(1, n + 1):
        if i == a[j]:
            dp[i] = 0
            if j != m - 1:
                j += 1
        elif i >= 2:
            dp[i] = (dp[i - 1] + dp[i - 2]) % mod
        else:
            dp[i] = dp[i - 1] % mod
else:
    for i in range(1, n + 1):
        if i >= 2:
            dp[i] = (dp[i - 1] + dp[i - 2]) % mod
        else:
            dp[i] = dp[i - 1] % mod
print(dp[n])

Submission status: Accepted

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

b = 0
for i in range(m-1):
    if a[i+1] - a[i] == 1:
        b = 1
if b == 1:
    print(0)
else:
    kaidan = [1,2]
    for i in range(2,n):
        kaidan.append(kaidan[i-1]+kaidan[i-2])
    kaidan = [0] + kaidan

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

Submission status: Accepted

Solution code:
#N = int(input())
INF = 1000000007
N,M = map(int,input().split())
a_list = [-1]
for i in range(M):
    a_list.append(int(input()))
a_list.append(N+1)
a_list.sort()
sa_list = []
for i in range(1,M+2):
    sa_list.append(a_list[i]-a_list[i-1])

#def fibonacci(n):
#    if (n<=1):
#        return (n)
#    else:
#        return(fibonacci(n-1) + fibonacci(n-2))
n=max(sa_list)+2
fib_list = []

a, b = 0, 1
for i in range(n):
    fib_list.append(a)
    a, b = b, a + b

#fib_list = [i for i in fib(n)]
#for i in range(n-1):
#    fib_list.append(fibonacci(i))
ans = 1
for sa_i in range(len(sa_list)):
    sa = sa_list[sa_i]
#    print(sa)
    ans = ans*fib_list[sa-1]
    ans = ans % INF
print(ans)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
N, M = map(int, input().strip().split())
F = [0, 1]


def fib(n):
  for i in range(len(F), n + 1):
    F.append((F[i - 1] + F[i - 2]) % MOD)

  return F[n]


total = 1
b = 0
for _ in range(M):
  #print('')
  a = int(input().strip())
  if a == b:
    total = 0
    break
  f = fib(a - b)
  #print('f = {}, total = {}'.format(f, total))
  total = total * f % MOD
  #print('f = {}, total = {}'.format(f, total))
  b = a + 1
else:
  f = fib(N - b + 1)
  total = total * f % MOD

print(total)

Submission status: Accepted

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

Submission status: Accepted

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

fib_l = [-1] * (n+3)

def make_fib(n):
    fib_l[0] = fib_l[1] = 1
    for i in range(2, n):
        fib_l[i] = fib_l[i-1] + fib_l[i-2]

make_fib(n+3)
ret = 1
for i in range(m+1):
    t = a[i+1] - a[i] - 2
    if t < 0:
        ret = 0
        break
    ret *= fib_l[t]
print(ret % 1000000007)

Submission status: Accepted

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

MOD = 1000000007  # type: int

def solve(N: int, M: int, a: "List[int]"):
    i = 2
    arr = [1, 1]
    seek = 0
    while seek < len(a) and a[seek]==1:
        arr[1] = 0
        seek+=1
    while i<=N:
        if seek < len(a) and i == a[seek]:
            arr[0], arr[1] = arr[1], 0
            seek+=1
        else:
            arr[0], arr[1] = arr[1], (arr[0]+arr[1])%MOD
        i+=1
    print(arr[1])

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [ int(next(tokens)) for _ in range(M) ]  # type: "List[int]"
    solve(N, M, a)

if __name__ == '__main__':
    main()

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
    
N, M = map(int, input().split())
a = [-1]
for i in range(M):
    a.append(int(input()))
    
for i in range(M-1):
    if a[i+1] == (a[i] + 1):
        print(0)
        exit()
    
combi = 1

for i in range(len(a)-1):
    dis = a[i+1] - a[i]
    #print(dis)
    combi *= fib(dis)
    #print(a[i])
    
dis = N+1 - a[-1]
#print(dis)
combi *= fib(dis)

print(combi % 1000000007)

Submission status: Accepted

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

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



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

for i in range(M):
    memo[a[i]] = 0


for i in range(1,N+1):
    if i == 1 and memo[i] == -1:
        memo[i] = memo[i-1]
    elif memo[i] >= 0:
       memo[i] = 0
        ## memo[i] i 番目の階段にいくまでのルート数
    else:
          memo[i] = memo[i-1] +memo[i-2]


print(memo[N] % 1000000007)