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 i in range(M)]
A.append(N+1)

#import math
def fibonacci(n):
    #a = 1/math.sqrt(5) * (((1+math.sqrt(5))/2)**n - ((1-math.sqrt(5))/2)**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)

Submission status: Accepted

Solution code:

# 壊れている床を無視すればフィボナッチ数になってる
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)

Submission status: Accepted

Solution code:

# 壊れている床を無視すればフィボナッチ数になってる
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)

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
n, m = [int(i) for i in input().split()]
obs = []
idou = []
 
for i in range(m):
  obs.append(int(input()))
  
obs = set(obs)
  
#i段目にいる確率
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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)
#print(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)

Submission status: Accepted

Solution code:
# 定数
INF = float("inf")
MOD = int(1e9 + 7)
# # データ構造：上限付き整数
# class intmod:
#     def __init__(self, v):
#         self.v = v
#     def __add__(self, o):
#         self.v += o.v
#         self.v %= MOD
#     def __sub__(self, o):
#         self.v -= o.v
#     def __mul__(self, o):
#         self.v *= o.v
#         self.v %= MOD

# エントリーポイント
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()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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:
    #リストに対するinは激遅なのでset
        dp[i] == 0
    else:
        dp[i] = dp[i-1] + dp[i-2]
        dp[i] %= mod
print(dp[-1])

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a = set(int(input()) for i in range(m))
#for i in range(m):
#  a.append(int(input()))
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])

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a = set(int(input()) for i in range(m))
#for i in range(m):
#  a.append(int(input()))
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))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

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

ans = [-1] * (N + 1)  # not evaluated yet

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

ans[0] = 1  # reachable

if ans[1]:  # if not unreachable
    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])

Submission status: Accepted

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

ans = [-1] * (N + 1)  # not evaluated yet

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

ans[0] = 1  # reachable

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)

Submission status: Accepted

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

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

ans = [-1] * (N + 1)  # not evaluated yet

for broken in a:
    ans[broken] = 0  # unreachable

ans[0] = 1  # reachable

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)

Submission status: Accepted

Solution code:

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)

Submission status: Accepted

Solution code:
# ABC 129, c
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])

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1
for i in [int(input()) for _ in range(m)]:
    dp[i] = -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])

Submission status: Accepted

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

p,q=(0,1)
#累積和っぽい考え
for i in range(1, n+1):
	p,q = q,(p+q)*(not i in a)
print(q%(10**9+7))

Submission status: Accepted

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

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

print(dp[-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,M = map(int, input().split())
a = []
for _ in range(M):
    a.append(int(input()))
    
def fibonacci(n):
    listf = [0]+[1]*n
    a, b = 1, 0
    for i in range(n-1):
        a, b = (a+b)%1000000007 , a
        listf[i+2] = a
    return listf 

fib = fibonacci(N+1)
if a:
    ans = [a[0]]
    
    for i in range(M-1):
        ans.append(a[i+1]-a[i]-1)
            

    result = 1
    for j in range(len(ans)):
        result = result * fib[ans[j]] % 1000000007
    
    result = result * fib[(N - a[-1])] % 1000000007
    
    print(result)
else:
    ans = fib[-1]
    print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=set([int(input()) for _ in range(m)])
p,q=0,1
for i in range(1,n+1):
    p,q=q,(p+q)*(not i in a)
print(q%(10**9+7))

Submission status: Accepted

Solution code:
INF = (10 ** 9) + 7
N, M = map(int, input().split())

aLst = set(int(input()) for i in range(M))
ansLst = [0] * (N + 1)
ansLst[0] = 1

for i in range(1, N + 1):
    if i in aLst:
        continue
    tmp = ansLst[i - 1]
    if i > 1:
        tmp += ansLst[i - 2]
    ansLst[i] = tmp % INF


print(ansLst[N])

Submission status: Accepted

Solution code:
INF = (10 ** 9) + 7
N, M = map(int, input().split())

aLst = set(int(input()) for _ in range(M))
ansLst = [0] * (N + 1)
ansLst[0] = 1

for i in range(1, N + 1):
    if i in aLst:
        continue
    tmp = ansLst[i - 1]
    if i > 1:
        tmp += ansLst[i - 2]
    ansLst[i] = tmp % INF


print(ansLst[N])

Submission status: Accepted

Solution code:
N ,M = map(int, input().split())
X = [int(input()) for _ in range(M)]
S = [0] * (N + 1)
dp = [0] * (N + 1)
mod = int(1e9 + 7)

for i in range(M):
	S[X[i]] = -1


for i in range(0, len(X) - 1):
	if X[i + 1] - X[i] == 1:
		print('0')
		exit()

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

for i in range(2, N + 1):
	#print(dp)
	if S[i - 1] != -1: dp[i] += dp[i - 1]
	if S[i - 2] != -1: dp[i] += dp[i - 2]
	dp[i] %= mod

#print(dp)
print(dp[N])

Submission status: Accepted

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

dp = [0]*(n+2)
mod = int(1e9+7)
dp[n] = 1
for i in range(n-1, -1 , -1):
  if broken[i]:
    dp[i] = 0
  else:
    dp[i] = (dp[i+1] + dp[i+2]) % mod

print(dp[0])

Submission status: Accepted

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

dp = [0]*(n+2)
dp[0] = 1
broken = 0
for i in range(n):
    if broken < len(a) and i == a[broken]:
        broken += 1
    else:
        dp[i+1] = (dp[i+1] + dp[i]) % (10e8+7)
        dp[i+2] = (dp[i+2] + dp[i]) % (10e8+7)
print(int(dp[-2]))

Submission status: Accepted

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

if M == 0:
    maxM = N
else:
    maxM = a[0] - 1
    for i in range(1, M):
        maxM = max(maxM, a[i] - a[i-1] - 2)
    maxM = max(maxM, N - a[-1])

dp = [0] * (maxM+1)
dp[1] = 1
if maxM > 1:
    dp[2] = 2
    if maxM > 2:
        for n in range(3, maxM+1):
            dp[n] = (dp[n-1] + dp[n - 2]) % 1000000007

if M == 0:
    print(dp[-1])
    exit()

if a[0] == 1:
    ans = 1
else:
    ans = dp[a[0] - 1]

if M > 1:
    for i in range(1, M):
        if a[i] - a[i - 1] == 1:
            ans = 0
        elif a[i] - a[i - 1] == 2:
            continue
        else:
            ans = ans * dp[a[i] - a[i - 1] - 2] % 1000000007
if N - a[-1] != 1:
    ans = ans * dp[N - a[-1] - 1] % 1000000007
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
N,M=map(int,input().split())
a=[int(input()) for i in range(M)]
a_a=np.ones( N+1 )
MOD=7+10**9
for i in range(M):
    a_a[a[i]]=0
c=np.zeros(N+1)
c[0]=1
for i in range(1,N+1):
    if i==1:
        c[i]=c[i-1]*a_a[i-1]
    else:
        c[i]=c[i-1]*a_a[i-1]%MOD+c[i-2]*a_a[i-2]%MOD
print(int(c[N])%MOD)

Submission status: Accepted

Solution code:
import sys
 
n,m=map(int,input().split())
a=[int(input()) for i in range(m)]+[0] #jがはみ出ないように最後に付け足しておく
MOD=7+10**9 #%MODを忘れない
 
dp=[1]+[0]*n
 
j=0
#iにのぼることができるかを考える
for i in range(1,n+1):
  if i==a[j]:
    j+=1
  elif i>1:
    dp[i] = (dp[i-1] + dp[i-2])%MOD #-1,-2からの遷移を考える
  else:
    if i!=a[0]:
      dp[i] = dp[i-1]

print((dp[-1])%MOD)

Submission status: Accepted

Solution code:
import sys

n,m=map(int,input().split())
c=set(map(int,sys.stdin))

d=[0]*(n+1)
d[0]=1
d[1]=1 if 1 not in c else 0
for j in range(2,n+1):
    if j in c:
        pass
    else:
        d[j]=(d[j-1]+d[j-2])%1000000007

print(d[n])

Submission status: Accepted

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

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

print(dp[N])

Submission status: Accepted

Solution code:
s,n=map(int,input().split())
if n>0:
	x=list(int(input()) for _ in range(n))

w0=int(1)
b0=int(0)
cnt=0

for i in range(1,s):
	if n>0 and i==x[cnt]:
		w1=int(0)
		b1=w0
		w0=w1
		b0=b1
		if cnt<n-1: 
			cnt+=1
	else:
		w1=b0+w0
		b1=w0
		w0=w1
		b0=b1

print((w0+b0)%1000000007)

Submission status: Accepted

Solution code:
import sys,math
N,M = map(int,input().split())
a = [int(input()) for i in range(M)]
b = set(a)
dp = [0] * (N+1)
mod = 10**9+7
for i in range(N,-1,-1):
    if i in b:
        continue
    elif i == N or i == N-1:
        dp[i] = 1
    else:
        dp[i] = (dp[i+1] + dp[i+2])%mod
print(dp[0])

Submission status: Accepted

Solution code:
import sys
 
n,m=map(int,input().split())
a=[int(input()) for i in range(m)]+[0] #jがはみ出ないように最後に付け足しておく
MOD=7+10**9 #%MODを忘れない

dp=[1]+[0]*n

j=0
#iにのぼることができるかを考える
for i in range(1,n+1):
  if i==a[j]:
    j+=1
  elif i>1:
    dp[i] = (dp[i-1] + dp[i-2])%MOD #-1,-2からの遷移を考える
  else:
    if i!=a[0]:
      dp[i] = dp[i-1]
print((dp[-1])%MOD)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
import logging
logging.basicConfig(level=logging.DEBUG)
logging.disable(logging.CRITICAL)

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

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

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

    logging.debug("{}".format(dp))
    return dp[N+1]

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

Submission status: Accepted

Solution code:
import sys

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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=set([int(input()) for _ in range(m)])
p,q=0,1
for i in range(1,n+1):
    p,q=q,(p+q)%(10**9+7)*(not i in a)
print(q)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,m= map(int, input().split())
if m!=0:
  a = [int(input()) for _ in range(m)]
else:
  a=[0]
dp=[0]*(n+1)
dp[0]=1
j=0

for i in range(1,n+1):
    if i==a[j]:
        if j<m-1:
            j+=1
    else:
        if i==1:
            dp[i]=1
        else:
            dp[i]=dp[i-1]+dp[i-2]

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

Submission status: Accepted

Solution code:
MOD=10**9+7
n,m=map(int,input().split())
A=[1 for i in range(n)]
if n!=1:
  A[1]=2
  for i in range(m):
    A[int(input())-1]=0
  
  if A[0]==0 and A[1]!=0:
    A[1]=1



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

    
  print(A[n-1])
  
else:print(1)

Submission status: Accepted

Solution code:
# DP
mod = 1000000007
 
n, m = map(int, input().split())
b_list = [True] * (n+1)
dp = [0 for _ in range(n+1)]
for i in range(m):
    b_list[int(input())] = False
 
dp[0] = 1
for i in range(n):
    for j in range(i+1, min(n, i+2)+1):
        if b_list[j] == True:
            dp[j] += dp[i]
            dp[j] %= mod
# print(b_list)
# print(dp)
print(dp[n])

Submission status: Accepted

Solution code:
# import bisect

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

# for i in range(N - 1):
#     idx = bisect.bisect_left(A, i)
#     if idx < N and A[idx + 1] == i:

p = [0] * (N + 1)
p[0] = 1
for i in A:
    p[i] = -1

for i in range(N):
    if p[i] < 0: continue
    if p[i + 1] >= 0:
        p[i + 1] += p[i]
    if i < N - 1 and p[i + 2] >= 0:
        p[i + 2] += p[i]
    # print(p)

print(p[-1] % 1000000007)

Submission status: Accepted

Solution code:
# ABC129C - Typical Stairs
import sys
input = sys.stdin.readline
 
def main():
    N, M = tuple(map(int, input().split()))
    A = set(map(int, [input() for _ in range(M)]))
    MOD = 10 ** 9 + 7
    dp = [0] * (N + 1)
    dp[:2] = 1, 1 if 1 not in A else 0
    for i in range(2, N + 1):
        if i in A:
            continue
        else:
            dp[i] = (dp[i - 1] + dp[i - 2]) % MOD
    print(dp[-1])
 
 
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC129C - Typical Stairs
import sys
input = sys.stdin.readline

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC129C - Typical Stairs
import sys
input = sys.stdin.readline

def main():
    n, m = tuple(map(int, input().split()))
    A = set(map(int, [input() for _ in range(m)]))
    MOD = 10 ** 9 + 7
    a, b = 1, 1 if not 1 in A else 0
    for i in range(2, n + 1):
        if i in A:
            a, b = b, 0
        else:
            a, b = b, (a + b) % MOD
    print(b)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC129C - Typical Stairs
import sys
input = sys.stdin.readline

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC129C - Typical Stairs
import sys
input = sys.stdin.readline

def main():
    N, M = tuple(map(int, input().rstrip().split()))
    A = set(map(int, [input().rstrip() for _ in range(M)]))
    MOD = 10 ** 9 + 7
    dp = [0] * (N + 1)
    dp[:2] = 1, 1 if 1 not in A else 0
    for i in range(2, N + 1):
        if i in A:
            continue
        else:
            dp[i] = (dp[i - 1] + dp[i - 2]) % MOD
    print(dp[-1])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC129C - Typical Stairs
import sys
input = sys.stdin.readline

def main():
    N, M = tuple(map(int, input().rstrip().split()))
    A = set(map(int, [input().rstrip() for _ in range(M)]))
    MOD = 10 ** 9 + 7
    dp = [0] * (N + 1)
    dp[0] = 1
    for i in range(1, N + 1):
        if i in A:
            continue
        else:
            for j in range(1, 3):
                if i - j >= 0:
                    dp[i] = (dp[i] + dp[i - j]) % MOD
    print(dp[-1])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# DP
mod = 1000000007

n, m = map(int, input().split())
b_list = [True] * (n+1)
dp = [0 for _ in range(n+1)]
for i in range(m):
    b_list[int(input())] = False

dp[0] = 1
for i in range(n):
    for j in range(i+1, min(n, i+2)+1):
        if b_list[j] == True:
            dp[j] += dp[i]
            dp[j] %= mod
# print(b_list)
# print(dp)
print(dp[n])

Submission status: Accepted

Solution code:
n, m = [int(e) for e in input().split()]
a = set(int(input()) for i in range(m))
t = [0] * (n + 2)
t[0] = 1
for i in range(n):
  if i in a:
    t[i] = 0
  else:
    t[i + 1] = (t[i + 1] + t[i]) % 1000000007
    t[i + 2] = (t[i + 2] + t[i]) % 1000000007
print(t[n])

Submission status: Accepted

Solution code:
temp=input().split()
N=int(temp[0])
M=int(temp[1])

index=[int(1) for i in range(N)]
for i in range(M):
  index[int(int(input())-1)]=0

temp=[0, 1]
for i in range(N):
  if index[i]==1:
    temp=[temp[1], temp[0]+temp[1]]
  else:
    temp=[temp[1], 0]
    
print(temp[1]%1000000007)