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 _ in range(M)]
dp = [0] * (N+1)
mod = 10**9 + 7

for i in range(M):
    dp[a[i]] = -1

if N == 1:
    print(1)
elif N == 2:
    if dp[1] == -1:
        print(1)
    else:
        print(2)
else:
    dp[0] = 1
    if dp[1] != -1 and dp[2] != -1:
        dp[1] = 1
        dp[2] = dp[0] + dp[1]
    elif dp[1] == -1 and dp[2] != -1:
        dp[2] = 1
    elif dp[1] != -1 and dp[2] == -1:
        dp[1] = 1
    else:
        print(0)
        exit()
    
    
    for i in range(3, N+1):
        if dp[i] == -1:
            continue
        elif dp[i-1] == -1 and dp[i-2] != -1:
            dp[i] = dp[i-2]
        elif dp[i-1] != -1 and dp[i-2] == -1:
            dp[i] = dp[i-1]
        elif dp[i-1] != -1 and dp[i-2] != -1:
            dp[i] = dp[i-1] + dp[i-2]
        else:
            print(0)
            exit()
    
    print(dp[N] % mod)

Solution (Python):
import sys
N,M = map(int, input().strip().split(' '))
if M > 0:
  broken = set(int(line.strip()) for line in sys.stdin)
else:
  broken = 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())
l=[0]*(n+1)
mod=10**9+7
M=set([int(input()) for _ in range(m)])
for i in M:
    l[i]=-1
l[0]=1
for i in range(n):
    if l[i]!=-1:
        if l[i+1]!=-1:
            l[i+1]=(l[i+1]+l[i])%mod
        if i+2<=n:
            if l[i+2]!=-1:l[i+2]=(l[i+2]+l[i])%mod
print(l[n])

Solution (Python):
MOD = 1000000007

n, m = map(int, input().split())
broken = [False] * (n + 1)
for _ in range(m):
    broken[int(input())] = True
dp = [0] * (n + 1)
dp[0] = 1 if not broken[0] else 0
dp[1] = 1 if (dp[0] and not broken[1]) else 0
for i in range(2, n + 1):
    if broken[i]:
        continue
    dp[i] = (dp[i - 2] + dp[i - 1]) % MOD
print(dp[n])

Solution (Python):
import sys,heapq
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True 
def ddprint(x):
  if DBG:
    print(x)

R = 1000000007

n,m = inm()
b = [0] * (n+2)
b[0] = 1
bad = [False] * (n+2)
for i in range(m):
    bad[inn()] = True

for i in range(1,n+1):
    if bad[i]:
        if bad[i-1]:
            print(0)
            exit()
        else:
            continue
    else:
        b[i] = (b[i-1] + b[i-2]) % R

print(b[n])

Solution (Python):

import sys
def input(): return sys.stdin.readline().rstrip()
def mi(): return map(int, input().split())


N, M = mi()


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

As = [int(input()) for _ in range(M)]

stairs = ['.'] * (N+1)


for a in As:
  stairs[a] = '
stairs = ''.join(stairs)


if '
  print(0)
  exit()



DP = [0]*(N+1)

DP[0] = 1

DP[1] = 1 if stairs[1] == '.' else 0


for i in range(2,N+1):
  DP[i] = (DP[i-2]+DP[i-1])%1000000007 if stairs[i] == '.' else 0

print(DP[N])

Solution (Python):
MAX = 1000000007

def solve():
    N, M = [int(_) for _ in raw_input().split()]
    a = [None] * M
    for i in range(M):
        a[i] = int(raw_input())
    ok = [1] * (N+1)
    for i in range(M):
        ok[a[i]] = 0
    ret = [1] * (N+1)
    ret[N-1] = ok[N-1]
    for i in range (N-2,-1,-1):
        ret[i] = (ret[i+1] * ok[i+1] + ret[i+2] * ok[i+2]) % MAX
    print ret[0]

if __name__ == '__main__':
    solve()

Solution (Python):
N,M=map(int,input().split())
num=[0]*(N+1)
num[0]=1
num[1]=1

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

P=10**9+7
index=0

if 1 in A:
    num[1]=0
    index+=1


if N>=2:
    for i in range(2,N+1):
        num[i]=(num[i-1]+num[i-2])%P
        if index<=M-1 and i==A[index]:
            num[i]=0
            index+=1

print(num[N])

Solution (Python):
mod=10**9+7
N,M=map(int,input().split())
alist = [True]*(N+1)
for i in range(M):
  alist[int(input())] = False


reslist = [0]*(N+1)
reslist[0] = 1
if alist[1]:
  reslist[1] = 1

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

print(reslist[N])

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

class comb():
  F = [1, 1]
  Fi = [1, 1]
  I = [0, 1]
  def __init__(self, num, mod):
    self.MOD = mod
    for i in range(2, num + 1):
      self.F.append((self.F[-1] * i) % mod)
      self.I.append(mod - self.I[mod % i] * (mod // i) % mod)
      self.Fi.append(self.Fi[-1] * self.I[i] % mod)
  def com(self, n, k):
    if n < k: return 0
    if n < 0 or k < 0: return 0
    return self.F[n] * (self.Fi[k] * self.Fi[n - k] % self.MOD) % self.MOD


MOD = 10 ** 9 + 7

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

com = comb(200000, MOD)
ans = 1
x = 0
a = a + [N + 1]

for i in a:
  t = i - 1 - x
  at = 0
  for j in range(t // 2 + 1):
    k = t - j
    at = at + com.com(k, j) % MOD
  ans = ans * at % MOD
  x = i + 1
  

print(ans)

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

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

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):
N,M = map(int,input().split())
A = []
B = [0] * (N + 5)

for i in range(M):
  A.append(int(input()))
  B[A[-1]] = -1
  
B[0] = 1
for i in range(N + 1):
  if B[i] == -1:
    continue
  if B[i + 1] != -1:
    B[i + 1] += B[i]
    B[i + 1] %= 1000000007
  if B[i + 2] != -1:
    B[i + 2] += B[i]
    B[i + 2] %= 1000000007
print(B[N])

Solution (Python):

MOD =  1000000007

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

a_list = set()
for _ in range(M):
	a_list.add(int(input()))



counts = [0] * (N + 10)
counts[0] = 1
for i in range(N):
	if not i in a_list:
		counts[i + 1] = (counts[i + 1] + counts[i]) % MOD
		counts[i + 2] = (counts[i + 2] + counts[i]) % MOD


print(counts[N])

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

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

MOD = 10 ** 9 + 7

N, M = MULTIPLE_INT_MAP()

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

for _ in range(M):
    floors[SINGLE_INT()] = -1

for i in range(2, N+1):

    if floors[i] == -1:
        continue

    if floors[i-2] == floors[i-1] == -1:
        floors[-1] = 0
        break

    if floors[i-2] > 0:
        floors[i] += floors[i-2]
    if floors[i-1] > 0:
        floors[i] += floors[i-1]

    floors[i] %= MOD

print(floors[-1])

Solution (Python):
MODULO = 1000000007


def solve(n, xs):
    dp = [0] * (n + 1)
    dp[0] = 1
    dp[1] = 1 if 1 not in xs else 0
    for i in range(2, n + 1):
        if i in xs:
            dp[i] = 0
        else:
            if i - 1 not in xs:
                dp[i] += dp[i - 1]
            if i - 2 not in xs:
                dp[i] += dp[i - 2]
        dp[i] %= MODULO
    return dp[n]
         


def main():
    n, m = (int(z) for z in input().split())
    xs = {int(input()) for _ in range(m)}
    res = solve(n, xs)
    print(res)


if __name__ == "__main__":
    main()

Solution (Python):
from collections import defaultdict


def read_input():
    n, m = map(int, input().split())

    d = defaultdict(lambda : True)
    for i in range(m):
        d[int(input())] = False

    return n, m, d


def submit():
    n, m, d = read_input()

    prev = 1
    prev_prev = 0
    curr = 1
    for i in range(1, n + 1):
        curr = 0
        if d[i - 1]:
            curr += prev
        if d[i - 2]:
            curr += prev_prev

        curr %= 1000000007

        prev_prev = prev
        prev = curr

    print(curr)


if __name__ == '__main__':
    submit()

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

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

idx = 0
for pos in range(1, N + 1):
    if a[idx] == pos:
        memo[pos] = 0
        idx += 1
        continue
    else:
        if pos > a[idx]:
            idx += 1
        
        if pos == 1:
            memo[1] = (memo[0]) % (10 ** 9 + 7)
        else:
            memo[pos] = (memo[pos - 2] + memo[pos - 1]) % (10 ** 9 + 7)


print(memo[-1])

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N,M=MAP()
broken=[False]*(N+1)
for i in range(M):
    a=INT()
    broken[a]=True

dp=[0]*(N+7)
dp[0]=1
for i in range(N):
    if not broken[i+1]:
        dp[i+1]+=dp[i]
        dp[i+1]%=MOD
    if i!=N-1 and not broken[i+2]:
        dp[i+2]+=dp[i]
        dp[i+2]%=MOD
print(dp[N])

Solution (Python):
n,m = map(int,input().split())
judge = [True for i in range(n+1)]
for i in range(m):
    judge[int(input())] = False
dp = [0]*(n+1)
dp[0] = 1
for i in range(n):
    if i + 1 > n:continue
    if judge[i + 1]:dp[i+1] = (dp[i] +dp[i+1]) %1000000007
    if i + 2 > n:continue
    if judge[i + 2]:dp[i+2] = (dp[i] + dp[i+2]) %1000000007
print(dp[-1]%1000000007)

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

mod = 10**9+7
stair_set = set(range(0, N)[::-1])
stair_set = stair_set - set(a)
stair_list = list(stair_set)
stair_list.sort(reverse=True)

for i in stair_list:
    if i == N-1:
        dp[N - 1] = 1
        continue
    if i == N-2:
        dp[N - 2] = 1 + dp[N - 1]
        continue
    dp[i] = (dp[i+1] + dp[i+2])%mod

print(dp[0])

Solution (Python):

N,M=map(int,input().split())
dp=[0]*(10**5+1)
table=[0]*(10**5+1)
for i in range(M):
    a=int(input())
    table[i]=a

dp[0]=1

count=0
if table[count]==1:
    dp[1]=0
    count+=1
else:
    dp[1]=1

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


print(dp[N]%1000000007)

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

mod = 10 ** 9 + 7

dp = [0] * (N + 100)
dp[0] = 1
a_set = set(a_list)

for i in range(N):
    if i in a_set:
        continue
    else:
        dp[i + 1] += dp[i]
        dp[i + 1] %= mod
        dp[i + 2] += dp[i]
        dp[i + 2] %= mod

print(dp[N] % mod)

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

if not B[0]:
    print(0)
    exit()

dp = [0]*(N+1)
dp[0] = 1
for i in range(N):
    if B[i+1]:
        dp[i+1] += dp[i]
    if i+2 <= N and B[i+2]:
        dp[i+2] += dp[i]
print(dp[-1] % MOD)

Solution (Python):

mod = 10**9 + 7
n, m = map(int, input().split())
ok = [True] * (n + 1)
if m > 0:
    a = [int(input()) for _ in range(m)]
    for x in a:
        ok[x] = False
dp = [0] * (n + 1)
dp[0] = 1
for i in range(n + 1):
    if i > 0 and ok[i - 1]:
        dp[i] = (dp[i] + dp[i - 1]) % mod
    if i > 1 and ok[i - 2]:
        dp[i] = (dp[i] + dp[i - 2]) % mod
print(dp[n])

Solution (Python):
import collections as c
ip = lambda : map(int, input().split())

mod = 1e9+7
N,M = ip()
a = set()
for i in range(M):
    a.add(int(input()))
dp = [0]*(N+1)
dp[0] = 1
if 1 in a:
    pass
else:
    dp[1] = dp[0]
if N>1:
    for i in range(2,N+1):
        if i in a:
            continue
        dp[i] += (dp[i-2] + dp[i-1])%mod
        dp[i] = int(dp[i] % mod)
print(dp[N])

Solution (Python):
def solve():
    mod = 10**9+7
    N, M = map(int, input().split())
    k = [0]*(N+1)
    if M==0:
        k[0]=1
        k[1]=1
        for i in range(2, N+1):
            k[i]=(k[i-1]+k[i-2])%mod
        print(k[N]%mod)
        return
    a = [int(input()) for _ in range(M)]
    k[0]=1
    cnt = 0
    if a[0]!=1:
        k[1]=1
    else:
        cnt+=1
    for i in range(2, N+1):
        if cnt<M and i ==a[cnt]:
            cnt+=1
            continue
        else:   
            k[i]=(k[i-1]+k[i-2])%mod
    print(k[N]%mod)
    return
solve()

Solution (Python):
n, m = map(int, input().split())
br = [False] * (n+1)
for _ in range(m):
    x = int(input())
    br[x] = True

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

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

dp = [0, 1]

for i in range(N):
    if i+1 == a[j]:
        dp.append(0)
        while i+1==a[j]:
            j+=1
    else:
        dp.append((dp[i]+dp[i+1]) % 1000000007)

print(dp[-1])

Solution (Python):
ll = lambda: list(map(int, input().split()))
testcases = 1
def abs(x):
    if x<0:
        return -x
    return x

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] + ans[i-2]*broken[i])%(10**9+7)
    
    print(ans[n])

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

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

for i in range(1, n + 1):
    if a[i] == 1:
        tmp[i] = 0
    else:
        if i - 2 >= 0:
            tmp[i] += tmp[i - 2]
        if i - 1 >= 0:
            tmp[i] += tmp[i - 1]
        tmp[i] %= 1000000007

print(tmp[n] % 1000000007)

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

Solution (Python):

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

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


print(dp[N])

Solution (Python):
n, m = map(int, input().split())
a = [int(input()) for i in range(m)]
MOD = 10**9 + 7
memo = {}
for i in range(n+1):
    memo[i] = 1
for i in range(m):
    memo[a[i]] = 0

dp = [0] * (n+1)

dp[0] = 1
dp[1] = memo[1]

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

Solution (Python):
mod = 10 ** 9 + 7
N, M = map(int, input().split())
F = [0, 1]
fib_minus1 = 1
fib_minus2 = 0
for i in range(N):
	fib = (fib_minus1 + fib_minus2) % mod
	F.append(fib)
	fib_minus2 = fib_minus1
	fib_minus1 = fib
x = 1
a = -1
for i in range(M):
	b = int(input())
	x = (x * F[b - a - 1]) % mod
	a = b
x = (x * F[N - a]) % mod
print(x)

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


if n==1 and k == 1:
    print(0)
else:
    print(dp[-1]%mod)

Solution (Python):


import sys
def input(): return sys.stdin.readline().strip()

MOD = 10**9 + 7


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


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

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

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

print(dp[N])

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)



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


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


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

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

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)


m = Mod(10**9 + 7)


def slv(N, M, A):
    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):

def ispossible(a):
    d = [a[i] - a[i-1] for i in range(1, len(a))]
    return not 1 in d


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

    MOD = 10**9+7

    if not ispossible(a):
        print(0)
        return

    s = [1] * (N+1)

    a = set(a)

    for i in a:
        s[i] = -1

    for i in range(2, N+1):
        if i in a:
            continue

        s[i] = 0
        if i-1 not in a:
            s[i] += s[i-1]
            s[i] %= MOD
        if i-2 not in a:
            s[i] += s[i-2]
            s[i] %= MOD

    print(s[N] % MOD)


if __name__ == '__main__':
    main()

Solution (Python):
N, M = list(map(int,input().split()))
A = []
S = [0 for i in range(N+1)]
S[0] = 1
for i in range(M):
  s = int(input())
  A.append(s)
  S[s] = -1
for i in range(N+1):
  if S[i] == -1:
    continue
  if i+1 <= N:
    if S[i+1] == 0:
      S[i+1] = S[i]
    elif S[i+1] > 0:
      S[i+1] += S[i]
  if i+2 <= N:
    if S[i+2] == 0:
      S[i+2] = S[i]
    elif S[i+2] > 0:
      S[i+2] += S[i]
print (S[-1]%1000000007)

Solution (Python):
N, M = map(int, input().split())
div = 10**9+7
A = [0 for i in range(N+1)]
A[0] = 1
for i in range(M):
    a = int(input())
    A[a] = -1
for i in range(N):
    if A[i] == -1:
        continue
    now = A[i]
    if A[i+1] != -1:
        A[i+1] += now * 1
    if i < N-1 and A[i+2] != -1:
        A[i+2] += now * 1

print(A[-1] % div)

Solution (Python):


import itertools
from collections import Counter
from collections import defaultdict
import bisect
from heapq import heappush, heappop

def main():
    MOD = 1000000007

    N, M = map(int, input().split())
    A = set()
    for _ in range(M):
        a = int(input())
        A.add(a)

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

    
    print(dp[N] % MOD)


if __name__ == '__main__':
    main()

Solution (Python):
N,M = map(int,input().split(' '))
MOD = 1000000007
a = [int(input()) for i in [0]*M]

a.append(-1)
a.append(N+1)

a.sort()

ds = [a[i+1] - a[i] - 1 for i in range(0,M+1)]

if 0 in ds:
	print(0)
	exit()

k = max(ds)

a = [0,1]
for i in range(2,k+1):
	a.append((a[i-2]+a[i-1]) % MOD)

ans = 1

for d in ds:
	ans = (ans * a[d] ) % MOD

print(ans)

Solution (Python):
N,M = (int(x) for x in input().split())
a_arr = [-1]
for _ in range(M):
    a_arr.append(int(input()))
a_arr.append(N+1)

n_dp_size = N+3
n_dp = [0]*(n_dp_size)
n_dp[0] = 1
n_dp[1] = 0
n_dp[2] = 1
for i in range(3,n_dp_size):
    n_dp[i] = (n_dp[i-2]+n_dp[i-1]) % 1000000007

ans = 1
for i in range(1,len(a_arr)):
    a_diff = a_arr[i]-a_arr[i-1]
    ans *= n_dp[a_diff]
    ans = ans % 1000000007

print(ans)

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

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

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

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

if l.count(0) > 0:
    print(0)
    exit()

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

print(res % 1000000007)

Solution (Python):
def getlist():
	return list(map(int, input().split()))

N, M = getlist()
L = [0 for i in range(N + 100)]
L[0] = 1

for i in range(M):
	a = int(input())
	L[a] = -1


for i in range(N):
	if L[i] != -1:
		if L[i + 1] != -1:
			L[i + 1] += L[i]
			L[i + 1] = L[i + 1] % 1000000007
		if L[i + 2] != -1:
			L[i + 2] += L[i]
			L[i + 2] = L[i + 2] % 1000000007


print(L[N] % 1000000007)

Solution (Python):


import sys

class bigint:
    def __init__(self,n,mod=10**9+7):
        self.n = n % mod
        self.mod = mod
        return
    
    def __str__(self):
        return str(self.n)
    
    def __add__(self,other):
        assert self.mod==other.mod, "modulos of the two not match"
        return bigint(self.n+other.n,self.mod)
    
    def __iadd__(self,other):
        assert self.mod==other.mod, "modulos of the two not match"
        self.n = (self.n + other.n) % self.mod
        return self
    
    def __sub__(self,other):
        assert self.mod==other.mod, "modulos of the two not match"
        return bigint(self.n-other.n,self.mod)
    
    def __isub__(self,other):
        assert self.mod==other.mod, "modulos of the two not match"
        self.n = (self.n - other.n) % self.mod
        return self


n,m = [ int(x) for x in sys.stdin.readline().split() ]
step= [bigint(0)] * (n+1)
wall= [False] * (n+1)
for i in range(m):
    am = int( sys.stdin.readline() )
    wall[am] = True

step[0]= bigint(1)
if not wall[1]: step[1]= bigint(1)

for i in range(2,n+1):
    if wall[i]: continue
    s1= step[i-1]
    s2= step[i-2]
    if s1==s2==0: break
    step[i] = s1 + s2

print( step.pop() )

Solution (Python):
MOD = 1000000007

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

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

print(dp[-1] % MOD)

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

class comb():
  F = [1, 1]
  Fi = [1, 1]
  I = [0, 1]
  def __init__(self, num, mod):
    self.MOD = mod
    for i in range(2, num + 1):
      self.F.append((self.F[-1] * i) % mod)
      self.I.append(mod - self.I[mod % i] * (mod // i) % mod)
      self.Fi.append(self.Fi[-1] * self.I[i] % mod)
  def com(self, n, k):
    if n < k: return 0
    if n < 0 or k < 0: return 0
    return self.F[n] * (self.Fi[k] * self.Fi[n - k] % self.MOD) % self.MOD


MOD = 10 ** 9 + 7

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

com = comb(N, MOD)
ans = 1
x = 0
a = a + [N + 1]

for i in a:
  t = i - 1 - x
  at = 0
  for j in range(t // 2 + 1):
    k = t - j
    at = at + com.com(k, j) % MOD
  ans = ans * at % MOD
  x = i + 1
  

print(ans)

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

a = [0] * (n+1)
for i in x:
    a[i] = 1

dp = [1]

if a[1] == 1:
    dp.append(0)
else :
    dp.append(1)

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

print(dp[n])

Solution (Python):
def gcd_core(a, b):
    if b == 0:
        return a
    else:
        return gcd_core(b, a % b)


def gcd(arr):
    g = gcd_core(arr[0], arr[1])
    for i in range(2, len(arr)):
        g = gcd_core(g, arr[i])
    return g




n,m = map(int,input().split())
a = {}
base = 1000000007
for i in range(m):
    temp = int(input())
    a[temp] = 0
steps = [0 for i in range(n+2)]
steps[0] = 0
steps[1] = 1

for i in range(2,n+2):
    if i-1 not in a:
        steps[i] = steps[i-1] + steps[i-2]
        steps[i] %= base
    else:
        steps[i] = 0

print(steps[-1])

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

aa = {}
for _ in range(m):
  aa[int(input())] = True

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

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

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

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

Solution (Python):
n, m = list(map(int, input().split(' ')))
arr  = set()
for _ in range(m):
    x = int(input())
    arr.add(x)

MOD = int(1e9) + 7

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

if 0 not in arr:
    w[0] = 1

for i in range(n + 1):
    if i in arr:
        continue

    if i - 1 >= 0 and i - 1 not in arr:
        w[i] += w[i-1]

    if i - 2 >= 0 and i - 2 not in arr:
        w[i] += w[i-2]
    
    w[i] %= MOD


print(w[n])

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

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

print(dp[N + 1] % 1000000007)

Solution (Python):

import sys
import math
import numpy as np
import itertools

MOD = 1000000007

n,m = (int(i) for i in input().split())  


a = [int(input()) for i in range(m)] 
a.append(9999999) 
dame=0

b=[1]
if a[dame]==1:
    dame += 1
    b.append(0)
else:
    b.append(1)

for i in range(2,n+1):
    if i==a[dame]:
        dame += 1
        b.append(0)
    else:
        c=(b[i-1]+b[i-2]) % MOD
        b.append(c)


print(b[n])

Solution (Python):
n,m=map(int,input().split())
a=[1 for i in range(n+2)]
for i in range(m):
    a[int(input())]=0
dp=[0 for i in range(n+1)]
dp[0]=1
for i in range(n):
    if ((i+1)<(n+1)) and a[i+1]:
        dp[i+1]=(dp[i+1]+dp[i])%1000000007
    if ((i+2)<(n+1)) and a[i+2]:
        dp[i+2]+=(dp[i+2]+dp[i])%1000000007
print(dp[n])

Solution (Python):
n,m=map(int,input().split())
l=[]
for i in range(m):
  l.append(int(input()))
l=set(l)
L=[0 for i in range(n+1)]
L[0]=1
if 1 in l:
  L[1]=0
else:
  L[1]=1
for i in range(2,n+1):
  if i in l:
    L[i]=0
  else:
    L[i]=L[i-1]+L[i-2]
    L[i]%=1000000007
print(L[n])

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

arr.append(10**10)

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

tmp = 0

if arr[0] == 1:
    dp[1] = 0
    tmp += 1
else:
    dp[1] = 1

for i in range(N-1):
    if arr[tmp] == i+2:
        dp[i+2] = 0
        tmp += 1
        continue
    dp[i+2] = dp[i+1] + dp[i]

print(dp[N]%(1000000007))

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

mod = 10 ** 9 + 7

dp = [0] * (N + 100)
dp[0] = 1
a_set = set(a_list)

for i in range(N+10):
    if i in a_set:
        continue
    else:
        dp[i + 1] += dp[i]
        dp[i + 1] %= mod
        dp[i + 2] += dp[i]
        dp[i + 2] %= mod

print(dp[N] % mod)

Solution (Python):
from collections import defaultdict


def read_input():
    n, m = map(int, input().split())

    d = defaultdict(lambda : True)
    for i in range(m):
        d[int(input())] = False

    return n, m, d




def submit():
    n, m, d = read_input()

    prev = 1
    prev_prev = 0
    for i in range(1, n + 1):
        curr = 0
        if d[i - 1]:
            curr += prev
        if d[i - 2]:
            curr += prev_prev

        curr %= 1000000007

        prev_prev = prev
        prev = curr

    print(curr)


if __name__ == '__main__':
    submit()

Solution (Python):
N, M = map(int, input().split())
div = 10**9+7
A = [0 for i in range(N+1)]
A[0] = 1
for i in range(M):
    A[int(input())] = -1
for i in range(N):
    if A[i] == -1:
        continue
    now = A[i]
    if A[i+1] != -1:
        A[i+1] += now * 1
    if i < N-1 and A[i+2] != -1:
        A[i+2] += now * 1

print(A[-1] % div)

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

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

dp[1] = 1

MOD = 1000000007

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

print(dp[N+1])

Solution (Python):
n,m=map(int,input().split())
dp=[0 for i in range(n+1)]
dp[0]=1
for i in range(m):
    dp[int(input())]="b"
for i in range(1,n+1):
    if(dp[i]=="b"):
        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 i in range(M)]
B = [1]*(N+2)
for a in A:
    B[a] = 0
MOD = 10**9+7

if not B[0]:
    print(0)
    exit()

dp = [0]*(N+1)
dp[0] = 1
for i in range(N):
    if B[i+1]:
        dp[i+1] += dp[i]
        dp[i+1] %= MOD
    if i+2 <= N and B[i+2]:
        dp[i+2] += dp[i]
        dp[i+2] %= MOD
print(dp[-1])

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

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


n, m = li()
a = [ni() for _ in range(m)]
aset = set(a)

MOD = 10**9+7

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

for i in range(n):
    if i+1 in aset:
        continue

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

    else:
        dp[i+1] = dp[i] + dp[i-1]
        dp[i+1] %= MOD

print(dp[n])