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):
import sys
sys.setrecursionlimit(200000)

mod = int(1e9+7)

def dfs(i,dp,bad):
    if i == 0:
      return 1
    if i in dp:
      return dp[i]
    dp[i] = 0
    for d in (1,2):
      x = i-d;
      if 0 <= x and x not in bad:
        dp[i] += dfs(x,dp,bad)
        dp[i] %= mod
    return dp[i]

n,m = [int(a) for a in input().split()]
bad = set()
for _ in range(m):
  a = int(input())
  bad.add(a)
print(dfs(n,dict(),bad))

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

for i in range(m):

    an[i] = int( input() )



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


if disjoint:
    print(0)

else:

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

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



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

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

    
    

    print(ans)

Solution (Python):
n,m = map(int,input().split())
 
h = []
a = 1
b = 0
mod = 10 ** 9 + 7
 
for i in range(m):
    h += [int(input()),]
h += [0,]
    
cur = 0
for i in range(1,n):
    if i == h[cur]:
        a,b = 0,a
        cur += 1
    else:
        a,b = a + b,a
        a %= mod

print((a + b) % mod)

Solution (Python):
import sys
N, M = map(int, input().split())
MOD = 10 ** 9 + 7

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

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

print(dp[-1])

Solution (Python):
import sys
inputs = sys.stdin.readline
def main():
	ans = 1
	a = 0
	b = 0
	flg2 = 0
	N, M = map(int,inputs().split())
	A =[0]*(M+1)
	for i in range(M):
		a = int(inputs())
		A[i] = a-1-b
		b = a + 1
	A[M] = N - b
	A.sort()
	if A [0] < 0:
		flg2 = 1
	p = 1
	q = 1
	t = 0
	flg = 0
	while (A[t]<2):
		t = t+1
		if t > M:
			flg = 1
			break
	for k in range(2,N+1):
		r = p + q
		p = q
		q = r
		if flg == 1:
			break
		while (A[t] == k):
			ans = ans*r%1000000007
			t += 1
			if t == M+1:
				flg = 1
				break
		if flg == 1:
			break
	if flg2 == 0:
		print(ans%1000000007)
	else:
		print(0)
main()

Solution (Python):
from collections import deque
 
N, M = map(int, input().split())
 
a = []
aindex = 0
for _ in range(M):
    a.append(int(input()))
 
before1 = 1
before2 = 0
ai=0
if len(a)>0:
    ai = a[aindex]
 
for i in range(1, N+1):
    if i == ai:
        before2 = before1
        before1 = 0
        if aindex < len(a)-1:
            aindex += 1
            ai = a[aindex]
    else:
        current = divmod(before1 + before2, 10**9+7)[1]
        before2 = before1
        before1 = current
 
 
print(before1)

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

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


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

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

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


if N == 1 and M != 1:
    print(1)
    exit()
elif N == 1 and M == 1:
    print(0)
    exit()

if 1 in a and 2 in a:
    print(0)
    exit()

if 1 in a:
    dp[1] = 0
    dp[2] = 1
elif 2 in a:
    dp[1] = 1
    dp[2] = 0
else:
    dp[1] = 1
    dp[2] = 2

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

print(dp[N])

Solution (Python):
import sys
 
n, m = list(map(int, input().split()))
if m > 0:
    aaa = set(map(int, sys.stdin))
else:
    aaa = set()
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1 if 1 not in aaa else 0
MOD = 10 ** 9 + 7
 
for i in range(2, n + 1):
    if i in aaa:
        continue
    dp[i] = (dp[i - 2] + dp[i - 1]) % MOD
print(dp[n])

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

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())
MOD = 10 ** 9 + 7
ng = set([int(input()) for _ in range(M)])
ans = [0, 1] 
for i in range(1, N+1):
  if i in ng:
    ans.append(0)
  else:
    ans.append((ans[-2] + ans[-1]) % MOD)
print(ans[-1] % MOD)

Solution (Python):
md = 1000000007
n,m = list(map(int,input().split()))
broken = [0 for i in range(n+1)]
dp=[0 for i in range(n+1)]
dp[0] = 1
for i in range(m):
	broken[int(input())]=1

for j in range(1,n+1):
	if(broken[n-j]==1):
		continue
	if(j==1):
		dp[j]=1
	else:
		dp[j]=(dp[j-1]+dp[j-2])%md

print(dp[n]%md)

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

MOD = pow(10, 9) + 7

if n == 1:
  if 1 in alist:
    print(0)
  else:
    print(1)
else:
  memo = [0 for _ in range(n)]
  memo[0] = 0 if 1 in alist else 1
  is_reach = True
  if 1 in alist and 2 in alist:
    is_reach = False
    memo[0] = 0
  elif 1 in alist:
    memo[1] = 1
  else:
    memo[1] = 2

  for i in range(2, n):
    if i+1 in alist:
      memo[i] = 0
    elif i in alist and i-1 in alist:
      memo[i] = 0
      is_reach = False
      break
    elif i in alist:
      memo[i] = memo[i-2]
    elif i-1 in alist:
      memo[i] = memo[i-1]
    else:
      memo[i] = (memo[i-1] + memo[i-2]) % MOD

  if is_reach:
    print(memo[-1])
  else:
    print(0)

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

broken = [1 for i in range(N+1)]
for i in range(M):
  broken[bro[i]] = 0

for i in range(N):
  if i == 0:
    last[i+1] = last[i]*broken[i]
  else:
    last[i+1] = last[i]*broken[i]+last[i-1]*broken[i-1]
  last[i+1] %= mod
print(last[N])

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

Solution (Python):

N, M = map(int, input().split())
m = 10**9+7
F = [0]*N
for _ in range(M):
    F[int(input())-1] = 1

a, b = 0, 1
for n in range(N):
    if F[n]:
        a, b = b, 0
    else:
        a, b = b, (a+b) % m
print(b)

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

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

for i in range(n+1):
  if not l[i] == -1:
    if i == 0 or i == 1:
      l[i] = 1
    else:
      l[i] = max(l[i-2], 0) + max(l[i-1], 0)

print(l[-1] % 1000000007)

Solution (Python):
n, m = map(int, input().split())
mod = 10 ** 9 + 7
A = []
for i in range(m):
    A.append(int(input()))
    
dp = [None for i in range(n + 1)]
dp[0] = 1

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

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

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

for i in range(0, m):
    a = int(raw_input())
    dp[a] = -1

for step in range(1, n + 1):
    if dp[step] < 0:
        continue

    ans = 0
    for prev in [1, 2]:
        if step - prev >= 0 and dp[step - prev] >= 0:
            ans += dp[step - prev]
    dp[step] = ans




print(dp[n] % 1000000007)

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

n, m = map(int, input().split())
s = set(map(int, [input() for _ in range(m)]))
MOD = 10 ** 9 + 7
a = 1 if not 0 in s else 0
b = 1 if not 1 in s else 0
for i in range(2, n + 1):
    if i in s:
        a, b = b, 0
    else:
        a, b = b, (a + b) % MOD
print(b)

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

b = [0]*(n+2)
b[0] = 1

for i in range(m):
    b[int(input())] = -1

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

print(b[n]%1000000007)

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

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

     
line = [int(s) for s in input().split()]
     
N, M = line[0], line[1]
     
b = [0]*(N+1)
for i in range(M):
    step_num = int(input().split()[0])
    b[step_num] = 1
        
        
dp = [0]*(N+1)
dp[0] = 1
if b[1] == 1:
    dp[1] = 0
else:
    dp[1] = 1
     
for i in range(2, N+1):
    if b[i] == 1:
        dp[i] = 0
    else:
        dp[i] = (dp[i-1]+dp[i-2])%MOD
print(dp[N])

Solution (Python):
n,m=map(int,input().split())
MOD = 1000000007 
D=[0] * (n+2)
D[0] = 1
for _ in range(m):
    D[int(input())] = -1
for i in range(n):
    if D[i] == -1:
        continue
    if D[i+1] != -1:
        D[i+1] += D[i]
    if D[i+2] != -1:
        D[i+2] += D[i]
    D[i]%=MOD
print(D[n] % MOD)

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

dp = [0] * (N+1)

dp[0] = 1

for i in range(N):
    for j in range(i+1, min(N, i+2)+1):
        if a[j]:
            dp[j] += dp[i]
            dp[j] %= MOD

print(dp[N])

Solution (Python):
fiblist = [0] * 100001
fiblist[0] = 1
fiblist[1] = 1
for p in range(2,100001):
    fiblist[p] = (fiblist[p-1]+fiblist[p-2]) % 1000000007

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

if m == 0:
    print(fiblist[n])
else:
    a = []
    for i in range(m):
        a.append(int(input()))

    d = [a[0]-1]
    for j in range(1,m):
        d.append(a[j]-a[j-1]-2)

    d.append(n-a[m-1]-1)






    if (-1 in d) or (-2 in d):
        print(0)
    else:
        ans = 1
        for k in range(m+1):
            ans = (ans * fiblist[d[k]]) % 1000000007

        print(ans)

Solution (Python):
import sys
 
n, m = list(map(int, input().split()))
if m > 0:
    aaa = set(map(int, sys.stdin))
else:
    aaa = set()
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1 if 1 not in aaa else 0
MOD = 10 ** 9 + 7
 
for i in range(2, n + 1):
    if i in aaa:
        continue
    dp[i] = (dp[i - 2] + dp[i - 1]) % MOD
print(dp[n])

Solution (Python):
n,m = map(int,input().split())
MOD = 10**9 + 7
dp = [0 for i in range(n+1)]
t = [True for _ in range(n+1)]
for i in range(m):
    a = int(input())
    t[a] = False

dp[0] = 1
for now in range(n):
    for next in range(now+1,min(n+1,now+3)):
        if t[next]:
            dp[next] += dp[now]
            dp[next] %= MOD

print(dp[n])

Solution (Python):
N, M = list(map(int,input().split()))
     
b = [0]*(N+2)
b[0] = 1
     
for i in range(M):
  b[int(input())] = -1
     
for i in range(N):
  if b[i] != -1:
    if b[i+1] != -1:
      b[i+1] += b[i]
    if b[i+2] != -1:
      b[i+2] += b[i]

print(b[N]%1000000007)

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

pre=-1

li=[-1]

for i in range(m):
  a=int(input())
  if pre+1==a:
    print(0)
    exit()
  pre=a
  li.append(a)

li.append(n+1)

result=[]
for i in range(1,len(li)):
  sum1=1
  sum2=1
  sum3=1
  if 3>li[i]-li[i-1]:
    continue
  for j in range(3,li[i]-li[i-1]):
    sum3=sum1+sum2
    sum1=sum2
    sum2=sum3
  result.append(sum3)

result_=1
for i in result:
  result_*=i

print(result_%1000000007)

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

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

dp = {}
for i in range(n + 1):
    dp[i] = 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:
        dp[i] = dp[i - 1] % mod + dp[i - 2] % mod
        dp[i] %= mod

print(dp[n] % mod)

Solution (Python):
N, M  = map(int, input().split())
a  = {}
for _ in range(M):
  a[int(input())] = 1
sdic  = {}
nn1 = 1
nn2 = 0
for n in reversed(range(N)):
  if n in a:
    nn2 = nn1
    nn1 = 0
    continue
  t = nn1 + nn2
  if t == 0:
    print(0)
    quit()
  nn2 = nn1
  nn1 = t
  
print(nn1%1000000007)

Solution (Python):
import bisect
def f(x,a):
  global M
  b = bisect.bisect_left(a,x)
  if x==a[min(b,M)]:
    return True
  else:
    return False
MOD = 10**9+7
N,M = map(int,input().split())
a = [-1]+[int(input()) for _ in range(M)]
a.sort()
x = 0
y = 1
for i in range(N):
  if f(i,a) and f(i+1,a):
    print(0)
    exit()
  elif f(i+1,a):
    z = 0
  else:
    z = x + y
  x = y
  y = z
print(z%MOD)

Solution (Python):

n, m = map(int, input().split())
BIGNUM = 10 ** 9 + 7

if m > 0:
    last_ana = int(input())
    blocks = [last_ana]

    for _ in range(1, m):
        ana = int(input())
        blocks.append(ana - last_ana - 1)
        last_ana = ana
    blocks.append(n - last_ana)
else:
    blocks = [n + 1]

if 0 in blocks:
    ans = 0
else:
    b_max = max(blocks)
    c = [1, 1]
    for i in range(2, b_max):
        ctmp = c[i - 1] + c[i - 2]
        c.append(ctmp % BIGNUM)

    ans = 1
    for num in blocks:
        if num == 1:
            continue
        ans = (ans * c[num - 1]) % BIGNUM
        if ans == 0:
            break

print(ans)

Solution (Python):

import sys
import bisect

MOD = 1000000007  

def is_ok(i,a):
    ii = bisect.bisect_left(a,i)
    if ii >= len(a):
        return True
    return i != a[ii]


def solve(N: int, M: int, a: "List[int]"):
    dp = [0]*N
    dp[0] = 1 if is_ok(1,a) else 0

    if N > 1:
        if is_ok(2,a):
            if is_ok(1,a):
                dp[1] = 2
            else:
                dp[1] = 1

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

    print(dp[N-1] % MOD)
    return



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

if __name__ == '__main__':
    main()

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

MOD = 1000000007

b = [0]*(N+2)
b[0] = 1

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

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

print(b[N]%MOD)

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

def main():
    if M>0:
        B = [0]*(M+1)
        for i in range(M+1):
            if i==0:
                B[i] = A[i]-1
            elif i==M:
                B[i] = N-A[i-1]-1
            else:
                if A[i]==A[i-1]:
                    B[i] = 0
                else:
                    B[i] = A[i] - A[i-1] - 2
    else:
        B = [N]
    min_B = min(B)
    if min_B<0:
        return 0
    
    max_B = max(B)
    F = [1]*(max_B+1)
    for i in range(max_B+1):
        if i<2:
            pass
        else:
            F[i] = F[i-2] + F[i-1]
    ans = 1
    for b in B:
        ans *= F[b]
        if ans >= DIV:
            ans %= DIV
    return ans

print(main())

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

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

for i in range(2, N):
  kaidan.append(kaidan[i-1]+ kaidan[i-2])

if M == 0:
  ans = kaidan[N - 1]
else:
  ans = 1

  if a[0] - 1 > 0:
      ans *= kaidan[a[0] - 2]

  for i in range(M-1):
    if((a[i] + 1) > (a[i+1] - 1)):
      ans *= 0
    elif((a[i] + 1) == (a[i+1] - 1)):
      ans *= 1
    else:
      ans *= (kaidan[a[i+1] - a[i] - 3])

  if N - (a[M - 1] + 1) > 0:
      ans *= kaidan[N - (a[M - 1] + 2)]
      
print(ans%1000000007)

Solution (Python):
from sys import stdin

n, m = [int(i) for i in stdin.readline().rstrip().split()]
a = [-1] + [int(stdin.readline()) for _ in range(m)] + [n+1]

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

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

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

Solution (Python):
import sys

n,m = map(int, input().split())
a = [0]
for i in range(m):
    a.append(int(input()))
a.append(n)
    
mod = 1000000007
ans = 1

for i in range(1,len(a)-2):
    if a[i+1]-a[i]==1:
        print(0)
        sys,exit()

b = []
for i in range(1,len(a)):
    if i == 1:
        b.append(a[1]-1-a[0])
    elif i == len(a)-1:
        b.append(a[i]-(a[i-1]+1))
    else:
        b.append(a[i]-1-(a[i-1]+1))

dp = []
for i in range(10**6):
    if i == 0:
        dp.append(1)
        continue
    if i == 1:
        dp.append(1)
        continue
    if i == 2:
        dp.append(2)
        continue
    dp.append((dp[i-1]+dp[i-2])%mod)

if m == 0:
  print(dp[n])
  sys.exit()
    
for i in range(len(b)):
    l = b[i]
    ans = (ans*dp[l])%mod
    
print(ans)

Solution (Python):

import sys
input = sys.stdin.readline

n, m = list(map(int, input().rstrip().split()))
skip = set(map(int, [input().rstrip() for _ in range(m)]))
MOD = 10 ** 9 + 7
a = 1 if not 0 in skip else 0
b = 1 if not 1 in skip else 0

for i in range(2, n + 1):
    if a == 0 and b == 0:
        print(0)
        break
    if i in skip:
        a = b
        b = 0
    else:
        tmp = b
        b = (a + b) % MOD
        a = tmp
else:
    print(b)

Solution (Python):
N, M=map(int, input().split())
a=[int(input()) for _ in range(M)]
tmp=[1,1,2]
for i in range(N):
    tmp.append(tmp[-1]+tmp[-2])
def func(x):
    if x==-1:
        return 0
    elif x==-2:
        return 1
    else:
        return tmp[x]

if M==0:
    print(func(N)%1000000007)
    exit(0)
s=func(a[0]-1)
for i in range(0, M-1):
    s*=func(a[i+1]-a[i]-2)
s*=func(N-a[M-1]-1)
print(s%1000000007)

Solution (Python):
def fib(n):
    a, b = 0, 1
    for i in range(n):
        a, b = b, a + b
    return b
n, m = (int(i) for i in input().split())
stops = [int(input())-1 for i in range(m)]
stops.append(n) 
current = 0
count = 1
for s, stop in enumerate(stops):
    steps = stop - current
    if steps < 0:
        count = 0
        break
    else:
        count *= fib(steps)


    current = stop + 2
print(count % 1000000007)

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

b = [0]*(N+2)
b[0] = 1

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

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

print(b[N]%1000000007)

Solution (Python):
n, m = map(int, input().split())
mod = 10 ** 9 + 7
pat = [0] * (n + 2)
pat[0] = 1
pat[1] = 1

for i in range(m):
    a = int(input())
    pat[a] = -1

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

print(pat[n])

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

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

b = [0]*(N+2)
b[0] = 1

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

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

print(b[N]%1000000007)

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

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

dp = [1]
n_with_a = [[i, False] for i in range(n+1)]



for a in a_s:
    n_with_a[a][1] = True



if 1 in a_s:
    dp.append(0)
else:
    dp.append(1)

for i, is_broken in n_with_a[2:]:
    if is_broken:
        dp.append(0)
    else:
        dp.append((dp[i-1] + dp[i-2]) % 1000000007)

print(dp[-1])

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

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

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

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

	print(dp[N]%1000000007)

solve()

Solution (Python):

n, m = map(int, input().split())
BIGNUM = 10 ** 9 + 7

if m > 0:
    last_ana = int(input())
    blocks = [last_ana]

    for _ in range(1, m):
        ana = int(input())
        blocks.append(ana - last_ana - 1)
        last_ana = ana
    blocks.append(n - last_ana)
else:
    blocks = [n + 1]

if 0 in blocks:
    ans = 0
else:
    b_max = max(blocks)
    c = [1, 1]
    for i in range(2, b_max):
        ctmp = c[i - 1] + c[i - 2]
        c.append(ctmp % BIGNUM)

    ans = 1
    for num in blocks:
        if num == 1:
            continue
        ans = (ans * c[num - 1]) % BIGNUM
        if ans == 0:
            break

print(ans)

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


def climb_stairs(n):
    """
    :param n: int
    :param danger: list
    :return: int
    """
    if n == 1 or n == 2:
        return n
    else:
        a, b = 1, 2
        for i in range(n-2):
            a, b = b, a + b
        return b


now_s = 0
cost = 1
for j in a:
    if now_s == j:
        cost *= 0
        break
    elif now_s == j - 1:
        now_s = j + 1
    else:
        cost *= climb_stairs((j - 1) - now_s)
        now_s = j + 1

if now_s != N:
    cost *= climb_stairs(N - now_s)

print(cost % 1000000007)

Solution (Python):
def fib(num):
    a, b = 0, 1 
    for _ in range(num - 1):

        a, b = a + b, a
    return a + b

def culcC(num):
    if num  < 2:
         return 1
    return fib(num) + fib(num-1)
            
n,m = map(int,input().split())
aa = [int(input()) for i in range(m)]

if n == 1:
    print(1)
elif m == 0:
    print(culcC(n) % 1000000007)
else:
    ans = 1
    stand = 0
    for i,a in enumerate(aa):

        if stand == a:
            ans = 0
            break
        step_num = a - stand - 1
        c = culcC(step_num)
        ans *= c if c > 0 else 1
        stand = a + 1
        
    
    ans *= culcC(n - aa[-1] - 1)
    
    print(ans % 1000000007)

Solution (Python):
import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, functools, random
import sys
from collections import deque, defaultdict, Counter; from heapq import heappush, heappop
from itertools import permutations, combinations, product, accumulate, groupby
from bisect import bisect_left, bisect_right, insort_left, insort_right
from operator import itemgetter as ig
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20; INF = float("INF"); ans = 0; tmp = 0; ansli = []; tmpli = []; candili = []
eps = 1.0 / 10 ** 10; mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]; ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]; ddn9 = ddn + [(0, 0)]
"""for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""
def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def ws(): return sys.stdin.readline().split()
def i(): return int(sys.stdin.readline())
def s(): return input()
def hi(n): return [i() for _ in range(n)]
def hs(n): return [s() for _ in range(n)]
def mi(n): return [wi() for _ in range(n)]
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]

n, m = wi()
a = hi(m)
aset = set(a)
dp = [0] * (n + 1)
dp[0] = 1
if 1 not in aset:
    dp[1] = 1

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

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


for i in range(n):
    if dp[i] != -1:
        if dp[i+1] != -1:
            dp[i+1] += dp[i] % mod

        if i != n-1 and dp[i+2] != -1:
            dp[i+2] += dp[i] % mod

print(dp[-1] % mod)

Solution (Python):
n,m = [int(_) for _ in input().split()]
a = {int(input()) for _ in range(m)}
dp = [0 for _ in range(n+1)]
dp[0] = 1
mod = int(1e9+7)
for i in range(1,n+1):
    if i-1 not in a:
        dp[i] += dp[i-1];dp[i] %= mod
    if i >= 2 and i-2 not in a:
        dp[i] += dp[i-2];dp[i] %= mod
print(dp[-1])

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):
def cmb(n, r):
    return fct[n] * inv[r] * inv[n - r] % md

md = 10 ** 9 + 7
n, m = map(int, input().split())
ans = 1
pa = -1
ds = []
for _ in range(m):
    a = int(input())
    if a == 1:
        pa = 1
        continue
    d = a - pa-2
    if d == -1:
        print(0)
        exit()
    ds.append(d)
    pa = a
ds.append(n - pa-1)

mxd = max(ds)
fct = [1, 1]
inv = [1] * (mxd + 1)
s = 1
for i in range(2, mxd + 1):
    s = (s * i) % md
    fct.append(s)
inv[-1] = s = pow(fct[-1], md - 2, md)
for i in range(mxd, 1, -1):
    s = s * i % md
    inv[i - 1] = s
for d in ds:
    tmp = 0
    for i in range(d // 2 + 1):
        tmp = (tmp + cmb(d - i, i)) % md
    ans = (ans * tmp) % md
print(ans)

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


step_now = 0
step_1   = 0
step_2   = 0
DIV_NUM = 1000000007
if 1 in a_list:
    a_list.pop(0)
    step_now = 0
else:
    step_now = 1
for i in range(1, n):
    if i == 1:
        step_1 = step_now
        if i+1 in a_list:
            a_list.pop(0)
            step_now = 0
        else:

            step_now = step_1 + 1
    else:
        step_2 = step_1
        step_1 = step_now
        if i+1 in a_list:
            a_list.pop(0)
            step_now = 0
        else:

            step_now = (step_1 + step_2) % DIV_NUM
    if step_now ==  step_1 == step_2 == 0:
        break

print(step_now)

Solution (Python):
MOD = 10**9+7
N,M = map(int,input().split())
a = [int(input()) for _ in range(M)]
dp = [0 for i in range(N+1)]
b = [0 for i in range(N+1)]
dp[0] = 1
for i in range(M):
    b[a[i]] += 1
for i in range(1,N+1):
    if b[i] == 1:
        dp[i] = 0
        continue
    elif i == 1:
        dp[i] = 1
        continue
    dp[i] = (dp[i-1] + dp[i-2]) % MOD
print(dp[N])

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


li_new = [-1]*(m+1)
li_new[0] = li[0]
for i in range(1,m):
    li_new[i] = li[i] - (li[i-1]+1)
li_new[m] = n - li[m-1]



fib = [0] * (max(max(li_new)+2,3))
fib[0] = 0
fib[1] = 1
fib[2] = 1
for i in range(3,max(li_new)+2):
    fib[i] = fib[i-2] + fib[i-1]



ans = 1
if m > 0:
    for i in li_new:
        ans *= fib[i]
else:
    ans = fib[n+1]
print(ans%1000000007)

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

for i in range(2, n + 1):
    if s[i] < 0:
        continue
    if s[i - 2] > 0:
        s[i] += s[i - 2]
    if s[i - 1] > 0:
        s[i] += s[i - 1]
print(s[n] % 1000000007)

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

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

ans = 1
before = -1
if m != 0:
    for i in range(m):
        step = a[i] - before - 2
        if step == -1:
            ans = 0
            break
        elif step > 0:
            ans = ans * tmp[step-1]
            ans = ans % 1000000007

        before = a[i]


step = n - before - 1
if step > 0:
    ans *= tmp[step-1]
    ans = ans % 1000000007

print(ans)

Solution (Python):
n,m = map(int,raw_input().split())
a = []
buf = -111
for q in range(m):
  a.append(int( raw_input() ))
  buf = a[q]
  if buf - a[q] == 1:
    print 0
    exit(0)

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

now = [-1]*100001

if m == 0:
  now[0] = 1
  now[1] = 1
  for q in range(2,n+1):
    now[q] = (now[q-1] + now[q-2]) % 1000000007
  print now[q] % 1000000007
  exit(0)
    
now[0] = 1
if a[0] == 1: now[1] = 0
else: now[1] = 1

for q in a:
  now[q] = 0

for q in range(2,n+1):
  if now[q] != -1: continue
  now[q] = (now[q-1] + now[q-2]) % 1000000007
  
print now[q] % 1000000007

Solution (Python):



import numpy as np
s = list(map(int, input().split()))
N = s[0]
M = s[1]
flag = 0
def fib(n):
    a, b = 0, 1
    c = [1]
    for i in range(n):
        a, b = b, a + b
        c.append(b)
    return c


broken = np.array([int(input()) for i in range(M)])
broken = np.append(-1,broken)
broken = np.append(broken,N+1)


gaps = np.array([])  
for i in range(M+1):
    gaps = np.append(gaps, broken[i+1]-broken[i]-1)
    if broken[i+1]-broken[i]-1 == 0:
        flag = 1
        break

gaps = np.array(gaps, np.int)  



if flag == 1:
    print(0)
else:
    fibs = fib(max(gaps))
    patterns = 1
    for i in range(len(gaps)):
        patterns *= fibs[gaps[i]-1]
    print(patterns % 1000000007)