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())
lists = [1,2]
bag_step = [-1]
last = 0
conbi = 1
 
def conbination(num):
    if len(lists) >= num:
        return lists[num-1]
    for i in range(len(lists),num):
        lists.append(lists[i-1]+lists[i-2])
    return lists[num-1]
 
for i in range(m):
    bag_step.append(int(input())) 
bag_step.append(n+1)
for i in range(1,len(bag_step)):
  if bag_step[i] == bag_step[i-1] + 1:
    conbi = 0
    break
  if bag_step[i] == bag_step[i-1] + 2:
    continue
  conbi = conbi * conbination(bag_step[i] - bag_step[i-1] - 2)%(1000000007)
print(conbi)

Solution (Python):
n, m = list(map(int, input().split()))
a = [input() for i in range(m)]
b = []
c = []
total_act = 0
total_act2 = 1
total = 1
if m == 0:
    for i in range(n + 1):
        if str(i) in a:
            total *= total_act
            total_act = 0
            total_act2 = 1
        else:
            total_act3 = total_act2 + total_act
            total_act2 = total_act
            total_act = total_act3
    total *= total_act
    print(total % 1000000007)
else:
    b.append(int(a[0]))
    for i in range(len(a) - 1):
        b.append(int(a[i + 1]) - int(a[i]) - 1)
        if int(a[i + 1]) - int(a[i]) - 1 == 0:
            print(0)
            exit()
    b.append(n - int(a[-1]))

    for i in range(max(b)):
        total_act3 = total_act2 + total_act
        total_act2 = total_act
        total_act = total_act3
        c.append(total_act)

    for i in b:
        total *= c[i - 1]
    print(total % 1000000007)

Solution (Python):
def Fib(n):
    a, b = 0, 1
    if n == 1:
        return a
    elif n == 2:
        return b
    else:
        for i in range(n-2):
            a, b = b, a + b
        return b
a,b=input().split()
a=int(a)
b=int(b)
ll=[]
y=-1
s=0
for i in range(b):
    x=input()
    x=int(x)
    ll.append(x)
    if x-y==1:
        s=1
        break
    y=x
ll.append(a+1)
l2=[]
if s==1:
    print(0)
else:
    x=-1
    for i in ll:
        l2.append(Fib(i-x))
        x=i
    ans=1
    for i in l2:
        ans*=i
    print(ans%1000000007)

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

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

Solution (Python):
import numpy as np

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


a = np.ones(n+1, dtype=np.bool)
for _ in range(m):
    a[int(input())] = 0

mod = 1e9 + 7


pos = np.zeros(n+1)
pos[0] = 1
for i in range(n-1):
    if a[i+1]:
        pos[i+1] += pos[i]
        pos[i+1] %= mod
    if a[i+2]:
        pos[i+2] += pos[i]
        pos[i+2] %= mod

pos[n] += pos[n-1]

print(int(pos[n] % mod))

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

def num_way(stair):
  memo = ["EMPTY"]*(stair+1)
  def _fib(stair):
    if stair == 1 or stair == 0:
      return 1
    elif stair == 2:
      return 2
    elif memo[stair] != "EMPTY":
      return memo[stair]
    else:
      memo[stair] = _fib(stair-1)+_fib(stair-2)
      return memo[stair]
  return _fib(stair)

N, M = map(int,input().split())
a = deque([0])
path_poss = 1
ans = 1
for m in range(M):
  start = a.popleft()
  buff = int(input())
  end = buff-1
  if (end-start) <= -1:
    path_poss = 0
    break
  a.append(buff+1)
  ans *= num_way(end-start)
  ans %= 1000000007

if path_poss == 0:
  print(0)
else:
  start = a.popleft()
  end = N
  if(end-start) <= -1:
    path_poss = 0
  if path_poss == 0:
    print(0)
  else:
    ans *= num_way(end-start)
    print(ans%1000000007)

Solution (Python):
from collections import defaultdict
N, M = map(int, input().split())
A = [int(input()) for i in range(M)]
dict = defaultdict(int)
for a in A:
    dict[a] += 1

mod = 10 ** 9 + 7
dp = [0 for _ in range(N+1)]
dp[0] = 1
if dict[1] == 0:
    dp[1] = 1

for i in range(1, N):
    if dict[i] == 0 and dict[i-1] == 0:
        dp[i+1] += ((dp[i-1] + dp[i]) % mod)
    elif dict[i] == 0:
        dp[i+1] += (dp[i] % mod)
    elif dict[i-1] == 0:
        dp[i+1] += (dp[i-1] % mod)

print(dp[-1])

Solution (Python):
from collections import defaultdict
N, M = map(int, input().split())
A = [int(input()) for i in range(M)]
dict = defaultdict(int)
for a in A:
    dict[a] += 1

mod = 10 ** 9 + 7
dp = [0 for _ in range(N+1)]
dp[0] = 1
dp[1] = 1
for i in range(1, N):
    if dict[i] == 0 and dict[i-1] == 0:
        dp[i+1] += ((dp[i-1] + dp[i]) % mod)
    elif dict[i] == 0:
        dp[i+1] += (dp[i] % mod)
    elif dict[i-1] == 0:
        dp[i+1] += (dp[i-1] % mod)

print(dp[-1])

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

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


for i in range(0, N-1):
    counter_arr[i+1] += counter_arr[i] * broken_lst[i+1]
    counter_arr[i+1] %= 10**9 + 7
    counter_arr[i+2] += counter_arr[i] * broken_lst[i+2]
    counter_arr[i+2] %= 10**9 + 7

counter_arr[-1] += counter_arr[-2] * broken_lst[-1]
counter_arr[-1] %= 10**9 + 7

print(counter_arr[-1])

Solution (Python):
def func(x, a, n):
    if a[n] == 1:
        x[n] = a[n-1] * x[n-1] + a[n-2] * x[n-2]
    else:
        x[n] = 0

def main():
    K = 1000000007
    line = input().split(' ')
    N = int(line[0])
    M = int(line[1])
    a = [1] * (N + 1)
    x = [0] * (N + 1)

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

    x[0] = 1
    if a[1] == 1:
        x[1] = 1
    else:
        x[1] = 0

    for i in range(2, N+1):
        func(x, a, i)
        
    print(x[N]%K)

if __name__ == "__main__":
    main()

Solution (Python):

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

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

broken = [0 for _ in range(n+1)]
for i in range(m):
    a = int(input())
    broken[a] = True

    
mod = 1000000007
dp = [0 for _ in range(n+2)]

dp[n] = 1
for i in range(n-1, -1, -1):
    if(broken[i]):
        dp[i] = 0
        continue

    dp[i] = (dp[i+1] + dp[i+2]) % mod

print(dp[0])

Solution (Python):
import copy
n,m = map(int,input().split())
a00 = 0
a0 = 1
if m > 0:
    ann = 0
    for i in range(m):
        an = int(input())
        if an != ann:
            for x in range(an-ann-1):
                ak = copy.copy(a00 + a0)
                a00 = copy.copy(a0)
                a0 = copy.copy(ak)
            ann = copy.copy(an)
            a00 = copy.copy(a0)
            a0 = 0
        else:
            ann = copy.copy(an)
    for j in range(n-an):
        ak = copy.copy(a00+a0)
        a00 = copy.copy(a0)
        a0 = copy.copy(ak)
else:
    for i in range(n):
        ak = copy.copy(a00 + a0)
        a00 = copy.copy(a0)
        a0 = copy.copy(ak)
print(a0 % 1000000007)

Solution (Python):
n, m = map(int, input().split())
k = []
count_sub = 0
steps = []
j = 0
for i in range(m):
    k.append(int(input())) 
    if len(k)>1 and k[i]-k[i-1]==1:
        count_sub = 1
        
if count_sub ==1:
    steps = [0 for i in range(n)]  
else:
    for i in range(n+1):
        if k!=[] and k[j]==i:
            steps.append(0)
            if j < len(k)-1:
                j = j + 1
        elif i ==0:
            steps.append(1)
        elif i ==1:
            steps.append(1)  
        else:
            steps.append((steps[i-1]+steps[i-2])%1000000007)
 
print(steps[-1])

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

a.append(0)

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

print(dp[-1])

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

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

print(dp[-1])

Solution (Python):
n, m = map(int, input().split())
k = []
count_sub = 0
steps = []
j = 0
for i in range(m):
    k.append(int(input())) 
    if len(k)>1 and k[i]-k[i-1]==1:
        count_sub = 1
        
if count_sub ==1:
    steps = [0 for i in range(n)]  
else:
    for i in range(n+1):
        if k!=[] and k[j]==i:
            steps.append(0)
            if j < len(k)-1:
                j = j + 1
        elif i ==0:
            steps.append(1)
        elif i ==1:
            steps.append(1)  
        else:
            steps.append(steps[i-1]+steps[i-2])
 
print(steps[-1]%(1000000007))

Solution (Python):
n,m = list(map(int, input().split()))
a=[]
a.append(-1)
for x in range(m):
  tmp=int(input())
  a.append(tmp)
a.append(n+1)
diff = []
for x in range(len(a)-1):
  diff.append(a[x+1]-a[x])
              
large = 0
small = 123456789012345
for x in diff:
  large=max(large,x)
  small=min(small,x)

num=[0,0,1]
for _ in range(large):
  num.append((num[-1]+num[-2])%1000000007)
    
answer=1
for x in diff:
  
  answer *=num[x]
  answer%=1000000007
print(answer)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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

memo = [0]*(n+1)
memo[0]=1
if not(1 in a):
    memo[1]=1

for i in range(2,n+1):
    
    if i in a:
        continue
    
    memo[i]=memo[i-2]+memo[i-1]
            


print(memo[n]% 1000000007)

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

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

for i in range(N+1):
    if a[i+1] != 1:
        dp[i+1]+=dp[i]
        dp[i+1]%=mod
    if a[i+2] != 1:
        dp[i+2]+=dp[i]
        dp[i+2]%=mod

print(dp[N])

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

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

a_set = {int(input()) for _ in range(m)}

ans_list = []

ans_list = [0] * (n + 1)

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):
import sys
input = sys.stdin.readline

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

a_set = {int(input()) for _ in range(m)}

ans_list = []

ans_list = [0] * (n + 1)

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):
import sys
input = sys.stdin.readline

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

a_set = {int(input()) for _ in range(m)}

ans_list = []

ans_list = [0] * (n + 1)

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):
import sys
input = sys.stdin.readline

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

a_set = {int(input()) for _ in range(m)}

ans_list = []

ans_list = [0] * (n + 1)

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):
import sys
input = sys.stdin.readline

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

a_set=set()

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

ans_list = []

ans_list = [0] * (n + 1)

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):
import sys
input = sys.stdin.readline

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

a_set=set()

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

ans_list = []

ans_list = [0] * (n + 1)

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):
import sys
input = sys.stdin.readline

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

a_set=set()

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

ans_list = []

ans_list = [0] * (n + 1)

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):
import sys
input = sys.stdin.readline

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

a_set=set()

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

ans_list=[0] * (n + 1)

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):
import sys
input = sys.stdin.readline

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):
import sys
input = sys.stdin.readline

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):
import sys
input = sys.stdin.readline

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):
import sys
n,m=map(int,input().split())
a=set(map(int,sys.stdin))
dp=[0]*(n+1)
dp[0]=1
if 1 not in a:dp[1]=1
for i in range(2,n+1):
    if i in a:continue
    if dp[i-1]==dp[i-2]==0:break
    dp[i]=(dp[i-1]+dp[i-2])%1000000007
print(dp[-1])

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

B = set(A)

X = [1, 1 if 1 not in B else 0]
for i in range(2, N + 1):
    x = (X[-1] + X[-2]) % 1000000007
    X.append(x if i not in B else 0)

print(X[N])

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

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

path = [-1] * (N+1)
path[0] = 1
path[1] = 1
for a in A:
    path[a] = 0
for i, p in enumerate(path):
    if i < 2:
        continue
    if p == -1:
        path[i] = (path[i-1] + path[i-2]) % MOD
print(path[-1])

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

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

MOD = 1000000007

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

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

for i in range(1,n+1):
    if count[i] == 0:
        continue
    
    if i == 1:
        count[i] = 1 
    elif i == 2:
        count[i] = count[i-1] + 1
    else:
        count[i] = (count[i-1] + count[i-2]) % MOD

print(count[n])

Solution (Python):
import os
import sys

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

safe = [True for _ in range(N + 1)]
for a in A:
    safe[a] = False

dp = [0 for _ in range(N + 1)]
dp[0] = 1
for i in range(N + 1):
    if not safe[i]:
        continue
    if i + 1 < len(dp):
        dp[i + 1] += dp[i]
        dp[i + 1] %= MOD
    if i + 2 < len(dp):
        dp[i + 2] += dp[i]
        dp[i + 2] %= MOD
print(dp[-1])

Solution (Python):
import sys
n,m=map(int,input().split())
a=set(map(int,sys.stdin))
dp=[0]*(n+1)
dp[0]=1
if 1 not in a:dp[1]=1
for i in range(2,n+1):
    if i in a:continue
    if dp[i-1]==dp[i-2]==0:break
    dp[i]=(dp[i-1]+dp[i-2])%1000000007
print(dp[-1])

Solution (Python):
import sys

 
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())
mod=10**9+7
a = [int(input()) for i in range(m)]
block=[0,1]
x=[True for i in range(n)]
for j in a:
  x[j-1]=False

for i in range(1,n+1):
  if x[i-1]==False:
    block=block[1:]+[0]
  else:
    block=block[1:]+[sum(block)%mod]
print(block[-1])

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):
def org_fib(t):
    t1 = 1
    t2 = 2
    fib = 0
    if t == 1:
        return t1
    elif t == 2:
        return t2
    else:
        for _ in range(t-2):
            fib = t1+t2
            t1 = t2
            t2 = fib
    return fib % 1000000007

N,M = map(int,input().split())
if N == 1:
    print(1)
elif M == 0:
    print(org_fib(N))
else:
    pre_a = -1
    k = []
    ef = True
    for i in range(M):
        a = int(input())
        if (a-pre_a == 1):break
        k.append(a-pre_a-2)
        pre_a = a
    else:
        ef = False
        k.append(N-a-1)

    if ef:print(0)
    else:
        g = 1
        for kk in k:
            if kk == 0:pass
            else:g = (g * org_fib(kk)) % 1000000007
        print(g)

Solution (Python):
MOD = 1000000007

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

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

for i in range(1,n+1):
    if count[i] == 0:
        continue
    
    if i == 1:
        count[i] = 1 
    elif i == 2:
        count[i] = count[i-1] + 1
    else:
        count[i] = (count[i-1] + count[i-2]) % MOD

print(count[n])

Solution (Python):
OK = "O"
BRO = "B"

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

K = list(OK for i in range(N+1))
for i in range(M):
  K[Broken[i]] = BRO
  
if N == 1:
  print(1)
  exit()
  
c=[0 for i in range(N+1)]
if K[N-1]==OK:
  c[1]=1
if K[N-2]==OK and K[N-1]==OK:
  c[2]=2
if K[N-2]==OK and K[N-1]==BRO:
  c[2]=1

for i in range(3,N+1):
  if K[N-i]==OK:
    if K[N-i+1]==OK and K[N-i+2]==OK:
      c[i]=c[i-1]+c[i-2]
    if K[N-i+1]==OK and K[N-i+2]==BRO:
      c[i]=c[i-1]
    if K[N-i+1]==BRO and K[N-i+2]==OK:
      c[i]=c[i-2]
  c[i]%=1000000007
  
print(c[N] % 1000000007)

Solution (Python):
OK = 0
BRO = 1

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

K = list(0 for i in range(N+1))
for i in range(M):
  K[Broken[i]] = 1
  
if N == 1:
  print(1)
  exit()
  
c=[0 for i in range(N+1)]
if K[N-1]==OK:
  c[1]=1
if K[N-2]==OK and K[N-1]==OK:
  c[2]=2
if K[N-2]==OK and K[N-1]==BRO:
  c[2]=1

for i in range(3,N+1):
  if K[N-i]==OK:
    if K[N-i+1]==OK and K[N-i+2]==OK:
      c[i]=c[i-1]+c[i-2]
    if K[N-i+1]==OK and K[N-i+2]==BRO:
      c[i]=c[i-1]
    if K[N-i+1]==BRO and K[N-i+2]==OK:
      c[i]=c[i-2]
  c[i]%=1000000007
  
print(c[N] % 1000000007)

Solution (Python):
import sys
MOD = 1000000007

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

count = [0 for i in range(n+1)]
nxt = 0

def scount(s,e):
    
    global count
    for i in range(s,e):
        if i == 0:
            count[i] = 1 
        elif i == 1:
            count[i] = 1
        else:
            count[i] = (count[i-1] + count[i-2]) % MOD

for i in range(m):
    a = int(input())
    if nxt == a:
        print(0)
        exit(0)
    scount(nxt,a)
    nxt = a+1

scount(nxt,n+1)


print(count[n])

Solution (Python):
OK = 0
BRO = 1
MOD = 1000000007

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

K = list(0 for i in range(N+1))
for i in range(M):
  K[Broken[i]] = 1
  
dp=[0 for i in range(N+1)]
dp[0]=1
for i in range(N):
  for j in range(i+1,min(i+2+1,N+1)):
    if K[j]==OK:
      dp[j]+=dp[i]
      dp[j]%=MOD
      
print(dp[N])

Solution (Python):
d = 1000000007
N, M = list(map(int, input().split()))
a = [int(input()) for i in range(M)]
safe = [True for i in range(N+1)]
for ai in a:
  safe[ai] = False
dp = [0 for i in range(N+1)]
dp[0] = 1
dp[1] = 1 if safe[1] else 0
for i in range(2, N+1):
  dp[i] = (dp[i-2]+dp[i-1]) % d if safe[i] else 0
print(dp[N])

Solution (Python):
import sys
n = [int(i) for i in input().split()]
a = []
for i in range(n[1]):
    a.append(int(input()))

a.append(n[0]+1)
a = sorted(list(set(a)))


def k(i):
    ans = 1
    pri = 0
    for idx in range(i):
        tmp = ans
        ans += pri
        pri = tmp
    return ans


for i in range(1, len(a)):
    if a[i]-a[i-1] == 1:
        print(0)
        sys.exit()
j = -1
ans = 1
for i in a:
    ii = i-j-2
    ans = ans*k(ii)
    j = i
if len(a) == 1:
    ans = k(n[0])
print(ans % 1000000007)

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

N, M = map(int, input().split())
L = set([int(input()) - 1 for _ in range(M)])
ans = [0] * N

if 0 not in L:
    ans[0] = 1
    
if N > 1 and 1 not in L:
    ans[1] = ans[0] + 1

for i in range(2, N):
    if i in L:
        continue
    
    if ans[i - 2] != 0 or ans[i - 1] != 0:
        ans[i] = ans[i - 2] + ans[i - 1]
        
print(ans[-1] % (1000000007))

Solution (Python):
MOD = 1000000007
N = 100001

fibo = [1, 1] + [0] * N
for i in range(2, N):
    fibo[i] = (fibo[i - 1] + fibo[i - 2]) % MOD

n, m = list(map(int, input().split(" ")))
a_list = [int(input()) for _ in range(m)]
is_ngs = [0] * (n + 2)
for a in a_list:
    is_ngs[a] = 1
for i in range(n):
    if is_ngs[i] and is_ngs[i + 1]:
        print(0)
        exit()
cnts = []
cnt = 0

for i in range(n + 1):
    if is_ngs[i]:
        cnts.append(cnt)
        cnt = 0
        continue
    cnt += 1
cnts.append(cnt)
ans = 1
for c in cnts:
    if c != 0:
        ans *= fibo[c - 1]


print(ans % MOD)

Solution (Python):
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
num = 10**9+7
nots = [int(input()) for i in range(m)]
dp = [-1]*(n+1)
dp[0] = 1

for i in nots:
  dp[i] = 0

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

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

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

Solution (Python):
import sys
import numpy as np

MOD = 1000000007

def main():
    n, m = [int(x) for x in input().split()]
    pattern = [1]
    broken = -1
    brokencnt = 0
    if brokencnt < m:
        broken = int(input())
        brokencnt += 1
    for i in range(1, n + 1):
        if i == broken:
            pattern.append(0)
            if brokencnt < m:
                broken = int(input())
                brokencnt += 1
            continue
        if i == 1:
            pattern.append(pattern[i - 1])
        if i > 1:
            pattern.append((pattern[i - 1] + pattern[i - 2]) % MOD)
    print(pattern[n])


main()

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9 + 7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))


def main():
    n,m = LI()
    a = [I() for _ in range(m)] + [inf]
    b = 0
    c = 1
    ai = 0
    for i in range(1,n+1):
        if a[ai] == i:
            ai += 1
            b,c = c,0
        else:
            b,c = c,b+c
            c %= mod

    return c


print(main())

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

mod = 10 ** 9 + 7

dp = [0] * 100010

j = 0
dp[0] = 1
if M > 0:
    if a[0] == 1:
        dp[1] = 0
        j += 1
    else:
        dp[1] = 1
else:
    dp[1] = 1

a += [-1]
for i in range(2, N+1):
    if M > 0:
        if i == a[j]:
            dp[i] = 0
            j += 1
            continue
    dp[i] = dp[i-1] + dp[i-2]
    dp[i] %= mod

print(dp[N] % mod)

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

ans=[0]*100001
ans[0]=1
if a[1]:
    ans[1]=0
else:
    ans[1]=1

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

Solution (Python):
N, M = map(int, input().split())
broken = []
for i in range(0, N+1):
	broken.append(False)
for i in range(0, M):
	broken[int(input())] = True
dp = [1, 1]
if broken[1]: dp[1] = 0
for i in range(2, N+1):
	if broken[i]: dp.append(0)
	else: dp.append(dp[-1]+dp[-2])
print(dp[N]%1000000007)

Solution (Python):


def main():
    num, koware_num = map(int, input().split())
    data = set([int(input()) for i in range(koware_num)])
    dp = [0 for i in range(num + 1)]
    dp[0] = 1
    if 1 not in data:
        dp[1] = 1

    mod = 10 ** 9 + 7

    for i in range(2, num + 1):
        if i in data:
            continue
        dp[i] = (dp[i - 2] + dp[i - 1]) % mod

    print(dp[num])



if __name__ == '__main__':
    main()