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:
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
a.sort(reverse=True)
dp = [0] * (N + 1)
dp[0] = 1
if len(a) > 0:
    A = a.pop()
else:
    A = -1

if A == 1:
    dp[1] = 0
    if len(a) > 0:
        A = a.pop()
    if A == 2:
        dp[2] = 0
    else:
        dp[2] = 1
else:
    dp[1] = 1
for i in range(2, N + 1):
    if i == A:
        if len(a) > 0:
            A = a.pop()
        continue
    if dp[i - 1] != 0 and dp[i - 2] != 0:
        dp[i] = (dp[i - 1] + dp[i - 2])  % 1000000007
    elif dp[i - 1] != 0:
        dp[i] = dp[i - 1]  % 1000000007
    elif dp[i - 2] != 0:
        dp[i] = dp[i - 2]  % 1000000007
    else:
        dp[i] = 0
print(dp[-1])

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7

N, M = MAP()
a = [INT() for _ in range(M)]

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

def fib(n):
	if n < 2:
		return fib_list[n]
	elif fib_list[n] != 0:
		return fib_list[n]
	else:
		fib_list[n] = fib(n-1) + fib(n-2)
		return fib_list[n]

tmp = -1
ans = 1

for x in a:
	#print(tmp, x)
	if x == tmp+1:
		print(0)
		exit()
	else:
		ans = ans*fib(x-tmp-2)%mod
		tmp = x

ans = ans*fib(N-tmp-1)%mod
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

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

if m != 0:
    a = [int(input()) for _ in range(m)]
else:
    a = [-1]

mod = 1000000007

if n == 1:
    print(1)
    exit()
elif n == 2:
    if a[0] == 1:
        print(1)
    else:
        print(2)
    exit()


if a[0] == 1:
    a_2, a_1 = 1, 0
    index = 1
else:
    a_2, a_1 = 1, 1
    index = 0

for i in range(2, n+1):
    if index < len(a):
        if i == a[index]:
            a_now = 0
            index += 1
            a_1, a_2 = a_now, a_1
            continue

    a_now = (a_1+a_2) % mod
    # print(a_now)
    a_1, a_2 = a_now, a_1
    # print(a_now)
print(a_now % mod)

# 0, 1, 2, 3, 4, 5, 6

# 1, 1, 2, 0, 2, 2, 4

Submission status: Accepted

Solution code:
mod = 1e9+7
n, m = [int(i) for i in input().strip().split()]

oks = [True]*(n+1)
for i in range(m):
  a = int(input())
  oks[a] = False


dp = [0]*(n+1)
dp[0] = 1
for i in range(1, n+1):
  if oks[i-1]:
    dp[i] += dp[i-1]
    dp[i] %= mod
  if i-2>-1 and oks[i-2]:
    dp[i] += dp[i-2]
    dp[i] %= mod
print(int(dp[n]))

Submission status: Accepted

Solution code:
#!/usr/bin/env pypy
import sys

readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
MOD = 10 ** 9 + 7


def main():
    n, m = map(int, readline().split())
    # a = readlines()
    As = set(map(int, readlines()))
    # diff_a = [a[i+1] - a[i] for i in range(m - 1)]
    # if 1 in diff_a:
    #     print(0)
    #     return
 
    p1, p2 = 1, 1
    if 1 in As:
        p1 = 0

    for i in range(2, n + 1):
        if i in As:
            p1, p2 = 0, p1
        else:
            p1, p2 = (p1 + p2) % MOD, p1

    print(p1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env pypy
import sys

readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
MOD = 10 ** 9 + 7


def main():
    n, m = map(int, readline().split())
    # a = readlines()
    As = list(map(int, readlines()))
    # diff_a = [a[i+1] - a[i] for i in range(m - 1)]
    # if 1 in diff_a:
    #     print(0)
    #     return
    broken = [False] * (n + 1)
    for a in As:
        broken[a] = True
    p1, p2 = 1, 1
    if broken[1]:
        p1 = 0

    for i in range(2, n + 1):
        if broken[i]:
            p1, p2 = 0, p1
        else:
            p1, p2 = (p1 + p2) % MOD, p1

    print(p1)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, M = map(int, readline().split())
A = list(map(int, readlines()))
assert len(A) == M

MOD = 10 ** 9 + 7


def solve():
    broken = [False] * (N + 1)
    for a in A:
        broken[a] = True
    p1, p2 = 1, 0
    for i in range(1, N + 1):
        if broken[i]:
            p1, p2 = 0, p1
        elif i == 1:
            p1, p2 = p1, p1
        else:
            p1, p2 = (p1 + p2) % MOD, p1
    return p1


if __name__ == "__main__":
    print(solve())

Submission status: Accepted

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

Submission status: Accepted

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

for i in range(n):
            fibo.append((fibo[-1]+fibo[-2])%1000000007)

if m:
    r = [a[0]-1]

    for i in range(m-1):
        r.append((a[i+1]-a[i])-2)
        if a[i+1]-a[i] == 1:
            print(0)
            exit()

    else:
        r.append(n-a[-1]-1)

        for i in range(len(r)):
            ans = (fibo[r[i]] * ans)%1000000007

        print(ans)
else:
    print(fibo[n])

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    N, M = map(int, input().split())
    a = [0] * (1 + 10 ** 5)
    for _ in range(M):
        a[int(input())] = 1
    dp = [0] * (N + 1)
    dp[0] = 1
    if a[1]:
        pass
    else:
        dp[1] = 1

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

    print(dp[N])

main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    N, M = map(int, input().split())
    a = [0] * (1 + 10 ** 5)
    for _ in range(M):
        a[int(input())] = 1
    dp = [0] * (N + 1)
    dp[0] = 1
    if not a[1]:
        dp[1] = 1

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

    print(dp[N])

main()

Submission status: Accepted

Solution code:
def main():
    N, M = map(int, input().split())
    a = [0] * (1 + 10 ** 5)
    for _ in range(M):
        a[int(input())] = 1
    dp = [0] * (N + 1)
    dp[0] = 1
    if not a[1]:
        dp[1] = 1

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

    print(dp[N])

main()

Submission status: Accepted

Solution code:
def main():
    N, M = map(int, input().split())
    a = set(int(input()) for _ in range(M))
    dp = [0] * (N + 1)
    dp[0] = 1
    if 1 not in a:
        dp[1] = 1

    for i in range(2, N + 1):
        for k in [-2, -1]:
            if i + k not in a:
                dp[i] += dp[i+k]
        dp[i] %= 1000000007

    print(dp[N])

main()

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 not in a:
    dp[1] = 1

for i in range(2, N + 1):
    for k in [-2, -1]:
        if i + k not in a:
            dp[i] += dp[i+k]
    dp[i] %= 1000000007

print(dp[N])

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 not in a:
    dp[1] = 1

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

print(dp[N])

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 not in a:
    dp[1] = 1

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

print(dp[N])

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 not in a:
    dp[1] = 1

for i in range(2, N + 1):
    for k in [-2, -1]:
        if i + k not in a:
            dp[i] += dp[i+k]
            dp[i] %= 1000000007

print(dp[N])

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 not in a:
    dp[1] = 1

for i in range(2, N + 1):
    for k in [-2, -1]:
        if i + k not in a:
            dp[i] += dp[i+k]

print(dp[N] % 1000000007)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
ans = ["0"]*(N+2)
ans[0] = 0
ans[1] = 1
mod = 10**9 + 7

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

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

print(ans[-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
mod=10**9+7

N,M=map(int,input().split())
a=[int(input()) for _ in range(M)]
dp=[1,1]
m=0
if M>0 and a[0]==1:
    dp[1]=0
    m+=1
for i in range(2,N+1):
    if m<M and i==a[m]:
        dp.append(0)
        m+=1
    else:
        dp.append((dp[-1]+dp[-2])%mod)
print(dp[-1])

Submission status: Accepted

Solution code:
def resolve():
    import sys
    input = sys.stdin.readline
    # 整数 1 つ
    #n, m = int(input())
    # 整数複数個
    n, m = map(int, input().split())
    # 整数 N 個 (改行区切り)
    A = [int(input()) for i in range(m)]
    # 整数 N 個 (スペース区切り)
    #A = list(map(int, input().split()))
    # 整数 (縦 H 横 W の行列)
    # A = [list(map(int, input().split())) for i in range(H)]

    Route = [0] * (n+1)
    Route[0] = 1
    MOD = 10**9 + 7

    is_safe = [True] * (n+1)
    for a in A:
        is_safe[a] = False

    if is_safe[1] == True:
       Route[1] = 1

    for i in range(2, n+1):
        if is_safe[i] == True:
            Route[i] = (Route[i-1] + Route[i-2]) % MOD
#            Route[i] %= MOD

    print(Route[n])
#    print(Route)
resolve()

Submission status: Accepted

Solution code:
import sys

def main():
    input = sys.stdin.readline
    MOD = 10**9 + 7
    N, M = map(int, input().split())
    A = [int(input()) for _ in range(M)]
    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

    return dp[N+1]


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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
w = [1 for _ in range(n+1)]
for _ in range(m):
    w[int(input())] = 0
for i in range(2, n+1):
    if w[i] != 0:
        w[i] = w[i-2] + w[i-1]
#print(w)
print(w[-1] % 1000000007)

Submission status: Accepted

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

print(dp[n] % 1000000007)

Submission status: Accepted

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

mod = 1000000007

dp = [0] * (N + 2)
dp[N] = 1  # GOAL

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

print(dp[0] % mod)

Submission status: Accepted

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

dp = [0 for _ in range(N+1)]
dp[0] = 1
if 1 not in broken:
  dp[1] = 1

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
large_p = 10**9 + 7
a = []
kazu_memo = {}
kazu_tmp = 0
def f(target_step):
    global kazu_memo, kazu_tmp
    #print(target_step)
    if target_step < 0:
        return 0
    else:
        if kazu_memo[target_step] >= 0:
            return kazu_memo[target_step]
        else:
            kazu_tmp = (f(target_step - 1) + f(target_step - 2)) % large_p
            kazu_memo[target_step] = kazu_tmp
            return kazu_tmp

def main():
    global a, kazu_memo
    n, m = map(int, input().split())
    kazu_memo = {e: -1 for e in range(0, n + 1)}
    kazu_memo[0] = 1
    for _ in range(m):
        ta = int(input())
        kazu_memo[ta] = 0

    r = f(n)
    print(r % large_p)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = set(int(input()) for i in range(M))
MOD = 10 ** 9 + 7
DP = [0] * (N + 10)
if 1 not in A:
    DP[1] = 1
if 2 not in A and 1 in A:
    DP[2] = 1
if 2 not in A and 1 not in A:
    DP[2] = 2
for i in range(3, N + 1):
    if i not in A:
        DP[i] = (DP[i - 1] + DP[i - 2]) % MOD
print(DP[N])

Submission status: Accepted

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

mod = 1000000007

A = []
for i in range(M):
    A.append(int(input()))
A=set(A)
    
DP = [0]*(N+2)
DP[1] = 1

for i in range(2, N+2):
    if i-1 not in A:
        DP[i] =  DP[i-1]%mod + DP[i-2]%mod

print(DP[N+1]%mod)

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:
N, M = map(int, input().split())
oks = [True] * (N+1)

for _ in range(M):
    a = int(input())
    oks[a] = False

dp = [1] + [0] * N
for now in range(N):
    for nxt in range(now+1, min(N, now+2)+1):
        if oks[nxt]:
            dp[nxt] += dp[now]
            dp[nxt] %= 1e9 + 7

print(int(dp[N]))

Submission status: Accepted

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

P = [-1] * (N+1)
P[0] = 1
P[1] = 1
flg=False
MOD = 10**9 + 7
for i in range(2, N+1):
    if i in a:
        continue
    if (i-1 not in a) and (i-2 not in a):
        P[i] = (P[i-1] + P[i-2]) % MOD
    elif i-1 not in a:
        P[i] = P[i-1] % MOD
    elif i-2 not in a:
        P[i] = P[i-2] % MOD
    else:
        flg=True
if flg:
    print(0)
else:
    print(P[N] % MOD)

Submission status: Accepted

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

P = [-1] * (N+1)
P[0] = 1
P[1] = 1
flg=False
MOD = 10**9 + 7
for i in range(2, N+1):
    if i-1 not in a:
        P[i] = P[i-1]
    if i-2 not in a:
        if P[i] != -1:
            P[i] += P[i-2] % MOD
        else:
            P[i] = P[i-2] % MOD
    if P[i]==-1:
        flg=True
        break
if flg:
    print(0)
else:
    print(P[N] % MOD)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(int(1e6))

n,m=map(int,input().split())
memo=[-1]*(n+1)
memo[0]=1
memo[1]=1
for i in range(m):
    memo[int(input())]=-2
def dp(i): #i段目(0~n)まで行く方法
    if memo[i]==-2:
        return 0
    elif memo[i]==-1:
        s=dp(i-1)
        if i>=2:
            s+=dp(i-2)
        memo[i]=s%(10**9+7)
        return memo[i]
    else:
        return memo[i]
print(dp(n))

Submission status: Accepted

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

mod = 10**9 + 7
for i in range(m):
    dp[int(input())] = -1 # 壊れているので、-1としておこう?

dp[0] = 0 # 0段目にいるとしよう
# 1段目が行けなかったら...?
dp[1] = 1 if dp[1] != -1 else -1 # 1段目にいく方法は1通り?
dp[2] = -1 if dp[2] == -1 else (1 if dp[2] != -1 and dp[1] == -1 else 2) # 2段目に行く方法は2通り?
for i in range(3,n+1):
    if dp[i] != -1 and dp[i-1] != -1:
        dp[i] += dp[i-1]
        dp[i] %= mod
    if i > 1:
        if dp[i] != -1 and dp[i-2] != -1:
            dp[i] += dp[i-2]
            dp[i] %= mod
#print(dp)
print(dp[n]%mod)

Submission status: Accepted

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

dp = [0] * (n+1)
dp[0] = 1
acounter = 0
if a[0] == 1:
  dp[1] = 0
  acounter = 1
else:
  dp[1] = 1

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

Submission status: Accepted

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

dp = [0 for _ in range(N+1)]
dp[0] = 1
if 1 not in broken:
  dp[1] = 1

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
from collections import defaultdict
from collections import deque
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N,M = IL()
A = ILs(M)[::-1]

d = [0 for i in range(N+1)]
d[0] = 1
for i in range(1,N+1):
  if A:
    if i == A[-1]:
      A.pop()
    else:
      if i>1:
        d[i] = d[i-1] + d[i-2]
      else:
        d[i] = d[i-1]
  else:
    if i>1:
      d[i] = d[i-1] + d[i-2]
    else:
      d[i] = d[i-1]
print(d[N]%MOD)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
a_n = [int(input()) for i in range(M)]
def Fib(n):
    a, b = 0, 1
    if n == 1:
        return a
    elif n == 2:
        return b
    else:
        for i in range(n-2):
            a, b = b, a + b
        return b
now = 0
before = -9999
answer = 1

for a in a_n:
    if a - before == 1:
        answer = 0
        break

    answer *= Fib( a - 1 - now + 2 )
    answer %= 1000000007
    now = a + 1
    before = a

if answer > 0:
    answer *= Fib( N - now + 2)
    answer %= 1000000007

print(answer)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
try:
    from typing import List
except ImportError:
    pass

MOD = 1000000007  # type: int


def solve(N: int, M: int, a: "List[int]"):
    sa = set(a)
    dp = [0] * (N + 1)
    dp[0] = 1
    for i in range(1, N + 1):
        if i in sa:
            continue
        c = dp[i - 1]
        if i >= 2:
            c += dp[i - 2]
        dp[i] = c % MOD
    print(dp[N])


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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def Fib(n, memo={}):
    if n < 2:
        return 1
    elif n in memo:
        return memo[n]
    else:
        memo[n] = Fib(n - 1, memo) + Fib(n - 2, memo)
        return memo[n]


def resolve():
    N, M = [int(i) for i in input().split()]
    aa = []
    for _ in range(M):
        aa.append(int(input()))
    fib_l = list(Fib(i) for i in range(N + 1))

    ans = 1
    now = 0
    for a in aa:
        if now == a:
            ans = 0
            break
        tmp = a - now - 1
        ans = ans * fib_l[tmp]
        now = a + 1
    else:
        ans = ans * fib_l[N - now]
    print(ans % (10**9 + 7))


resolve()

Submission status: Accepted

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

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

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

for i in a:
    broken[i] = 1

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

mod = 1000000007

dp[n] = 1

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

print(dp[0])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
N,M=map(int,input().split())
dp=[1]*N
listA=[]
for i in range(M):
  a=int(input())
  listA+=[a]
  dp[a-1]=0
for i in range(1,M):
  if listA[i]==listA[i-1]:
    print(0)
    sys.exit()
setA=set(listA)    
if (1 not in setA) and (2 not in setA) and N!=1:
  dp[1]=2
for i in range(2,N):
  if i+1 not in setA:
    dp[i]=dp[i-1]+dp[i-2]
ans=dp[-1]%(10**9+7)
print(ans)

Submission status: Accepted

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

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]
    dp[i] %= MOD

print(dp[-1])

Submission status: Accepted

Solution code:
# input
N, M = map(int, input().split())
a = []
a_append = a.append

for n in range(M):
    a_append(int(input()))

mod = 1000000007

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

dp = {0: 1}
if check[1] is True:
    dp[1] = 1
else:
    dp[1] = 0

for n in range(2, N + 1):
    dp[n] = 0
    if check[n - 1] is True:
        dp[n] += dp[n - 1]
    if check[n - 2] is True:
        dp[n] += dp[n - 2]
    dp[n] %= mod

print(dp[N])

Submission status: Accepted

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

ok = [True] * (n + 1)
for v in a:
    ok[v] = False

dp = [0] * (n + 1)
dp[0] = 1
if 1 in a:
    dp[1] = 0
else:
    dp[1] = 1
MOD = 10 ** 9 + 7

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

print(dp[-1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)

n,m=map(int,input().split())
a=set()
for ii in range(m):
  a.add(int(input()))
#print(a)
b=[-1]*(n+2)

def delta_n(ii):
  if b[ii]>=0:
    return b[ii]

  if ii>n or ii in a:
    r=0
  elif ii==n:
    r=1
  else:
    r=delta_n(ii+1)+delta_n(ii+2)
  #print(ii,r)
  b[ii]=r
  return r

print(delta_n(0)%(7+10**9))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import itertools,sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,M = LI()
a = set([I() for _ in range(M)])
dp = [0]*(N+1) #1_indexed
dp[0] = 1
dp[1] = 0 if 1 in a else 1
for i,j in itertools.product(range(2,N+1),[1,2]):
    if i in a:
        dp[i] = 0
        continue
    dp[i] += dp[i-j]
    dp[i] %= 10**9+7
print(dp[-1])

Submission status: Accepted

Solution code:
#import bisect,collections,copy,heapq,itertools,math,numpy,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
N, M = LI()
A = [I() for _ in range(M)]
md = 10**9+7


dp = [0] * (N+1)
dp[0] = 1
chk = [True] * (N+1)
for a in A:
  chk[a] = False

for now in range(N):
  for next in range(now+1, now+3):
    if next == N:
      dp[next] += dp[now]
      dp[next] %= md
      break
    if not chk[next]:
      continue
    else:
      dp[next] += dp[now]
      dp[next] %= md

print(dp[N])

Submission status: Accepted

Solution code:
import math

MOD = int(math.pow(10, 9)) + 7
N, M = map(int, input().split(' '))
broken_steps = {int(input()) for _ in range(M)}

dp = [0] * (N + 1)

dp[0] = 1
if 1 not in broken_steps:
    dp[1] = 1

for step in range(2, N + 1):
    if step not in broken_steps:
        dp[step] = (dp[step - 1] + dp[step - 2]) % MOD

print(dp[N])

Submission status: Accepted

Solution code:
n, m = map(int,input().split())
mod = 1000000007
stair = [True] * (n+1)
for i in range(m):
    a = int(input())
    stair[a] = False

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

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

print(dp[n])

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7


def resolve():
    N, M = map(int, input().split())

    broken = [False] * (N + 1)
    dp = [0 for _ in range(N + 1)]
    dp[0] = 1

    for _ in range(M):
        broken[int(input())] = True

    for i in range(1, N + 1):
        if broken[i]:
            continue

        if i == 1:
            dp[i] = dp[i - 1]
        else:
            dp[i] = dp[i - 1] + dp[i - 2]
            dp[i] %= MOD

    print(dp[N])


resolve()

Submission status: Accepted

Solution code:
def main():
    MOD = 1000000007
    N, M = map(int, input().split())
    a = [int(input()) for _ in range(M)]
    table = [1]*(N+1)
    for broken in a:
        table[broken] = 0
    table[1] = table[0] * table[1]
    if N > 1:
        for n in range(2, N+1):
            table[n] = ((table[n-2] + table[n-1]) * table[n]) % MOD
    print(table[-1])
main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,m,*a=map(int,open(0).read().split())
mod=10**9+7
p=[1]
a=iter(a)
b=next(a,-1)
if 1==b:
    p.append(0)
    b=next(a,-1)
else:
    p.append(1)
for i in range(2,n+1):
    if i==b:
        p.append(0)
        b=next(a,-1)
    else:
        p.append((p[i-1]+p[i-2])%mod)
print(p[-1])

Submission status: Accepted

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

dp=[0]*(n+1)
#dp=[-1]*(n+1)
dp[0]=1
if 1 not in mList:
  dp[1]=1

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

#def calc(i):
#  if dp[i]!=-1: return dp[i]
#  if i in mList:
#    dp[i]=0
#    return dp[i]
#  dp[i]=calc(i-1)+calc(i-2)
#  dp[i]%=1000000007
#  return dp[i]

#print(calc(n))
print(dp[n])

Submission status: Accepted

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

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

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

print(dp[n])