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):
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])

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

for x in range(2,n):
    if x == 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)

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

for x in range(2,n):
    if x == 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)

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

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

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

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

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

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

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

Solution (Python):
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,m= (int(i) for i in input().split())       




a=[ip() for i in range(m)]    





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)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

MOD = 10**9 + 7

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

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)

Solution (Python):

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


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])

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

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

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

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

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

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

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

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

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

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

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

Solution (Python):

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
        
        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
        
        answer = (answer * count_valiation(normal_steps)) % 1000000007
    
    
    print(answer)    
    
if __name__ == '__main__':
    main()

Solution (Python):

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

m_lst=[-1]
for i in range(m):
    m_lst.append(int(input()))
m_lst.append(n+1)
d_lst=[]
for i in range(len(m_lst)-1):
    d_lst.append(m_lst[i+1]-m_lst[i]-1)
def f(length):
    d=length-1
    if d==-1:
        return 0
    elif d==0:
        return 1
    elif d == 1:
        return 1
    elif d == 2:
        return 2
    else:
        last_two=1
        last_one=2
        last=0
        for i in range(d-2):
            last=last_two+last_one
            last_two=last_one
            last_one=last
        return last

output =1 
for d in d_lst:
    output*=f(d)
print(output%1000000007)

Solution (Python):
mod = 1000000007
N,M = [int(i) for i in input().split()]
A = []
for _ in range(M):
    A.append(int(input()))
steps = [0]*N
for a in A:
    steps[a-1] = 1
cnt = []
for n in range(N):
    if n == 0:
        if steps[n]==0:
            cnt.append(1)
        elif steps[n]==1:
            cnt.append(0)
    elif n == 1:
        if steps[n]==0:
            cnt.append(cnt[n-1]+1)
        elif steps[n]==1:
            cnt.append(0)
    elif steps[n] == 0:
        cnt.append((cnt[n-2]+cnt[n-1])%mod)
    elif steps[n] == 1:
        cnt.append(0)
print(cnt[-1])

Solution (Python):
n,m=map(int,input().split())
a=[]
for _ in range(m):
    a.append(int(input()))
for i in range(m-1):
    if a[i+1]-a[i]==1:
        print(0)
        exit()
dp=[0 for x in range(n+1)]
for j in range(m):
    dp[a[j]]=-1
dp[0]=1
if 1 in a:
    dp[1]=0
else:
    dp[1]=1
for k in range(1,n):
    if dp[k+1]!=-1:
        dp[k+1]=dp[k]+dp[k-1]
    else:
        dp[k+1]=0
print(dp[n]%1000000007)

Solution (Python):

import numpy as np
MOD = 1000 * 1000 * 1000 + 7

N,M = map(int,raw_input().split())
A = np.zeros(N+1, dtype=np.int32)

for i in xrange(M):
	a = int(raw_input())
	A[a] = -1

A[0] = 1
for i in xrange(1,N+1):
	if A[i] == -1:
		A[i] = 0
	else:
		if  i == 1:
			A[i] = A[i-1]
		else:
			A[i] = A[i-1]+A[i-2]

		A[i] %= MOD

print A[N]

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

is_broken = [1] * (n+1)

for i in range(m):
    is_broken[a[i]] = 0

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

for i in range(n):
    if i - 1 >= 0:
        step[i+1] = step[i] * is_broken[i] + step[i-1] * is_broken[i-1]
    else:
        step[i+1] = step[i] * is_broken[i]
    step[i+1] %= mod

print(step[n])

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

j = 0
sum = []

for i in range(N+1):
    if j < M and i == A[j]:
        sum.append(0)
        if j < M-1:
            j += 1
    elif i == 0 or i == 1:
        sum.append(1)
    else:
        sum.append(sum[i-2] + sum[i-1])


print(sum[N]%1000000007)

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

li_m = list()

for _ in range(m):
    li_m.append(int(input()))


if set(li_m).intersection([l + 1 for l in li_m]):
    print(0)
    exit(0)


answer = 1

def pt(length):

    if length == 0:
        return 1

    li_test = [0] * length
    for i in range(length):
        if i == 0:
            li_test[i] = 1
        elif i == 1:
            li_test[i] = li_test[i - 1] + 1
        elif i == len(li_test):
            li_test[i] = li_test[i - 1] + 1
        else:
            li_test[i] = li_test[i - 1] + li_test[i - 2]

    return li_test[-1]


idx_start = 0
idx_end = 0

if len(li_m) != 0:

    for idx, v in enumerate(li_m):
        if idx == 0:
            idx_end = v - 1
        else:
            idx_start = idx_end + 2
            idx_end = v - 1

        subkaidan = idx_end - idx_start

        answer = answer * pt(subkaidan)

        if idx == len(li_m) - 1:
            idx_start = idx_end + 2
            idx_end = n
            subkaidan = idx_end - idx_start

            answer = answer * pt(subkaidan)
else:
    answer = answer * pt(n)


print(answer % 1000000007)