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:
INFTY = 10**9+7
N,M = map(int,input().split())
A = []
for _ in range(M):
    A.append(int(input()))
dp = [0 for _ in range(N+1)]
dp[0] = 1
dp[1] = 1
cur = 0
if M>0 and A[0]==1:
    dp[1] = 0
    cur = 1
for i in range(2,N+1):
    if M>0 and cur<M and i==A[cur]:
        cur += 1
    else:
        dp[i] = (dp[i-1]+dp[i-2])%INFTY
print(dp[N])

Submission status: Accepted

Solution code:
def resolve():
    n, m  = list(map(int, input().split()))
    aaa = [int(input()) for _ in range(m)]
    dp = [0 for i in range(n+1)]
    mod = 10**9 + 7
    dp[0] = 1
    isbroken = [1 for i in range(n+1)]
    for i in range(m):
        isbroken[aaa[i]] = 0
    for i in range(n):
        if i-1 >= 0:
            dp[i+1] = dp[i] * isbroken[i] + dp[i-1] * isbroken[i-1]
        else:
            dp[i+1] = dp[i] * isbroken[i]
        dp[i+1] %= mod 
    
    print(dp[n])
resolve()

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
a,b = [int(i) for i in input().split()]
c = {int(input()) for _ in range(b) }
mod = 1000000007

memo = [1] * (a+1)

for i in c:
    memo[i] = 0

for i in range(a+1):
    if i > 1:
        memo[i] = (memo[i-1] + memo[i-2])%mod*memo[i]
        
print(memo[a])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

    sep = []
    pre = -1
    ok = True
    for t in a:
        tmp = t - pre - 1
        if tmp == 0:
            ok = False
            break
        sep.append(tmp)
        pre = t
    sep.append(N-pre)
    # print(sep)

    if not ok:
        print(0)
        return
    max_sep = max(sep)

    MOD = 1000000007
    fib = [1] * (max_sep)
    for i in range(2, max_sep):
        fib[i] = fib[i-2] + fib[i-1]
        fib[i] %= MOD
    
    ans = 1
    for s in sep:
        ans *= fib[s-1]
        ans %= MOD
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

print(dp[n])

Submission status: Accepted

Solution code:
mod = 1000000007

while True:
    try:
        N, M = map(int, input().split())
        
        # check obstacles: O(1)
        a = [0] * (N+1)
        for _ in range(M):
            a[int(input())] = 1
        
        dp = [0] * (N+1)
        dp[0] = 1
        dp[1] = 0 if a[1] else 1
        
        for i in range(2, N+1):
            if a[i]:
                dp[i] = 0
            else:
                dp[i] = dp[i-1] + dp[i-2]
        
        print(dp[N] % mod)
    except:
        break

Submission status: Accepted

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

mod=10**9+7
if n==1:
	print(1)
	exit()
dp = [0]*(n+1)
dp[0]=1
dp[1]=1 if dic[1]!=1 else 0

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

Submission status: Accepted

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

mod=10**9+7
if n==1:
	print(1)
	exit()
dp = [0]*(n+1)
dp[0]=1
dp[1]=1 if dic[1]!=1 else 0

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
mod=10**9+7
data=[0]*(n+1)
for i in range(m):
	data[int(input())]=1
dp=[0]*(n+1)
dp[0]=1
dp[1]=0 if data[1] else 1
for i in range(2,n+1):
	if data[i]:
		dp[i]=0
	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 = [int(input()) for _ in range(M)] # a_0...a_(M-1)

def fib(x): # フィボナッチ数列
    a, b = 1, 1
    if x == 0:
        return a
    elif x == 1:
        return b
    else:
        for i in range(x-1):
            a, b = b, a + b
        return b
"""
# 再帰だとTLEとかREとかになるよ
def fib(x): # フィボナッチ数列
    if x == 0:
        return(1)
    elif x == 1:
        return(1)
    else:
        return(f(x-1) + f(x-2))
"""

ans = 0
MOD = 10**9 + 7

if M == 0:
    ans += fib(N) % MOD
    print(ans)
else:
    ans += fib((a[0]-1) - 0) % MOD # 0段目からa_0-1段目に上る(その後a_0段目を飛ばしてa_0+1段目に上る)
    for i in range(1, M): # iは1からM-1
        stair = (a[i] - 1) - (a[i-1] + 1) # 登る段数
        if stair >= 0:
            ans *= fib(stair) % MOD # a_(i-1)+1段目からa_i-1段目に上る(その後a_i段目を飛ばしてa_i+1段目に上る)
        else:
            ans = 0
            break
    ans *= fib(N - (a[M-1] + 1)) % MOD # a_M-1段目からN段目に上る
    print(ans % MOD)

Submission status: Accepted

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

def f(x):
    a, b = 1, 1
    if x == 0:
        return a
    elif x == 1:
        return b
    else:
        for i in range(x-1):
            a, b = b, a + b
        return b
"""
# 再帰だとTLEとかREとかになるよ
def f(x): # フィボナッチ数列
    if x == 0:
        return(1)
    elif x == 1:
        return(1)
    else:
        return(f(x-1) + f(x-2))
"""

ans = 0
MOD = 10**9 + 7

if M == 0:
    ans += f(N) % MOD
    print(ans)
else:
    ans += f((a[0]-1) - 0) % MOD # 0段目からa_0-1段目に上る(その後a_0段目を飛ばしてa_0+1段目に上る)
    for i in range(1, M): # iは1からM-1
        stair = (a[i] - 1) - (a[i-1] + 1) # 登る段数
        if stair >= 0:
            ans *= f(stair) % MOD # a_(i-1)+1段目からa_i-1段目に上る(その後a_i段目を飛ばしてa_i+1段目に上る)
        else:
            ans = 0
            break
    ans *= f(N - (a[M-1] + 1)) % MOD # a_M-1段目からN段目に上る
    print(ans % MOD)

Submission status: Accepted

Solution code:
MOD_NUM = 1000000007
N, M = map(int, input().split())
alist = [int(input()) for _ in range(M)]
cases = [1] + [0 for _ in range(N)]
for a in alist:cases[a] = None

for i in range(1,N+1):
  if cases[i] is None:continue
  if cases[i-1] is not None:cases[i] += cases[i-1] 
  if i >= 2 and cases[i-2] is not None: cases[i] += cases[i-2]
print(cases[-1]%MOD_NUM)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
fib=[0]*(n+2)
fib[0]=0
fib[1]=1
for i in range(n):
  fib[i+2]=fib[i]+fib[i+1]
ans=1
k=0
for i in range(m):
  a=int(input())
  ans*=fib[a-k]
  k=a+1
ans*=fib[n-k+1]
print(ans%1000000007)

Submission status: Accepted

Solution code:
import sys

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

if N == 1:
    print(1)

else:
    a = 1
    ans = 1

    if M == 0:
        b = 1
        for i in range(2, N+1):
            ans = (a+b)%1000000007
            a, b = b, ans

    elif M == 1:
        if a_list[0] == 1:
            b = 0
            m = 1
        else:
            b = 1
            m = 0
        for i in range(2, N+1):
            if a_list[0] == i:
                a, b = b, 0
            else:
                ans = (a+b)%1000000007
                a, b = b, ans

    else:
        if a_list[0] == 1:
            b = 0
            m = 1
        else:
            b = 1
            m = 0
        for i in range(2, N+1):
            if m < M-1:
                if a_list[m+1] - a_list[m] == 1:
                    print(0)
                    sys.exit()

                if a_list[m] == i:
                    a, b = b, 0
                    m += 1
                else:
                    ans = (a+b)%1000000007
                    a, b = b, ans

            else:
                if a_list[m] == i:
                    a, b = b, 0
                else:
                    ans = (a+b)%1000000007
                    a, b = b, ans

    print(ans)

Submission status: Accepted

Solution code:
N,M = map(int, input().split())
a = [int(input()) for _ in range(M)]
dp = [0 for _ in range(N+1)]
dp[0] = 1
no_step = 0
for i in range(N+1):
    if no_step >= M:
        if i+1 <= N:
            dp[i+1] += dp[i]
        if i+2 <= N:
            dp[i+2] += dp[i]
    else:
        if i == a[no_step]:
            no_step += 1
            continue
        else:
            if i+1 != a[no_step] and i+1 <= N:
                dp[i+1] += dp[i]
            if i+2 != a[no_step] and i+2 <= N:
                dp[i+2] += dp[i]
print(dp[-1]%1000000007)

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
for i in range(1,n+1):
  dp[i]=(dp[i-1]+dp[i-2])%(10**9+7)
  if i in a:dp[i]=0
print(dp[n])

Submission status: Accepted

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

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

dp = [0] * (n + 1)

dp[0] = 1
if issafe[1]: dp[1] = 1;

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

print(dp[n])

Submission status: Accepted

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

A = []
d = [1 for i in range(N+1)]
for i in range(M):
    a = int(input())
    A.append(a)
    d[a] = 0
    if i != 0:
        if a-A[i-1] == 1:
            print(0)
            exit()

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

for n in range(2,N+1):
    # if d[n] == 0:
        # dp[n] = (dp[n-1] if d[n-1] == 0 else dp[n-2]+dp[n-3])+(dp[n-2] if d[n-2] == 0 else 0)
    dp[n] = dp[n-1]+dp[n-2]
    buff = 0
    if d[n-1]:
        buff += dp[n-1]
    if d[n-2]:
        buff += dp[n-2]
    dp[n] = buff

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

Submission status: Accepted

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

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

print(arr[-1])

Submission status: Accepted

Solution code:
def slove():
    import sys
    input = sys.stdin.readline
    n, m = list(map(int, input().rstrip('\n').split()))
    a = dict([[int(input().rstrip('\n')), 0] for i in range(m)])
    dp = [0] * (n + 1)
    dp[0] = 1 if 0 not in a else 0
    dp[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]) % (10 ** 9 + 7)
        else:
            dp[i] = 0
    print(dp[-1])


if __name__ == '__main__':
    slove()

Submission status: Accepted

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

kaidan = [-1] * (n+1)

for i in range(m):
  a = int(input())
  kaidan[a] = 0
  
kaidan[0] = 1
if kaidan[1] == -1:
  kaidan[1] = kaidan[0]
  
for i in range(2,len(kaidan)):
  if kaidan[i] == -1:
    kaidan[i] = (kaidan[i-2] + kaidan[i-1]) % 1000000007

print(kaidan[-1])

Submission status: Accepted

Solution code:
#coding utf-8
N,M=map(int,input().split())
a =[int(input()) for i in range(M)]
a.append(0)
mod =10**9+7
dp = [1]
j = 0
for i in range(1,N+1):
  if i != a[j]:
    if i ==1:
      dp.append(dp[-1])
    else:
      dp.append((dp[-1]+dp[-2])%mod)
  else:
    dp.append(0)
    j +=1 

print(dp[-1])

Submission status: Accepted

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

dp = []
for i in range(N + 1):
    dp.append(None)

for _ in range(M):
    a = int(input())
    A.add(a)

dp.append(0)
dp[N] = 1

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

# print('dp', dp)
print(dp[0] % 1000000007)

Submission status: Accepted

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

dp = []
for i in range(N + 1):
    dp.append(None)
    A.append(None)

for _ in range(M):
    a = int(input())
    A[a] = 1

dp.append(0)
dp[N] = 1

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

# print('dp', dp)
print(dp[0] % 1000000007)

Submission status: Accepted

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

ans = [0,1]

for n in range(1,N+1):
  if n in broken_list:
    ans.append(0)
  else:
    ans.append((ans[-2]+ans[-1]) % MOD)

print(ans[-1] % MOD)

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

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

dp[0] = 1
for now in range(n):
    for next in range(now+1, min(n+1, now + 3)):
        if oks[next]:
            dp[next] += dp[now]
            dp[next] %= 10 ** 9 + 7
print(dp[n])

Submission status: Accepted

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

Submission status: Accepted

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

from collections import defaultdict as dd
n,m=[int(i) for i in input().split()]
brkn = dd(int)
mod = 10**9+7
for i in range(m):
    num = int(input())
    brkn[num]+=1
dp = [-1]*(n+1)

def func(curr):
    if(curr==0):
        dp[0]=1
        return dp[0]
    if(curr>0 and (curr in brkn)):
        dp[curr]=0
        return dp[curr]%mod
    if(curr==1):
        dp[1]=1
        return dp[1]
    if(dp[curr]!=-1):
        return dp[curr]%mod
    else:
        dp[curr] =  (func(curr-1) + func(curr-2))%mod
        return dp[curr]%mod

print(func(n))

Submission status: Accepted

Solution code:
from collections import defaultdict as dd
n,m=[int(i) for i in input().split()]
brkn = dd(int)
mod = 10**9+7
for i in range(m):
    num = int(input())
    brkn[num]+=1
dp = [0]*(n+1)
dp[0]=1
if(1 in brkn):
    dp[1]=0
else:
    dp[1]=1
for i in range(2,n+1):
    if(i in brkn):
        dp[i]=0
    else:
        dp[i] = (dp[i-1]+ dp[i-2])%mod
print(dp[n])

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)

N, M = map(int, input().split())
A = []
ANS = []
for i in range(N + 10):
    ANS.append(None)

for _ in range(M):
    a = int(input())
    A.append(a)
    ANS[a] = 0


def f(x):
    if ANS[x] is not None:
        return ANS[x]

    if x > N:
        return 0
    if x == N:
        return 1

    ans = f(x + 1) + f(x + 2)
    ANS[x] = ans
    return ans


print(f(0) % 1000000007)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)

N, M = map(int, input().split())
A = []
ANS = []
for i in range(N + 10):
    ANS.append(None)

for _ in range(M):
    a = int(input())
    A.append(a)
    ANS[a] = 0


def f(x):
    if ANS[x] is not None:
        return ANS[x]

    if x > N:
        return 0
    if x == N:
        return 1

    if ANS[x + 1] is None:
        x1 = f(x + 1)
        ANS[x + 1] = x1
    else:
        x1 = ANS[x + 1]

    if ANS[x + 2] is None:
        x2 = f(x + 2)
        ANS[x + 2] = x1
    else:
        x2 = ANS[x + 2]

    ans = x1 + x2
    # ans = f(x + 1) + f(x + 2)
    ANS[x] = ans
    return ans


print(f(0) % 1000000007)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(1000000)

N, M = map(int, input().split())
A = []
ANS = []
for i in range(N + 10):
    ANS.append(None)

for _ in range(M):
    a = int(input())
    A.append(a)
    ANS[a] = 0


def f(x):
    if ANS[x] is not None:
        return ANS[x]

    if x > N:
        return 0
    if x == N:
        return 1

    if ANS[x + 1] is None:
        x1 = f(x + 1)
        ANS[x + 1] = x1
    else:
        x1 = ANS[x + 1]

    if ANS[x + 2] is None:
        x2 = f(x + 2)
        ANS[x + 2] = x1
    else:
        x2 = ANS[x + 2]

    ans = x1 + x2
    # ans = f(x + 1) + f(x + 2)
    ANS[x] = ans
    return ans


print(f(0) % 1000000007)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(1000000)

N, M = map(int, input().split())
A = []
ANS = []
for i in range(N + 10):
    ANS.append(None)

for _ in range(M):
    a = int(input())
    A.append(a)
    ANS[a] = 0


def f(x):
    # print(ANS)
    # if x in A:
    #     print('::::', x)
    #     d[x] = 0
    #     return 0
    if ANS[x] is not None:
        return ANS[x]

    if x > N:
        return 0
    if x == N:
        return 1

    # if d.get(x + 1):
    #     x1 = d.get(x + 1)
    # else:
    #     x1 = f(x + 1)
    #     d[x + 1] = x1
    #
    # if d.get(x + 2):
    #     x2 = d.get(x + 2)
    # else:
    #     x2 = f(x + 2)
    #     d[x + 2] = x2

    # ans = x1 + x2
    ans = f(x + 1) + f(x + 2)
    ANS[x] = ans
    return ans


print(f(0) % 1000000007)

Submission status: Accepted

Solution code:
# ここから
import sys
input = sys.stdin.readline

def resolve():
    n, m = map(int, input().split())
    aa = [False] * (n+1)

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

    dp = [0] * (n+1)
    dp[0] = 1
    dp[1] = 0 if aa[1] else 1

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

    print(dp[n])



resolve()

Submission status: Accepted

Solution code:
n, m = tuple([int(i) for i in input().split(' ')])

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

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

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

    dp[i + 1] %= 1000000007
    if a[i + 2] != 1:
        dp[i + 2] += dp[i]

    dp[i + 2] %= 1000000007

print(dp[n])

Submission status: Accepted

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

flag = True
if M == 1:
    print(Fib(a[0])*Fib(N-a[M-1]))
elif M == 0:
    print(Fib(N+1)%1000000007)
else:
    m = Fib(a[0])*Fib(N-a[M-1])
    for i in range(M-1):
        if a[i] + 1 == a[i+1]:
            print(0)
            flag = False
            break
    if flag:
        for j in range(M-1):
            dev = a[j+1]-a[j]-1
            m = m*Fib(dev)%1000000007
        print(m%1000000007)

Submission status: Accepted

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

p = [1] * (n+1)
ans = 1

for a in la:
	p[a] = 0

for i in range(n+1):
	if i == 0 and p[i] == 0:
		ans = 0
		break
	elif i > 1:
		if p[i] == 0 and p[i-1] == 0:
			ans = 0
			break
		elif p[i] > 0:
			ans = p[i-1] + p[i-2]
			p[i] = ans

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

Submission status: Accepted

Solution code:
nm=list(map(int,input().split()))
stair=[1]*(nm[0]+1)
for i in range(nm[1]):
    stair[int(input())]=0

i=0#現在地
b1=1#現在地までの行き方
b2=0#現在地のひとつ前までの行き方
while i <nm[0]:
    if stair[i+1]==1:
        i+=1
        b1+=b2
        b2=b1-b2
    elif stair[i+1]==0 and stair[i+2]==1:
        i+=2
        b2=0
    else:
        i=nm[0]
        b1=0
print(b1%(10**9+7))

Submission status: Accepted

Solution code:
N, M, *A = map(int, open(0).read().split())
MOD = 10**9 + 7
F = [1]*(N+1)
for j in A:
    F[j-1] = 0
 
a = 1; b = 0
for i in range(N):
    if not F[i]:    #F[i] == 0
        a, b = 0, a
    else:
        a, b = ((a+b) % MOD), a
print(a)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc129/submissions/5841482 を参考 
N,M = map(int, input().split())
A = [int(input()) for _ in range(M)]
MOD = 10**9 + 7
F = [1]*(N+1)
for j in A:
    F[j-1] = 0
 
a = 1; b = 0
for i in range(N):
    if not F[i]:    #F[i] == 0
        a, b = 0, a
    else:
        a, b = ((a+b) % MOD), a
print(a)

Submission status: Accepted

Solution code:
Mod = 10**9+7
N,M = map(int, input().split())
a = [int(input()) for _ in range(M)]
b = [1]*(N+1)
for j in a:
    b[j] = 0
for i in range(1,N+1):
    if b[i] == 0:
        continue
    if i == 1:
        b[1] = 1
        continue
    b[i] = b[i-1]+b[i-2]
    if b[i] >= Mod:
        b[i] %= Mod
print(b[N])

Submission status: Accepted

Solution code:
z=list(map(int,input().split()))
n,m,b,c=z[0],z[1],[1],0
a=[int(input()) for i in range(m)]
if len(a)>=1:
    if a[0]==1:
        b.append(0)
        c=1
    else:
        b.append(1)
        c=0
else:
    b.append(1)
for i in range(n-1):
    if c<len(a):
        if i+2==a[c]:
            b.append(0)
            c+=1
        else:
            b.append(b[i]+b[i+1])
    else:
        b.append(b[i]+b[i+1])
print(b[-1]%1000000007)

Submission status: Accepted

Solution code:
#フィボナッチ数列か…
#c問題も解けないのか…
#典型問題なんだろうな
#踏めない段の分は除いて考えれば良い
n,m=input().split()
n,m=int(n),int(m)
ax=[1]*(n+1)
for i in range(m):
    ax[int(input())]=0
bx=[1,1]
for i in range(2,n+1):
    if ax[i-1]==1:
        f1=bx[i-1]
    else:
        f1=0
    if ax[i-2]==1:
        f2=bx[i-2]
    else:
        f2=0
    bx.append((f1+f2)%(10**9+7))

print(bx[n])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
state = [1] * (n+1)

for _ in range(m):
  state[int(input())] = 0
  
f = [1, 1]

for i in range(2, n+1):
  f_nm1 = f[i-1] if state[i-1]==1 else 0
  f_nm2 = f[i-2] if state[i-2]==1 else 0
  f.append(f_nm1 + f_nm2)

print(f[-1]%1000000007)

Submission status: Accepted

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

Submission status: Accepted

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

ste = [0] *(n+1)
ste[0] = 1
if 1 not in aa:
    ste[1] = 1
else:
    ste[1] = 0
for i in range(2,n+1):
    if i in aa:
        continue
    ste[i] = (ste[i-1]+ste[i-2])%mod

print(ste[n])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:

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

def fib(x):
    a = 1
    b = 1
    if x == 0:
        return 0
    elif x == 1:
        return a
    elif x == 2:
        return b
    else:
        for i in range(x-2):
            c = a + b
            a = b
            b = c
        return b 

before_a=1
output=1
if M>=1:
    output = fib(A[0])
    for i in range(M-1):
        output *= fib(A[i+1]-A[i]-1)
    output *= fib(N-A[M-1])
else:
    output *= fib(N+1)
print(output%1000000007)

Submission status: Accepted

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

#listの中をinで探すのはくっそ遅い
if 1 in a:
    n[1] = 0

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

print(n[N])

Submission status: Accepted

Solution code:
def fib(x):
  a = 1
  b = 1
  if x == 0:
    return 0
  elif x == 1:
    return a
  elif x == 2:
    return b
  else:
    for i in range(x-2):
      c = a + b
      a = b
      b = c
    return b 
n,m = map(int, input().split())
A = [int(input()) for i in range(m)]
if m >= 1:
  c = fib(A[0])
  for i in range(m-1):
    c *= fib(A[i+1] - A[i] - 1)
  c*= fib(n - A[m-1])
  print(c%1000000007)
else:
  print(fib(n+1)%1000000007)

Submission status: Accepted

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

dp = [-1]*(N+1)
for i in a:
    dp[i] = 0

dp[0] = 1
mod = 1000000007

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

print(dp[-1] % mod)

Submission status: Accepted

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

dp = [-1]*(N+1)
for i in a:
    dp[i] = 0

dp[0] = 1
mod = 1000000007

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

print(dp[-1])

Submission status: Accepted

Solution code:
import sys
n,m=map(int,input().split())
if m > 0:
  a = set(map(int, sys.stdin))
else:
  a = set()

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

print(fibo[-1])

Submission status: Accepted

Solution code:
import sys
mod = 10**9+7

def main():
    n, m = map(int, input().split(' '))
    if m > 0:
        aaa = set(map(int, sys.stdin))
    else:
        aaa = set()
 
    dp = [0] * (n+1)
    dp[0] = 1
    dp[1] = 1 if 1 not in aaa else 0
    
    for i in range(2, n+1):
        if i in aaa:
            continue
        dp[i] = (dp[i-1]+dp[i-2])%mod
 
    print(dp[n])
 
main()

Submission status: Accepted

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

flag = 0
for i in range(m-1):
    if a[i+1] - a[i] == 0:
        flag = 1
        print(0)
        break

if flag == 0:
    b = [1]
    if len(a) != 0 and a[0] == 1:
        b.append(0)
        a.pop(0)
    else:
        b.append(1)
    for i in range(2, n+1):
        if len(a) != 0 and a[0] == i:
            b.append(0)
            a.pop(0)
        else:
            b.append((b[i-1]+b[i-2])%1000000007)

    print(b[-1])

Submission status: Accepted

Solution code:
NUM = int(10**9 + 7)

n, m = map(int, input().split())
nums = [int(input()) for _ in range(m)]

if m > 0:
    split = [[0, nums[0] - 1]]
    for i in range(1, m):
        split.append([nums[i - 1] + 1, nums[i] - 1])
    split.append([nums[-1] + 1, n])
else:
    split = [[0, n]]

n_steps = [h - l for l, h in split]

counts = [1, 1]
for _ in range(max(n_steps) - 1):
    c = counts[-1] + counts[-2]
    counts.append(c)

if min(n_steps) < 0:
    print(0)
else:
    res = 1
    for s in n_steps:
        res *= counts[s]
        res %= NUM
    print(res)

Submission status: Accepted

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

dp = [1, 2]
A = [int(input()) for _ in range(M)]
if M != 0:
    if M >= 2 and A[0] == 1 and A[1] == 2:
        dp = [0, 0]
    elif A[0] == 1:
        dp = [0, 1]
    elif A[0] == 2:
        dp = [1, 0]
else:
    A = [0]

MOD = 1000000007

if N == 1:
    print (1)
elif N == 2:
    print (dp[-1])
else:
    cnt = 0
    for n in range(2, N):
        while(cnt < M - 1 and A[cnt] < n + 1):
            cnt += 1
        if A[cnt] == n + 1:
            dp[0] = dp[1]
            dp[1] = 0
        else:
            new_val = (max(dp[0], 0) + max(dp[1], 0)) % MOD
            dp[0] = dp[1]
            dp[1] = new_val

    print (dp[-1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
import numpy as np
N, M = map(int, input().split())

MOD = 1000000007
dp = np.zeros(N, dtype = int)
if M != 0:
    A = np.array([int(input()) for _ in range(M)], dtype = int)
    dp[A - 1] = -1


if dp[0] == -1 and dp[1] == -1:
    pass
else:
    if dp[0] == -1:
        dp[1] = 1
    elif N >= 2 and dp[1] == -1:
        dp[0] = 1
    elif N >= 2:
        dp[0] = 1
        dp[1] = 2
    else:
        dp[0] = 1


if N >= 3:
    for n in range(2, N):
        if dp[n] != -1:
            dp[n] = (max(dp[n-1], 0) + max(dp[n-2], 0)) % MOD

print (dp[-1])

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
lst = []
for i in range(m):
    lst.append(int(input()))
safe = [True] * (n+2)
for a in lst:
    safe[a+1] = False #壊れた床をリスト化

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

Submission status: Accepted

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

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

traps = {}
for i in range(m):
    t = int(input())
    traps[t] = 1

mem = {}

def f(k):
    if k in mem:
        return mem[k]

    if k >= n:
        return 0
    if k == n - 1:
        return 1
    if k == n - 2:
        if n - 1 in traps:
            return 1
        else:
            return 2

    res = 0
    if k + 1 not in traps:
        res += f(k + 1)
    if k + 2 not in traps:
        res += f(k + 2)
    mem[k] = res

    return res % MOD

print(f(0))

Submission status: Accepted

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

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,m = LI()
a = [I() for _ in range(m)]
dp = [0]*(n+1)
dp[0],dp[1] = 1,1
for i in a:
    dp[i] = -1
for i in range(2,n+1):
    if dp[i] < 0:
        continue
    if dp[i-1] < 0:
        dp[i] = dp[i-2]
        continue
    if dp[i-2] < 0:
        dp[i] = dp[i-1]
        continue
    dp[i] = (dp[i-1] + dp[i-2]) % mod
if dp[-1] == -1:
    print(0)
else:
    print(dp[-1])