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


def main():
    MOD = 10 ** 9 + 7
    sc = Scan()
    n, m = sc.intarr()
    w = sc.intarr_ver(m)
    is_safe = [True] * (n)
    for i in w:
        is_safe[i-1] = False
    dp = [0] * (n+2)
    dp[1] = 1
    for i in range(2, n+2):
        if is_safe[i-2]:
            dp[i] = dp[i-1] + dp[i-2]
            dp[i] %= MOD
        else:
            dp[i] = 0
    print(dp[n+1])


class Scan():

    def intarr(self):
        line = input()
        array = line.split(' ')
        num_array = [int(n) for n in array]
        return num_array

    def intarr_ver(self, n):
        return [int(input()) for _ in range(n)]

    def strarr(self):
        line = input()
        array = line.split(' ')
        array[-1] = array[-1].strip('\n')
        return array


main()

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


def main():
    MOD = 10 ** 9 + 7
    sc = Scan()
    n, m = sc.intarr()
    w = sc.intarr_ver(m)
    is_safe = [True] * (n+2)
    for a in w:
        is_safe[a + 1] = False
    dp = [0] * (n+2)
    dp[1] = 1
    for i in range(2, n+2):
        if is_safe[i]:
            dp[i] = dp[i-1] + dp[i-2]
            dp[i] %= MOD
        else:
            dp[i] = 0

    print(dp[n+1])


class Scan():

    def intarr(self):
        line = input()
        array = line.split(' ')
        num_array = [int(n) for n in array]
        return num_array

    def intarr_ver(self, n):
        return [int(input()) for _ in range(n)]

    def strarr(self):
        line = input()
        array = line.split(' ')
        array[-1] = array[-1].strip('\n')
        return array


main()

Solution (Python):
MOD=10**9+7
N,M=map(int,input().split())
A=[True]*(N+2)

for i in range(M):
    a=(int(input())+1)
    A[a]=False

S=[0]*(N+2)
S[1]=1
for i in range(2,N+2):
    if(A[i]):
        S[i]=(S[i-1]+S[i-2])%MOD
    else:
        S[i]=0
print(S[N+1])

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

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

for i in range(idx+1, N+1):
    dp[i] = dp[i-1] + dp[i-2]
    dp[i] %= mod

print(dp[-1])

Solution (Python):
n,m=map(int,input().split())
a=[0]*(n+1)
b=[int(input()) for i in range(m)]
a[0]=a[1]=1
if m==0:
  for i in range(2,n+1):
    a[i]=(a[i-1]+a[i-2])%(10**9+7)
else:
  j=0
  if b[0]==1:
    a[1]=0
    if m>1:
      j=1
  for i in range(2,n+1):
    if i==b[j]:
      if j<m-1:
        j+=1
    else:
      a[i]=(a[i-1]+a[i-2])%(10**9+7)
print(a[n])

Solution (Python):
import sys
N,M=map(int,input().split(' '))
if M>0:
  As=set(map(int,sys.stdin))
else:
  As=set()

d=[0]*(N+1)
d[0]=1
if 1 in As:
  pass
else:
  d[1]=1

for i in range(2,N+1):
  if i in As:
    continue
  else:
    d[i]=(d[i-1]+d[i-2])%1000000007

print(d[-1])

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):
import math

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

'''
factorial_list = [1] * (N+1)
for i in range(1,N+1):
    factorial_list[i] = factorial_list[i-1] * i

def combinations_count(n, r):
    return factorial_list[n] // (factorial_list[n - r] * factorial_list[r])
'''

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


def nCk(n, k):
    ret = 1
    mo = 10**9 + 7
    for i in range(k):
        ret = ret * (n - i) * pow(i + 1, mo - 2, mo) % mo
    return ret

def one_two_comb(N):
    two_n = N//2
    comb_list = []
    for i in range(1,two_n+1):
        comb_list.append([N-i,i])
    return comb_list

def sum_comb(comb_list):
    comb_sum = 0
    for val in comb_list:
        comb_sum += nCk(val[0],val[1])
    return comb_sum
    

diff_list = []
current_num = 0
max_diff = -1
for a in An:
    diff = a - current_num
    if diff == 0:
        print(0)
        exit(0)
    diff_list.append(diff)
    current_num = a +1
diff = N+1 - current_num
diff_list.append(diff)



all_sum = 1
for idx,diff in enumerate(diff_list):
    
    if idx == 0 or len(diff_list):
        diff -= 1
    '''
    if diff == 0:
        all_sum *= 1
    else:
        internal_comb_list = one_two_comb(diff)
        comb_count = sum_comb(internal_comb_list) + 1
        if all_sum > 10**9+7:
            all_sum = all_sum%(10**9+7)
        all_sum *= comb_count
    '''

    comb_count = feruma_list[diff]
    if all_sum > 10**9+7:
        all_sum = all_sum%(10**9+7)
    all_sum *= comb_count

print(all_sum%(10**9+7))

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

dp = [0] * (n + 1)
dp[0] = 1
if 1 not in broken_stairs:
	dp[1] = 1
else:
	dp[1] = 0
for i in range(2, n + 1):
	if i in broken_stairs:
		continue
	dp[i] = dp[i - 1] + dp[i - 2]
	dp[i] %= INF
print(dp[n])

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

dp = [0] * (n + 1)
dp[0] = 1
if 1 not in broken_stairs:
	dp[1] = 1
else:
	dp[1] = 0
for i in range(2, n + 1):
	if i in broken_stairs:
		continue
	dp[i] = dp[i - 1] + dp[i - 2]
	dp[i] %= INF
print(dp[n])

Solution (Python):


import sys










mod = 10 ** 9 + 7
def main():
    n, m, *a = [int(x) for x in sys.stdin.read().split()]

    safe = sorted(set(range(1,n+1)) - set(a))
    dp = [0] * (n + 2) 
    dp[0] = 0  
    dp[1] = 1  
    for i in safe:
        dp[i+1] = (dp[i] + dp[i-1]) % mod

    print(dp[-1])

if __name__ == "__main__":
    main()

Solution (Python):
import sys

mod = 10 ** 9 + 7
n, m, *a = [int(x) for x in sys.stdin.read().split()]

safe = sorted(set(range(1,n+1)) - set(a))
dp = [0] * (n + 2)
dp[0] = 0
dp[1] = 1
for i in safe:
    dp[i+1] = (dp[i] + dp[i-1]) % mod

print(dp[-1])

Solution (Python):
a = [-1]

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

for _ in range(M):
    a.append(int(input()))
a.append(N+1)



b = []
for i in range(M+1):
    b.append(a[i+1] - a[i] - 2)

if min(b) < 0:
    print(0)
else:
    result = 1

    f_list = []
    for i in range(max(b)+1):
        if i == 0 or i == 1:
            f_list.append(1)
        else:
            f_list.append(f_list[i-2] + f_list[i-1])

    for i in range(M+1):
        result = result * f_list[b[i]]
        result = result % (10**9 + 7)

    print(result)

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

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

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

Solution (Python):
N, M = map(int, input().split())
a = []
dp = [0]*(N+1)
br = [False]*(N+1)
for i in range(M):
  br[int(input())] = True
  
dp[0] = 1
if br[0] is not True:
  dp[1] = 1

for i in range(2, N+1):
  if br[i-1] is not True:
    dp[i] += dp[i-1]
  if br[i-2] is not True:
    dp[i] += dp[i-2]    
  dp[i] %= 1000000007
    
print(dp[N])

Solution (Python):
import sys
input = sys.stdin.readline
N, M = map(int,input().split())
hole = [0] * (N+1)
for i in range(M):
    hole[int(input())] = 1
if N == 1:
    print(1)
    exit()
if N == 2:
    if hole[1] == 1:
        print(1)
        exit()
    if hole[1] == 0:
        print(2)
        exit()
flg_one = False
flg_two = False
first = 1
second = 2
if hole[1] == 1:
    first = 0
    second = 1
    flg_one = True
if hole[2] == 1:
    first = 1
    second = 0
    flg_two = True
if flg_one and flg_two:
    print(0)
    exit()

for i in range(3,N):
    if hole[i] == 1:
        first = second
        second = 0
        continue
    tmp = first + second
    tmp %= 1000000007
    first = second
    second = tmp
tmp = first + second
tmp %= 1000000007
print(tmp)

Solution (Python):
def dp1(n,a):
    dp=[0]*(n+1)
    dp[0]=1
    ok=[True]*(n+1)
    for x in a:
        ok[x]=False
    if 1 not in a:
        dp[1]=1
    if n==1:
        return dp[1]
    else:
        for i in range(2,n+1):
            if ok[i]:
                dp[i]=(dp[i-1]+dp[i-2])%1000000007 
    return dp[n]

def main():
    n, m= map(int, input().split())
    a = [int(input()) for _ in range(m)]    
    print(dp1(n,a))

main()

Solution (Python):

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

MOD = 10**9+7
dp = [0 for i in range(N+2)]
dp[N] = 1

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

print(dp[0])

Solution (Python):

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

MOD = 10**9+7
dp = [0 for i in range(N+2)]
dp[N] = 1

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

print(dp[0])

Solution (Python):
import numpy as np
N , M = map(int, input().split())
a = list()
for n in range(M):
    a.append(int(input()))
dp = np.zeros(N+1)
dp[0] = 1
if M == 0:
    dp[1] = 1
else:
    dp[1] = 0 if a[0] == 1 else 1
ok = [False]*(N+1)
for x in a:
    ok[x] = True
for n in range(2,N+1):
    if ok[n]:
        continue
    dp[n] = (dp[n-1]+dp[n-2])%(10**9+7)
print(int(dp[N]))

Solution (Python):
N, M = map(int, input().split())
a = []
dp = [0 for i in range(N + 2)]
dp[0] = 0
dp[1] = 1
db = [1 for j in range(N + 2)]
for i in range(M):
    ta = int(input())
    db[ta + 1] = 0
for i in range(2, N + 2):
    if db[i]:
        if dp[i - 2]:
            if dp[i - 1]:
                dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007
            else:
                dp[i] = dp[i - 2]
        else:
            if dp[i - 1]:
                dp[i] = dp[i - 1]
            else:
                print(0)
                exit()
    else:
        dp[i] = 0
print(dp[N + 1])

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

arr = [0] * (N + 1)
arr[1] = 1 if a[1] else 0
if 2 <= N:
    arr[2] = arr[1] + 1 if a[2] else 0
    for i in range(3, N + 1):
        arr[i] = arr[i - 2] + arr[i - 1] if a[i] else 0

print(arr[N] % 1000000007)

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
def input():
    return sys.stdin.readline().rstrip()

def main():
    N,M=map(int,input().split())
    a=[int(input()) for i in range(M)]
    dp=[1]*(N+1)
    if M!=0:
        dp[1]=0 if a[0]==1 else 1
        for i in a:
            dp[i]=0
    for i in range(1,N):
        if dp[i+1]!=0:
            dp[i+1] = (dp[i]+dp[i-1]) % 1000000007
    print(dp[N])


if __name__ == '__main__':
    main()

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

MOD = 10 ** 9 + 7
MIN = 100


def org(N, M, dp):
    a = [0] * M

    dp[0] = 1
    dp[1] = 1
    dp[2] = 2
    for i in range(3, max(N+1, MIN)):
        dp[i] = dp[i-1] + dp[i-2]

    ans = 1

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

        if i != 0 and abs(a[i] - a[i-1]) == 1:
            print(0)
            return

        if a[i] == 1:
            ans *= 1
        elif i == 0:
            ans *= dp[a[i] - 1]
            ans %= MOD
            
        else:
            ans *= dp[a[i] - a[i-1] - 2]
            ans %= MOD
            

    if M == 0:
        ans *= dp[N]
        ans %= MOD
        
        print(ans)
    else:
        ans *= dp[N - a[M-1] - 1]
        ans %= MOD
        
        print(ans)


def good(N, M, dp):
    a = [0] * len(dp)

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

    dp[0] = 0 if a[0] is True else 1
    dp[1] = 0 if a[1] is True else dp[0] + 1

    if N == 1:
        print(dp[0])
        return
    elif N == 2:
        print(dp[1])
        return

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

    print(dp[N-1] % MOD)
    


def main():
    N, M = map(int, input().split())
    dp = [0] * max((N + 1), MIN)

    good(N, M, dp)


if __name__ == '__main__':
    main()

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

MOD = 10 ** 9 + 7
MIN = 100


def main():
    N, M = map(int, input().split())
    memo = [0] * max((N + 1), MIN)
    a = [0] * M

    memo[0] = 1
    memo[1] = 1
    memo[2] = 2
    for i in range(3, max(N+1, MIN)):
        memo[i] = memo[i-1] + memo[i-2]

    ans = 1

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

        if i != 0 and abs(a[i] - a[i-1]) == 1:
            print(0)
            return

        if a[i] == 1:
            ans *= 1
        elif i == 0:
            ans *= memo[a[i] - 1]
            ans %= MOD
            
        else:
            ans *= memo[a[i] - a[i-1] - 2]
            ans %= MOD
            

    if M == 0:
        ans *= memo[N]
        ans %= MOD
        
        print(ans)
    else:
        ans *= memo[N - a[M-1] - 1]
        ans %= MOD
        
        print(ans)


if __name__ == '__main__':
    main()

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

MOD = 10 ** 9 + 7


def main():
    N, M = map(int, input().split())
    memo = [0] * max((N + 1), 10)
    a = [0] * M

    memo[0] = 1
    memo[1] = 1
    memo[2] = 2
    for i in range(3, max(N+1, 10)):
        memo[i] = memo[i-1] + memo[i-2]

    
    ans = 1

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

        if i != 0 and abs(a[i] - a[i-1]) == 1:
            print(0)
            return

        if a[i] == 1:
            ans *= 1
        elif i == 0:
            ans *= memo[a[i] - 1]
            ans %= MOD
            
        else:
            ans *= memo[a[i] - a[i-1] - 2]
            ans %= MOD
            

    if M == 0:
        ans *= memo[N]
        ans %= MOD
        
        print(ans)
    else:
        ans *= memo[N - a[M-1] - 1]
        ans %= MOD
        
        print(ans)


if __name__ == '__main__':
    main()

Solution (Python):

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

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

    p = 0
    steps=[]
    m = 0
    for a in a_list:
        if a != 1:
            steps.append((p, a-1))
            m = max(m, a-p)
        p = a + 1
    else:
        steps.append((p, N))
        m = max(m, N-p+1)

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

    divider = 1000000007
    dp[0], dp[1] = 1, 1
    for i in range(2,m+1):
        dp[i]=(dp[i-1]+dp[i-2])%divider

    ans = 1
    for p, n in steps:
        if n < p:
            ans = 0
            break
        else:
            r = dp[n-p]
        ans = (ans*r)%divider 

    print(ans)
        


if __name__ == '__main__':
    main()

Solution (Python):
N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
inf = float("inf")
dp = [0] * (N+1)
for i in A:
	dp[i] = inf
dp[0] = 1
if dp[1] != inf:
	dp[1] = 1
for i in range(2,N+1):
	if dp[i] == inf:
		continue

	a = dp[i-2] if dp[i-2] != inf else 0
	b = dp[i-1] if dp[i-1] != inf else 0

	dp[i] = (a + b) % 1000000007


print(dp[N])

Solution (Python):
MOD = 1000000007

n, m = map(int, input().split())
a = [-1] + [int(input()) for i in range(m)] + [n+1]

fib = [0, 1]
fa, fb = 0, 1
for _ in range(n):
    fa, fb = fb,(fa + fb) % MOD
    fib.append(fb)

ans = 1
for i in range(m + 1):
   ans *= fib[a[i + 1] - a[i] - 1] % MOD
print(ans%MOD)

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

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

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

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

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

for i in range(n+1):
    if i == 0:
        dp[0] = 1
    elif i == 1 and al[1] == 0:
        dp[1] = dp[0]
    else:
        if al[i] == 0:
            dp[i] = dp[i-1] + dp[i-2]
            dp[i] %= 1000000007

print(dp[-1])

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

lis = [0 for i in range(n+1)]
lis[0] = 1
if s1 == 1:
    lis[1] = 0
    p += 1
    if p > m - 1:
        pass
    else:
        s1 = s[p]
else:
    lis[1] = 1

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

Solution (Python):
n, m = (int(_) for _ in input().split())
a = [int(input()) for _ in range(m)]
ai, p1, p2 = (0, 0, 1)

for i in range(1, n+1):
    if ai < m and i == a[ai]:
        p = 0
        ai += 1
    else:
        p = p1 + p2
    p1 = p2
    p2 = p

print(p%1000000007)

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

p1 = 0
p2 = 1

for i in range(1, n+1):
    if ai < m:
        if i == a[ai]:
            p = 0
            ai += 1
        else:
            p = p1 + p2
    else:
        p = p1 + p2
    p1 = p2
    p2 = p

print(p%1000000007)

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

break_list.append(-10)
t = 0
fib = [0] * (N + 1)
if break_list[0] == 1:
    fib[1] = 0
    t += 1
else:
    fib[1] = 1
    
fib[0] = 1

for i in range(N - 1):
    if ( i + 2 ) ==  break_list[t]:
        fib[i + 2] = 0
        t += 1
    else:
        fib[i + 2] = fib[i] + fib[i + 1]
 
if N == 1:
    print( fib[1] )
else:
    print( fib[i+2] %  1000000007 )

Solution (Python):
import sys
n,m = map(int,input().split())
fib = []
mod = 10**9 + 7

a = []
for i in range(m):
    a.append(int(input()))
    if a[i] == a[i-1] +1:
        print(0)
        sys.exit()
a.append(n+1)
dp = [1]
tmp = 0
for i in range(1,n+1):
    if i == a[tmp]:
        tmp += 1
        dp.append(0)
    elif i > 1:
        dp.append((dp[i-1] + dp[i-2])%mod)
    else:
        dp.append(1)

print(dp[-1])

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

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

broken = [False] * (n + 1)

for i in range(m):
    broken[a[i]] = True

dp = []
dp.append(1)

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

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

print(dp[n])

Solution (Python):
N, M = map(int, input().split())
A = set([int(input()) for i in range(M)])
t = 10**9+7
import sys
sys.setrecursionlimit(500000)
from functools import lru_cache
@lru_cache(maxsize=None)
def fibo(n):
    if n in A:
        return 0
    elif n == 0 or n == 1:
        return 1
    return (fibo(n-2) + fibo(n-1)) % t
print(fibo(N) % t)

Solution (Python):

n, m = map(int, input().split())
a = [int(input()) for i in range(m)]
s = [1] + [0 for i in range(1,n+1)]
p = 1000000007
if n==1:
    print(1)
else:
    ind = 0
    if ind < m:
        if a[0] != 1:
            s[1] = 1
        else:
            ind += 1
    else:
        s[1] = 1
    for i in range(2,n+1):
        if ind < m:
            if a[ind] != i:
                s[i] = (s[i-1] + s[i-2]) % p
            else:
                ind += 1
        else:
            s[i] = (s[i-1] + s[i-2]) % p
    print(s[-1])

Solution (Python):
sum_ = [0]

N,M = input().split()
N,M = int(N),int(M)
m_ = []
for i in range(M):
    m_.append(int(input()))


m = [1 for i in range(N+1)]
for i in m_:
    m[i] = 0
for i in range(1,N+1):
    if(i==1):
        if(m[i]==1):
            sum_.append(1)
        else:
            sum_.append(0)
    elif(i==2):
        if(m[i]==1):
            sum_.append(1+sum_[1])
        else:
            sum_.append(sum_[1])
    
    else:
        sum_.append((m[i-1]*sum_[i-1]+m[i-2]*sum_[i-2])*m[i])
print(sum_[N]%1000000007)

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

for i in range(N-1):
  if (i+2) == cantuse:
    dp.append(0)
    if a:
      cantuse = a.pop(0)
  else:
    dp.append(dp[-1]+dp[-2])
print(dp[-1]%1000000007)

Solution (Python):
tmp = list(map(int, input().split()))
n = tmp[0]
m = tmp[1]

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

for i in range(2, n+1):
  if s[i] != 0:
    s[i] = s[i-1] + s[i-2]

print(s[n] % 1000000007)

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

def main():
    n,m=map(int,input().split())
    if n == 1:
        print(1)
        return
    aa=[]
    for _ in range(m):
        aa.append(int(input()))
    for i in range(m-1):
        if aa[i]+1==aa[i+1]:
            print(0)
            return
    cc = [0] * n
    i = 0
    j = 2 
    cc[0] = 1
    if m < 1 or aa[0] > 1:
        cc[1] = 1
    else:
        cc[1] = 0
        i += 1
    while j < n:
        if i < m and aa[i] == j:
            i+=1
        else:
            cc[j]=cc[j-1]+cc[j-2]
        j+=1
    print((cc[n-1]+cc[n-2])%1000000007)

main()

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


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

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

  
dp = [0]*N

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

for i in range(2,N):
  dp[i] = (dp[i-1]+dp[i-2]) *a[i]
  
print(dp[-1]%mod)

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

Solution (Python):
n,m=map(int,input().split())
broken=[0]*m
for i in range(m):
  broken[i]=int(input())
broken=set(broken)
  
dp=[0]*(n+1)
dp[0]=1
dp[1]=1 if 1 not in broken else 0

for i in range(2,len(dp)):
  if i in broken:
    dp[i]=0
  else:
    dp[i]=(dp[i-2]+dp[i-1])%1000000007
  
print(dp[-1])

Solution (Python):
n,m=map(int,input().split())
broken=[False]*(n+1)
for i in range(m):
  broken[int(input())]=True
dp=[0]*(n+1)
dp[0]=1
dp[1]=0 if broken[1] else 1

for i in range(2,len(dp)):
  if broken[i]:
    dp[i]=0
  else:
    dp[i]=(dp[i-2]+dp[i-1])%1000000007
  
print(dp[-1])

Solution (Python):
def p_c():
    nb, mb = map(int, input().split())
    mod = 10 ** 9 + 7
    ans = 1
    fb = [1, 1]
    current = 0
    for _ in range(mb):
        a = int(input())
        width = a - current - 1
        if width == -1:
            ans = 0
            break
        while width > len(fb) - 1:
            fb.append(fb[-1] + fb[-2])
        ans *= fb[width]
        current = a + 1
        ans %= mod
    width = nb - current
    while width > len(fb) - 1:
        fb.append(fb[-1] + fb[-2])
    ans *= fb[width]
    ans %= mod
    print(ans)
    
p_c()

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

for i in range(M):
    B[int(input())] = True


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

dp[0] = 1
dp[1] = 1
mod = 1000000007
for i in range(2, N + 1):
    if not B[i - 1]:
        dp[i] = (dp[i] + dp[i - 1]) % mod
    if not B[i - 2]:
        dp[i] = (dp[i] + dp[i - 2]) % mod
    if dp[i] == 0:
        break

print(dp[N])

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

Solution (Python):
def xgcd(a, b):
    if b == 0:
        g = a
        x = 1
        y = 0
        return g, x, y
    else:
        g, s, t = xgcd(b, a%b)
        x = t
        y = s - a//b*x
        return g, x, y

def invmod(a, p):
    _, x, _ = xgcd(a, p)
    if x < 0:
        x = x + p
    return x

def count_route(n):
  if n < 0:
    return 0
  res = 0
  for i in range(n//2+1):
    res += f[n - i] * inv[i] * inv[n - 2* i]
  return res%const
    
n, m = map(int, input().split())
const = 1000000007

f = [1 for i in range(n + 1)]
inv = [1 for i in range(n + 1)]
for i in range(1, n+1):
  f[i] = (f[i - 1] * i)%const
  inv[i] = invmod(f[i], const)
prev = 0
ans = 1
for i in range(m):
  m = int(input())
  ans = (ans * count_route(m - 1 - prev))%const
  prev = m + 1
  if ans == 0:
    break
ans = (ans * count_route(n - prev))%const
print(ans)

Solution (Python):
n,m=map(lambda x: int(x), input().split())
INF=10**12
dp=[INF]*n
for _ in range(m):
    dp[int(input())-1]=0
dp[0]=1 if dp[0]==INF else 0
if n>1:
    dp[1]=dp[0]+1 if dp[1]==INF else 0
if n>2:
    for i in range(2, n):
        if dp[i]==0:
            continue
        dp[i]=(dp[i-1]+dp[i-2])%(10**9+7)
print(dp[n-1])

Solution (Python):

import sys
sys.setrecursionlimit(10000000)
INF = 1<<32

MOD = 1000000007  

def solve(N: int, M: int, a: "List[int]"):
    dp = [-1] *(N+2)
    ckc = [True] * (N+2)
    for i in a:
        ckc[i] = False

    def f(n: int):
        if(dp[n] != -1):
            return dp[n]

        if n <= 0:
            dp[n] = 0
        else:
            if not ckc[n-1] and not ckc[n-2]:
                dp[n] = 0
            elif not ckc[n-1]:
                dp[n] = f(n-2) % MOD
            elif not ckc[n-2]:
                dp[n] = f(n-1) % MOD
            else:
                dp[n] = (f(n-1) + f(n-2)) % MOD
            
        return dp[n]

    dp[0] = 1
    f(N)
    print(dp[N])
    

    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):
def main():
    n, m = map(int, input().split())
    a = set([int(input()) for _ in range(m)])

    ansls = [0]*(n+1)

    if 0 not in a:
        ansls[0] = 1
    if 1 not in a:
        ansls[1] = 1

    for i in range(2, n+1):
        if i not in a:
            ansls[i] = (ansls[i-2] + ansls[i-1])%(10**9 + 7)
    
    print(ansls[-1])
    
if __name__ == "__main__":
    main()

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

    ansls = [0]*(n+1)
    

    if 0 not in a:
        ansls[0] = 1
    if 1 not in a:
        ansls[1] = 1

    for i in range(2, n+1):
        if i not in a:
            ansls[i] = (ansls[i-2] + ansls[i-1])%(10**9 + 7)
    
    print(ansls[-1])
    
if __name__ == "__main__":
    main()

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

    ansls = [0]*(n+1)
    big = 10**9 + 7

    if 0 not in a:
        ansls[0] = 1
    if 1 not in a:
        ansls[1] = 1

    for i in range(2, n+1):
        if i not in a:
            ansls[i] = (ansls[i-2] + ansls[i-1])%(10**9 + 7)
    
    print(ansls[-1])
    
if __name__ == "__main__":
    main()

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

    ansls = [0]*(n+1)
    big = 10**9 + 7

    if 0 not in a:
        ansls[0] = 1
    if 1 not in a:
        ansls[1] = 1

    for i in range(2, n+1):
        if i not in a:
            ansls[i] = (ansls[i-2] + ansls[i-1])%(10**9 + 7)
    
    print(ansls[-1])
    
if __name__ == "__main__":
    main()

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

    ansls = [0]*(n+1)
    big = 10**9 + 7

    if 0 not in a:
        ansls[0] = 1
    if 1 not in a:
        ansls[1] = 1

    for i in range(2, n+1):
        if i not in a:
            ansls[i] = (ansls[i-2] + ansls[i-1])%big
    
    print(ansls[-1])
    
if __name__ == "__main__":
    main()

Solution (Python):

big=10**9+7

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

a = set([int(input()) for _ in range(m)])
  

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

for i in range(2,n+1):
  if i not in a:
    cho[i] = (cho[i-1]+cho[i-2])%big


print(cho[-1])

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

a = {int(input()) for _ in range(m)}
route = [0] * (n + 1)

route[0] = 1
for i in range(1, n + 1):
    
    if not (i in a):
        if i == 1:
            route[i] = 1
        else:
            route[i] = (route[i - 1] + route[i - 2]) % (10 ** 9 + 7)
print(route[n])

Solution (Python):
import sys
import collections


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, input().rstrip('\n').split()))
    a = collections.defaultdict(list)
    for _ in range(m):
        a[int(input().rstrip('\n'))]
    ls = [0] * (n + 1)
    ls[0] = 1 if 0 not in a else 0
    ls[1] = 1 if 1 not in a else 0
    for i in range(2, n + 1):
        if i not in a:
            ls[i] = (ls[i-1] + ls[i-2]) % mod
        else:
            ls[i] = 0
    print(ls[-1])


if __name__ == '__main__':
    solve()