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())
a = [int(input()) for i in range(m)]
res_arr = [-1] * n

for i in a:
    res_arr[i] = 0

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

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

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

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

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

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

ans = 1

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

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

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

print(ans)

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

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

    print(cnts[N])

if '__main__' == __name__:
    resolve()

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

a = 1
b = 1

i = 2

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

Solution (Python):
from collections import Counter

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

c = Counter(a).keys()

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

b[0] = 1

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

print(b[N])

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

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

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

  print(P%1000000007)

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

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

    ans = 1

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

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

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

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

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

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

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

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

dp[0] = 1

if ngs[1]:
    
    dp[1] = 1

for i in range(2, n+1):
    if ngs[i] == False:
        
        dp[i] = 0
    else:
        dp[i] = dp[i-1] + dp[i-2]
print(dp[n] % 1000000007)

Solution (Python):

import sys
imput =sys.stdin.readline

p = 10**9 + 7

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

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


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

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

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

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

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

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

for i in range(m):

    an[i] = int( input() )



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


if disjoint:
    print(0)

else:

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

    for i in range(3, len(tab)):
        tab[i] = tab[i-1]+tab[i-2]



    an.append(n)
    prev = 0
    ans = 1
    for a in an:
        index = a-prev + (1 if a == n else 0)

        ans *= tab[index]
        ans %= mod
        prev = a+1

    
    

    print(ans)

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

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

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

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

import functools
import operator

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

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

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

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


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

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

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

Solution (Python):
import sys

input = sys.stdin.readline

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

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

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

    mod = 10**9+7 
    N = 10**5
    g1 = [1, 1] 
    g2 = [1, 1] 
    inverse = [0, 1] 
    for i in range( 2, N + 1 ):
        g1.append( ( g1[-1] * i ) % mod )
        inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
        g2.append( (g2[-1] * inverse[-1]) % mod )

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

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

    print(ans % 1000000007)

if __name__ == '__main__':
    main()

Solution (Python):

import sys


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



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


if n == 1:
    if not steps[1]:
        print(0)
    else:
        print(1)
    exit()
elif n == 2:
    if not steps[2]:
        print(0)
        exit()
    else:
        if not steps[1]:
            print(1)
        else:
            print(2)
        exit()


ans = 1

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

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

    if steps[idx]:
        r = idx
    else:
        
        
        if steps[idx+1] == False:
            print(0)
            exit()
        else: 
            if r-l > finished:
                for i in range(finished+1, r-l+1):
                    dp[i] = dp[i-2] + dp[i-1]
                    finished = i
            ans *= dp[r-l]
            l = idx+1
            r = idx+1
    idx += 1

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

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

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

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

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

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

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

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

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

cur = 0
tot = 1




for i in range(m):
    nxt = a[i] - 1
    add = chk(nxt - cur)
    
    tot *= add
    tot %= 1000000007
    cur = nxt + 2
print(tot % 1000000007)

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

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

inf=1000000007

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



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

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

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

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

Solution (Python):
import sys

fin = sys.stdin.readline

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


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

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

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

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

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

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

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

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

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

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

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

Solution (Python):

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






n=max(sa_list)+2
fib_list = []

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




ans = 1
for sa_i in range(len(sa_list)):
    sa = sa_list[sa_i]

    ans = ans*fib_list[sa-1]
    ans = ans % INF
print(ans)

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


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

  return F[n]


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

print(total)

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

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

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

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

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

Solution (Python):

import sys

MOD = 1000000007  

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

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

if __name__ == '__main__':
    main()

Solution (Python):
def fib(n):
    a, b = 0, 1
    if n == 1:
        return a
    elif n == 2:
        return b
    else:
        for i in range(n-2):
            a, b = b, a + b
        return b
    
N, M = map(int, input().split())
a = [-1]
for i in range(M):
    a.append(int(input()))
    
for i in range(M-1):
    if a[i+1] == (a[i] + 1):
        print(0)
        exit()
    
combi = 1

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

combi *= fib(dis)

print(combi % 1000000007)

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

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



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

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


for i in range(1,N+1):
    if i == 1 and memo[i] == -1:
        memo[i] = memo[i-1]
    elif memo[i] >= 0:
       memo[i] = 0
        
    else:
          memo[i] = memo[i-1] +memo[i-2]


print(memo[N] % 1000000007)

Solution (Python):
import sys
n,m = map(int,input().split())
mark = [1 for x in range(n+3)]
score = [0 for x in range(n+3)]
score[0]=1
mod = 1000000007
for i in range(m):
    mark[int(sys.stdin.readline())] = 0
c = 0
for i in range(0,n+1):
    if mark[i+1]:
        score[i+1]+=score[i]
        score[i+1]%=mod
    if mark[i+2]:
        score[i + 2] += score[i]
        score[i + 2]%mod
print(score[n]%mod)

Solution (Python):


def solve():
    N, M = list(map(int, input().split()))
    A = {}
    for i in range(1, N+1):
        A[i] = True  
    for i in range(M):
        a = int(input())
        A[a] = False  
    MOD = 10**9+7

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

    for i in range(1, N+1):
        if A[i] is False: continue

        dp[i] += dp[i-1]
        if i-2 >= 0:
            dp[i] += dp[i-2]
        dp[i] %= MOD
    
    print(dp[N]%MOD)


if __name__ == "__main__":
    solve()

Solution (Python):
n,m=map(int,input().split())
l=[]
def nibutan(x,l):
    low=0
    high=len(l)-1
    while low<=high:
      mid=(low+high)//2
      guess=l[mid]
      if guess==x:
         return True
      elif guess>x:
          high=mid-1
      elif guess<x:
          low=mid+1
    return False
if m==0:
  pass
else:
  for i in range(m):
    l.append(int(input()))
l1=[0 for i in range(n+1)]
if 1 in l:
  l1[0]=0
else:
  l1[0]=1

if 2 in l:
  l1[1]=0
elif 1 in l:
  l1[1]=1
else:
  l1[1]=2

if n>=3:
  for i in range(3,n+1): 
    if nibutan(i,l):
      pass
    else:
      l1[i-1]=(l1[i-2]+l1[i-3])%(((10**9)+7))
print(l1[n-1])

Solution (Python):
n,m = map(int, input().split())
bl = [int(input())-1 for _ in range(m)]
l = [i for i in range(n)]
cnt = 0
for num in bl:
    del l[num-cnt]
    cnt +=1
    
mod = 1000000007

al = [0]*n
if 0 in l and 1 in l:
    al[0] = 1
    al[1] = 2
elif 0 in l:
    al[0] =1
elif 1 in l:
    al[1] = 1
else:
    print(0)
    exit()
    
li = [i for i in l if i>=2]
for i in li:
    al[i] = al[i-1] + al[i-2]
    if al[i] == 0:
        print(0)
        exit()

print(al[-1]%mod)

Solution (Python):
p = [0]*100001
p[0] = 1
p[1] = 1
p[2] = 2
ans = 1
flag = 0
for i in range(3,100001):
	p[i] = p[i-1] + p[i-2]


n,m = map(int,input().split())
l = [0]*(m+2)
l[m+1] = n
for i in range(m):
	l[i+1] = int(input())

l1 = [0]*(m+1)
for i in range(m+1):
	l1[i] = l[i+1] - l[i]



if m == 0:
	print(p[n] % 1000000007)
	flag = 1
else:
	for i in range(m+1):
		if i == 0 or i == m:
			ans = ans * p[l1[i]-1]
		else:
			if l1[i] == 1:
				print(0)
				flag = 1
				break
			else:
				if l1[i] == 0:
					ans = ans
				else:
					ans = ans * p[l1[i]-2]

if flag != 1:
	print(ans % 1000000007)

Solution (Python):
import sys
from itertools import product

def mat2_mul(X, Y):
    Z = [ [0, 0], 
          [0, 0] ]
    for (i,j,k) in product(range(2),range(2),range(2)):
        Z[i][j] += X[i][k] * Y[k][j]
    return Z

def mat2_pow(X, n):
    if n == 0:
        return [ [1, 0],
                 [0, 1] ]
    elif n % 2:
        return mat2_mul(X, mat2_pow(X, n-1))  
    else:
        half_pow = mat2_pow(X, n/2)
        return mat2_mul(half_pow, half_pow)

def fib(n):
    if n == 0:
        return 0
    else:
        F = [ [0, 1],
              [1, 1] ]
        return mat2_pow(F, n-1)[1][1]
    
n, m = map(int,input().split())

li = [input() for _ in range(m)]

for i in range(1,len(li)):
    if int(li[i]) - int(li[i-1]) == 1:
        print(0)
        sys.exit()

ans = ["a" for i in range(n+1)]

for i in li:
    ans[int(i)] = "
    
ans = "".join(ans)

ans = ans.split("

result = 1

for i in ans:
    result *= fib(len(i))

print(result%1000000007)

Solution (Python):
import sys
sys.setrecursionlimit(1000000)

def step(n, memo={}):
    if n <= 1:
        return 1
    elif n == 2:
        return 2
    elif n in memo:
        return memo[n]
    else:
        memo[n] = (step(n-1,memo)+step(n-2,memo))%1000000007
        return memo[n]

N, M = map(int, input().split())
a = [-1]

if M == 0:
    print(step(N))

else:
    for m in range(M):
        a.append(int(input()))
        if a[m+1] - a[m] == 1:
            print(0)
            break
    else:
        a.append(N+1)
        ans = 1
        for m in range(M+1):
            ans = (ans*(step(a[m+1]-a[m]-2)))%1000000007
        print(ans)

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

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

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

t = 1000000007
ans = 1


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


if m == 0:
    ans = Fib(n)
elif m == 1:
    ans = ans * Fib(a[0] - 1) * Fib(n - a[0] - 1)
else:
    for i in range(m):
        
        if i == 0:
            ans = ans * Fib(a[i] - 1)
        
        elif a[i] - a[i - 1] == 1:
            ans = 0
            break
        
        elif i == m - 1:
            ans = ans * Fib(a[i] - a[i - 1] - 2)
            if a[i] != n - 1:
                ans = ans * Fib(n - a[i] - 1)
            break
        
        else:
            ans = ans * Fib(a[i] - a[i - 1] - 2)

print(ans % t)

Solution (Python):
n, m = (int(_) for _ in input().split())
x = [int(input()) for i in range(m)]
xi = 0

if m == 0:
    x = [999999]

a = [1,1]
if x[xi] == 1:
    xi = min(len(x)-1,xi+1)
    a[1] = 0

for i in range(n-1):
    if x[xi]-2 == i:
        a.append(0)
        xi = min(len(x)-1,xi+1)
    else:
        a.append(a[i+1]+a[i])

print(a[n]%1000000007)

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

mod = int(1e9+7)
dp = [0 for i in range(n+1)]
dp[0] = 1
ind = 0

for i in range(1,n+1):
    if ind < m and a[ind] == i:
        dp[i] = 0
        ind += 1
    else:
        if i != 1:
            dp[i] = dp[i-1] + dp[i-2]
        else:
            dp[i] = dp[i-1]
print(int(dp[-1]%mod))

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

a.sort()
A = [0]*(N+1)
A[0] = 1

flag = True
if M==0: flag = False

for i in range(1, N+1):
  if flag and i == a[0]:
    A[i] = 0
    a.remove(i)
    if len(a)==0: flag = False
  else:
    if i==1: A[i] = 1
    else:
      A[i] = (A[i-1] + A[i-2])%div

print(A[N])

Solution (Python):
fib=[0,1]
for i in range(100000):
  fib.append(fib[-1]+fib[-2])
  
n,m=map(int,input().split())
hoge=[-1]
ans=1
for i in range(m):
  hoge.append(int(input()))
hoge.append(n+1)

for i in range(len(hoge)-1):
  if(hoge[i+1]-hoge[i]==1):
    print(0)
    exit()
    
for i in range(len(hoge)-1):
  sa=hoge[i+1]-hoge[i]-1
  ans=ans*fib[sa]
  ans=ans%1000000007
print(ans)

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

def fb(num):
    a, b = 1, 0
    for _ in range(num):
        a, b = a + b, a
    if num==-1:
        b=0
    return b 

if m==0:
    print(fb(n+1) % (10**9+7))
    
else:
    sum=fb(int(a[0]))

    for i in range(m-1):
        sum=sum*fb(int(a[i+1])-int(a[i])-1)

    sum=sum*fb(n-int(a[m-1]))

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

Solution (Python):
def howmany(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 = map(int,input().split())

x = 1
a = [0]*(m+2)
a[0] = -1
a[m+1] = n

if m == 0:
    print(howmany(n+1) % 1000000007)
else:
    for i in range(1,m+1):
        a[i] = int(input())

    if all(a[i+1]-a[i] != 1 for i in range(1,m)):
        for i in range(1,m+1):
            if a[i] - a[i-1] > 1:
                x *= howmany(a[i] - a[i-1] -1)
        if a[m] + 1 == n:
            print(x % 1000000007)
        else:
            x *= howmany(a[m+1]-a[m])
            print(x % 1000000007)
    else: print(0)

Solution (Python):


import sys                                                      
sys.setrecursionlimit(10**6)                                    
from collections import deque, Counter                          
from itertools   import accumulate, permutations, combinations  
from operator    import itemgetter                              
from bisect      import bisect_left, bisect_right, bisect       
from heapq       import heappop, heappush                       
from fractions   import gcd                                     
from math        import ceil, floor, sqrt, cos, sin, tan, pi    
from copy        import deepcopy                                
import numpy         as np                                      


def main():
    
    im = InputManager()
    
    n, m = im.inputMultiple()
    maxdif = 0
    a = []
    for _ in range(m):
        a.append(im.inputSingle())
        if len(a) >= 2:
            maxdif = max(maxdif, a[-1] - a[len(a) - 2])
    if len(a) >= 2:
        maxdif = max(maxdif, n - a[-1])
    else:
        maxdif = n
    MOD = 1000000007
    
    idx = 0
    total = 1
    fib = fibonacci(maxdif + 2)
    for ai in a:
        if idx - 1 == ai and idx != 0:
            print()
            continue
        if (ai - idx) == 0 and idx != 0:
            print(0)
            return
        total *= fib[ai - idx - 1]
        idx = ai+1
    total *= fib[n - idx]
    
    print(total % MOD)
    
    return

def fibonacci(n):
    fib = [1, 1]
    for _ in range(n - 1):
        fn_1 = fib[len(fib)-1]
        fn_2 = fib[len(fib) - 2]
        fib.append(fn_2 + fn_1)
    return fib


class InputManager(object):
    def __init__(self):
        pass

    @staticmethod
    def inputSingle(dtype=int):
        return dtype(input())
    
    @staticmethod
    def inputMultiple(dtype=int, aslist=False):
        if aslist:
            return list(map(dtype, input().split()))
        else:
            return map(dtype, input().split())

    @staticmethod
    def input2D(h, dtype=int):
        return [list(map(dtype, input().split())) for i in range(h)]


main()

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





checked_steps = {-1:0, 0:1, 1:1}
divide_num = 1000000007 

for i in range(2, n+1):
    checked_steps[i] = (checked_steps[i-1] + checked_steps[i-2]) % divide_num

all_count = 1
for i in range(m):
    a = int(input())
    if(a < now_step):
        continue
    all_count = (all_count * checked_steps[a - 1 - now_step]) % divide_num
    now_step = a + 1
all_count = (all_count * checked_steps[n - now_step]) % divide_num
print(all_count)

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

ans = 1
clist = []
for i in range(len(a)):
    if i == 0:
        cnt = a[0]+1
        clist.append(cnt)
    else:
        cnt = a[i]-a[i-1]
        clist.append(cnt)
    if cnt == 1:
        ans = ans * 0
        break
    
    ans = (ans * memo[cnt-1]) % p
print(ans)