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

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

f = [0 for i in range(n)]
f[-2:] = [1, 1]
for i in range(m):
  f[int(input())-1] = -1

div_num = 1000000007

for i in range(n-2)[::-1]:
  if f[i] == -1:
    continue
  if f[i+1] == -1 and f[i+2] == -1:
    print(0)
    exit()
  elif f[i+1] == -1 and f[i+2] != -1:
    f[i] = f[i+2]
  elif f[i+1] != -1 and f[i+2] == -1:
    f[i] = f[i+1]
  else:
    f[i] = f[i+1]+f[i+2]

if f[0] != -1 and f[1] != -1:
  print(int((f[0]+f[1])%div_num))
elif f[0] == -1 and f[1] != -1:
  print(int(f[1]%div_num))
elif f[0] != -1 and f[1] == -1:
  print(int(f[0]%div_num))
else:
  print(0)

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

m = [0] * n
m[0] = 1 if 1 not in a else 0

if n == 1:
    print(m[0])
    exit()

m[1] = 2 if 2 not in a else 0

if m[0] == 0 and m[1] == 2:
    m[1] = 1

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

print(m[-1] % 1000000007)

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

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

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

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

print(dp[n]%mod)

Solution (Python):
n,m = map(int,input().split())
dp = [1]*(n+1)

for _ in range(m):
    idx = int(input())
    dp[idx] = 0
for i in range(2,n+1):
    if dp[i] != 0:
        dp[i] = dp[i-1] + dp[i-2]
print(dp[-1]%1000000007)

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

a = [-1] + a + [N+1] 


s1=[]
for i in range(len(a)-1):
    if a[i+1]-a[i]-2<0:
        flag = False
        break
    s1.append(a[i+1]-a[i]-2) 

if flag==False:
    print(0)    
else:     
    
    s2 = [1, 1, 2]
    while len(s2) < max(s1)+1:
        s2.append(s2[-2]+s2[-1])
    
    
    s3 = 1 
    for j in s1:
        s3 = s3 * s2[j] 
        
    s4 = s3 % 1000000007 
    print(s4)

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

a = [-1] + a + [N+1] 


s1=[]
for i in range(len(a)-1):
    if a[i+1]-a[i]-2<0:
        flag = False
        break
    s1.append(a[i+1]-a[i]-2) 

if flag==False:
    print(0)    
else:     
    
    s2 = [1, 1, 2]
    while len(s2) < N+1:
        s2.append(s2[-2]+s2[-1])
    
    
    s3 = 1 
    for j in s1:
        s3 = s3 * s2[j] 
        
    s4 = s3 % 1000000007 
    print(s4)

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

Solution (Python):



n, m = list(map(int, input().split()))
a_list = []

for _ in range(m):
    a = int(input().split()[0])
    a_list.append(a)

steps_list = [dict(fx1=True, fx2=True) for _ in range(n + 1)]

for step_index in a_list:
    steps_list[step_index] = dict(fx1=False, fx2=False)

    if step_index < n - 1:
        steps_list[step_index + 1]['fx1'] = False
    if step_index < n - 2:
        steps_list[step_index + 2]['fx2'] = False

steps_list[1]['fx2'] = False
p_count_list = [0] * (n + 1)




for i, op in enumerate(steps_list):
    if i == 0:
        p_count_list[i] = 1
        continue

    p_count = 0
    if steps_list[i]['fx1']:
        p_count += p_count_list[i-1]
    if steps_list[i]['fx2']:
        p_count += p_count_list[i-2]

    p_count_list[i] = p_count % 1000000007


ans = p_count_list[-1]
print(ans)

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

if m > 0:
  As = set(map(int, sys.stdin))
else:
  As = set()

nums = [0] * (n + 1)
nums[0] = 1
if 1 in As:
  pass
else:
  nums[1] = 1
  
for i in range(2, n + 1):
  if i in As:
    continue
  else:
    nums[i] = (nums[i-1] + nums[i-2]) % 1000000007
    
print(nums[-1])

Solution (Python):
import sys

input = sys.stdin.readline

n, m = map(int, input().split())
mod = 10 ** 9 + 7
broken_steps = [False for _ in range(n + 1)]

for _ in range(m):
    broken_steps[int(input())] = True

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

for now in range(n):
    next = now + 1
    if not broken_steps[next]:
        steps[next] = (steps[now] + steps[now - 1]) % mod

print(steps[n])

Solution (Python):
import sys

input = sys.stdin.readline

n, m = map(int, input().split())
mod = 10 ** 9 + 7
broken_steps = [False for _ in range(n)]

for _ in range(m):
    a = int(input())
    broken_steps[a - 1] = True

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

for i in range(n):
    if not broken_steps[i]:
        steps[i + 1] = (steps[i] + steps[i - 1]) % mod

print(steps[n])

Solution (Python):
n,m = map(int,input().split(" "))
s = [0]*(n+1)
flag = 0
for i in range(m):
    s[int(input())] = 1
    if i>=1 and s[i-1] == 1 and s[i] == 1:
        flag = 1
i = 0
counter = 1
dp = [0 for i in range(n+1)]
dp[0] = 1
for i in range(0,n+1):
    for j in range(i+1,min(i+3,n+1)):
        if s[j] ==0:
            dp[j] += dp[i]
if flag == 1:
    print(0)
else: 
    print(dp[n] % 1000000007)

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

def main():
    N, M = map(int, input().split())
    broken_floors = set(int(input()) for _ in range(M))
    dp = [0]*(N+2)
    dp[1] = 1

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

    print(dp[-1])

if __name__ == '__main__':
    main()

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

N, M = map(int, input().split())
broken_floors = set(int(input()) for _ in range(M))
dp = [0]*(N+2)
dp[1] = 1

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

print(dp[-1])

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

def typical_stairs(n,m,a):

    flag = [True]*(n+1)
    for i in range(m):
        tmp = a[i]
        flag[tmp] = False

    route = [0]*(n+1)
    route[0] = 1
    ans = route[0]
    if flag[1]:
        route[1] = 1
    else:
        route[1] = 0

    for i in range(2,n+1):
        if flag[i]:
            route[i] = route[i-1] + route[i-2]

        ans = route[i]

    return ans%big
if __name__ == '__main__':
    n,m = map(int,raw_input().split())
    a = [int(raw_input()) for _ in range(m)]
    print typical_stairs(n,m,a)

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    N, M = map(int, input().split())
    A = {}
    mod = 10**9+7
    for _ in range(M):
        k = int(input())
        l = int(k)
        A[k] = 1
    answer = [0] * (N+1)
    answer[0] = 1
    if 1 in A:
        answer[1] = 0
    else:
        answer[1] = answer[0]
    
    for i in range(2,N+1):
        if i in A:
            answer[i] = 0
        else:
            answer[i] = (answer[i-1] + answer[i-2])%mod
    print(answer[-1])
    
    
    
main()

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

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

Solution (Python):
def main():
    N, M = map(int, input().split())
    a = set()
    for _ in range(M):
        a.add(int(input()))

    mod = pow(10, 9) + 7
    dp = [0 for _ in range(N+1)]
    dp[0] = 1
    for i in range(1, N+1):
        if i in a:
            dp[i] = 0
        else:
            if i == 1:
                dp[i] = dp[i-1]
            else:
                dp[i] = dp[i-1] + dp[i-2]
        dp[i] %= mod
    return dp[N]

if __name__ == '__main__':
    print(main())

Solution (Python):
N, M = map(int,input().split())
a = list(int(input()) for i in range(M))
a.append(N+1)
a.insert(0,-1)
if a[0] == 0:
  print(0)
  exit()

def Fib(n):
    a, b = 1, 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

ans = 1
if M > 1:
    for i in range(len(a)-1):
        n = a[i+1]-a[i]-1
        if n == 0:
            print(0)
            exit()
        ans = ans*Fib(n)%1000000007
        i += 1
    print(ans)
elif M == 1:
    print(Fib(a[1])%1000000007 * Fib(N-a[1])%1000000007)
elif M == 0:
    print(Fib(N+1)%1000000007)

Solution (Python):
from functools import lru_cache
from sys import setrecursionlimit

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

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

@lru_cache(maxsize=n)
def stairway(i) :
    if i in a :
        return 0
    elif i == 0 :
        return 1
    elif i == 1 :
        return stairway(0)
    else :
        return (stairway(i-1)+stairway(i-2))%mod
    
print(stairway(n))

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

MOD = 10 ** 9 + 7
n,m = map(int,input().split())
A = set(int(input()) for _ in range(m)) 

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

for i in range(1,n+1):
    if i in A:
        continue
    x = dp[i-1]
    if i > 1:
        x += dp[i-2]
    dp[i] = x%MOD

print(dp[n])

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

Bs = []
if len(As) == 0:
    Bs.append(N + 1)
else:
    Bs.append(As[0])
    for i in range(M-1):
        Bs.append(As[i+1] - As[i] - 1)
    Bs.append(N - As[-1])

count = [0, 1, 1]
for i in range(3, max(Bs)+1):
    count.append(count[i - 1] + count[i - 2])

res = 1
for b in Bs:
    res *= count[b]
    res %= 1000000007

print(res)

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

b=[]
num=0
if len(a)>1:
    b.append(a[1]-a[0]-1)
    for i in range(1,M):
            b.append(a[i+1]-a[i]-2)
    b.append(N-a[M]-1)
else:
    b.append(N)

num=max(b)

mod=1000000007

fib=[0 for i in range(num+10)]
fib[0]=1
fib[1]=1
for i in range(2,num+1):
    fib[i]=fib[i-1]+fib[i-2]

if -1 in b:
    print(0)
else:
    p=1
    for j in range(M+1):
        p*=fib[b[j]]
    print(p%mod)

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



mod = 10**9 + 7

d = [0]*(n+1)


d[0] = 1
d[1] = 1
for i in a:
    d[i] = -1




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

print(d[n]%mod)

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

DENOMINATOR = 1000000007

pos = 0
route = 1
before = 0

for i in range(1, N+1):
    route, before = route+before, route
    if pos < M:
        if A[pos] == i:
            route = 0
            pos+=1

print(route%DENOMINATOR)

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

b=[]
num=0
if len(a)>1:
    b.append(a[1]-a[0]-1)
    for i in range(1,M):
            b.append(a[i+1]-a[i]-2)
    b.append(N-a[M]-1)
else:
    b.append(N)

num=max(b)


mod=1000000007

def fib(n,num):
    fib=[0 for i in range(num+10)]
    fib[0]=1
    fib[1]=1
    for i in range(2,num+1):
        fib[i]=fib[i-1]+fib[i-2]
    return fib[n]

if -1 in b:
    print(0)
else:
    p=1
    for j in range(M+1):
        p*=fib(b[j],num)
    print(p%mod)

Solution (Python):
N, M = map(int, input().split())
a = set(int(input()) for i in range(M)) 

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

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

print (A[-1])

Solution (Python):
def resolve():
    n, m = list(map(int, input().split()))
    mod = 10 ** 9 + 7
    is_safe = [True] * (n + 1)
    broken = list(int(input()) for _ in range(m))
    for b in broken:
        is_safe[b] = False

    steps = [1] + [0] * n
    if is_safe[1]:
        steps[1] = 1
    for i in range(2, n + 1):
        if is_safe[i - 1]:
            steps[i] += steps[i - 1]
        if is_safe[i - 2]:
            steps[i] += steps[i - 2]
        steps[i] %= mod
    print(steps[n])


if __name__ == "__main__":
    resolve()

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

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

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

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

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

print(dp[n]%1000000007)

Solution (Python):
N, M = map(int, input().split())
A = set([int(input()) for _ in range(M)])
 
dp = [0, 1]
for i in range(N):
    if i+1 in A: dp.append(0)
    else: dp.append(dp[i]+dp[i+1])
print(dp[N+1]%1000000007)

Solution (Python):
dp = [1] * (10**5 + 1)
dp[2] = 2
for i in range(3, 10**5+1):
    dp[i] = (dp[i-1] + dp[i-2]) % 1000000007

n, m = map(int, input().split())
start = 0
res = 1
for i in range(m):
    nex = int(input())
    if nex == start:
        res = 0
        break
    res = (res * dp[(nex-1)-start]) % 1000000007
    
    start = nex + 1
else:
    res = (res * dp[n - start]) % 1000000007
    
print(res)

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

Solution (Python):
N, M = map(lambda x: int(x), input().split())
a = [int(input()) for _ in range(M)]
mod = 1e9+7

is_broken = [False]*(N+1)
for aa in a:
    is_broken[aa] = True

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

for now in range(N):
    for next in range(now+1, min(N, now+2)+1):
        if not is_broken[next]:
            dp[next] += dp[now]
            dp[next] %= mod
print(int(dp[N]))

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

mod = 10**9+7

for i in range(1, N+1):
    if A[i-1] == 0:
        dp[i] += dp[i-1]
    if A[i-2] == 0:
        dp[i] += dp[i-2]
    dp[i] %= mod
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

dp = [0]*(n+1)
dp[0] = 1
MOD = 10**9+7
   
for i in range(1,n+1):
  if hole[i]==1:
    dp[i] = 0
  else:
    dp[i] = dp[i-1]+dp[i-2]
    dp[i] %= MOD

print(dp[-1])

Solution (Python):
import sys

sys.setrecursionlimit(110000)

d = {}


def calc_step_combination(num):
    if num == 0:
        return 0
    if num == 1 or num == 2:
        return 1
    if num in d:
        return d[num]
    res = calc_step_combination(num - 1) + calc_step_combination(num - 2)
    d[num] = res
    return res


def sol(n, a_list):
    step_batch = []
    batch_start = 0
    for a in a_list:
        step_batch.append(a - batch_start)
        batch_start = a + 1
    step_batch.append(n - batch_start + 1)

    result = 1
    for i, steps in enumerate(step_batch):
        result *= calc_step_combination(steps)
    print(result % 1000000007)


def main():
    n, m = map(int, input().split())
    a_list = []
    for i in range(0, m):
        a_list.append(int(input()))
    sol(n, a_list)


main()

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


def fibonacci(n):
    
    if n <= 0:
        a = 0
    elif n<=2:
        a =1
    else:
        a0=1
        a1=1
        for i in range(3,n+1):
            a = a0 + a1
            a0 = a1
            a1 = a
    return(int(a))

ans = 1
t1 = 0
a_ind = 0
for i in range(N+1):
    if i == A[a_ind] or i == N:
        t2 = A[a_ind]
        ans *= fibonacci(t2-t1)
        t1 = A[a_ind]+1
        a_ind =min(a_ind+1, len(A)-1)
print(ans%1000000007)

Solution (Python):


from collections import defaultdict

def Fib(n, broken):
    dd = defaultdict(int)

    dd[0] = 1
    dd[1] = 1

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

    return dd[n]


n, m = map(int, input().split())
A = [int(input()) for _ in range(m)]
broken = defaultdict(int)
for c in A:
    broken[c] = 1

ans = Fib(n, broken)
print(ans % 1000000007)

Solution (Python):


from collections import defaultdict

def Fib(n, broken):
    dd = defaultdict(int)

    dd[0] = 1

    for i in range(n):
        for j in range(i+1, min(n, i+2)+1):
            if broken[j] == 0:
                dd[j] += dd[i]
                dd[j] %= 1000000007

    return dd[n]


n, m = map(int, input().split())
A = [int(input()) for _ in range(m)]
broken = defaultdict(int)
for c in A:
    broken[c] = 1

ans = Fib(n, broken)
print(ans % 1000000007)

Solution (Python):
N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
MOD = 10**9 + 7
is_safe = [True] * (N+2)
for a in A:
    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])

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

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

d = [0] * (n+5)
d[1] = (0 if 1 in a else 1)
d[2] = (0 if 2 in a else d[1] + 1)

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

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

mod = 1000000007

dp = [1 for _ in range(N + 1)]
for a in A:
    dp[a] = 0

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

    if dp[n] >= mod:
        dp[n] -= mod

print(dp[N])

Solution (Python):
n,m = map(int,input().split())
a = [int(input()) for i in range(m)]
b = []
if a:
  b = [a[0]-1] + [a[i+1]-a[i]-2 for i in range(m-1)] + [n-a[m-1]-1]
c = [1,1]+[0]*(n-1)
for i in range(2,n+1):
  c[i] = c[i-1] + c[i-2]
ans = 1
if b:
  for j in b:
    if j == -1:
      ans = 0
      break
    ans = (ans * c[j]) %1000000007
else:
  ans = c[n] % 1000000007
print(ans)

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

def main():
    n, m = 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
    
    for i in range(2, n+1):
        if i in aaa:
            continue
        dp[i] = (dp[i-1]+dp[i-2])%mod
 
    print(dp[n])
 
main()

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

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

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

a = [1] * (n+1)

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

for i in range(n+1):
    if i > 1:
        a[i] = (a[i-2] + a[i-1])%(10**9+7) * a[i]

print(a[n])

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

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

print (dp[n] % 1000000007)

Solution (Python):
n, m = map(int, input().split())
a = []
for i in range(m):
  a.append(int(input()))
ans = 0
flag = 0
a = set(a)


dp = [0] * (n+1)
dp[0] = 1
if 1 in a:
  dp[1] = 0
else:
  dp[1] = 1
  
for i in range(2, n+1):
  if dp[i-2] == 0 and dp[i-1] == 0:
    ans = 0
    flag = 1
    break
  elif i in a:
    continue
  else:
    dp[i] = dp[i-1] + dp[i-2]
    dp[i] = dp[i] % (10**9+7)
if flag == 0:
  ans = dp[n]
print(ans)

Solution (Python):
n, m = map(int, input().split())
a = []
for i in range(m):
  a.append(int(input()))
ans = 0
flag = 0
a = set(a)


dp = [0] * (n+1)
dp[0] = 1
if 1 in a:
  dp[1] = 0
else:
  dp[1] = 1
  
for i in range(2, n+1):
  if dp[i-2] == 0 and dp[i-1] == 0:
    ans = 0
    flag = 1
    break
  elif i in a:
    continue
  else:
    dp[i] = dp[i-1] + dp[i-2]
if flag == 0:
  ans = dp[n]
print(ans%(10**9+7))

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

n,m = map(int, input().split())
a = {}
for i in range(m):
    a[int(input())] = 0

dp = [0]*(n+1)
dp[0] = 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] + dp[i-2]

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

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

def fib(n):
    a, b = 1, 0
    for _ in range(n):
        a, b = a + b, a
    return b

n,m = map(int, input().split())
a = []
for i in range(m):
    a.append(int(input()))
if len(a) >= 2:
    for i in range(m-1):
        if a[i]+1 == a[i+1]:
            print(0)
            exit()

tmp = 0
ans = 1
for i in range(len(a)):
    ans *= fib(a[i]-tmp)
    tmp = a[i]+1
if tmp < n:
    ans *= fib(n-tmp+1)
print(ans%(10**9+7))

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

for i in range(n+1):
  if i==0:
    idou.append(1)
  elif i==1 and not(i in obs):
    idou.append(1)
  elif i in obs:
    idou.append(0)
  else:
    tasu = idou[-1] + idou[-2]
    tasu = tasu%1000000007
    idou.append(tasu)
    
print(idou[-1])

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

bads = {}
for i in range(m):
    bads[int(input())] = None

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

print(dp[-1])

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

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

Solution (Python):

INF = float("inf")
MOD = int(1e9 + 7)














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

    dp = [1] + [0] * N
    for n in range(1, N + 1):
        if n in A: continue
        if 1 < n:
            dp[n] = dp[n - 1] + dp[n - 2]
        else:
            dp[n] = dp[n - 1]
        dp[n] %= MOD
    print(dp[-1])

main()

Solution (Python):
n,m=[int(i) for i in input().split()]
badone=[int(input()) for i in range(m)]
badstares=[1 for i in range(n)]
for i in badone:
    badstares[i-1]=0


stares=[-1 for i in range(n)]
if n==1:
    print(1)
else:
    for i in range(n):

        i=n-1-i
        if i==n-1:
            stares[i]=1
        elif i==n-2:
            if badstares[i]==0:
                stares[i]=-1
            else:
                stares[i]=1
        else:
            if badstares[i]==0:
                stares[i]=-1
            else:
                if stares[i+1]==-1 and stares[i+2]==-1:
                        stares[i]=-1
                elif stares[i+1]==-1 and stares[i+2]!=-1:
                        stares[i]=stares[i+2]
                elif stares[i+2]==-1:
                    stares[i]=stares[i+1]
                else:
                    stares[i]=stares[i+1]+stares[i+2]

    if stares[0]==-1 and stares[1]==-1:
        print(0)
    elif stares[0]==-1:
        print(stares[1]%1000000007)
    elif stares[1]==-1:
        print(stares[0]%1000000007)
    else:
        print((stares[0]+stares[1])%1000000007)

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

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

for v in a:
    stairs[v] = 0

for i in list(range(0, N - 1))[::-1]:
    if stairs[i] == 0:
        continue
    stairs[i] = (stairs[i+1] + stairs[i+2]) % 1000000007

print(stairs[0])

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

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

for _ in range(m):
    a=int(input())
    NG[a]=1

for i in range(n):
    if i==0:            
        dp[i+1]=dp[i] if NG[i+1]==0 else 0
        continue

    if NG[i+1]==1:
        dp[i+1]=0
    else:
        dp[i+1]=dp[i]+dp[i-1]
        dp[i+1]%=mod

print(dp[n])

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

A = set(A)
dp = [0] * (N+1)
dp[0] = 1
if 1 in A:
  dp[1] = 0
else:
  dp[1] = 1
mod = 1000000007

for i in range(2,N+1):
  if (dp[i-1] == 0) & (dp[i-2]==0):
    print(0)
    exit()
  elif i in A:
    continue
  else:
    dp[i] = dp[i-1]+dp[i-2]

print(dp[N]%mod)

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

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

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

dp = [1] * (N + 1)
for i in range(len(halls)):
    dp[halls[i]] = 0

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

print(dp[N] % 1000000007)

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

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

dp = [1] * (N + 1)
for i in range(len(halls)):
    dp[halls[i]] = 0

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

print(dp[N] % 1000000007)

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

halls = {}
for i in range(M):
    index = int(input())
    halls[index] = True

dp = [1] * (N + 1)

for i in range(1, N + 1):
    if i in halls:
        dp[i] = 0
        continue
    if i == 1:
        continue
    dp[i] = dp[max(0, i - 1)] + dp[max(0, i - 2)]
    
print(dp[N] % 1000000007)

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

dp = [0] * (N + 1)
dp[0] = 1
b = 1
f = False
for _ in range(M):
    a = int(input())
    if a - b == 1:
        f = True
        break
    dp[a] = -1
    b = a

if f:
    ans = 0
elif len(dp) == 2:
    if dp[1] == -1:
        ans = 0
    else:
        ans = 1
else:
    MOD = 10**9 + 7
    
    if dp[1] != -1:
        dp[1] = 1
    for i in range(2, N + 1):
        if dp[i] != -1:
            s = 0 if dp[i-2] == -1 else (dp[i-2] % MOD)
            p = 0 if dp[i-1] == -1 else (dp[i-1] % MOD)
            dp[i] = s + p
            ans = dp[-1] % MOD
print(ans)

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


b=[0 for x in range(n+1)]
b[0]=1
for i in range(1,n+1):
  if i in a:
    continue
  x=b[i-1]
  if i>1:x+=b[i-2]
  b[i]=x%(10**9+7)
print(b[n])

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


b=[0 for x in range(n+1)]
b[0]=1
for i in range(1,n+1):
  if i in a:
    continue
  x=b[i-1]
  if i>1:x+=b[i-2]
  b[i]=x
print(b[n]%(10**9+7))

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


b=[0 for x in range(n+1)]
b[0]=1
for i in range(1,n+1):
  if i in a:
    continue
  x=b[i-1]
  if i>1:x+=b[i-2]
  b[i]=x
print(b[n]%(10**9+7))

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

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

Solution (Python):
N,M=map(int,input().split())
A={int(input()) for _ in [0]*M}
D=[1,0 if 1 in A else 1]
for i in range(2,N+1):
  D += [0] if i in A else [(D[-1]+D[-2])%1000000007]
print(D[N])

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

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

for line in sys.stdin:
    ans[int(line)] = 0  

ans[0] = 1  

if ans[1]:  
    ans[1] = 1

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

print(ans[N])

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

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

for line in sys.stdin:
    ans[int(line)] = 0  

ans[0] = 1  

if ans[1]:
    ans[1] = 1

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

print(ans[N] % 1000000007)

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

a = [int(line) for line in sys.stdin]

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

for broken in a:
    ans[broken] = 0  

ans[0] = 1  

if ans[1]:
    ans[1] = 1

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

print(ans[N] % 1000000007)

Solution (Python):

N,M = map(int,input().split())
step  = [-1] * (N + 1)

for _ in range(M):
    a = int(input())
    step[a-1] = 0

if step[0] == -1:
    step[0] = 1

if step[1] == -1:
    step[1] = step[0]+1

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

print(step[N-1] % 1000000007)

Solution (Python):

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