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.



Sample input:
6 1
3


Sample output:
4

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[15]:


from collections import deque


# In[38]:


N,M = map(int, input().split())
alist = [False]*N
for _ in range(M):
    alist[int(input())-1] = True


# In[41]:


dp = deque([0]*2)
dp[0] = 1
ans = 0
mod = 10**9+7
if N == 1:
    ans = 1
else:
    if alist[0]:
        dp[1] = 0
    else:
        dp[1] = 1
    for i in range(2,N+1):
        if alist[i-1]:
            dp.append(0)
        else:
            dp.append((dp[0]+dp[1])%mod)
        dp.popleft()
    ans = dp[-1]
print(ans)


# In[ ]:

Submission status: Accepted

Solution code:
import sys
N, M = map(int, input().split())
A = set(int(sys.stdin.readline()) for _ in range(M))
MOD = 10 ** 9 + 7

ans = 0
if N == 1:
    ans = 1
elif N == 2:
    if M == 0:
        ans = 2
    else:
        ans = 1
else:
    if 1 in A:
        p2 = 0
    else:
        p2 = 1
    if 2 in A:
        p1 = 0
    else:
        p1 = p2 + 1
    for i in range(3, N + 1):
        if i in A:
            p2 = p1
            p1 = 0
        else:
            c = (p1 + p2) % MOD
            p2 = p1
            p1 = c
    ans = p1
print(ans)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
N, M = list(map(int, input().split()))
B = [True] * (N + 1)
D = [1] + [0] * N
for _ in range(M):
    a = int(input())
    B[a] = False
for i in range(N):
    for j in range(i + 1, min(N, i + 2) + 1):
        if B[j]:
            D[j] = (D[j] + D[i]) % MOD
print(D[N])

Submission status: Accepted

Solution code:
MOD = 10**9 + 7

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

dp = [1] * (N+1)

if 1 in A:
    dp[1] = 0

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
am = [int(input()) for _ in range(m)]
hole = [False]*(n+1)

for i in am:
    hole[i] = True

dp = [0]*(n+1)
dp[0] = 1
for i in range(n):
    for j in range(i+1, min(n, i+2)+1):
        if not hole[j]:
            dp[j] += dp[i]
            dp[j] %=1000000007
print(dp[n])

Submission status: Accepted

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

for broken in a:
    for j in range(s + 1, broken):
        if j > s + 1:
            dp[j] += dp[j - 1] % MOD
        if j > 1:
            dp[j] += dp[j - 2] % MOD
        dp[j] %= MOD
    s = broken

print(dp[-1])

Submission status: Accepted

Solution code:
def main():
    n, m = map(int, input().split())
    As = set([int(input()) for _ in range(m)])
    mod = 1000000007

    Steps = [0] * (n+1)
    Steps[0] = 1
    if 1 not in As:
        Steps[1] = 1

    for i in range(2, n+1):
        if i in As:
            continue
        Steps[i] = Steps[i-1] + Steps[i-2]
    ans = Steps[-1] % mod
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

for i in range(2, n+1):
    if dp[i] != 0:
        dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007
    else:
        pass

print(dp[-1])

Submission status: Accepted

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

stairs = []
is_continuous = False
for i in range(m):
    stairs.append(int(input()))
    if i > 0 and stairs[i] - 1 == stairs[i - 1]:
        is_continuous = True
        break

if is_continuous:
    print(0)
else:
    countup_num = [0] * (n + 1)
    countup_num[0] = 1
    countup_num[1] = 1
    for i in range(2, n + 1):
        countup_num[i] = (countup_num[i - 1] + countup_num[i - 2]) % 1000000007
    res = 1
    diff = 0
    now = 0
    for i in range(m):
        diff = stairs[i] - now - 1
        now = stairs[i] + 1
        res *= (countup_num[diff]) % 1000000007
        # print(res, now)
    if m == 0:
        res = countup_num[n]
    else:
        diff = n - stairs[-1] - 1
        res *= (countup_num[diff]) % 1000000007

    res %= 1000000007
    # print(countup_num)
    print(res)

Submission status: Accepted

Solution code:
MOD=10**9+7
N,M=map(int,input().split())
A=[int(input()) for _ in range(M)]
L=[-1 for _ in range(N)]
p=0
if A == []:
  A=[0]
if 1 == A[p]:
  L[0] = 0
  if p < M-1:
    p +=1
else:
  L[0] = 1
if N>1:
  if 2 == A[p]:
    L[1] = 0
    if p < M-1:
      p+=1
  else:
    L[1]=L[0]+1
for i in range(2,N):
  if i+1 == A[p]:
    L[i] = 0
    if p < M-1:
      p+=1
  else:
    L[i]=L[i-1]+L[i-2]
print(L[-1]%MOD)

Submission status: Accepted

Solution code:

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

MOD = 10 ** 9 + 7
dp = [-1] * (N + 1)
dp[0] = 1
for i in range(M):
    dp[X[i]] = 0

for i in range(N):
    if dp[i + 1] < 0:
        if i == 0:
            dp[i + 1] = dp[i]
        else:
            dp[i + 1] = (dp[i] + dp[i - 1]) % MOD

print(dp[-1])

Submission status: Accepted

Solution code:
MOD=10**9+7
n,m = list(map(int, input().split()))
a = set([int(input()) for _ in range(m)])

dp = [0] * (n+1)

dp[0] = 1
dp[1] = int(1 not in a)
for step in range(2, n+1):
    if dp[step-1]==0 and dp[step-2]==0:
        break
    if step not in a:
        dp[step] = (dp[step-1] + dp[step-2])%MOD
    else:
        dp[step] = 0
        
print(dp[-1])

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
A_list = set([int(input()) for _ in range(M)])
Dp_list = [0] * (N+1)
Dp_list[0] = 1

if 1 in A_list:
    Dp_list[1] = 0
else:
    Dp_list[1] = 1

if N != 1:
    for i in range(2, N + 1):
        if i in A_list:
            continue

        Dp_list[i] = Dp_list[i-2] + Dp_list[i-1]
        Dp_list[i] %= 1000000007
    print(Dp_list[N])
else:
    print(1)

Submission status: Accepted

Solution code:
import math
import sys
import collections
import bisect
readline = sys.stdin.readline


def main():
    n, m = map(int, readline().rstrip().split())
    A = [-1] + [int(readline().rstrip()) for _ in range(m)] + [n + 1]
    num = 10 ** 5 + 10
    # num = 10
    aList = [0] * (num)
    aList[0] = 1
    aList[1] = 1
    aList[2] = 2
    for i in range(3, num):
        aList[i] = aList[i - 1] + aList[i - 2]
    sumA = 1
    for j in range(m + 1):
        if A[j + 1] - 1 == A[j]:
            print(0)
            return
        sumA = (sumA * aList[(A[j + 1] - 1) - (A[j] + 1)]) % (10 ** 9 + 7)
    print(sumA)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
mod = 10**9+7
dp = [0]*(n+1)
dp[0] = 1
dp[1] = 1
seta = set([int(input()) for _ in range(m)])

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

print(dp[-1])

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
mod = 10**9+7
facs = [1] * (n-m+1)
invs = [1] * (n-m+1)
nfac = 1
for i in range(1, n-m+1):
    nfac = nfac * i % mod
    facs[i] = nfac
    invs[i] = pow(facs[i], mod-2, mod)

ans = 1
start = 0
def steps(start, end):
    t = end - start
    pat = 0
    for j in range(t//2+1):
        pat += (facs[t-j] * invs[j] * invs[t-j-j]) % mod
    return pat%mod

for i in range(m):
    a = int(input())
    end = a-1
    if start == end+1:
        print(0)
        break
    # startからendまで行く方法
    ans *= steps(start, end)
    ans %= mod
    start = a+1
else:
    ans *= steps(start, n)
    ans %= mod
    print(ans)

Submission status: Accepted

Solution code:
mod=10**9+7
n,m=map(int,input().split())
def fib_dynamic(n):
  cal_result={}
  
  cal_result[0]=1
  cal_result[1]=1
  
  if n==0 or n==1:
    return 1
  
  for i in range(2,n+1):
    cal_result[i]=cal_result[i-1]+cal_result[i-2]
    
  return cal_result[n]


if m==0:
  print(fib_dynamic(n)%mod)
  
else:
  ans=1
  ch=0
  for x in range(m):
    a=int(input())
    if a-ch==1 and ch!=0:
      ans=ans*0
      break
     
    
    if x==0:
      ans=ans*fib_dynamic(a-1)
      ch=a
    else:
      ans=ans*fib_dynamic((a-1)-ch-1)
      ch=a
      
    if x==m-1:
      ans=ans*fib_dynamic(n-a-1)
      
  print(ans%mod)

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
MOD = 10 ** 9 + 7
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N, M = LI()
    a = set([I() for _ in range(M)])

    dp = [0] * (N + 1)
    dp[0] = 1
    if 1 not in a:
        dp[1] = 1
    for i in range(N - 1):
        if i + 2 not in a:
            dp[i+2] = dp[i] + dp[i+1]
            dp[i+2] %= MOD

    print(dp[-1])

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc129/tasks/abc129_c

n, m = map(int, input().split())
mod = 10 ** 9 + 7
broken = set()
for _ in range(m):
    broken.add(int(input()))

dp = [0 for _ in range(n + 1)]
dp[0] = 1
for i in range(n):
    for j in range(2):
        if i + 1 in broken:
            dp[i + 1] = 0
        else:
            if i - j >= 0:
                dp[i + 1] += dp[i - j] % mod

ans = dp[n] % mod
print(ans)

Submission status: Accepted

Solution code:
n, m = (int(xi) for xi in input().split())

a = []
diff = []
a0 = 0
if m>0:
    a1 = int(input())
    a.append(a1)
    diff.append(a1+1)

    if m>1:
        for xi in range(m-1):
            a0 = a1
            a1 = int(input())
            a.append(a1)
            diff.append(a1-a0)

    if a1==n-1:
        diff.append(n-a1+1)
    else:
        diff.append(n-a1+1)


else:
    if n==1: diff.append(n+1)
    diff.append(n+2)

# print(diff)
# print(a)

p = [0]
p.append(1)
p.append(1)
for xi in range(3,max(diff)+2):
    add = (p[xi-1]+p[xi-2])%1_000_000_007
    p.append(add)

# print(p)

# print(len(diff))
out = 1
for xi in range(len(diff)):
    out *= p[diff[xi]-1]

print(out% 1_000_000_007 )

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import collections as cl
import sys

MOD = 10 ** 9 + 7


def II():
    return int(sys.stdin.readline())


def MI():
    return map(int, sys.stdin.readline().split())


def LI():
    return list(map(int, sys.stdin.readline().split()))


def main():
    N, M = MI()
    isbroken = [False] * (N + 1)
    for i in range(M):
        a = II()
        isbroken[a] = True

    steps = [0] * (N + 1)

    steps[0] = 1
    if not isbroken[1]:
        steps[1] = 1
    for i in range(2, N + 1):
        if isbroken[i]:
            continue
        steps[i] = steps[i - 1] + steps[i - 2]
        steps[i] %= MOD
    print(steps[-1])


main()

Submission status: Accepted

Solution code:
def resolve():
    '''
    code here
    '''
    from functools import lru_cache
    import sys
    sys.setrecursionlimit(10**6)

    N, M = [int(item) for item in input().split()]
    As = [int(input()) for _ in range(M)]
    memo = [False for _ in range(N+1)]

    for item in As:
        memo[item] = True

    res_list = []

    prev = 0
    for i in range(1,N+1):
        if memo[i] == True:
            res_list.append(i-1 - prev)
            prev = i+1
    else:
        if memo[N] == False and memo[N] == False:
            res_list.append(N - prev)

    @lru_cache
    def cal(num):
        if 0 <= num <= 1:
            return 1
        elif num == -1:
            return 0
        else:
            return cal(num-1) + cal(num-2)
    # print(res_list)
    res = 1
    for item in res_list:
        res *= cal(item)% (10**9 + 7)

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



if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
a=set([int(input()) for i in range(M)])
mod=10**9+7

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

total=[0 for i in range(N+1)]
total[0] = 1
for i in range(1,N+1):
  if i>=2 and i-2 not in a:
  	total[i] += total[i-2]
  if i-1 not in a:
    total[i] += total[i-1]

print(total[-1] % mod)

Submission status: Accepted

Solution code:
#create date: 2020-07-25 09:13

import sys
stdin = sys.stdin
mod = 10**9+7

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def main():
    n, m = na()
    a = [0] * (10**5+1)
    for i in range(m):
        st = ni()
        a[st] = 1

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#https://atcoder.jp/contests/abc129/tasks/abc129_c
N,M = map(int,input().split())
Danger_List = []
Route_List = [[] for i in range(N+1)]
for i in range(M):
    Route_List[int(input())] = 0
        
Route_List[0] = 1

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

    
    
        
print(Route_List[-1] % 1000000007)

Submission status: Accepted

Solution code:
mod = 1000000007

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

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

print (s[n])

Submission status: Accepted

Solution code:
def main():
    n,m = map(int,input().split())
    dp = [0 for i in range(n+1)]
    mod = 10**9+7
    for i in range(m):
        a = int(input())
        dp[a] = -1
    dp[0] = 1
    if dp[1]!=-1:
        dp[1] = 1
    for i in range(2,n+1):
        if dp[i]==-1:
            continue
        if dp[i-1]!=-1 and dp[i-2]!=-1:
            dp[i] = dp[i-1] + dp[i-2]
            dp[i] = dp[i]%mod
        elif dp[i-1]!=-1 and dp[i-2]==-1:
            dp[i] = dp[i-1]
        elif dp[i-1]==-1 and dp[i-2]!=-1:
            dp[i] = dp[i-2]
        else:
            dp[i] = 0
    print(dp[-1])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**5+10)
N, M = map(int, input().split())
A = set([int(input()) for _ in range(M)])
MOD = 1000000007
memo = {}
def Fib(n, MOD):
    if n in A:
        return 0
    elif n == 0:
        return 1
    elif n == 1:
        return 1
    elif n in memo:
        return memo[n]
    else:
        memo[n] = ( Fib(n-1, MOD) + Fib(n-2, MOD) ) % MOD
        return memo[n]
print(Fib(N, MOD))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=[int(input()) for _ in range(m)]
if n==1:
    print(1)
    exit()
for i in range(m-1):
    if a[i+1]-a[i]==1:
        print(0)
        exit()
ans=1
a.append(n+1)
for i in range(m+1):
    if i==0:
        l=[1,1]
        for j in range(1,a[i]-1):
            l.append(l[-1]+l[-2])
        ans*=l[-1]
        ans%=(10**9 +7)
        #print(l)
    else:
        l=[1,1]
        for j in range(a[i-1]+2,a[i]-1):
            l.append(l[-1]+l[-2])
        ans*=l[-1]
        ans%=(10**9 +7)
        #print(l)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
def C():
    N, M = map(int, input().split())
    A = set([int(input()) for _ in range(M)])
    dp = deque([1, 1 if 1 not in A else 0])
    MOD = 1000000007
    for i in range(2,N+1):
        #print(i, dp)
        if i in A:
            dp.append(0)
        else:
            dp.append((dp[0]+dp[1]) % MOD)
        dp.popleft()
    print(dp[-1])

C()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = set([int(input()) for _ in range(M)])
MOD = 1000000007
memo = [0]*(N+1)
memo[0] = 1
if 1 not in A:
    memo[1] = 1
for i in range(2, N+1):
    if i not in A:
        memo[i] = (memo[i-2] + memo[i-1])%MOD
print(memo[N])

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
if N == 1:
    print(1)
    quit()
S = [-1] * (N + 1)
S[0] = 1
for i in range(M):
    S[int(input())] = 0
if S[1] != 0:
    S[1] = 1
for i in range(2, N + 1):
    if S[i] == 0:
        continue
    else:
        S[i] = (S[i - 1] + S[i - 2]) % 1000000007
        if S[i] == 0:
            print(0)
            quit()
print(S[N])

Submission status: Accepted

Solution code:
def fib(n):
    if n <= 1:
        return n
    result = [1, 0, 0, 1]
    matrix = [1, 1, 1, 0]
    while n > 0:
        if n % 2:
            result = mul(matrix, result)
        matrix = mul(matrix, matrix)
        n //= 2
    return result[2]

def mul(a, b):
    return [a[0]*b[0] + a[1]*b[2],
            a[0]*b[1] + a[1]*b[3],
            a[2]*b[0] + a[3]*b[2],
            a[2]*b[1] + a[3]*b[3]]
    
N, M = map(int, input().split())
if N == 1:
    print(1)
    quit()
S = [-1]
for i in range(M):
    S.append(int(input()))
S.append(N + 1)
S = [S[i + 1] - S[i] for i in range(M + 1)]
if any([x == 1 for x in S]):
    print(0)
    exit()
num = 1
for x in S:
    num *=  fib(x - 1)
    num = num % 1000000007
print(num)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from itertools import product

def mat2_mul(X, Y):
	z = [[0, 0], [0, 0]]
	for (i, j, k) in product(range(2), range(2), range(2)):
		z[i][j] += X[i][k] * Y[k][j]
	return z

def mat2_pow(X, n):
	if n == 0:
		return [[1, 0], [0, 1]]
	elif n % 2:
		return mat2_mul(X, mat2_pow(X, n - 1))
	else:
		half_pow = mat2_pow(X, n / 2)
		return mat2_mul(half_pow, half_pow)

def fibona(n):
	if n == 0:
		return 0
	else:
		f = [[0, 1], [1, 1]]
	return mat2_pow(f, n - 1)[1][1]

def main():
    n, m = map(int,input().split())
    mlis = []
    for _ in range(m):
        a = int(input())
        mlis.append(a)
    ans = 1
    mae = 0

    infi = 10 ** 9 + 7
    for num in mlis:
        ans *= fibona(num-mae)
        ans %= infi
        mae = num + 1

    nobori = n - mae + 1
    ans *= fibona(nobori) 
    ans %= infi
    print(int(ans))
    



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque, defaultdict
from math import sqrt, factorial, gcd, ceil
# def input(): return sys.stdin.readline()[:-1] # warning not \n
# def input(): return sys.stdin.buffer.readline().strip() # warning bytes
# def input(): return sys.stdin.buffer.readline().decode('utf-8')
import string
# string.ascii_lowercase
from bisect import bisect_left
MOD = int(1e9)+7
INF = float('inf')


def solve():
    n, m = [int(x) for x in input().split()]
    d = [0] * (n+1)
    d[0] = 1
    for _ in range(m):
        x = int(input())
        d[x] = -1

    for i in range(1, n+1):
        if d[i] != -1:
            if d[i-1] != -1:
                d[i] = d[i-1]
            if i > 1 and d[i-2] != -1:
                d[i] += d[i-2]
            d[i] %= MOD

    print(d[n]%MOD)

t = 1
# t = int(input())
for case in range(1,t+1):
    ans = solve()


"""

azyxwvutsrqponmlkjihgfedcb

"""

Submission status: Accepted

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

Submission status: Accepted

Solution code:
 # -*- coding: utf-8 -*-
n, m = map(int, input().split())
a = set([int(input()) for _ in range(m)])

INF = 1000000007

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

if 1 not in a:
    dp[1] = 1
else:
    dp[1] = 0

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

print(dp[n])

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
def Fib(n):
  seq = []
  a,b = 0,1
  for i in range(1,n+10):
    if i == 1:
      seq.append(0)
    elif i == 2:
      seq.append(1)
    else:
      a, b = b, a + b
      seq.append(b)
  return seq
table = Fib(n)
temp = -1
route = 1
mod = 10**9+7
for _ in range(m):
  a = int(input())
  dif = a-temp-1
  temp = a
  route = route*table[dif]%mod
print(route*table[n-temp]%mod)

Submission status: Accepted

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

Submission status: Accepted

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

danger=[0 for n in range(N+1)]
for m in range(M):
    danger[a[m]]=1

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

print(dp[N]%1000000007)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,m=map(int, input().split())
a=set(int(input())  for i in  range(m))
x=(10**9)+7

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

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

Submission status: Accepted

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

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

dp = [0] * (N+1)
dp[0] = 1
if aa[1]:
    dp[1] = 1

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

Submission status: Accepted

Solution code:
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)

N, M = rl()
A = [-1]
prev_a = -float('inf')
for i in range(M):
	a = ri()
	if a-prev_a == 1:
		print(0)
		exit()
	A.append(a)
	prev_a = a
A.append(N+1)

dp = [0]*(N+5)
dp[0] = 0
dp[1] = 1
for i in range(N+5-2):
	dp[i+2] = dp[i+1] + dp[i]
ans = 1
for i in range(len(A)-1):
	ans *= dp[A[i+1]-A[i]-1]
	ans = ans % mod
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
a = set([int(input())for _ in range(m)])
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 i in a:
        continue
    dp[i] = (dp[i-1]+dp[i-2])%1000000007
print(dp[n])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
dp = [0]*(n+1)
dp[0] = 1
m_list = [int(input()) for _ in range(m)]
for i in range(1,n+1):
  if i==1:
    if m_list and i==m_list[0]:
      m_list.pop(0)
      dp[i]=0
    else:
      dp[i]=1
  elif m_list and i == m_list[0]:
    m_list.pop(0)
    dp[i] = 0
  else:
    dp[i] = (dp[i-1]+dp[i-2])% 1000000007
print(dp[-1])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from math import ceil,floor,comb,factorial,gcd,pow,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n, m = MAP()
k = [0]*(n+1)
for i in range(m):
    a = INT()
    k[a] = -1

for i in range(n+1):
    if k[i] == -1:
        continue
    elif i <= 1:
        k[i] = 1
    else:
        k[i] = ( (k[i-1] if k[i-1] != -1 else 0) + (k[i-2] if k[i-2] != -1 else 0) ) % (10**9+7)

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    n,m=map(int,input().split())
    a=set(int(input()) for _ in range(m))
    pattern = [0] * (n+1)
    pattern[0] = 1
    for i in range(n-1):
        if i in a:
            continue
        if i+1 not in a:
            pattern[i+1] += pattern[i]
            pattern[i+1] %= 1000000007
        if i+2 not in a:
            pattern[i+2] += pattern[i]
            pattern[i+2] %= 1000000007
    pattern[n] += pattern[n-1]
    pattern[n] %= 1000000007
    print(pattern[n])
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
MOD = 10**9+7
 
n, m = map(int, readline().split())
a = set(map(int, read().split()))
 
dp = [0] * (n + 1)
dp[0] = 1
if 1 not in a:
    dp[1] = 1
cnt = 0
for i in range(2, n + 1):
    if i not in a:
        dp[i] = (dp[i - 1] + dp[i - 2]) % MOD
        cnt = 0
    else:
        cnt += 1
        if cnt == 2:
            print('0')
            exit()
print(dp[n])

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
MOD = 10**9+7

n, m = map(int, readline().split())
a = list(map(int, read().split()))

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

for i in a:
    ng[i] = 1

dp[0] = 1
if ng[1] != 1:
    dp[1] = 1

for i in range(2, n + 1):
    if ng[i - 1] == 1 and ng[i - 2] == 1:
        print(0)
        exit()
    elif ng[i - 1] == 1:
        dp[i] = dp[i - 2]
    elif ng[i - 2] == 1:
        dp[i] = dp[i - 1]
    else:
        dp[i] = dp[i - 1] + dp[i - 2]
    if dp[i] > MOD:
        dp[i] %= MOD

print(dp[-1])

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
MOD = 10**9+7

n, m = map(int, readline().split())
a = list(map(int, read().split()))

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

for i in a:
    ok[i] = 0

dp[0] = 1
dp[1] = 1 * ok[1]

for i in range(2, n + 1):
    if ok[i - 1] == 0 and ok[i - 2] == 0:
        print(0)
        exit()
    else:
        dp[i] = dp[i - 1]*ok[i - 1] + dp[i - 2]*ok[i - 2]
    if dp[i] > MOD:
        dp[i] %= MOD

print(dp[-1])

Submission status: Accepted

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

Submission status: Accepted

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

MOD = 10**9 + 7

safe = [True] * (N+1)
for i in range(len(A)):
    safe[A[i]] = False

dp = [0] * (N+1)
dp[0] = 1
if safe[1]:
    dp[1] = 1

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

print(dp[N])

Submission status: Accepted

Solution code:
import sys
import math


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


def main():
    mod =10**9+7
    N,M = map(int,input().split())
    A =[]
    for _ in range(M):
        a = int(input())
        A.append(a)

    dp= [0]*(N+1)
    ds= [0]*(N+1)
    for j in A:
        ds[j] =1

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





if __name__ == "__main__":
    main()

Submission status: Accepted

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

a.append(10 ** 15)
c = 0
for i in range(1, N + 1):
  if a[c] == i:
    c += 1
    continue
  D[i] = D[i - 1]
  if i - 2 >= 0:
    D[i] = (D[i] + D[i - 2]) % MOD

print(D[-1])