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 = list(map(int, input().split()))
dp = [1]*(n+1)
for _ in range(m):
    dp[int(input())] = 0

for index,value in enumerate(dp):
    if index == 0 or index == 1:
        continue
    if dp[index] == 0:
        continue
    dp[index] = dp[index-1] + dp[index -2]
print(dp[n]%1000000007)

Solution (Python):
from operator import itemgetter
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
stairs = [0] * (n + 1)
a = [int(input()) for i in range(m)]
mod = (10 ** 9 + 7)
stairs[0] = 1

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

for i in a:
    stairs[i] = -100


for i in range(1, n + 1):
    if stairs[i] >= 0:
        stairs[i] = max(stairs[i-1], 0) + max(stairs[i-2], 0)
        stairs[i] = stairs[i] % mod


print(stairs[n] % mod)

Solution (Python):
def step(num):
	a = 1
	b = 1
	for i in range(1,num):
		c = a
		a = b
		b += c
	return b

def main():
	data = input().split()
	person = 0
	road = 1
	for i in range(int(data[1])):
		a = int(input())
		if a - person == 0:
			print(0)
			return
		length = a - 1 - person
		road_1 = step(length)
		road *= (road_1 % 1000000007)
		person = a + 1
	length = int(data[0]) - person
	road_1 = step(length)
	road *= (road_1 % 1000000007)
	print(road % 1000000007)
	return

if __name__ == "__main__":
	main()

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7


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

mod = 10**9+7 
N = 2*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 )


def combinations_with_repetition(n, k):
    return cmb(n+k-1, k, mod)

def num_of_pattern(n):
    sum_of_pattern = 0
    if n%2 == 1:
        for k in range(0,n,2):
            sum_of_pattern += combinations_with_repetition(((n-k)//2)+1, k)
        return sum_of_pattern % mod
    else:
        for k in range(1,n,2):
            sum_of_pattern += combinations_with_repetition(((n-k)//2)+1, k)
        return sum_of_pattern % mod

def main(): 
    N, M = LI()
    a_li = [-1]
    prev = INF
    for _ in range(M):
        now = II()
        if prev+1 == now:
            print(0)
            return
        elif prev == now:
            continue
        prev = now
        a_li.append(now)
    a_li.append(N+1)

    ans = 1
    for i in range(len(a_li)-1):
        ans *= num_of_pattern(a_li[i+1] - a_li[i] - 1)
        ans %= mod

    print(ans)

main()

Solution (Python):
from sys import stdin
data = stdin.readline().split()
N, M = int(data[0]), int(data[1])
a = [None] * M
fib = [None] * N
if N == 1:
    print(1)
    exit()
for i in range(M):
    a[i] = int(stdin.readline().rstrip())
    fib[a[i] - 1] = 0
    if i > 0 and a[i] - a[i-1] == 1:
        print(0)
        exit()
if not 1 in a:
    fib[0] = 1
    if not 2 in a:
        fib[1] = 2
    else:
        fib[1] = 0
else:
    fib[0] = 0
    fib[1] = 1
for i in range(2,N):
    if fib[i] == 0:
        continue
    else:
        fib[i] = fib[i-1] + fib[i-2]

print(fib[N-1] % 1000000007)

Solution (Python):

 
import math
import numpy as np
import random
import copy
import statistics 
import bisect
import heapq
from collections import defaultdict 
import time
import sys

WARU = 1000000007

N, M = [ int(x) for x in input().split() ]
A = {}
for i in range(M):
    A[int(input())] = 1

ans = [None for i in range(N + 1)]
ans[0] = 1
ans[1] = 1
for a in A:
    ans[a] = 0

for i in range(N):
    n = i + 1
    if ans[n] is not None:
        continue
    ans[n] = (ans[n-2] + ans[n-1]) % WARU


print(ans[N])

Solution (Python):
import sys
N,M = map(int, input().split())
mod = 1000000007
if N == 1:
    print(1)
    sys.exit()
a = set()
b = -1
for _ in range(M):
    c = int(input())
    a.add(c)
    if abs(b-c) == 1:
        print(0)
        sys.exit()
    b = c
dp = [0]*(N+2)
dp[0] = 1
if 1 in a:
    dp[1] = 0
else:
    dp[1] = 1
for i in range(2, N+2):
    if i in a:
        dp[i] = 0
    else:
        dp[i] = dp[i-1]%mod + dp[i-2]%mod
print(dp[N]%mod)

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


def main():
    N, M = map(int, input().split())  
    li = list()
    last = -1
    current = N
    ans = 1
    beforeBroken = 0
    for i in range(M):
        current = int(input())
        beforeBroken = current
        if last == current - 1 and last != 0:
            print(0)
            return

        if current != 1:
            li.append(current - last-2)
        last = current

    if M != 0:
        li.append(N - beforeBroken-1)
    else:
        li.append(N)
    for i in li:
        ans *= Fib(i+2)
    print(ans % 1000000007)


main()

Solution (Python):
MOD = 10**9 + 7

N,M = map(int,input().split())
dp = [0]*(N+1)
dp[0] = 1
A = set(int(input()) for _ in range(M)) 

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

answer = dp[N]
print(answer)

Solution (Python):
mod = 1000000007
n, m = map(int, input().split())
dat_m = []
dp = [0] * (n + 1)
for i in range(m):
    t = int(input())
    dp[t] = -1

dp[0] = 1
for i in range(1, n + 1):
    if dp[i] == -1:
        dp[i] = 0
        continue
    dp[i] = dp[i - 1]
    if i > 1:
        dp[i] += dp[i - 2]
    if i in dat_m:
        dp[i] = 0
    dp[i] = dp[i] % mod

print(dp[n])

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

A = []
for _ in range(M):
    A.append(int(input()))

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

ptr = 0

step[0] = 1
step[1] = 1
if ptr < M and A[ptr] == 1:
    step[1] = 0
    ptr += 1

for i in range(2, N+1):
    if ptr < M and i == A[ptr]:
        ptr += 1
    else:
        step[i] = step[i-1] + step[i-2]


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

Solution (Python):
from sys import stdin

def main():
    N, M = map(int, input().split())
    A = [int(input()) for _ in [0] * M]

    stair = [0] * (N + 1)
    stair[0], stair[1] = 1, 1
    for a in A:
        stair[a] = -1

    mod = 1000000007
    for i in range(2, N + 1):
        if stair[i-1] == stair[i-2] == -1:
            print(0)
            return
        elif stair[i] == -1:
            continue
        if stair[i-1] > -1:
            stair[i] += stair[i-1]
        if stair[i-2] > -1:
            stair[i] += stair[i-2]
        stair[i] = stair[i] % mod
    print(stair[-1])

input = lambda: stdin.readline()
main()

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

C = [0]*(N+1)
C[0]=1
for i in range(N-1):
    C[i+1]+=(C[i]*D[i])%MOD
    C[i+2]+=(C[i]*D[i])%MOD
C[N]+=(C[N-1]*D[N-1])%MOD
    
print(C[N]%MOD)

Solution (Python):
n, m = map(int, input().split())
r = [0, 1]
mod = 1000000007
a = []
for i in range(m):
  a.append(int(input()))
j = 0
for i in range(n):
  if j < m and i == a[j] - 1:
    r = [r[1], 0]
    j += 1
  else:
    r = [r[1], (r[0] + r[1]) % mod]
print(r[-1])

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]]
        s%=rem
    print(s)

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] == a[i+1] - 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):
N, M = map(int, input().split())
MOD = 1000000007
a = [0] * (N+1)
can_pass = True
for i in range(M):
    ai = int(input())
    if a[ai-1] == 1:
        can_pass = False
        break
    a[ai] = 1

if not can_pass:
    print(0)
else:
    c = [0] * (N+1)
    c[0] = 1
    for i in range(1, N+1):
        if a[i] == 0:
            if i > 1:
                c[i] = (c[i-1] + c[i-2]) % MOD
            else:
                c[i] = c[i-1]
        else:
            c[i] = 0
    print(c[N])

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

print(dp[n]%modulo)

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

MOD = 1000000007

p = [0]*(N+1)
for i in range(M):
    a = int(input())
    p[a] = -1

p[N] = 1
if p[N-1] != -1:
    p[N-1] = 1

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

    if p[i] > 0:
        p[i] %= MOD

ans = p[0]
if ans < 0:
    ans = 0

print(ans)

Solution (Python):
N,M=map(int,input().split())
list1=set([int(input()) for i in range(M)])
list2=[1]+[0]*N
if not 1 in list1:
    list2[1]=1
for i in range(N-1):
    if not i+2 in list1:
        list2[i+2]=(list2[i]+list2[i+1])%1000000007
print(list2[N])

Solution (Python):
N, M = list(map(int, input().split()))
a = []
for _ in range(M):
    a.append(int(input()))
a = sorted(list(set(a)))
if len(a)>0:
    dif = [a[0]-1]
    dif.extend([(a[i]-1)-(a[i-1]+1) for i in range(1,len(a))])
    dif.extend([N-a[-1]-1])
else:
    dif = [N]
max_dif = max(dif)
Fiblist = {-1:0,0:1,1:1,2:2}
for n in range(3,max_dif+1):
    Fiblist[n]=Fiblist[n-1]+Fiblist[n-2]
ans = 1
for part in dif:
    ans= ans*Fiblist[part]%1000000007
print(ans)

Solution (Python):
def main():
    n, m = map(int, input().split())
    a = [int(input()) for _ in range(m)]
    s = [True for _ in range(n + 1)]

    for ai in a:
        s[ai] = False

    print(solve(n, s))

def solve(n, s):
    M = 10 ** 9 + 7

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

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


main()

Solution (Python):
n,m = map(int,input().split())
displace = {}
for _ in range(m):
    displace[int(input())] = 1
dp = {0:1}
if 1 in displace:
    dp[1] = 0
else:
    dp[1] = 1

for i in range(2,n+1):
    next_case = 0
    if i not in displace:
        next_case += dp[i-1]+dp[i-2]
    dp[i] = next_case%1000000007
print(dp[n])

Solution (Python):
import sys,collections,math,random;sys.setrecursionlimit(10**7)
def Is(): return [int(x) for x in sys.stdin.readline().split()]
def Ss(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

MOD = 10**9 + 7
n,m = Is()
ns = [0] * (n+1)
ns[0] = 1
for i in range(m):
    ns[I()] = -1
for i in range(n):
    if ns[i] >= 0 and i+1 <= n and ns[i+1] >= 0:
        ns[i+1] = (ns[i+1] + ns[i]) % MOD
    if ns[i] >= 0 and i+2 <= n and ns[i+2] >= 0:
        ns[i+2] = (ns[i+2] + ns[i]) % MOD
print(ns[n])

Solution (Python):
import fractions as fr
import itertools as it
import collections as col
import heapq as hq
import sys
sys.setrecursionlimit(10**9)

"""
N=int(input())
W=list(map(int, input().split()))
ans=10**100
for T in range(1,N):
        S1=sum(W[:T])
        S2=sum(W[T:])
        ans = min(ans, abs(S1-S2))
print(ans)
"""
"""
P,Q,R=map(int, input().split())
print(min([P+Q, P+R, Q+R]))
"""
MOD=1000000007
N,M=map(int, input().split())
A=set()
for i in range(M):
        A.add(int(input()))

dp=dict()
dp[0]=1
dp[1]=0 if 1 in A else 1
for i in range(2, N+1):
        if i in A: dp[i] = 0
        else:
                m1=0 if (i-1) in A else dp[i-1]
                m2=0 if (i-2) in A else dp[i-2]
                dp[i]=(m1+m2) % MOD
print(dp[N])
"""

        print(i)
        if i in A: return 0
        if i in dp: return dp[i]
        m1=0 if (i-1) in A else f(i-1)
        m2=0 if (i-2) in A else f(i-2)
        dp[i]=(m1+m2) % MOD
        return dp[i]

print(f(N))
"""

Solution (Python):
import sys

inp = input().split(" ")
n,m = int(inp[0]),int(inp[1])
brokens = []
for i in range (m):
    brokens.append(int(input()))

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


dp = []
for i in range(n+1):
    dp.append(0)

for i in brokens:
    dp[i]= -1

if dp[1] == -1 and dp[2] == -1:
    dp[1] = 0
    dp[2] = 0
elif dp[1] == -1:
    dp[1] = 0
    dp[2] = 1
elif dp[2] == -1 :
    dp[1] = 1
    dp[2] = 0
else:
    dp[1] = 1
    dp[2] = 2


if n <= 2:
    print(dp[n])
    sys.exit(0)


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

print(dp[n] % 1000000007)

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

broken = [False for it in range(n)]
for it in a:
    broken[it] = True

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

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

fib = [1 for _ in range(n+1)]
for i in range(n-1):
  fib[i+2] = fib[i] + fib[i+1]

total = 1
for x in S:
  if x == -1:
    print(0)
    exit()
  total *= fib[x]


print(total%1000000007)

Solution (Python):
from collections import defaultdict
from collections import deque
from string import ascii_uppercase
import sys, bisect, math
stdin = sys.stdin
read_int = lambda : list(map(int,stdin.readline().split()))
read_str = lambda : stdin.readline().rstrip()

N, M = read_int()
num_array = [read_int()[0] for _ in range(M)]

BIG = 1000000007

dp = [0 for _ in range(N + 2)]
for i in range(M):
    dp[num_array[i]] = -1

def solve():
    ans = 0
    dp[0] = 1
    for i in range(N):
        if dp[i] == -1:
            if dp[i + 1] == -1:
                return 0
            continue
        if dp[i + 1] != -1:
            dp[i + 1] += dp[i] % BIG if dp[i + 1] == 0 else dp[i]
        if dp[i + 2] != -1:
            dp[i + 2] += dp[i] % BIG if dp[i + 2] == 0 else dp[i]
    return dp[N] % BIG

if __name__ == "__main__":
    print(solve())

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
def lmi(): return list(map(int, input().split()))

n, m = lmi()

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

a = 0
if m != 0:
    a = int(input())
k = 1
for i in range(n+1):

    if i != a:
        if i == 1:
            l[i] = 1
        elif i >= 2:
            l[i] = l[i-1] + l[i-2]
            l[i] %= 1000000007
    else:
        k += 1
        if k <= m:
            a = int(input())




print(l[n] % 1000000007)

Solution (Python):
n, m = map(int, input().split())
stair = [0] * (n + 10)
stair[1] = 1
stair[2] = 1
mod = 1000000007
for i in range(m):
    a = int(input())
    stair[a] = -1

for i in range(1, n+1):
    if (stair[i] == -1):
        continue
    if (stair[i + 2] != -1):
        stair[i + 2] = (stair[i] + stair[i + 2]) % mod

    if (stair[i + 1] != -1):
        stair[i + 1] = (stair[i] + stair[i + 1]) % mod

print(stair[n])

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

fib = [0]*(n + 1)
fib[0] = 1
fib[1] = 1
for x in range(2, n+1):
    fib[x] = fib[x-1] + fib[x-2]

mod = 10**9+7
ans = 1
prev_a = -1
a = 0
for i in range(m):
    a = int(input())
    if a - 1 == prev_a:
        ans = 0
        break
    else:
        ans = (ans * fib[a - prev_a - 2]) % mod
    prev_a = a

if m == 0:
    ans = fib[n] % mod
else:
    ans = (ans * fib[n - a - 1]) % mod
print(ans)

Solution (Python):
n,m = map(int, input().split())
list = [0] * n
list[0] = 1
if n >= 2:
    list[1] = 2
if n >= 3:
    for i in range(2, n):
        list[i] = list[i - 2] + list[i - 1]

if m == 0:
    print(list[n - 1] % 1000000007)
else:
    ans = 1
    o = 0
    for i in range(m):
        a = int(input())
        if a == o:
            ans = 0
            break
        if a > o + 1:
            ans = (ans * list[a - o - 2]) % 1000000007
        o = a + 1

    if a + 1 < n:
        ans = (ans * list[n - a - 2]) % 1000000007
    print(ans)

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

C = [0] * 100001
C[1] = 1
C[2] = 2

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

start = 0

result = 1

for i in range(M):
    a = int(input())
    next = a - 1
    if next == start:
        start = a + 1
        continue
    if next < start:
        print(0)
        exit(0)
    range = a - 1 - start
    pattern = C[range]
    result *= pattern
    start = a + 1

if start < N:
    range = N - start
    pattern = C[range]
    result *= pattern

print(result % 1000000007)

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

ax = [1]*(N+1)
for m in range(M):
    ai = int(input()) - 1
    ax[ai+1] = None



chunk_num = []
num = 0
for i in range(len(ax)):
    if ax[i] is not None:
        num += 1
    else:
        chunk_num.append(num)
        num = 0
chunk_num.append(num)


bu = {0:1, 1:1}
for i in range(1, max(chunk_num)):
    if bu.get(i) is None:
        bu[i] = bu[i-1] + bu[i-2]

rs = 1
for num in chunk_num:
    
    try:
        rs *= bu[num-1]
    except:
        rs = 0
    rs %= 1000000007
print(rs%1000000007)

Solution (Python):
import bisect

def find_bisect(a, x):
    i = bisect.bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return True
    return False

val = list(map(int, input().strip().split()))
n = val[0]
m = val[1]
a = []

for i in range(m):
    a.append(int(input().strip()))

pastpast_result = 0
past_result = 1
result = 0

for i in range(n):
    result = 0
    if not find_bisect(a, i):
        result += past_result
    if not find_bisect(a, i-1):
        result += pastpast_result

    if result > 1000000007:
        result = result % 1000000007
    
    if result == 0:
        break
    
    pastpast_result = past_result
    past_result = result

print(result % 1000000007)

Solution (Python):
import sys

from collections import deque

from collections import defaultdict

import heapq

import bisect





s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def fib_memo(n):
    memo = [0] * (n+1)
    memo[0] = 1
    if n < 1:
        return memo
    memo[1] = 1
    for i in range(2, n+1):
        memo[i] = memo[i-1] + memo[i-2]
    return memo

def main():
    N, M = i2nn()
    A = ii2nn(M)
    MOD = int(1e+9) + 7
    D = [0] * (M+1)
    if M == 0:
        D[0] = N
    else:
        D[0] = A[0] - 1
        for i in range(1, M):
            t = A[i] - A[i-1] - 2
            if t <= -1:
                print(0)
                return
            D[i] = t
        D[M] = N - A[M-1] - 1
    n = 1
    memo = fib_memo(max(D))
    for d in D:
        n = (n * memo[d]) % MOD
    print(n)

main()

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

if M == 0:
    a = [-1]

inf = 1000000007
index = 0
n_way = [0 for i in range(N+2)]
n_way[0] = 1

for i in range(N):
    if a[index] == i:
        index += 1
        index = min(index,len(a)-1)
    else:
        n_way[i+1] += n_way[i]
        n_way[i+1] = n_way[i+1]%inf
        n_way[i+2] += n_way[i]
        n_way[i+2] = n_way[i+2]%inf

print(n_way[N])

Solution (Python):
from sys import stdin

MOD = 1000000007

n, m = map(int, raw_input().strip().split())
inp = stdin.readlines()
broken = [0] * n

for line in inp:
    a = int(line.strip())
    broken[a] = 1

dp = [0] * (n + 1)

dp[n] = 1
if not broken[n - 1]: dp[n - 1] = 1
for i in xrange(n - 2, -1, -1):
    if broken[i]: continue
    dp[i] = dp[i + 1] + dp[i + 2]
    if dp[i] >= MOD: dp[i] -= MOD

print dp[0] % MOD

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

dan=[]

for i in range(m):
    b=list(map(int, input().split()))
    dan.append(b[0])

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

for ii in range(n-1):
    i=ii+3
    fib[i]=(fib[i-1]+fib[i-2])%1000000007
    


eachans=[]

if(m==0):
    print(fib[n])

if(m>=1):
    if(dan[0]!=1):
        eachans.append(fib[dan[0]-1])

    for i in range(m-1):
        if(dan[i+1]-dan[i]-2 == 0):
            eachans.append(1)
        elif(dan[i+1]-dan[i]-2 == -1):
            eachans.append(0)
        else:
            eachans.append(fib[dan[i+1]-dan[i]-2])
        

if(m>=1):
    if(dan[-1]!=n-1):
        eachans.append(fib[n-dan[-1]-1])
    
if(m>=1):
    
    ans=1
    for i in range(len(eachans)):
        ans = ans*eachans[i]%1000000007

    print(ans)

Solution (Python):
n,m=map(int,input().split())
w=[int(input()) for i in range(m)]
s=0
k=[]
for i in w:
    j=i-s-1
    if j==-1:
        print(0)
        exit()
    k.append(i-s-1)
    s=i+1
k.append(n-s)
fib=[1,1,2]
for i in range(max(k)-2):
    fib.append(fib[-1]+fib[-2])
ans=1
for i in k:
    ans*=fib[i]
print(ans%1000000007)

Solution (Python):
n,m = map(int, input().split())
u = [0]*(n+1)
for i in range(m):
    u[int(input())] = 1
ll = [0]*(n+2)
ll[1] = 1
for i in range(2,n+2):
    if not u[i-1]:
        ll[i] = ll[i-1] + ll[i - 2]
print(ll[-1] % 1000000007)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)

MOD = 10**9+7
memo = {}
def steps(n):
  if not(n in memo):
    if n == 0:
      memo[n] = 1
    elif n == 1:
      memo[n] = 1
    else:
      memo[n] = (steps(n-1)+steps(n-2))%MOD
  return memo[n]

N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
nowstep = 0
ans = 1
for a in A:
  if nowstep == a:
    ans = 0
    break
  ans = (ans * steps(a-1-nowstep))%MOD
  nowstep = a+1
ans = (ans * steps(N-nowstep))%MOD
print(ans)

Solution (Python):
MOD = 10 ** 9 + 7
def add(a, b):
  return (a + b) % MOD
def sub(a, b):
  return (a - b) % MOD
def mul(a, b):
  return ((a % MOD) * (b % MOD)) % MOD
def div(a, b):
  return ( (a % MOD) * (power(b, MOD)) ) % MOD
def power(a, b):
  return pow(a, b, MOD)

fn = [1, 1]
for i in range(10 ** 5):
  fn1 = fn[-2] + fn[-1]
  fn.append(fn1)

n, m = map(int, input().split())
an = []
for _ in range(m):
  an.append(int(input()))
an.append(n+1)

now = 0
pattern = 1
for a in an:
  if now >= a:
    pattern = 0
    break
  steps = a - now - 1
  pattern = mul(pattern, fn[steps])
  now = a + 1

print(pattern)

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


ans = [0]*(n+1)
ans[0] = 1
for i in range(m):
  ans[a[i]] = -1
for i in range(1,n+1):
  if i > 1:
    if ans[i] != -1:
      if ans[i-2] != -1:
        ans[i] += ans[i-2]
      if ans[i-1] != -1:
        ans[i] += ans[i-1]
  else:
    if ans[i] != -1:
      ans[i] = ans[i-1]

print(ans[n]%1000000007)

Solution (Python):
flag=0
N,M=map(int,input().split())
A=[-1]+[int(input()) for _ in range(M)]+[N+1]
mod=10**9+7
    
fib=[1,1]
for i in range(10**5):
    fib.append((fib[i]+fib[i+1])%mod)
    
for i in range(1,M):
    if A[i+1]==A[i]+1:
        flag=1

if flag==0:
    B=[A[i+1]-A[i]-2 for i in range(M+1)]
    ans=1
    for i in range(M+1):
        ans=(ans*fib[B[i]])%mod
    print(ans)
else:
    print(0)

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

if M == 0:
    if N == 1:
        print(1)
        exit(0)
    dp[0] = 1
    dp[1] = 1
    dp[2] = 1
    for k in range(2,N+1):
        dp[k] = dp[k-1] + dp[k-2]
        dp[k] %= MOD
    print(dp[N])
else:
    A = [int(input()) for k in range(M)]
    dp[0] = 1
    dp[1] = 1
    dp[2] = 1
    if N == 1:
        if M == 1:
            print(0)
        exit(0)
    else:
        t = 0
        if A[0] == 1:
            t += 1
            dp[1] = 0
        for k in range(2,N+1):
            if t < len(A) and A[t] == k:
                dp[k] = 0
                t += 1
            else:
                dp[k] = dp[k-1] + dp[k-2]
                dp[k] %= MOD
        print(dp[N])

Solution (Python):
n,m = [int(i) for i in input().split()]
a = {int(input()) for i in range(m)}
dp = {}
for step in range(1,n+1):
    if step in a:
        dp[step] = 0
        continue
    if step == 1:
        if step in a:
            dp[1] = 0
        else:
            dp[1] = 1
        continue
    if step == 2:
        if step in a:
            dp[2] = dp[1]
        else:
            dp[2] = dp[1] + 1
        continue
    dp[step] = dp[step-1] + dp[step-2]
print(int(dp[n]%1000000007))

Solution (Python):


M = 1000000007


def main():
  n, m = map(int, input().split())
  a = [int(input()) for _ in range(m)]
  a.sort()
  a += [-1, -1]
  b = 0
  w = [0] * (n + 2)
  w[0] = 1

  for i in range(n):
    if a[b] == i:
      b += 1
      continue
    elif a[b] == i + 1 and a[b + 1] == i + 2:
      print(0)
      return

    if a[b] != i + 1:
      w[i + 1] = (w[i] + w[i + 1]) % M

    if a[b] != i + 2:
      w[i + 2] = (w[i] + w[i + 2]) % M

  print(w[-2])


if __name__ == '__main__':
  main()

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

table = [0] * (n + 2)
table[0] = 1
for i in range(m):
    a = int(input())
    table[a] = -2

for i in range(1, n + 1):
    if table[i-1] == -2 and table[i-2] == -2:
        print(0)
        exit()


    if table[i] != -2:
        if table[i-1] != -2:
            table[i] += table[i-1]
        if table[i-2] != -2:
            table[i] += table[i-2]

        table[i] %= (10**9+7)

print(table[n])

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

if N == 1:  print(1)
elif N == 2:
    if 1 == M:  print(1)
    else:   print(2)
else:
    temp, temp1, temp2 = 0,0,0
    if 1 not in a:  temp1 = 1
    if 2 not in a:  temp2 = 1 + temp1
    
    for i in range(2,N-1):
        temp = 0
        if i+1 not in a:    temp = temp1 + temp2
        temp1 = temp2
        temp2 = temp

    print( int((temp1+temp2) % 1000000007) )

Solution (Python):
def solve():
    N, M = map(int, input().split())
    A = []
    if M != 0:
        A = [int(input()) for _ in range(M)]
    A.sort(reverse=True)
    mm = 10 ** 9 + 7
    dp = [0] * (N + 1)
    dp[0] = 1  
    tag = -1
    if len(A) != 0:
        tag = A.pop()
    
    if tag == 1:
        dp[1] = 0
        if len(A) == 0:
            tag = -1
        else:
            tag = A.pop()
    else:
        dp[1] = 1
    for i in range(2, N + 1):
        if i == tag:
            if len(A) == 0:
                tag = -1
            else:
                tag = A.pop()
            continue
        dp[i] = (dp[i - 1] + dp[i - 2]) % mm
    print(dp[N])


if __name__ == '__main__':
    solve()

Solution (Python):
N,M=map(int,input().split())
cango=[True]*(N+1) 
mod=10 ** 9 + 7
for i in range(M):
    cango[int(input())]=False
dp=[0]*(N+1) 
dp[0]=1 
dp[1]=int(cango[1])
for x,ok in enumerate(cango):
    if x==0 or x==1 :continue
    if ok:
        dp[x] += (dp[x - 1] + dp[x - 2])%mod
print(dp[N])

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

a=[1,1]
for i in range(2,100001):
    a.append((a[i-1]+a[i-2])%1000000007)

bad=[]
for i in range(m):
    bad.append(int(input()))
num=[]
before=0
bad_flag=0

if m!=0:
    for i in range(len(bad)):
        nxt=bad[i]-before-1
        if nxt==-1:
            bad_flag=1
            break
        num.append(nxt)
        before=bad[i]+1
    num.append(n-bad[len(bad)-1]-1)
else:
    num.append(n)
if bad_flag:
    print(0)
else:
    ans=0
    last=1
    for i in num:
        ans=a[i]*last
        last=ans%1000000007
    print(last)

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

if M == 0:
    A = [-1]
else:
    A = [-1] * M
    for i in range(M):
        A[i] = int(input())
A = set(A)

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

if N == 1:
    if 1 in A:
        print(0)
    else:
        print(1)
    exit()

if N == 2:
    if 2 in A:
        print(0)
    else:
        if 1 in A:
            print(1)
        else:
            print(2)
    exit()

root[1] = 0 if 1 in A else 1
root[2] = 0 if 2 in A else (root[0] + root[1])

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

print(root[N] % 1000000007)