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 .

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')


def A():
    a,b,c = LI()
    ans = 10 ** 5
    ans = min(ans, a + b)
    ans = min(ans, a + c)
    ans = min(ans, c + b)
    print(ans)
    return


def B():
    n = II()
    w = LI()
    ans = inf
    for i in range(n):
        ans = min(ans, abs(sum(w[:i]) - sum(w[i:])))
    print(ans)
    return


def C():
    n, m = LI()
    a = IR(m)+[inf]
    dp = [0] * (n + 3)
    dp[0] = 1
    for i in range(n + 1):
        if a[bisect_left(a, i + 1)] != i + 1:
            dp[i + 1] += dp[i] % mod
        if a[bisect_left(a, i + 2)] != i + 2:
            dp[i + 2] += dp[i] % mod
    print(dp[n] % mod)
    return


def D():
    return



if __name__ == '__main__':
    C()

Solution (Python):
n,m = map(int,input().split())
a = list(int(input()) for i in range(m))

mod = 1000000007
b = [0]*(m + 1)
if m != 0:
    b[0] = a[0] - 1
    b[m] = n - a[m - 1] - 1
else:
    b[0] = n

for i in range(1,m):
    b[i] = a[i] - a[i-1] - 2

b.sort()
ans = 1
if b[0] == -1:
    ans = 0
else:
    pattern = [0]*(max(b[m]+1,2))
    pattern[0] = 1
    pattern[1] = 1
    for i in range(2,b[m]+1):
        pattern[i] = pattern[i-1] + pattern[i-2]
    for i in range(m + 1):
        ans *= pattern[b[i]]

print(ans % mod)

Solution (Python):


import sys
import array
import base64
import zlib

P_NUM = 1000000007


code = b'c$^g2S3nI88^`f;I(v`K?(DtyPBPP?kd}%vqfk~FlvSiuBveK!i6lf>5t5?FtVmf|X`qC7|L?`;@_YGQ{2m|x0092S;Xk1NK>h>&59UAQ|M34~`A^V)vi|e&KO6oFBK`|H{|j88000dM0L;My0MQHppk59DXr=-HgDU|5ZZ!Zv5CH+Y4j^FCKL^0-b}*p&ISe2@iw3;hNdiDzc!1Y;On_c+0O0PuU4SzW-vBloS_PD?@^dJ{-Uc;qq(h@Kx)4_MPh81?r}UR4EwY5QNO+)AyY5le8=LSoPdiYyOpUoQ$R9p@gA58kXB{$k5Wn6Z!gYi1^IO{L^v5wn^c55;fh<HQ5?5^lWbe&XU?3!AUMq}Qh)h8nJJO^N-y%$ZzmM=5aZ8-)?6-iao(h)RwtjX4BpHBCU&(39>gPP0c?)


def solv(n, m, a):
    by1 = base64.b85decode(code)
    by2 = zlib.decompress(by1)
    no_hole2 = array.array('I')
    no_hole2.frombytes(by2)

    ans = 1
    start = 0
    for broken in a:
        dist = broken-1-start
        if dist < 0:
            return 0
        ans *= no_hole2[dist] % P_NUM
        start = broken+1

    dist = n-start
    if dist < 0:
        return 0
    ans *= no_hole2[dist] % P_NUM

    return ans % P_NUM


if __name__ == '__main__':

    n, m = map(int, input().split())
    a = map(int, sys.stdin)

    ans = solv(n, m, a)

    print(ans)

Solution (Python):


import sys

P_NUM = 1000000007


def solv(n, m, a):
    no_hole = [1] * (n+1)
    for i in range(2, n+1):
        no_hole[i] = no_hole[i-1] + no_hole[i-2]

    ans = 1
    start = 0
    for broken in a:
        dist = broken-1-start
        if dist < 0:
            return 0
        ans *= no_hole[dist] % P_NUM
        start = broken+1

    dist = n-start
    if dist < 0:
        return 0
    ans *= no_hole[dist] % P_NUM

    return ans % P_NUM


if __name__ == '__main__':

    n, m = map(int, input().split())
    a = map(int, sys.stdin)

    ans = solv(n, m, a)

    print(ans)

Solution (Python):


P_NUM = 1000000007


def solv(n, m, a):
    no_hole = [1] * (n+1)
    for i in range(2, n+1):
        no_hole[i] = no_hole[i-1] + no_hole[i-2]

    ans = 1
    start = 0
    for broken in a:
        dist = broken-1-start
        if dist < 0:
            return 0
        ans *= no_hole[dist] % P_NUM
        start = broken+1

    dist = n-start
    if dist < 0:
        return 0
    ans *= no_hole[dist] % P_NUM

    return ans % P_NUM


if __name__ == '__main__':

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

    ans = solv(n, m, a)

    print(ans)

Solution (Python):


P_NUM = 1000000007


def solv(n, m, a):
    start = 0
    dists = []
    max_dist = 0
    for broken in a:
        dist = broken-1-start
        if dist < 0:
            return 0
        elif dist > max_dist:
            max_dist = dist
        dists.append(dist)
        start = broken+1
    dist = n-start
    if dist < 0:
        return 0
    elif dist > max_dist:
        max_dist = dist
    dists.append(dist)

    no_hole = [1] * (max_dist+1)
    for i in range(2, max_dist+1):
        no_hole[i] = no_hole[i-1] + no_hole[i-2]

    ans = 1
    for dist in dists:
        ans = (ans * no_hole[dist]) % P_NUM

    return ans


if __name__ == '__main__':

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

    ans = solv(n, m, a)

    print(ans)

Solution (Python):


import sys

P_NUM = 1000000007


def solv(n, m, a):
    comb_m2 = 1
    if 1 in a:
        comb_m1 = 0
    else:
        comb_m1 = 1

    for i in range(2, n+1):
        if i in a:
            comb_m1, comb_m2 = 0, comb_m1
        else:
            comb_m1, comb_m2 = (comb_m1 + comb_m2) % P_NUM, comb_m1

    return comb_m1


if __name__ == '__main__':

    n, m = map(int, input().split())
    if m:
        a = set(map(int, sys.stdin))
    else:
        a = set()

    ans = solv(n, m, a)

    print(ans)

Solution (Python):


import sys

P_NUM = 1000000007


def solv(n, m, a):
    comb_m2 = 1
    if 1 in a:
        comb_m1 = 0
    else:
        comb_m1 = 1

    comb = 1
    for i in range(2, n+1):
        if i in a:
            comb = 0
            a.remove(i)
        else:
            comb = (comb_m1 + comb_m2) % P_NUM

        comb_m1, comb_m2 = comb, comb_m1

    return comb


if __name__ == '__main__':

    n, m = map(int, input().split())
    if m:
        a = set(map(int, sys.stdin))
    else:
        a = set()

    ans = solv(n, m, a)

    print(ans)

Solution (Python):


import sys

P_NUM = 1000000007


def solv(n, m, a):
    comb_m2 = 1
    if 1 in a:
        comb_m1 = 0
    else:
        comb_m1 = 1

    comb = 1
    for i in range(2, n+1):
        if i in a:
            comb = 0
        else:
            comb = (comb_m1 + comb_m2) % P_NUM

        comb_m1, comb_m2 = comb, comb_m1

    return comb


if __name__ == '__main__':

    n, m = map(int, input().split())
    if m:
        a = set(map(int, sys.stdin))
    else:
        a = set()

    ans = solv(n, m, a)

    print(ans)

Solution (Python):


import sys

P_NUM = 1000000007


def solv(n, m, a):
    comb =  [1] * (n+1)
    for i in a:
        comb[i] = 0

    for i in range(2, n+1):
        comb[i] *= (comb[i-1] + comb[i-2]) % P_NUM

    return comb[-1]


if __name__ == '__main__':

    n, m = map(int, input().split())
    if m:
        a = map(int, sys.stdin)
    else:
        a = []

    ans = solv(n, m, a)

    print(ans)

Solution (Python):


import array


P_NUM = 1000000007


def solv(n, m, a):
    comb = array.array('I', [1] * (n+1))
    for i in a:
        comb[i] = 0

    for i in range(2, n+1):
        comb[i] *= (comb[i-1] + comb[i-2]) % P_NUM

    return comb[-1]


if __name__ == '__main__':

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

    ans = solv(n, m, a)

    print(ans)

Solution (Python):


import array


P_NUM = 1000000007


def solv(n, m, a):
    comb = array.array('I', [1] * (n+1))
    for i in a:
        comb[i] = 0

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

    return comb[-1]


if __name__ == '__main__':

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

    ans = solv(n, m, a)

    print(ans)

Solution (Python):


P_NUM = 1000000007


def solv(n, m, a):
    comb = [1] * (n+1)
    for i in a:
        comb[i] = 0

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

    return comb[-1]


if __name__ == '__main__':

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

    ans = solv(n, m, a)

    print(ans)

Solution (Python):


P_NUM = 1000000007


def solv(n, m, a):
    comb = [1] * (n+1)
    for i in a:
        comb[i] = 0

    for i in range(2, n+1):
        if comb[i] != 0:
            comb[i] = comb[i-1] + comb[i-2]

    return comb[-1]


if __name__ == '__main__':

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

    ans = solv(n, m, a)

    print(ans % P_NUM)

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

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

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

Solution (Python):


import math
from functools import lru_cache


def ncr(n, r):
    r = min(r, n - r)
    
    if n + r < 4000:
        return math.factorial(n) // math.factorial(n-r) // math.factorial(r)
    if r == 0:
        return 1
    if r == 1:
        return n
    numerator = list(range(n - r + 1, n + 1))
    denominator = list(range(1, r+1))
    for p in range(2, r + 1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p - 1, r, p):
                numerator[k - offset] //= pivot
                denominator[k] //= pivot
    result = 1
    for k in range(r):
        result *= numerator[k]
    return result



def no_hole(n):
    count = 0
    m = n // 2
    for i in range(0, m+1):
        count += ncr(n-i, i)
    return count



@lru_cache(maxsize=8192)
def no_hole2(n):
    if n <= 5:
        return (1, 1, 2, 3, 5, 8)[n]
    if n % 2:
        h = (n-1) // 2
        m1 = no_hole2(h-1)
        m0 = no_hole2(h)
        return 2 * m1 * m0 + m0 * m0
    else:
        h = n // 2
        m2 = no_hole2(h-2)
        m1 = no_hole2(h-1)
        m0 = no_hole2(h)
        return m1 * m1 + m2 * m0 + m1 * m0


def solv(n, m, a):
    ans = 1
    current_pos = 0
    for pos in a:
        dist = pos - 1 - current_pos
        if dist < 0:
            return 0
        ans *= no_hole2(dist)
        current_pos = pos + 1
    dist = n - current_pos
    ans *= no_hole2(dist)
    return ans


if __name__ == '__main__':

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

    ans = solv(n, m, a)

    P_NUM = 1000000007
    print(ans % P_NUM)

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

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

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

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

print(r[n])

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

dparr=[[0,False] for i in range(n+1)]
b=[0 for i in range (n+1)]
adash=[0 for i in range(n+1)]
i=0
while(i<m):
	k=int(input())
	adash[k]=1
	i+=1
s=0
i=n
while(i>=0):
	if(adash[i]==1):
		b[i]=0
	else:
		if(i==n):
			b[i]=1
		elif(i==n-1):
			b[i]=1
		else:
			b[i]=(b[i+1]+b[i+2])%1000000007

	i-=1
print(b[0])

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

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

MAX_N = int(1e5) + 10
memo = [0 for i in range(MAX_N + 10)]
memo[0] = 1
memo[1] = 1
memo[2] = 2
for i in range(3, MAX_N + 10):
    memo[i] = memo[i - 1] + memo[i - 2]

now = 0
ans = 1

for a in A:
    diff = a - now - 1
    ans *= memo[diff]
    ans %= int(1e9 + 7)
    now = a + 1

diff = N - now
ans *= memo[diff]
ans %= int(1e9 + 7)
print(ans)

Solution (Python):
import sys
N,M = map(int,input().split(' '))
A = set([int(sys.stdin.readline()) for _ in range(M)])
dp = [0]*(N+1)
dp[0] = 1
dp[1] = 0 if 1 in A else 1

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

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

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

for i in range(m):
    broken[int(input())] = 1

dp[0] = 1

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

if n == 1:
    print(dp[n])
    exit()
else:
    for i in range(2, n+1):
        if broken[i] == 1:
            continue
        else:
            dp[i] = (dp[i-1] + dp[i-2]) % 1000000007
            
print(dp[n])

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

dp = [ 0 for _ in range(N+5)]

def check(n):
    i = bisect.bisect_left(A, n)
    if i != M and A[i] == n:
        return False
    else:
        return True

dp[0] = 1
for i in range(N):
    if check(i+1):
        dp[i+1] += dp[i]
        dp[i] %= 1000000007
    if check(i+2):
        dp[i+2] += dp[i]
        dp[i] %= 1000000007

print(dp[N] % 1000000007)

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

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

for _ in range(m):
  broken[int(input())] = 1
  if broken[-1] == 1 and broken[-2] == 1:
    print(0)
    exit()

dp[0] = 1

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

if n == 1:
  print(dp[n])
  exit()
else:
  for i in range(2, n+1):
    if broken[i] == 1:
      continue
    else:
      dp[i] = (dp[i-1] + dp[i-2]) % 1000000007

print(dp[n])

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

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

for _ in range(m):
  broken[int(input())] = 1
  if sum(broken[-2:]) == 2:
    print(0)
    exit()

dp[0] = 1

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

if n == 1:
  print(dp[n])
  exit()
else:
  for i in range(2, n+1):
    if broken[i] == 1:
      continue
    else:
      dp[i] = (dp[i-1] + dp[i-2]) % 1000000007

print(dp[n])

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

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

for _ in range(m):
  broken[int(input())] = 1

dp[0] = 1

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

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

print(dp[n])

Solution (Python):
n,m = map(int,input().split())
ali = [int(input()) for _ in range(m)]
mod=10**9+7;dif = [];cap = 0
for num in ali:
  dif.append(num-cap)
  cap = num
dif.append(n-cap+1)
dif[0] += 1
ref = [0,0,1,1]
a,b = 1,1
for i in range(100000):
  a,b = b,a+b 
  ref.append(b)
ans = 1
for num in dif:
  ans *= (ref[num] % mod)
print(ans % mod)

Solution (Python):
a, b = map(int, input().split())
c = [int(input()) for _ in range(b)]
d = [0] * (a + 1)
d[0] = 1
d[1] = 1
for i in c:
    d[i] = -1
for i in range(2, len(d)):
    if d[i] != -1:
        d[i] = ((0 if d[i-1] == -1 else d[i-1]) + (0 if d[i-2] == -1 else d[i-2])) % 1000000007
print(d[len(d)-1])

Solution (Python):
N, M = map(int, input().split())
A = [True] * (N+1)
for _ in range(M):
  idx = int(input())
  A[idx] = False

step = [0] * (N+1)
step[0] = 1
for i in range(1, N+1):
  if A[i]:
    step[i] = step[i-1] + step[i-2]
  else:
    step[i] = 0
print(step[N]%(10**9+7))

Solution (Python):
n,m = map(int,input().split())
a = [int(input()) for _ in range(m)]
dp=[0]*(n+1)
dp[0]=1

af = [0]*(n+1)
for ai in a:
  af[ai]+=1

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

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

print(dp[-1]%1000000007)

Solution (Python):
def C_TypicalStairs():
    N, M = map(int, input().split())
    am = [int(input()) for i in range(M)]
    can_move = True
    num_move = 0
    if(M == 0):
        num_move = fib(N+1)
    else:
        
        for i in range(M-1):
            if ((am[i] + 1) == am[i+1]):
                can_move = False
        if (can_move):
            num_move = fib(am[0])
            if (M <= 1):
                pass
            else:
                for i in range(M-1):
                    num_move *= fib(am[i+1] - am[i] - 1)
            num_move *= fib(N - am[M-1])
    print(num_move % 1000000007)

def fib(n):
    if (n <= 1):
        a0 = n
    else:
        a0, a1 = 0, 1
        for _ in range(n):
            a0, a1 = a1, a0 + a1
    return a0
if __name__ == "__main__":
    C_TypicalStairs()

Solution (Python):
def C_TypicalStairs():
    N, M = map(int, input().split())
    am = [int(input()) for i in range(M)]
    n_list = [i for i in range(N+1)]
    can_move = True
    num_move = 0
    if(M == 0):
        num_move = fib(len(n_list))
    else:
        
        for i in range(M-1):
            if ((am[i] + 1) == am[i+1]):
                can_move = False
        if (can_move):
            num_move = fib(len(n_list[:am[0]]))
            if (M <= 1):
                pass
            else:
                for i in range(M-1):
                    num_move *= fib(len(n_list[am[i]+1:am[i+1]]))
            num_move *= fib(len(n_list[am[M-1]+1:]))
    print(num_move % 1000000007)

def fib(n):
    if (n <= 1):
        a0 = n
    else:
        a0, a1 = 0, 1
        for _ in range(n):
            a0, a1 = a1, a0 + a1
    return a0
if __name__ == "__main__":
    C_TypicalStairs()

Solution (Python):



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


broken = [0] * (n+1)


dp = [0] * (n+1)

dp[0] = 1



for i in range(m):
    broken[int(input())] = 1


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


for i in range(2, n+1):
    if broken[i] == 1:
        
        continue
    dp[i] = dp[i-1] + dp[i-2]
    dp[i] = dp[i] % 1000000007

print(dp[n])

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

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

print(step[-1]%(10**9+7))

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

dp = [0, 1]
for i in range(N):
    if i+1 in A: dp.append(0)
    else: dp.append(dp[i]+dp[i+1])
print(dp[N+1]%1000000007)

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

b = [0] * (n+1)

for i in a:
    b[i] = 1

dp = [0] * (n+1)

dp[0] = 1

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

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

print(dp[n] % 1000000007)

Solution (Python):
def main():
    N, M = list(map(int, input().split()))
    A = set()
    for i in range(M):
        A.add(int(input()))

    mod = 1000000007

    dp = [0] * (N+1)
    dp[0] = 1
    for now in range(0, N):
        for next in range(now+1, min(N, now+2)+1):
            if next not in A:
                dp[next] += dp[now]
                dp[next] %= mod

    print(dp[N] % mod)

if __name__ == '__main__':
    main()

Solution (Python):
N, M = map(int, input().split())
a = set([int(input()) for _ in range(M)])
mod =  1000000007
ret = [0] * (N+1)
ret[0] = 1
for i in range(1,N+1):
    if i in a:
        continue
    elif i == 1:
        ret[1] = 1
    else:
        ret[i] = ret[i-2] + ret[i-1]

print(ret[len(ret)-1]%mod)

Solution (Python):
N,M = map(int,input().split())
bro = [int(input()) for i in range(M)]
mod = 10**9 + 7
dp = [0]*(N+1)
dp[0] = 1
if len(bro) >= 1 and bro[0] != 1:
    dp[1] = 1
elif len(bro) >= 1:
    del bro[0]
elif len(bro) == 0:
    dp[1] = 1
for i in range(2,N+1):
    if len(bro) == 0:
        dp[i]= (dp[i-1] + dp[i-2]) % mod
    elif bro[0] == i:
        del bro[0]
        continue
    else:
        dp[i]= (dp[i-1] + dp[i-2]) % mod
print(dp[-1] % mod)

Solution (Python):
a, b = map(int, input().split())
d = [0] * (a+1)

for i in range(b):
    d[int(input())] = -1
d[0] = 1 if d[0] != -1 else 0
d[1] = 1 if d[1] != -1 else 0
for i in range(2, a+1):
    if d[i] != -1:
        d[i] = (d[i-1] + d[i-2]) % 1000000007
    else:
        d[i] = 0
print(d[len(d)-1])

Solution (Python):
N, M = map(int, input().split())
am = [int(input()) for i in range(M)]
safe = [True]*(N+1)
for i in am:
    safe[i] = False
dp = [0]*(N+1)
dp[0]=1
for i in range(N):
    if safe[i+1]:
        dp[i+1] += dp[i]
    if i+2<=N:
        if safe[i+2]:
            dp[i+2] += dp[i]
print(dp[N]%(10**9+7))

Solution (Python):
def fibonacci(n):
	if n==0:
		return 0
	a,b=1,1
	for i in range(0,int((n-1)/2)):
		a+=b
		b+=a
	if n%2!=0:
		return a
	return b

n=[int(i) for i in input().split()]
f=1
a=-1
for i in range(0,n[1]):
	b=int(input())
	f*=fibonacci(b-a-1)
	a=b
f*=fibonacci(n[0]-a)
print(f%1000000007)

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


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


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


combi = 1

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

combi *= fib(dis)
 
print(combi % 1000000007)

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

a.append(n+1)
mod=1000000007

b=[0]*(n+1)
b[0]=1
if a[0]==1:
    b[1]=0
    count=1
else:
    b[1]=1
    count=0

if n==1:
    if m==0:
        print("1")
    else:
        print("0")
else:
    for i in range(2,n+1):
        if i==a[count]:
            b[i]=0
            count += 1
        else:
            b[i]=b[i-1]+b[i-2]
    print(int(b[n]%mod))

Solution (Python):

import sys
sys.setrecursionlimit(10**6)


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



memo = [0]*(N+2)
def fibonacci(n):
    if n < 3:
        return 1
    if memo[n] < 1:
        memo[n] = fibonacci(n-1) + fibonacci(n-2)
    return memo[n]

now = 0 
count = 1
for i in a:
    count *= fibonacci(i-now)
    count = count%mod
    if now == i:
        print(0)
        quit()
    now = i+1 


count *= fibonacci(N-now+1)
print(count%mod)

Solution (Python):

import sys
sys.setrecursionlimit(10**6)


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



fib_memo = {}
def fib(n):
    if n < 3: return 1
    if n not in fib_memo:
        fib_memo[n] = fib(n-1) + fib(n-2)
    return fib_memo[n]

now = 0 
count = 1
for i in a:
    count *= fib(i-now)
    count = count%mod
    if now == i:
        print(0)
        quit()
    now = i+1 


count *= fib(N-now+1)
print(count%mod)

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

Solution (Python):


def solve():
    MOD = 1000000007
    N, M = list(map(int, input().split()))
    dp = [0 for i in range(0, N+1)]
    A = set()
    for i in range(M):
        A.add(int(input()))
    
    dp[0] = 1
    dp[1] = 0 if 1 in A else 1

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


if __name__ == "__main__":
    solve()

Solution (Python):

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))



sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
A = [INT() for _ in range(M)]

b = [0] * (N + 2)

for i in A:
    b[i] = 1

dp = [0] * (N + 2)


dp[0] = 1

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

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

ans = dp[N] % mod
print(ans)

Solution (Python):
import sys
from collections import deque, defaultdict
import copy
import bisect
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 9)

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

num = [0 for i in range(N)]
for i in range(M):
    num[a[i] - 1] = 1000000008
if num[0] == 0:
    num[0] = 1
if len(num) >= 2 and num[1] == 0:
    num[1] = 1 + min(1000000007, num[0])
    num[1] = num[1] % 1000000007
for i in range(2, N):
    if num[i] < 1000000008:
        num[i] = min(1000000007, num[i - 1]) + min(1000000007, num[i - 2])
        num[i] = num[i] % 1000000007
print(num[N - 1])

Solution (Python):
N, M = map(int, input().split())
MOD = 10 ** 9 + 7
broken = []
for i in range(0, M):
  broken.append(int(input()))

memo = [1]
cnt = 1
while cnt <= N:
  if len(broken) > 0 and cnt == broken[0]:
    del broken[0]
    memo.append(0)
  elif cnt == 1:
    memo.append(1)
  else:
    memo.append((memo[-1] + memo[-2])%MOD)
  cnt += 1
  
print(memo[-1])

Solution (Python):
import sys

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

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

Solution (Python):
import sys

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

if M > 0:
    set_a = set(map(int, sys.stdin))
else:
    set_a = set()
MOD = 10**9 + 7

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

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


for i in broken:
    num[i] = 0

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

Solution (Python):
N, M = map(int, input().split())
set_a = set([int(input()) for _ in range(M)])
MOD = 10**9 + 7

dp = [0] * (N + 1)
dp[0] = 1
dp[1] = 0 if 1 in set_a else 1
for i in range(2, N+1):
    dp[i] = 0 if i in set_a else dp[i-1] + dp[i-2]
    dp[i] %= MOD
ans = dp[N] % MOD

print(ans)

Solution (Python):
N, M = map(int, input().split())
set_a = set([int(input()) for _ in range(M)])
MOD = 10**9 + 7

dp = [0] * (N + 1)
dp[0] = 1
dp[1] = 0 if 1 in set_a else 1
for i in range(2, N+1):
    dp[i] = 0 if i in set_a else dp[i-1] + dp[i-2]
ans = dp[N] % MOD

print(ans)

Solution (Python):
N, M = map(int, input().split())
set_a = set([int(input()) for _ in range(M)])
MOD = 10**9 + 7

dp = [0] * (N + 1)
dp[0] = 1
dp[1] = 0 if 1 in set_a else 1
for i in range(2, N+1):
    dp[i] = 0 if i in set_a else dp[i-1] + dp[i-2]
ans = dp[N] % MOD

print(ans)

Solution (Python):
import logging
from math import factorial

logging.basicConfig(level=logging.INFO, format="%(message)s")


steps_memo =[0 for _ in range(150000)]
def cal_steps(num):
    steps_memo[0] = 1
    steps_memo[1] = 1

    for i in range(2, num):
        steps_memo[i] = steps_memo[i - 1] + steps_memo[i - 2]

    return steps_memo[num - 1]
    
def main():
    N, M = (int(x) for x in input().split())
    a_s = [int(input()) for _ in range(M)]

    logging.info(a_s)
    
    a_s.append(N + 1)
    a_s.insert(0, -1)
    diff_a = [a_s[i + 1] - a_s[i] - 1 for i in range(M + 1)]

    if diff_a[0] == 0:
        diff_a[0] = 1
    
    logging.info(diff_a)

    
    answer = 1
    for i in diff_a:
        answer *= int(cal_steps(i))

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

if __name__ == "__main__":
    main()

Solution (Python):
n,m = map(int,input().split())
l = [1]*(n+1)

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

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

Solution (Python):
n, m = (int(i) for i in input().split())
broken = [False]*(n+1)

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

dp = [0]*(n+2)
mod = 1000000007
dp[n] = 1
for i in range(n)[::-1]:
  if broken[i]:
    dp[i] = 0
    continue
  dp[i] = (dp[i+1] + dp[i+2]) % mod
print(dp[0])

Solution (Python):
N,M = map(int,input().split())
MOD = 1000000007
a = [int(input()) for _ in range(M)]
dp_list = [-1] * (N+1)


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


if dp_list[N] != 0:
  dp_list[N] = 1
  

if dp_list[N-1] != 0:
  dp_list[N-1] = 1


for i in range(N-2,-1,-1):
  if dp_list[i] == 0:
    continue
  dp_list[i] = dp_list[i+1] + dp_list[i+2]

print(dp_list[0]%MOD)