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=[0]*(N+2)
b=[0]*(M+2)
c=[0]*(M+2)
a[0]=0
a[1]=1
a[2]=1
for i in range(3,N+2):
    a[i]=a[i-1]+a[i-2]
if M==0:
    print(a[N+1]%1000000007)
else:
    b[0]=-1
    b[M+1]=N+1
    way=1
    for i in range(1,M+1):
        b[i]=int(input())
        c[i]=b[i]-b[i-1]-1
        way=(way*a[c[i]])%1000000007
    c[M+1]=b[M+1]-b[M]-1
    way=(way*a[c[M+1]])%1000000007
    print(way)

Solution (Python):
n,m=map(int,input().split())
a=[]
for i in range(m):
    x=int(input())
    if a:
        if x!=a[-1]:
            a.append(x)
    else:
        a.append(x)
count=[0]*(n+2)
count[1]=2
count[0]=1
i=0
s=0
if a:
    s=a.pop(0)
if s==1:
    count[1]=1
    count[0]=0
    if a:
        s=a.pop(0)
if s==2:
    count[1]=0
    if a:
        s=a.pop(0)

while i<n:        
    if (i+2==s-1):
        i=i+1
        if a:
            s=a.pop(0)
    else:
        count[i+2]=(count[i]+count[i+1])%1000000007
        i=i+1

print(count[n-1])

Solution (Python):
n, m = map(int, input().split())
 
a_set=set()
 
for index in range(m):
    a_set.add(int(input()))
 
ans_list=[]
 
for index in range(n + 1):
    ans_list.append(0)
 
for index in range(n + 1):
    if index == 0:
        ans_list[index] += 1
        continue
    if index == 1 and (index not in a_set):
        ans_list[index] += ans_list[index - 1]
        continue
    
    if index not in a_set:
        if (index - 1) not in a_set:
            ans_list[index] += ans_list[index - 1]
            ans_list[index] %= 1000000007
        if (index - 2) not in a_set:
            ans_list[index] += ans_list[index - 2]
            ans_list[index] %= 1000000007
 
print(ans_list[n])

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

s = [0] * (n + 1)
s[-1] = 1
for _ in range(m):
    a = int(input())
    s[a] = None

if s[0] is None and s[1] is None:
    print(0)
    exit()

for i in range(n - 1, -1, -1):
    if s[i] is None:
        continue
    if i + 1 < len(s) and s[i + 1] is not None:
        s[i] += s[i + 1]
    if i + 2 < len(s) and s[i + 2] is not None:
        s[i] += s[i + 2]

print(s[0] % 1000000007)

Solution (Python):
import sys
input = sys.stdin.readline


def binary_search(l, value):
    low = 0
    high = len(l) - 1
    while low <= high:
        mid = (low + high) // 2
        if l[mid] == value:
            return True
        elif l[mid] < value:
            low = mid + 1
        else:
            high = mid - 1
    return False


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

A.append(10**6)
A.append(10**6)
B = [0] * (N + 1)
B[0] = 1
if binary_search(A, 1) is True:
    B[1] = 0
else:
    B[1] = 1
mod = 10**9 + 7

for i in range(2, N + 1):
    if i != 2 and binary_search(A, i - 1) is True and binary_search(
            A, i - 2) is True:
        print(0)
        exit()
    elif binary_search(A, i - 2) is True:
        B[i] = B[i - 1]
    elif binary_search(A, i - 1) is True:
        B[i] = B[i - 2]
    else:
        B[i] = B[i - 1] + B[i - 2]
    B[i] %= mod
print(B[N] % mod)

Solution (Python):
n,m = map(int,input().split())
lis = [int(input()) for i in range(m)]
dp = [0 for i in range(n+2)]
lis.append(0)
dp[0] = 1
cou = 0
co = 0
if lis[0] == 1:co += 1
for i in range(n):
  if i+1 != lis[cou]:
    dp[i+1] += dp[i]
    dp[i+1] %= 10 ** 9+7
  else:
    cou +=1
  if i+2 != lis[co]:
    dp[i+2] += dp[i]
    dp[i+2] %= 10 ** 9 + 7
  else:
    co += 1
print(dp[n])

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

a_set=set()

for index in range(m):
    a_set.add(int(input()))

ans_list=[]

for index in range(n + 1):
    ans_list.append(0)

for index in range(n + 1):
    if index == 0:
        ans_list[index] += 1
        continue
    if index == 1 and (index not in a_set):
        ans_list[index] += ans_list[index - 1]
        continue
    
    if index not in a_set:
        if (index - 1) not in a_set:
            ans_list[index] += ans_list[index - 1]
            ans_list[index] %= 1000000007
        if (index - 2) not in a_set:
            ans_list[index] += ans_list[index - 2]
            ans_list[index] %= 1000000007

print(ans_list[n])

Solution (Python):
from sys import stdin

N, M = [int(x) for x in stdin.readline().rstrip().split()]
a = [int(stdin.readline().rstrip()) for _ in range(M)]
fib = [1, 1]
for k in range(N):
    fib.append((fib[-1] + fib[-2]) % 1000000007)
if M == 0:
    print(fib[N])
    exit()
ans = fib[a[0] - 1]
for l in range(M - 1):
    if a[l + 1] - a[l] == 1:
        print(0)
        exit()
    ans = ans * fib[a[l + 1] - a[l] - 2]
ans = ans * fib[N - a[-1] - 1]
print(ans % 1000000007)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
import itertools



debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)

def solve():
    memo = {}

    def fib(n):
        if n in memo.keys():
            return memo[n]
        else:
            if n >= 4:
                ans = fib(n - 1) + fib(n - 2)
                memo[n] = ans
                return ans
            elif n == 3:
                return 2
            elif n == 2:
                return 1
            elif n == 1:
                return 1
            else:
                return 1

    n, m = map(int, input().split())
    w_list = []
    last = -1
    dead = False
    for i in range(m):
        a = int(input())
        w = a-last-1
        dprint(i, a, w)
        if w == 0:
            dead = True
            break
        w_list.append(w)
        last = a

    w_list.append((n+1)-last-1)

    dprint(w_list)

    mx = 10**9 + 7
    if dead == True:
        ans = 0
    else:
        ans = 1
        for w in w_list:
            fibw = fib(w)
            ans *= fibw
            dprint(w, fibw, ans)
            ans %= mx

    print(ans)

solve()

Solution (Python):
N,M  = map(int, input().split())
A = {}
mod = 10**9+7
for i in range(M):
    a = int(input())
    A[a] = 1
    if a-1 in A:
        print(0)
        exit()

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

for i in range(N):
    if i+1 not in A:
        stairs[i+1] = (stairs[i] + stairs[i+1]) % mod
    if i+2 not in A:
        stairs[i+2] = (stairs[i] + stairs[i+2]) % mod
        
print(stairs[N])

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

a_set=set()

for index in range(m):
    a_set.add(int(input()))

ans_list=[]

for index in range(n + 1):
    ans_list.append(0)

for index in range(n + 1):
    if index == 0:
        ans_list[index] += 1
        continue
    if index == 1 and (index not in a_set):
        ans_list[index] += ans_list[index - 1]
        continue
    
    if index not in a_set:
        if (index - 1) not in a_set:
            ans_list[index] += ans_list[index - 1]
            ans_list[index] %= 1000000007
        if (index - 2) not in a_set:
            ans_list[index] += ans_list[index - 2]
            ans_list[index] %= 1000000007

print(ans_list[n])

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

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

a = [0 for i in range(0, m)]
b = [True for i in range(0, n + 1)]
dp = [0 for i in range(0, n + 1)]

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

for i in range(0, m):
    b[a[i]] = False

dp[0] = 1

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

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

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

Solution (Python):
mod = 1000000007

N, M = [int(i) for i in input().split()]
A = [int(input()) for _ in range(M)] + [N + 1]

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

fib = [-1] * (N + 1)
fib[0] = 1
fib[1] = 1
for i in range(2, len(fib)):
    fib[i] = fib[i - 1] + fib[i - 2]


ans = 1
pre = -1
lo = 0
for a in A:
    f = fib[a - 1 - lo]
    ans = (ans * f) % mod

    lo = a + 1
    pre = a

print(ans)

Solution (Python):
import sys
import heapq

N, M = map(int,input().split())
a_lists = []

if N == 1:
    if M == 0:
        print (1)
        sys.exit()
    else:
        print(0)
        sys.exit()

for m in range (M):
    temp = int(input())
    a_lists.append(temp-1)

a_lists.append(10**6)

datas = [0]*N
if 0 in a_lists:
    datas[0] = 0
    heapq.heappop(a_lists) 
    
else:
    datas[0]=1

if 1 in a_lists:
    datas[1] = 0
    heapq.heappop(a_lists) 
else:
    datas[1]= datas[0]+1
    
heapq.heapify(a_lists)
    
for i in range (2,N):
    if i == a_lists[0]:
        datas[i] =0
        heapq.heappop(a_lists) 
    else:
        datas[i] = datas[i-1] + datas[i -2]

print(datas[-1]%1000000007)

Solution (Python):
import sys
INPUT = sys.stdin.readline
MOD = 10 ** 9 + 7

def SINGLE_INT(): return int(INPUT())
def MULTIPLE_INT_LIST(): return list(map(int, INPUT().split()))
def MULTIPLE_INT_MAP(): return map(int, INPUT().split())
def SINGLE_STRING(): return INPUT()
def MULTIPLE_STRING(): return INPUT().split()

def solve(n, m):
    floors = [0] * (n + 1)
    floors[0] = 1
    floors[1] = 1

    last, current = 0,0

    for i in range(m):
        if i == 0:
            current = SINGLE_INT()
            floors[current] = -1

        else:
            last = current
            current = SINGLE_INT()
            floors[current] = -1
            if current == last + 1:
                return 0

    for i in range(2, n+1):
        if floors[i] == -1:
            continue
        else:
            if floors[i-2] > 0:
                floors[i] += floors[i-2]
            if floors[i-1] > 0:
                floors[i] += floors[i-1]

        floors[i] %= MOD

    return(floors[-1])


N, M = MULTIPLE_INT_MAP()

if N == 1:
    print(1)

elif N > 1:
    print(solve(N,M))

Solution (Python):
from heapq import heappush, heappop, heapify, heapreplace
from collections import defaultdict


class Solution:
    def main_old(self):
        N, M = map(int, input().split())
        self.memo = {}
        for _ in range(M):
            a = int(input())
            self.memo[a] = 0
        res = self.rec(N)
        print(res)

    def main(self):
        N, M = map(int, input().split())
        A = set()
        for _ in range(M):
            A.add(int(input()))
        dp = [0] * (N+1)
        dp[0] = 1
        for i in range(0, N+1):
            
            if i+1 <= N and i+1 not in A:
                dp[i+1] += dp[i]
                dp[i + 1] %= 1000000007
            if i+2 <= N and i+2 not in A:
                dp[i+2] += dp[i]
                dp[i + 2] %= 1000000007
        print(dp[N])

    def rec(self, n):
        if n < 0:
            return 0
        elif n == 0:
            return 1
        elif n in self.memo:
            return self.memo[n]
        else:
            val = (self.rec(n-1) + self.rec(n-2)) %1000000007
            self.memo[n] = val
            return val


if __name__ == '__main__':
    Solution().main()

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

s = [0] * (N+1)

for i in range(M):
    ai = int(input())
    s[ai] = -1

s[0] = 1

if N == 1:
    print(1)
else:
    if s[1] == 0:
        s[1] = 1

    for i in range(2,N+1):
        if s[i] >= 0:
            s[i] += (max(0,s[i-1]) + max(0,s[i-2]))

    print(s[N] % 1000000007)

Solution (Python):
n, m = list(map(int, input().split()))
a = []
for i in range(m):
	a.append(int(input()))
a.sort()
f0 = 1
if len(a) > 0 and a[0] == 1:
	f1 = 0
else:
	f1 = 1
k = 0
for i in range(2, n + 1):
	while k < len(a) and a[k] < i:
		k += 1
	if k == len(a) or a[k] != i:
		f = (f0 + f1) % 1000000007
	else:
		f = 0
	f0 = f1
	f1 = f
	if f0 == f1 == 0:
		break
print(f1)

Solution (Python):
read = input 
rn = lambda :list(map(int, read().split()))
n, m  = rn()
M = []
P = 1000000007
for i in range(m):
    M.append(int(read()))
M = set(M)
dp = [0 for i in range(n + 1000)]
dp[0] = 1
for i in range(n+1):
    for nxt in range(i+1, i+3):
        if(nxt not in M):
            dp[nxt] += dp[i]
            dp[nxt] %= P
print(dp[n])

Solution (Python):
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

p = 1000000007
n,m = na()

dp = [1]*(n+1)

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

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

print(dp[-1])

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

for i in range(1, N + 1):
    if i == a[a_flag]:
        dp.append(0)
        while a[a_flag] == i:
            a_flag += 1
        continue
    dp.append(dp[i - 1] + dp[i])

print(dp[N + 1] % 1000000007)

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

for i in range(M):
  a.append(int(input()))
s=[1]
b=0 if 1 in a else 1
s.append(b)
p,q=-1,-1
j=-1
for i in range(2,N+1):
  while j<M:
    if a[j+1]<=i:
      j+=1
    else:
      break
  v=s[i-2]+s[i-1]
  if a[j]==i:
    v=0
  s.append(v%MOD)
print(s[N])

Solution (Python):

def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return list(input())
n,m=IL()
D=[True]*n
for i in range(m):
    D[I()-1]=False
A=[0]*n
if n==1:
    if D[0]:
        print(1)
    else:
        print(0)

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

Solution (Python):
MOD = int(1e9 + 7)

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

A.sort(reverse=True)

for i in range(M-1):
  if A[i+1] - A[i] == 1:
    print(0)
    exit(0)
  
dp = [0] * (N+1)
dp[0] = 1
for i in range(N):
  if len(A) > 0 and i+1 == A[-1]:
    A.pop()
  else:  
    dp[i+1] = (dp[i] + dp[i-1]) % MOD
'''
  if len(A) < 1:
    dp[i+1] = (dp[i] + dp[i-1]) % MOD
  elif i-1 < 0 or i-1 == A[-1]:
    dp[i+1] = dp[i] % MOD
  elif i == A[-1]:
    dp[i+1] = dp[i-1] % MOD
  else:
    dp[i+1] = (dp[i] + dp[i-1]) % MOD
'''
print(dp[N])

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

X = 1000000007

flags = [True for _ in range(N+1)]
for i in range(M):
    a = int(input())
    flags[a] = False

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

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

    if flags[i-1] == False:
        counts[i] = counts[i-2]
    elif flags[i-2] == False:
        counts[i] = counts[i-1]
    else:
        counts[i] = (counts[i-2] + counts[i-1]) % X

print(counts[N])

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

for i in range(m+1):
    diff = b[i]
    dp = [1, 1]
    if i != 0 and diff == 0:
        print(0)
        exit()
    for j in range(diff-2):
        dp.append(dp[j]+dp[j+1])
    ans *= dp[-1]
    ans %= mod
print(ans)

Solution (Python):

def dp(a):
	dp_list = [ 1 for i in range(a+1) ]
	for i in range(2,a+1):
		dp_list[i] = (dp_list[i-1] + dp_list[i-2]) % mod
	return dp_list

n, m = [ int(v) for v in input().split() ]
mod = 10**9+7
l, r = 0, 0
s = 0
stop = 0
c = -100
step_list = [ None for i in range(m+1) ]

for i in range(m):
	b = int(input())
	l, r = b-1,b+1
	d = l-s
	step_list[i] = d
	s = r
	if b == c+1:
		stop = 1
		break
	c = b
	
step_list[-1] = (n-r)


if stop == 0:
	ans = 1
	step2_list = dp(max(step_list))
	for i in step_list:
		ans = (ans*step2_list[i])%mod

	print(ans)
else:
	print(0)

Solution (Python):







import sys
from itertools import combinations, permutations 
from math import factorial
def combinations_count(n, r):
    
    
    
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n
    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]
    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
    return result
def combination_with_repetition_count(n, r):
    return combinations_count(n + r - 1, r)
from collections import deque, Counter 
from heapq import heapify, heappop, heappush, heappushpop, heapreplace,nlargest,nsmallest 
from copy import deepcopy, copy 
from functools import reduce
from fractions import gcd 
def gcds(numbers):
    return reduce(gcd, numbers)
def lcm(i, y):
    return (i * y) // gcd(i, y)
def lcms(numbers):
    return reduce(lcm, numbers, 1)

    
    
    
    
    
    
    
    
    







R = lambda: list(map(int, input().split()))
n, m = R()
a = [int(input()) for i in range(m)]




dp = [-1] * (n+1)
for i in a:
    dp[i] = 0
dp[0] = 1
if dp[1] != 0:
    dp[1] = 1

for i in range(n+1):
    if dp[i] > -1:
        pass
    else:
        dp[i] = dp[i-1] + dp[i-2]

print(dp[-1] % 1000000007)

Solution (Python):

N,M = map(int,input().split())
a = []
d = {}
MOD = 10**9+7
for i in range(N+1):
    d[i] = 0
for i in range(M):
    a.append(int(input()))
    d[a[i]] = 1

dp = [0] *(N+1)

dp[0] = 1
if d[1] == 0:
    dp[1] = 1

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

    if d[i] == 0:
        dp[i] = dp[i-1] + dp[i-2]
    else:
        dp[i] = 0

print(dp[N]%MOD)

Solution (Python):
N, M = map(int, input().split())
m = 0
if M > 0:
  broken = int(input())
else:
  broken = 0
a1, a2, a3 = 1, 0, 0
for i in range(1, N+1):
  a3, a2 = a2, a1
  if i == broken:
    a1 = 0
    m += 1
    if m < M:
      broken = int(input())
  else:
    a1 = (a2 + a3) % 1000000007
print(a1)

Solution (Python):

mod = 1000000007
n, m = list(map(int, input().split()))
dp = [0]*(n+1)
dp[0] = 1
dp[1] = 1
for _ in range(m):
    ai = int(input())
    dp[ai] = -1

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

Solution (Python):
N, M = map(int, input().split())
a = [0 for i in range(M)]
sosu = 10 ** 9 + 7
for i in range(M):
    a[i] = int(input())
seta = list(set(a))
seta.sort()
dp = [0 for i in range(N+1)]
dp[0] = 1
now = 0
for i in range(1, N+1):
    if now <= M-1 and i == seta[now]:
        now += 1
    elif i >= 2:
        dp[i] = (dp[i-2] + dp[i-1]) % sosu
    elif i == 1:
        dp[i] = dp[i-1]

print(dp[N])

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

a = [int(input()) for _ in range(M)]
a .append(N+10)

mod_num = 10 ** 9 + 7


def check(target, _pointer):
    while _pointer < M + 2:
        if a[_pointer] == target:
            return True, _pointer
        elif a[_pointer] < target:
            _pointer += 1
        else:
            return False, _pointer


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

step[0] = 1
step[1] = 1 if a[0] != 1 else 0

pointer = 0

for i in range(2, N + 1):
    is_broken, pointer = check(i, pointer)
    step[i] = 0 if is_broken else (step[i - 1] + step[i - 2]) % mod_num

print(step[-1])

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

step_route = [-1] * (N+1)

step_route[0] = 1
step_route[1] = 1

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

for j in range(2,N+1):  
    if step_route[j] == -1:
        step_route[j] = step_route[j-1] + step_route[j-2]
    
print(step_route[N] % 1000000007)

Solution (Python):
N, M = map(int, input().split())
a = []
stair = [1 for i in range(N+2)]
for i in range(M):
    stair[int(input())] = 0

dp = [0 for i in range(N+2)]
dp[0] = 1

MOD = 1000000007

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

print(dp[N])

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

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

for i in range(N):
    c=l[i]%1000000007
    if i>N-2:
        if i not in a:
            l[i+1]+=c
    elif i not in a:
        l[i+1]+=c
        l[i+2]+=c

print(l[N]%1000000007)

Solution (Python):



from collections import defaultdict

N, M = map(int, input().rstrip().split(' '))
if M == 0:
    A = [0]
else:
    A = sorted([int(input()) for _ in range(M)]) + [N + 1]
    
dp = [0] * (N+1)
dp[0] = 1
if A[0] != 1:
    dp[1] = 1
    index_A = 0
else:
    dp[1] = -1
    index_A = 1
    
for i in range(2,N+1):
    if A[index_A] == i:
        dp[i] = -1
        index_A += 1
    else:
        if dp[i-1] != -1:
            dp[i] += dp[i-1]
        if dp[i-2] != -1:
            dp[i] += dp[i-2]
            
print(dp[N] %  (1000000007))

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

Solution (Python):
import sys
N,M=map(int, raw_input().split())

NG=[ 0 for i in range(N+1) ]
for i in range(M):
	a=int( sys.stdin.readline().strip() )
	NG[a]=1

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

mod=10**9+7

for i in range(N):
	if i+1<=N and NG[i+1]==0:
		dp[i+1]+=dp[i]
		dp[i+1]%=mod
	if  i+2<=N and NG[i+2]==0:
		dp[i+2]+=dp[i]
		dp[i+2]%=mod

print dp[N]%mod

Solution (Python):
read = input 
rn = lambda :list(map(int, read().split()))
n, m  = rn()
M = []
P = 1000000007
for i in range(m):
    M.append(int(read()))
M = set(M)
dp = [0 for i in range(n + 10)]
dp[0] = 1
for i in range(n+1):
    for nxt in range(i+1, i+3):
        if(nxt not in M):
            dp[nxt] += dp[i]
            dp[nxt] %= P
print(dp[n])

Solution (Python):
N,M = map(int,input().split())
A = [int(input()) for _ in range(M)]
MOD = 10**9+7
table = [0]*(N+1)
table[0] = 1
broken = [1]*(N+1)
for a in A:
    broken[a] = 0

for i in range(N+1):
    if i+1<=N and broken[i+1]:
        table[i+1] += table[i]
    if i+2<=N and broken[i+2]:
        table[i+2] += table[i]

print(table[N]%MOD)

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

counts = [0] * (N + 1)
for i in range(N + 1):
    if i == 0:
        counts[i] = 1
    elif i == 1:
        if i not in A:
            counts[i] = 1
    else:
        if i not in A:
            for j in [i - 2, i - 1]:
                if j not in A:
                    counts[i] += counts[j]
                    counts[i] %= 1000000007

print(counts[N])

Solution (Python):

import copy
import random
import bisect 
import fractions 
import math
import sys

mod = 10**9+7
sys.setrecursionlimit(mod) 


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

miss_stairs = [0 for i in range(N)]
for i in range(M):
    miss_stairs[a[i]-1] = 1


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


print(dp[-1]% mod)

Solution (Python):
N, M = map(int, input().split())
s = set()
for i in range(M):
    s.add(int(input()))
l = [0, 1]
for i in range(1, N+1):
    if i in s:
        l.append(0)
    else:
        tmp = (l[-1] + l[-2]) % 1000000007
        l.append(tmp)

ans = l[-1]
print(ans)

Solution (Python):
import sys
N,M = map(int, input().strip().split(' '))
broken = set(int(line.strip()) for line in sys.stdin) if M > 0 else set()
p = [0]*(N+2)
p[0] = 1
for i in range(N):
  
  if i in broken:
    continue
  p[i+1] += p[i]
  p[i+2] += p[i]
print(p[N]%1000000007)

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

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 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 input()

def main():
    N, M = LI()
    A = []
    for _ in range(M):
        A.append(II())
    A.append(INF)
    pre = 0
    cur = 1
    k = 0
    for i in range(1, N + 1):
        if i == A[k]:
            k += 1
            pre = cur
            cur = 0
        else:
            tmp = cur
            cur = (cur + pre) % MOD
            pre = tmp
    ans = cur
    return ans

print(main())

Solution (Python):
ll = lambda: list(map(int, input().split()))
testcases = 1

for testcase in range(testcases):
    [n,m]=ll()
    broken=[1]*(n+1)
    
    for i in range(m):
        [ai]=ll()
        broken[ai]=0
    ans=[0]*(n+1)
    ans[0]=1
    ans[1]=1*broken[1]
    for i in range(2,n+1):
        ans[i] = (ans[i-1]*broken[i-1] + ans[i-2]*broken[i-2])%(10**9+7)
    
    print(ans[n])

Solution (Python):
mod = 1000000007

n, m = list(map(int, input().split()))
nums = [int(input()) for _ in range(m)]
 
dp = [1] + [0 for _ in range(n)]

if len(nums) > 0 and nums[0] == 1:
	del nums[0]
else:
	dp[1] = 1
	

for i in range(2, n + 1):
	
	if len(nums) ==  0:
		dp[i] = (dp[i - 1] + dp[i - 2]) % mod
	else:
		for j in range(len(nums)):
			if nums[j] > i:
				dp[i] = (dp[i - 1] + dp[i - 2]) % mod
				break
			elif nums[j] == i:
				del nums[:(j + 1)]
				break


print(dp[-1])

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

def Fib(n1):
    a1, b1 = 0, 1
    if n1 == 1:
        return a1
    elif n1 == 2:
        return b1
    else:
        for i in range(n1-2):
            a1, b1 = b1, a1 + b1
        return b1

l = []
pre = -1
for x in a:
    if x-pre == 1:
        print(0)
        exit()
    l.append(Fib(x-pre-1 +1))
    pre = x

l.append(Fib(n-pre +1))

res = 1
for x in l:
    res *= x

print(res % 1000000007)

Solution (Python):
MOD = 10**9 + 7
N, M = [int(x) for x in input().split()]
a = set()
for i in range(M):
    a.add(int(input()))

dp = [0]*(N + 1)
dp[0] = 1
for step in range(N):
    if not step in a:
        for width in [1, 2]:
            to = step + width
            if to <= N and not to in a:
                dp[to] = (dp[to] + dp[step]) % MOD

print(dp[N])

Solution (Python):
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

N, M = list(map(int, sys.stdin.readline().split()))
A = [int(sys.stdin.readline()) for _ in range(M)]

MOD = 10 ** 9 + 7
A = np.array(A)



def mod_invs(max, mod):
    """
    逆元のリスト 0 から max まで
    https://atcoder.jp/contests/abc127/submissions/5630531
    ここから。あんまり良くわかってない
    :param max:
    :param mod:
    :return:
    """
    invs = [1] * (max + 1)
    for x in range(2, max + 1):
        invs[x] = (-(mod // x) * invs[mod % x]) % mod
    return invs


def get_factorials(max, mod=None):
    """
    階乗 0!, 1!, 2!, ..., max!
    :param int max:
    :param int mod:
    :return:
    """
    ret = [1]
    n = 1
    if mod:
        for i in range(1, max + 1):
            n *= i
            n %= mod
            ret.append(n)
    else:
        for i in range(1, max + 1):
            n *= i
            ret.append(n)
    return ret


def can_go():
    
    return len(A) < 2 or min(np.diff(A)) > 1


factorials = get_factorials(N, MOD)


def mod_inv(a, mod):
    """
    a の逆元
    :param int a:
    :param int mod:
    :return:
    """
    return pow(a, mod - 2, mod)


def ncr(n, r, mod=None):
    """
    scipy.misc.comb または scipy.special.comb と同じ
    組み合わせの数 nCr
    :param int n:
    :param int r:
    :param int mod: 3 以上の素数であること
    :rtype: int
    """
    if n < r:
        return 0

    
    return (
            factorials[n]
            * mod_inv(factorials[r], mod)
            * mod_inv(factorials[n - r], mod)
            % mod
    )


if not can_go():
    print(0)
    exit()


def count(n):
    ans = 0
    for r in range(n):
        if r > n - r:
            break
        ans += ncr(n - r, r, MOD)
    return max(1, ans)


step = 0
ans = 1
for a in A:
    ans = ans * count(a - step - 1) % MOD
    step = a + 1
ans *= count(N - step)
print(ans % MOD)

Solution (Python):

import sys

sys.setrecursionlimit(100000)



def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m


def slv(N, M, A):
    m = Mod(10**9 + 7)
    dp = [0] * (N+10)
    b = [False] * (N+10)
    for a in A:
        b[a] = True

    dp[0] = 1
    for i in range(N):
        if not b[i+1]:
            dp[i+1] = m.add(dp[i+1], dp[i])
        if not b[i+2]:
            dp[i+2] = m.add(dp[i+2], dp[i])
    return dp[N]


def main():
    N, M = read_int_n()
    A = [read_int() for _ in range(M)]
    print(slv(N, M, A))


if __name__ == '__main__':
    main()

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

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

for i in range(N):
    if i == 0:
        if a[i] != '!':
            a[i] = 1
        else:
            a[i] = 0
    elif i == 1:
        if a[i] != '!':
            a[i] = a[i-1] + 1
        else:
            a[i] = 0
    else:
        if a[i] != '!':
            a[i] = a[i-1] + a[i-2]
        else:
            a[i] = 0

print(a[N-1] % 1000000007)