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: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
def lmi(): return list(map(int, input().split()))

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

l = [0] * (n+1)
l[0] = 1
for i in range(n+1):
     if i not in a:

         if i == 1:
            l[i] = 1
         elif i >= 2:
            l[i] = l[i-1] + l[i-2]
            l[i] %= 1000000007


#print(l)
print(l[n] % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
broken = []
for i in range(M):
  broken.append(int(input()))
a1, a2, a3 = 1, 0, 0
for i in range(1, N+1):
  a3 = a2
  a2 = a1
  if i in broken:
    a1 = 0
  else:
    a1 = (a2 + a3) % 1000000007
print(a1)

Submission status: Time Limit Exceeded

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

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

step_route = [0] * (N+1)

step_route[0] = 1
step_route[1] = 1

for j in range(N+1):  
  if j in a_list:
    step_route[j] = 0
    continue
  if j >= 2:
    step_route[j] = step_route[j-1] + step_route[j-2]
    if step_route[j] == 0:
      break
    
print(step_route[N] % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)

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

n,m=intinput()
a=[]
memo={x:0 for x in range(n+4)}
memo[0]=1
mod = 10**9+7
for i in range(m):
    a.append(int(input()))
for i in range(n):
    if i+1 not in a:
        memo[i+1]=(memo[i+1]+memo[i])%mod
    if i+2 not in a:
        memo[i+2]=(memo[i+2]+memo[i])%mod
print(memo[n])

Submission status: Time Limit Exceeded

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

a_list = []
former_a = -1
imp = False

for _ in range(M):
    a = int(input())
    a_list.append(a)
    if former_a < 0:
        former_a = a
    else:
        if a - former_a == 1:
            imp = True
            break

if imp:
    print(0)
else:
    a_list.extend([-1]*N)

    ans_list = [0, 1]
    one, two = 1, 0
    for i in range(1, N+1, 1):

        if i == a_list[0]:
            a_list.pop(0)
            ans_list.append(0)
            two = one
            one = 0
        else:
            ans_list.append(one + two)
            two_ = two
            two = one
            one = one + two_
    print(ans_list[-1] % 1000000007)

Submission status: Time Limit Exceeded

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

memo = [-1 for _ in range(n)]

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

print(memo[-1])

Submission status: Time Limit Exceeded

Solution code:
def solve():
    N, M = map(int, input().split())
    A = [int(input()) for _ in range(M)]
    mm = 10 ** 9 + 7
    dp = [0] * (N + 1)
    dp[0] = 1  # 0段目に行くパターンは1とする
    dp[1] = 0 if 1 in A else 1  # 1段目の行き方を設定
    for i in range(2, N + 1):
        if i in A:
            continue
        dp[i] = dp[i - 1] + dp[i - 2]
    print(dp[N] % mm)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9+7
import sys
sys.setrecursionlimit(1000000)

N,M = [int(x) for x in input().split()]
a = [int(input()) for _ in range(M)]
di = {}
for i in a:
    di[i] = 1
dp = [0 for _ in range(N+1)]
dp[0] = 1

def dfs(num):
    if(num<0):
        return 0
    if(num==0):
        return 1
    if(num in di):
        return 0
    if(dp[num]==0):
        dp[num] = (dfs(num-1)+dfs(num-2))%mod
    return dp[num]

print(dfs(N))

Submission status: Time Limit Exceeded

Solution code:
mod=1000000007
n,m=map(int,input().split())
a=[]
for i in range(m):
    a.append(int(input()))
f=0
for i in range(len(a)):
    if a[i]+1 in a:
        f=1
        break
        
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:
        dp[i]=0
    else:
        dp[i]=(dp[i-1]+dp[i-2])%mod

if f==1:
    print(0)
else:
    print(dp[n]%mod)

Submission status: Time Limit Exceeded

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

counts = [0] * (N + 1)
for i in range(N + 1):
    if i == 0:
        counts[i] = 1
    elif i == 1:
        if i not in A:
            counts[i] = 1
    else:
        for j in [i - 2, i - 1]:
            if j not in A and i not in A:
                counts[i] += counts[j]
                counts[i] %= 1000000007

print(counts[N])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(200000)
input = sys.stdin.readline

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

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

Submission status: Time Limit Exceeded

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

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

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

step[0] = 1
if 1 not in A:
    step[1] = 1

if len(A) != 0 and A[0] == 1:
    A = A[1:]

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


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

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
num=[0]*(N+1)
num[0]=1
num[1]=1

A=[]
for i in range(M):
    A.append(int(input()))

P=10**9+7

if 1 in A:
    num[1]=0

if N>=2:
    for i in range(2,N+1):
        num[i]=(num[i-1]+num[i-2])%P
        if i in A:
            num[i]=0

print(num[N])

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
B = [0] * (N + 1)
B[0] = 1
if 1 not in A:
    B[1] = 1
else:
    B[1] = 0

for i in range(2, N + 1):
    if i != 2 and i - 1 in A and i - 2 in A:
        print(0)
        exit()
    elif i - 2 in A:
        B[i] = B[i - 1]
    elif i - 1 in A:
        B[i] = B[i - 2]
    else:
        B[i] = B[i - 1] + B[i - 2]
mod = 10**9 + 7
print(B[N] % mod)

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9+7
import sys
sys.setrecursionlimit(1000000)

N,M = [int(x) for x in input().split()]
a = [int(input()) for _ in range(M)]
dp = [0 for _ in range(N+1)]
dp[0] = 1

def dfs(num):
    if(num<0):
        return 0
    if(num==0):
        return 1
    if(num in a):
        return 0
    if(dp[num]==0):
        dp[num] = (dfs(num-1)+dfs(num-2))%mod
    return dp[num]

print(dfs(N))

Submission status: Time Limit Exceeded

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

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

    return dp[N+1]


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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
A = list(int(input()) for _ in range(M))
P = 10**9 + 7

dp = [0] * (N+1)
dp[0] = 1
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]
    else:
        dp[i] = 0
print(dp[N]%P)

Submission status: Time Limit Exceeded

Solution code:
mod=1000000007
n,m=map(int,input().split())
a=[]
for i in range(m):
    a.append(int(input()))
f=0
for i in range(len(a)):
    if a[i]+1 in a or a[i]-1 in a:
        f=1
        
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:
        dp[i]=0
    else:
        dp[i]=(dp[i-1]+dp[i-2])%mod

if f==1:
    print(0)
else:
    print(dp[n]%mod)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

a_list = []
former_a = -1
imp = False

for _ in range(M):
    
    a_list.append(int(input()))
    if former_a < 0:
        former_a = a_list[-1]
    else:
        if a_list[-1] - former_a == 1:
            imp = True
            break

if imp:
    print(0)
else:
    a_list.extend([-1]*N)

    ans_list = [0, 1]
    for i in range(1, N+1, 1):

        if i == a_list[0]:
            a_list.pop(0)
            ans_list.append(0)
            pass
        else:
            ans_list.append(ans_list[-1] + ans_list[-2])
    print(ans_list[-1] % 1000000007)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

l=[0]*(N+1)
l[0]=1
# print(l)

for i in range(N):
    c=l[i]
    # print(c)
    if i not in a:
        if i+1 not in a:
            l[i+1]+=c
        if i<=N-2 and i+2 not in a:
            l[i+2]+=c

print(l[N]%1000000007)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

step_route = [0] * (N+1)

step_route[0] = 1
step_route[1] = 1

for j in range(N+1):  
  if j >= 2:
    step_route[j] = step_route[j-1] + step_route[j-2]
  if j in a_list:
    step_route[j] = 0
    
print(step_route[N] % 1000000007)

Submission status: Time Limit Exceeded

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

mod = 10**9+7

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

print(dp[0])

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

a_list = []
former_a = -1

for _ in range(M):
    
    a_list.append(int(input()))
    if former_a < 0:
        former_a = a_list[-1]
    else:
        if a_list[-1] - former_a == 1:
            print(0)
            sys.exit()
            
a_list.extend([-1]*N)

ans_list = [0, 1]
for i in range(1, N+1, 1):
    
    if i == a_list[0]:
        a_list.pop(0)
        ans_list.append(0)
        pass
    else:
        ans_list.append(ans_list[-1] + ans_list[-2])
print(ans_list[-1] % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
list1=[int(input()) for i in range(M)]
list2=[1]
if 1 in list1:
    list2.append(0)
else:
    list2.append(1)
for i in range(N-1):
    if i+2 in list1:
        list2.append(0)
    else:
        list2.append(list2[i]+list2[i+1])
print(list2[N]%1000000007)

Submission status: Time Limit Exceeded

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

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

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

step[0] = 1
if 1 not in A:
    step[1] = 1

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


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

Submission status: Time Limit Exceeded

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

dp = [0, 1]

for i in range(1, N + 1):
    if i in a:
        dp.append(0)
        continue
    dp.append(dp[i - 1] + dp[i])

print(dp[N + 1] % 1000000007)

Submission status: Time Limit Exceeded

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

dp = [0, 1]

for i in range(N):
    if i+1 in a:
        dp.append(0)
    else:
        dp.append(dp[i]+dp[i+1])

print(dp[-1] % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
import sys
N,M = map(int, input().strip().split(' '))
broken = [int(line.strip()) for line in sys.stdin]
p = [0]*(N+2)
p[0] = 1
for i in range(N):
  # 今i段目にいる
  if i in broken:
    continue
  p[i+1] += p[i]
  p[i+2] += p[i]
print(p[N]%1000000007)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
def lmi(): return list(map(int, input().split()))

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

l = [0] * (n+1)
l[0] = 1
for i in range(n+1):
     if i not in a:

         if i == 1:
            l[i] = 1
         elif i >= 2:
            l[i] = l[i-1] + l[i-2]


#print(l)
print(l[n]%1000000007)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

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

for i in range(1,N+1):
    if i>=2:
        total[i] += total[i-2]
    if i>=1:
        total[i] += total[i-1]
    if i in A:
        total[i] = 0
    total[i] = total[i]%1000000007

print(int(total[N]))

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9+7
import sys
sys.setrecursionlimit(1000000)

N,M = [int(x) for x in input().split()]
a = [int(input()) for _ in range(M)]
dp = [0 for _ in range(N+1)]
dp[0] = 1
for i in range(N+1):
    if(i in a):
        continue
    if(i<N-1):
        if(i+2 not in a):
            dp[i+2]+=dp[i]
            dp[i+2]%=mod
    if(i<N):
        if(i+1 not in a):
            dp[i+1]+=dp[i]
            dp[i+1]%=mod
print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
MOD = int(1e9 + 7)

N,M = list(map(int, input().split()))
A = []
for i in range(M):
  A.append(int(input()))
  
for i in range(M-1):
  if A[i+1] - A[i] == 1:
    print(0)
    exit(0)
    
dp = [0] * (N+1)
dp[0] = 1
for i in range(N):
  if i-1 < 0 or i-1 in A:
    dp[i+1] = dp[i] % MOD
  elif i in A:
    dp[i+1] = dp[i-1] % MOD
  else:
    dp[i+1] = (dp[i] + dp[i-1]) % MOD
    
print(dp[N])

Submission status: Time Limit Exceeded

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

dp = [1]
if 1 in displace:
    dp.append(0)
else:
    dp.append(1)

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

Submission status: Time Limit Exceeded

Solution code:
Q = 1000000007
n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
dp = {
    0: 1,
    1: 0 if 1 in a else 1
}

for k in range(2, n + 1):
    dp[k] = (0 if k in a else dp[k - 1] + dp[k - 2]) % Q


print(dp[n])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

b = [(-1 if x in a else 0) for x in range(N+1)]

b[0] = 1

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

print(b[N])

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9+7

N,M = [int(x) for x in input().split()]
a = [int(input()) for _ in range(M)]
dp = [0 for _ in range(N+1)]
dp[0] = 1
for i in range(N+1):
    if(i in a):
        continue
    if(i<N-1):
        if(i+2 not in a):
            dp[i+2]+=dp[i]
    if(i<N):
        if(i+1 not in a):
            dp[i+1]+=dp[i]
print(dp[-1]%mod)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def getN():
    return int(input())

def getMN():
    return list(map(int, input().split()))

def getlist():
    return list(map(int, input().split()))

MOD = 1000000007
n,m = getlist()

broken = []
for i in range(m):
    broken.append(getN())

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

print(dp[n])

Submission status: Accepted

Solution code:
#96 C - Typical Stairs
N,M = map(int,input().split())
A = [int(input()) for _ in range(M)]
A = set(A)
MOD = 1000000007

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

Submission status: Accepted

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

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

#初期化
dp=[0]*(N+1)
dp[0] = 1
if A[1] == 0:
  dp[1] = 1

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

Submission status: Accepted

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

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

for x in a:
    is_broken[x] = 1

for i in range(n):
    for j in range(i+1, min(n, i+2) + 1):
        if not is_broken[j]:
            dp[j] += dp[i]
            dp[j] %= MOD

print(dp[n])

Submission status: Accepted

Solution code:
def abc129c():
    n, m = map(int, input().split())
    set_a = set()
    for _ in range(m):
        set_a.add(int(input()))
    dp = [0] * (n+1)
    dp[0] = 1
    for i in range(1, n+1):
        if i in set_a: continue
        dp[i] = dp[i-1]
        if i > 1:
            dp[i] += dp[i-2]
    print(dp[n]%1000000007)
abc129c()

Submission status: Accepted

Solution code:
import math
from math import gcd,pi,sqrt
INF = float("inf")
MOD = 10**9 + 7

import sys
sys.setrecursionlimit(10**6)
import itertools
import bisect
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]


def main():
    n,m = i_map()
    a = set([i_input() for i in range(m)])

    dp = [INF] * (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  not in a:
            dp[i] = dp[i-1] + dp[i-2]
        else:
            dp[i] = 0
    print(dp[n]%MOD)




if __name__=="__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:

url = "https://atcoder.jp//contests/abc129/tasks/abc129_c"

def main():
    n, m = list(map(int, input().split()))
    isbreak = [False] * (n+1)
    for _ in range(m):
        isbreak[int(input())] = True

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




if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().strip()
n, m = [int(x) for x in input().split()]
can = [True for i in range(n + 1)]
for i in range(m):
    ai = int(input())
    can[ai] = False
C = [0 for i in range(n + 1)]
for i in range(n + 1):
    if i == 0:
        C[i] = 1
    else:
        C[i] = sum(C[j] if j >= 0 and can[j] else 0 for j in (i - 1, i - 2)) % (10**9 + 7)
print(C[n])

Submission status: Accepted

Solution code:
#!/usr/bin/python3
import sys
input = lambda: sys.stdin.readline().strip()
n, m = [int(x) for x in input().split()]
can = [True for i in range(n + 1)]
for i in range(m):
    ai = int(input())
    can[ai] = False
C = [0 for i in range(n + 1)]
for i in range(n + 1):
    if i == 0:
        C[i] = 1
    else:
        C[i] = sum(C[j] if j >= 0 and can[j] else 0 for j in (i - 1, i - 2)) % (10**9 + 7)
print(C[n])

Submission status: Accepted

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

    pos = 0
    ans = 1

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

    for _ in range(M):

        a = int(input())

        if a == pos:
            ans = 0
            pos = N
            break
        elif a == pos + 1:
            pos = a + 1
        else:
            ans *= fib[(a - 1 - pos)]
            pos = a + 1

    if pos + 1 < N:
        ans *= fib[(N - pos)]

    print(ans % 1_000_000_007)



if __name__ == "__main__":
    main()

Submission status: Accepted

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

    pos = 0
    ans = 1

    fib = [1 for _ in range(100002)]
    for i in range(2, 100002):
        fib[i] = fib[i-1] + fib[i-2]

    for _ in range(M):

        a = int(input())
        if a == pos:
            ans = 0
            pos = N
            break
        elif a == pos + 1:
            pos = a + 1
        else:
            ans *= fib[(a - 1 - pos)]
            pos = a + 1

    if pos + 1 < N:
        ans *= fib[(N - pos)]

    print(ans % 1_000_000_007)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
a=[0]*(N+1)
INF=10**100
NUM=7+10**9
dp=[0]*(N+1)

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

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

print(dp[N])

Submission status: Accepted

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

A = set([int(input()) for _ in range(M)])

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


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

print(lis[N])

Submission status: Accepted

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

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

print(dp[n] % 1000000007)

Submission status: Accepted

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

for i in range(N+1):
  if dp[i] == -1:
    continue
  if i+1 <= N and dp[i+1] != -1:
    dp[i+1] = (dp[i+1] + dp[i]) % MOD
  if i+2 <= N and dp[i+2] != -1:
    dp[i+2] = (dp[i+2] + dp[i]) % MOD
print(dp[N])

Submission status: Accepted

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

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

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

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

    if i+1<=n and dp[i+1]!=-1:
        dp[i+1]=(dp[i+1]+dp[i])%MOD
    if i+2<=n and dp[i+2]!=-1:
        dp[i+2]=(dp[i+2]+dp[i])%MOD

print(dp[-1])

Submission status: Accepted

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

dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1 if not broken[1] else 0
MOD = 10 ** 9 + 7

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

print(dp[n])

Submission status: Accepted

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

dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1 if not broken[1] else 0
MOD = 10 ** 9 + 7

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

print(dp[n])

Submission status: Accepted

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

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

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

print(dp[n])

Submission status: Accepted

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

def main(n,m,a):
    dp = [0 for i in range(n+1)]
    mod = 10**9 + 7
    dp[0] = 1
    it1 = iter(a)
    it2 = iter(a)
    d = dict(zip(it1,it2))
    for i in range(1,n+1):
        if i in d:
            continue
        if i==1:
            dp[1] = dp[0]
        else:
            dp[i] = (dp[i-1] + dp[i-2]) % mod

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

if __name__=="__main__":
    n,m,a = getval()
    main(n,m,a)

Submission status: Accepted

Solution code:
#import math
#import itertools
#import numpy as np
#from collections import deque
# sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
#INF = 10 ** 9
#PI = 3.14159265358979323846

INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))

def do():
    n,m=INTM()
    b_sts=[False]*n
    for i in range(m):
        b=INT()
        b-=1
        b_sts[b]=True
        
    step=[0]*(n+2)
    step[1]=1
    for i in range(n):
        if b_sts[i]:
            continue
        else:
            step[i+2]=(step[i+1]+step[i])%MOD
    print(step[-1]%MOD)

if __name__=='__main__':
    do()

Submission status: Accepted

Solution code:
# input here
_INPUT = """\
10 2
4
5
"""
"""
K = int(input())
H, W, K = map(int, input().split())
a = list(map(int, input().split()))
xy = [list(map(int, input().split())) for i in range(N)]
p = tuple(map(int,input().split()))
"""
def main():
    N, M = map(int, input().split())
    a = set([int(input()) for i in range(M)])
    inf = 10**9+7

    #動的計画法問題
    dp = [0] * (N+1)
    dp[0] = 1
    if 1 not in a:
        dp[1] = 1
    else:
        dp[1] = 0

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

    print(dp[N]) 

     
if __name__ == '__main__':
    import io
    import sys
    import math
    import itertools
    from collections import deque

    # sys.stdin = io.StringIO(_INPUT)
    main()

Submission status: Accepted

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

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

print(dp[N])

Submission status: Accepted

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

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

    print(dp[-1] % mod)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

    print(dp[-1] % mod)


if __name__ == "__main__":
    main()