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(4100000)
n,m = [int(i) for i in input().split()]
a = {int(input()) for i in range(m)}
dp = {}
def stairs(step):
  if step in a:
    return 0
  if step == 1:
    return 1
  if step == 2:
    return stairs(step-1) + 1
  if step in dp.keys():
    return dp[step]
  else:
    dp[step] = stairs(step-1) + stairs(step-2)
    return dp[step]
print(int(stairs(n)%1000000007))

Submission status: Accepted

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

MOD = 1000000007

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

broken_step = []
p_a = -1
for i in range(M):
    a = int(input())
    if (a - p_a == 1):
        print("0")
        exit()
    else:
        p_a = a
    broken_step.append(a-1)

count_0 = 0
count_1 = 1
next_broken = 0
pre_is_broken = False
for i in range(N):
    if (next_broken >= len(broken_step) or i != broken_step[next_broken]):
        if (pre_is_broken):
            count_0 = 0
            pre_is_broken = False
        else:
            count_0, count_1 = count_1, count_0 + count_1
            count_0 %= MOD
            count_1 %= MOD
    else:
        next_broken+=1
        count_0 = 0
        pre_is_broken = True

print(count_1)

Submission status: Accepted

Solution code:
n,m = list(map(int,input().split()))
L = set(int(input()) for _ in range(m))
dp = [0]*(n+1)
mod = 10**9+7
dp[0] = 1
for i in range(n):
    if i + 1 not in L:
        dp[i+1] += dp[i]
        dp[i+1] %= mod
    if i+2 not in L and i+2 < n+1 :
        dp[i+2] += dp[i]
        dp[i+2] %= mod
print(dp[n])

Submission status: Accepted

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

for i in range(n):
    if i+1 not in aa:
        l[i+1]+=l[i]
        l[i+1]=l[i+1]%mod
    if i+2 not in aa and i+2<n+1:
        l[i+2]+=l[i]
        l[i+2]=l[i+2]%mod

print(l[n])

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7

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

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

for i in range(1, N + 1):
    if broken[i]:
        continue
    if i >= 2:
        dp[i] = dp[i - 1] + dp[i - 2]
    else:
        dp[i] = dp[i - 1]
    dp[i] %= MOD
print(dp[N])

Submission status: Accepted

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

P = 10**9+7

dp = [1]*(N+1)

for a in List:
    dp[a]=0

for i in range(1, N+1):
    if (i>=2)&(dp[i]!=0):
        dp[i] = (dp[i-1]+dp[i-2])%P
        
print(dp[N])

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 next in range(1,N+1):
    if next in A:
        dp[next] = 0
    else:
        dp[next] = (dp[next-1] + dp[next-2])%1000000007

print(dp[N])

Submission status: Accepted

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

dp = [1]*(N+1)
mod = 10**9+7

for A in a:
    dp[A] = 0

for i in range(N+1):
    if i>=2 and dp[i]:
        dp[i] = (dp[i-1]+dp[i-2])%mod

print(dp[N])

Submission status: Accepted

Solution code:
maxNum, brokenCount = map(int,input().split(" "))

brokenIndexSet = set([int(input()) for i in range(brokenCount)])

ans = [0] * (maxNum + 1)
ans[0] = 1

for i in range(1,maxNum+1):
  if i in brokenIndexSet:
    ans[i] = 0
  else:
    ans[i] = (ans[i-1] + ans[i-2]) % 1000000007

print(ans[maxNum])

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

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

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

a.append(n + 1)
a.insert(0, -1)
b = [i-j-1 for i,j in zip(a[1:], a[:-1])]

mm = max(b) - 1

step = [0,1]

for i in range(mm):
	step.append(step[-1] + step[-2])

mul = 1
for i in b:
	mul *= step[i]
	
print(mul%1000000007)

Submission status: Accepted

Solution code:
def main():
	N, M = map(int, input().split())
	a = set()

	for i in range(M):
		b = int(input())
		a.add(b)

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

	MOD = 1000000007
	for i in range(3, N+1):
		if i in a:
			continue
		dp[i] = dp[i-1]+dp[i-2]
		dp[i] %= MOD
	print(dp[N])


if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
A = [int(input()) for i in range(M)]
A.append(N+1)
m=0
if A[0] != 1:
    s=[1,1]
else:
    s = [1,0]
    m = 1

for i in range(2,N+1):
    if A[m] == i:
        s.append(0)
        m += 1
    else:
        s.append(s[i-2]+s[i-1])


print(s[N]%1000000007)

Submission status: Accepted

Solution code:
maxNum, brokenCount= map(int, input().split())
brokenIndexSet= set([int(input()) for i in range(brokenCount)])

ans = [0]*(maxNum+2)

ans[maxNum] = 1

for i in reversed(range(maxNum)):
    if i in brokenIndexSet:
        ans[i] = 0
    else:
        ans[i] = (ans[i+1] + ans[i+2]) % 1000000007 

print(ans[0])

Submission status: Accepted

Solution code:
maxNum, brokenCount= map(int, input().split())

brokenIndexSet= set([int(input()) for i in range(brokenCount)])

ans = [0]*(maxNum + 1)
ans[0] = 1

#print(ans[-1])

for i in range(1, maxNum + 1):
    if i in brokenIndexSet:
        ans[i] = 0
    else:
        ans[i] = (ans[i - 1] + ans[i - 2]) % 1000000007 

print(ans[maxNum])

Submission status: Accepted

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

oks = [True]*(N+1)

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

dp = [0]*(N+1)

dp[0]=1
if oks[1]==True: dp[1] = 1

for i in range(2, N+1):
    if oks[i]==True:
        dp[i] = (dp[i-1] + dp[i-2]) % (1e9+7)

print(int(dp[N]))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
mod = 1e+9+7
flags = [True  for i in range(N+1)]
for i in range(M):
    tmp = int(input())
    flags[tmp-1] = False
dp = [0 for i in range(N+1)]
dp[0] = 1
dp[1] = 2

if not flags[0]:
    dp[0] = 0
    dp[1] = 1
if not flags[1]:
    dp[1] = 0
for i in range(2, N):
    if flags[i]:
        dp[i] = int((dp[i-1] + dp[i-2]) % mod)
print(dp[N-1])

Submission status: Accepted

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

a = 1; b = 0
for i in range(n):
    if kaidan[i]:
        a, b = 0, a
    else:
        a, b = a+b, a

mod = 10**9+7
print(a%mod)

Submission status: Accepted

Solution code:
import sys
import numpy as np
sys.setrecursionlimit(1000000)
 
N,M = map(int,input().split())
a = [int(input()) for i in range(M)]

ans = 0

now = 0

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

for i in range(M):
    #print(i)
    disable[a[i]] = 1
    

waru = 10**9+7
dp[0] = 1

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

print(dp[N])

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
MOD=10**9+7
p,q,n=0,1,1
for _ in range(M):
    a=int(input())
    while n<=a:
        p,q=q,p+q
        n+=1
    q=0
while n<=N:
    p,q=q,p+q
    n+=1

print(q%MOD)

Submission status: Accepted

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

n,m = map(int,input().split())
if n in [0,1]:
    print(1)
    sys.exit()
    
if not m == 0: lis = [int(input()) for x in range(m)]
else: lis = [-1]
val1 = 1
if 1 in lis: val2 = 0
else: val2 = 1

if lis[0] == 1 and len(lis) >= 2:
    flg = lis[1]
    nex = 1
else:
    flg = lis[0]
    nex = 0
#print(lis)
for x in range(2,n):
    if x == flg: #x in lis
        #print(flg)
        nex += 1
        try: flg = lis[nex]
        except:flg = 0
        now = 0
    else:
        now = (val1 + val2) % mod
    val1,val2 = val2,now
    
print((val1 + val2) % mod)

Submission status: Accepted

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

n,m = map(int,input().split())
if n in [0,1]:
    print(1)
    sys.exit()
    
if not m == 0: lis = [int(input()) for x in range(m)]
else: lis = [-1]
val1 = 1
if 1 in lis: val2 = 0
else: val2 = 1

if lis[0] == 1 and len(lis) >= 2:
    flg = lis[1]
    nex = 1
else:
    flg = lis[0]
    nex = 0
#print(lis)
for x in range(2,n):
    if x == flg: #x in lis
        #print(flg)
        nex += 1
        try: flg = lis[nex]
        except:flg = 0
        now = 0
    else:
        now = (val1 + val2) % mod
    val1,val2 = val2,now
    
print((val1 + val2) % mod)

Submission status: Accepted

Solution code:
import sys
n = [int(i) for i in input().split()]
a = []
for i in range(n[1]):
    a.append(int(input()))

a.append(n[0]+1)
a = sorted(list(set(a)))


def k(i):
    ans = 1
    pri = 0
    for idx in range(i):
        tmp = ans
        ans += pri
        pri = tmp
    return ans


for i in range(1, len(a)):
    if a[i]-a[i-1] == 1:
        print(0)
        sys.exit()
j = -1
ans = 1
for i in a:
    ii = i-j-2
    ans = ans*k(ii)
    j = i
if len(a) == 1:
    ans = k(n[0])
print(ans % 1000000007)

Submission status: Accepted

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

    a = 0
    b = 1
    j = 0
    tmp = 0
    if N == 1:
        print(1)
    else:
        for i in range(1, N + 1):
            if A[j] == i:
                if tmp == 1:
                    print(0)
                    exit()
                tmp = 1
                j += 1
                a = 0
            else:
                if tmp == 1:
                    b = a + b
                    a = 0
                else:
                    c = a + b
                    a = b
                    b = c
                tmp = 0
        print(b % 1000000007)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

if n+1 < 2*m:
    print(0)
else:
    a = [int(input()) for _ in range(m)]

    pre2 = 0
    pre1 = 0
    cur = 1
    a_id = 0

    for i in range(n):
        pre2 = pre1
        pre1 = cur 
        cur = pre1 + pre2
        if a_id < m:
            if i+1 == a[a_id]:
                a_id += 1 if a_id < m-1 else 0
                cur = 0
        if cur == 0 and pre1 == 0:
            break
    print(cur%1000000007)

Submission status: Accepted

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

def solve(n, m):
    dp = [0] * (n + 1)
    ai = 0
    a = -1
    dp[0] = 1
    if ai < m:
        a = int(raw_input())
    if a == 1:
        ai += 1
        if ai < m:
            a = int(raw_input())
        dp[1] = -1
    else:
        dp[1] = 1

    for i in range(2, n+1):
        if i == a:
            ai += 1
            if ai < m:
                a = int(raw_input())
            dp[i] = -1
        else:
            if dp[i-2] != -1:
                dp[i] = dp[i-2]
            if dp[i-1] != -1:
                dp[i] += dp[i-1]
    return dp[n] % (10**9+7)
print solve(n, m)

Submission status: Accepted

Solution code:
mod = 1000000007

def add(a, b):
    return (a + b) % mod

def sub(a, b):
    return (a + mod - b) % mod

def mul(a, b):
    return ((a % mod) * (b % mod)) % mod
    
a = []
N, M = map(int, input().split())
for i in range(M):
    a.append(int(input()))

def main():
  results = []

  flag = True

  for m in range(1, M):
      if a[m] - a[m - 1] == 1:
          flag = False
          break

  flag_end = True
  if M == 0:
      flag_end = False

  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

  if flag and flag_end:
      for m in range(M):
          if m == 0:
              results.append(Fib(a[m] + 1))
          else:
              results.append(Fib(a[m] - a[m - 1]))
      results.append(Fib(N - a[m] + 1))
      result = 1
      for i in range(len(results)):
          result = mul(result, results[i])
      print(result % mod)
  elif not flag:
      print(0)
  else:
      print(Fib(N + 2) % mod)

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
mod = 1000000007

def add(a, b):
    return (a + b) % mod

def sub(a, b):
    return (a + mod - b) % mod

def mul(a, b):
    return ((a % mod) * (b % mod)) % mod
    
a = []
N, M = map(int, input().split())
for i in range(M):
    a.append(int(input()))

def main():
  results = []

  flag = True

  for m in range(1, M):
      if a[m] - a[m - 1] == 1:
          flag = False
          break

  flag_end = True
  if M == 0:
      flag_end = False

  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

  if flag and flag_end:
      for m in range(M):
          if m == 0:
              results.append(Fib(a[m] + 1))
          else:
              results.append(Fib(a[m] - a[m - 1]))
      results.append(Fib(N - a[m] + 1))
      result = 1
      for i in range(len(results)):
          result = mul(result, results[i])
      print(result % mod)
  elif not flag:
      print(0)
  else:
      print(Fib(N + 2) % mod)

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
def fib(n):
    if n <= 1:
        return n
    result = [1, 0, 0, 1]
    matrix = [1, 1, 1, 0]
    while n > 0:
        if n % 2:
            result = mul(matrix, result)
        matrix = mul(matrix, matrix)
        n //= 2
    return result[2]

def mul(a, b):
    return [a[0]*b[0] + a[1]*b[2],
            a[0]*b[1] + a[1]*b[3],
            a[2]*b[0] + a[3]*b[2],
            a[2]*b[1] + a[3]*b[3]]

n, m = [int(i) for i in input().split()]
a = []
frag = 1
ans = 0
step = []
for i in range(m):
    a.append(int(input()))
for i in range(m-1):
    if(a[i]+1 == a[i+1]):
        frag = 0
if(frag == 0):
    ans = 0
else:
    ans = 1
    sirusi = 0
    for i in range(len(a)):
        step.append(a[i] - 1 - sirusi)
        sirusi = a[i] + 1
    step.append(n - sirusi)
    for i in range(len(step)):
        ans = ans * fib(step[i]+1)
    ans = ans % 1000000007
print(ans)

Submission status: Accepted

Solution code:
import math
import fractions
import copy
#以下てんぷら
def j(q):
    if q==1: print("YES")
    elif q == 0:print("NO")
    exit(0)
rem = pow(10,9)+7
"""
def ct(x,y):
    if (x>y):print("+")
    elif (x<y): print("-")
    else: print("?")
"""

def ip():
    return int(input())
def printrow(a):
    for i in a:
        print(i)
def combinations(n,r):
    if n<r:return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
def permutations(n,r):
    if n<r:return 0
    return math.factorial(n) // math.factorial(n - r)
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)


#n = ip()                                     #入力整数1つ
n,m= (int(i) for i in input().split())       #入力整数横2つ以上
#a = [int(i) for i in input().split()]        #入力整数配列
#a = input()                                  #入力文字列
#a = input().split()                          #入力文字配列
#n = ip()                      #入力セット(整数改行あり)(1/2)
a=[ip() for i in range(m)]    #入力セット(整数改行あり)(2/2)
#a=[input() for i in range(n)]    #入力セット(整数改行あり)(2/2)
#jの変数はしようできないので注意
#全足しにsum変数使用はsum関数使用できないので注意
#a.pop(0)は10^5あるときTLEしやすい!注意!抜くなら逆ソート!
#これを消すとなぜかWAになる呪い
for i in range(m-1):
    if a[i]+1 == a[i+1]:
        print(0)
        exit(0)
if n == 1:
    print(1)
else:
    p = 0
    dp = [0 for i in range(n+1)]
    dp[1]  = 1
    dp[2] = 2
    for i in range(3,n+1):
        dp[i] = dp[i-1]+dp[i-2]
    left = [i+1 for i in a]
    right = [i-1 for i in a]
    left.insert(0,0)
    right.append(n)
    s = 1
    for i in range(len(right)):
        if right[i] != left[i] :s*=dp[right[i]-left[i]]
    print(s%rem)

Submission status: Accepted

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

broken = [False for _ in range(N+1)]
for a in A:
    broken[a] = True
bp = [0 for _ in range(N+1)]
bp[0] = 1
for i in range(N+1):
    for j in range(1, 3):
        if i + j >= N+1:
            continue
        if not broken[i + j]:
            bp[i + j] = (bp[i+j] + bp[i]) % 1000000007
print(bp[-1])

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
broke = [ 0 for i in range(n+1) ]
for i in range(m):
  s = int(input())
  broke[s] = 1
dp = [ 0 for i in range(n+1) ]
dp[0] = 1
for i in range(n+1):
    if broke[i] == 1:
        continue
    else:
        if i-1 >= 0:
            dp[i] += dp[i-1]
        if i-2 >= 0:
            dp[i] += dp[i-2]

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

Submission status: Accepted

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

X = [0] * (N + 1)
for i in A:
  X[i] = -1

for i in range(N + 1):
  if i == 0:
    X[i] = 1
  elif i == 1:
    if X[i] == -1:
      X[i] = 0
    else:
      X[i] = 1
  else:
    if X[i] == -1:
      X[i] = 0
    else:
      X[i] = (X[i - 1] + X[i - 2]) % 1000000007

print(X[N])

Submission status: Accepted

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

print(b[n]%max_int)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
c=10**9+7
a = [-1 for _ in range(m + 1)]
for i in range(1, m+1):
    a[i] = int(input())
a =a+[n+1] 
for i in range(m+1):
    a[i]=a[i+1] - a[i]-1
b=[0 for _ in range(max(a) + 1)]
b[1]=1
for i in range(2, max(a)+1):
    b[i] = (b[i-1] + b[i-2])%c
s=1
for i in range(m+1):
    s=(s*b[a[i]])%c
print(s)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
c=10**9+7
a = [-1 for _ in range(m + 1)]
for i in range(1, m+1):
	a[i] = int(input())
a = a+[n+1] 
for i in range(m+1):
    a[i] = a[i+1] - a[i] - 1
b = [0 for _ in range(max(a) + 1)]
b[1] = 1
for i in range(2, max(a)+1):
  	b[i] = (b[i-1] + b[i-2]) % c
s = 1
for i in range(m+1):
    s=(s * b[a[i]])%c
print(s)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, M = [int(x) for x in input().split()]

dp = [1] * (N + 1)

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

if N == 1:
	print(1)
else:
	for i in range(N - 1):
		dp[i + 2] = (dp[i] + dp[i + 1]) * dp[i + 2]
	print(dp[N] % 1000000007)

Submission status: Accepted

Solution code:
N, M = [int(x) for x in input().split()]

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

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

if N == 1:
	print(ans)
else:
	for i in range(N - 1):
		dp[i + 2] = (dp[i] + dp[i + 1]) * dp[i + 2]
	print(dp[N] % 1000000007)

Submission status: Accepted

Solution code:
N, M = [int(x) for x in input().split()]

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

for i in range(M):
	a.append(int(input()))
	if i > 0:
		if a[i] - a[i - 1] == 1:
			ans = 0
			break
	dp[a[i]] = 'broken'

if ans == 0:
	print(ans)
else:
	if dp[1] != 'broken':
		dp[1] = 1

	if N == 1:
		print(ans)
	else:
		for i in range(N - 1):
			tmp = 0
			if dp[i] != 'broken':
				tmp += dp[i]
			if dp[i + 1] != 'broken':
				tmp += dp[i + 1]
			if dp[i + 2] != 'broken':
				dp[i + 2] = tmp
		print(dp[N] % 1000000007)

Submission status: Accepted

Solution code:
mod=1000000007
N,M = map(int,input().split())
dp = [-1]*(N+1)
dp[0] = 1

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

Submission status: Accepted

Solution code:
import sys
N, W = sys.stdin.readline().split()
aArr = list()
ans = 0
tmp = int(N)
MOD = 10 ** 9 + 7
aArr = set(map(int, sys.stdin))

tmp = 0
tmpB = 0
ans = 1
for i in range(int(N)):
    if (i in aArr):
        tmp = 0
    elif i < 2:
        tmp = 1
    else:
        tmp = ans
    ans = (tmp + tmpB) % MOD
    tmpB = tmp
print(ans)

Submission status: Accepted

Solution code:
st=[1,1]
for i in range(10**5+1):
  st.append((st[-1]+st[-2])%1000000007)
st.append(0)
n,m=list(map(int,input().split()))
ret=1
x=-1
for i in range(m):
  y=int(input())
  ret=(ret*st[y-x-2])%1000000007
  x=y
ret=(ret*st[n-x-1])%1000000007
print(ret)

Submission status: Accepted

Solution code:
import sys
N, W = input().split()
aArr = list()
ans = 0
tmp = int(N)
MOD = 10 ** 9 + 7
aArr = set(map(int, sys.stdin))

tmp = 0
tmpB = 0
ans = 1
for i in range(int(N)):
    if (i in aArr):
        tmp = 0
    elif i < 2:
        tmp = 1
    else:
        tmp = ans
    ans = (tmp + tmpB) % MOD
    tmpB = tmp
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
line = input().split()
N = int(line[0])
M = int(line[1])
broken = []
count = 0
step = []
def check(value):
  if count < M:
    return broken[count]==value
  else:
    return False
for i in range(M):
  a = int(input())
  broken += [a]
if check(1):
  step+=[0]
  count += 1
else:
  step +=[1]
if check(2):
  step += [0]
  count += 1
else:
  step += [1+step[0]]
for j in range(2, N):
  if check(j+1):
    step += [0]
    count += 1
  else:
    step += [step[j-2]+step[j-1]]
ans = step[N-1]%(10**9+7)
print(ans)

Submission status: Accepted

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

MOD = 10**9 + 7

dp = [1 for _ in range(N + 1)]
#print(dp)
for A in a:
    dp[A] = 0
for i in range(2, N + 1):
    if dp[i]:
        dp[i] = (dp[i - 1] + dp[i - 2]) % MOD
ans = dp[N]
print(ans)

Submission status: Accepted

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

# solve
dp = [1] * (n+1)

for i in a:
    dp[i] = 0

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

print(dp[n])

Submission status: Accepted

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

mod = 10**9+7 #出力の制限
Nmax = 10**5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

for i in range( 2, Nmax + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

def f(a, b):
  a -= 1
  b += 1
  n = abs(a-b)
  r = int(n/2)
  if r == 0: return 1
  n = r if n % 2 == 0 else r + 1
  ret = 0
  while r > 0:
    ret += cmb(n, r, mod)
    r -= 1
    n += 1

  ret += 1
  return ret

result = 0
if M == 0:
  result = f(N+1, -1) % mod
else:
  a0 = -1
  a1 = a.pop(0)
  while len(a) > 0:
    if a1 - a0 <= 1 and a0 != -1:
      result = 0
      break

    if result == 0:
      result += f(a1, a0)
    else:
      result *= f(a1, a0)
      result %= mod
    a0 = a1
    a1 = a.pop(0)

  if a1 - a0 <= 1 and a0 != -1:
    result = 0
  else:
    if result == 0:
      result += f(a1, a0)
    else:
      result *= f(a1, a0)
      result %= mod
    a0 = a1
    a1 = N+1
    result *= f(a1, a0)
    result %= mod

print(result)

Submission status: Accepted

Solution code:
MOD = 1000000007
def solve(n, m, a):
    a = set(a)
    dp = [0] * (n+1)
    dp[n] = 1
    for i in range(n-1, -1, -1):
        for d in range(1, 3):
            j = i + d
            if (j <= n) and (not j in a):
                dp[i] = (dp[i] + dp[j]) % MOD
    return dp[0]

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
from functools import reduce
import sys
MOD = 1000000007
def culc(min, max):
	if max - min <= 1:
		return 0
	num = max - min - 3
	x = [0, 1]
	y = x[0] + x[1]
	for i in range(num):
		x[i%2] = y
		y = (x[0] + x[1]) % MOD
	return y

n, m = map(int, input().split())
a = [-1]
for i in range(m):
	a.append(int(input()))
a.append(n + 1)
res = []
for i in range(m + 1):
	res.append(culc(a[i], a[i + 1]))
	if(res[i] <= 0):
		print(0)
		sys.exit()
print(reduce(lambda x, y: (x * y) % MOD, res))

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
if M != 0:
    chk = int(input())
else :
    chk = 0
ans1 = 1
count = 0
if chk == 1:
    ans2 = 0
    if M != 1:
        chk = int(input())
    count += 1
else:
    ans2 = 1
for i in range(N-1):
    if chk == i+2:
        ans1 = ans2
        ans2 = 0
        count += 1
        if count != M:
            chk = int(input())
    else:
        tempo = ans2
        ans2 = ans1 + ans2
        ans1 = tempo
print(ans2%1000000007)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2 * (10 ** 5 ))

input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''
N, M = map(int, input().split())
mod = 10 ** 9 + 7
a = [0] * M
memo = [-1] * (N + 1)

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

def step(n):
	if memo[n] >= 0:
		return memo[n]
	elif n < 2:
		memo[n] = 1
		return 1
	else:
		memo[n] = (step(n - 1) + step(n - 2)) % mod
		return memo[n]
			
for i in a:
	memo[i] = 0
	
print(step(N))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''

N, M = map(int, input().split())
mod = 10 ** 9 + 7
a = [0] * M
dp = [0] * (N + 2)
dp[0] = 1
dp[1] = 1

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

for i in a:
	next = i
	for j in range(now + 1, next + 1):
		if j == i:
			dp[i] = 0
		else:
			dp[j] = (dp[j - 1] + dp[j - 2]) % mod
	
	now = next

next = N
for j in range(now + 1, next + 1):
		dp[j] = (dp[j - 1] + dp[j - 2]) % mod
print(dp[N])

Submission status: Accepted

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

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

Submission status: Accepted

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

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

Submission status: Accepted

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

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:

dp = {0:1, -1:0}

def count_valiation(steps):
    
    if steps in dp:
        return dp[steps]
    
    for i in range(1,steps + 1):
        dp[i] = dp[i-1] + dp[i-2]
    
    return dp[steps]
    
    
    
def main():
    
    n, m = [int(x) for x in input().rstrip(" ").split(" ")]
    
    current = 0
    
    answer = 1
    
    for i in range(m):
        broken_step = int(input().rstrip(" "))
        
        normal_steps = (broken_step - 1 )- current
        #print(normal_steps)
        if normal_steps < 0:
            answer = 0
            break
        answer = (answer * count_valiation(normal_steps)) % 1000000007
        
        current = broken_step + 1
    
    if current < n and answer >= 1:
        normal_steps = n - current
        #print(normal_steps)
        answer = (answer * count_valiation(normal_steps)) % 1000000007
    
    
    print(answer)    
    
if __name__ == '__main__':
    main()