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: Runtime Error

Solution code:
N, M = [int(_) for _ in input().split()]
A = [int(input()) for i in range(M)]
isBroken = [False] * (N + 1)
for i in A:
    isBroken[i] = True


def solve():

    # It's impossible
    if M > 0:
        temp = A[0]
        for a in A[1:]:
            if a - 1 == temp:
                return 0
            temp = a

    # We can
    memo = [0] * (N + 1)

    def rec(i):
        if i == 0:
            return 1
        if i < 0:
            return 0
        if isBroken[i]:
            return 0
        if memo[i] == 0:
            count1 = rec(i - 1) % 1000000007
            count2 = rec(i - 2) % 1000000007
            memo[i] = (count1 + count2) % 1000000007
            # print(f"memo[{i}] = {count1} + {count2} -> {memo[i]}")
        return memo[i]
    return rec(N)


print(solve())

Submission status: Runtime Error

Solution code:
N, M = [int(_) for _ in input().split()]
A = [int(input()) for i in range(M)]
isBroken = [False] * (N + 1)
for i in A:
    isBroken[i] = True


def solve():

    # It's impossible
    temp = A[0]
    for a in A[1:]:
        if a - 1 == temp:
            return 0
        temp = a

    return 1

    # We can
    memo = [0] * (N + 1)

    def rec(i):
        if i == 0:
            return 1
        if i < 0:
            return 0
        if isBroken[i]:
            return 0
        if memo[i] == 0:
            count1 = rec(i - 1) % 1000000007
            count2 = rec(i - 2) % 1000000007
            memo[i] = (count1 + count2) % 1000000007
            # print(f"memo[{i}] = {count1} + {count2} -> {memo[i]}")
        return memo[i]
    return rec(N)


print(solve())

Submission status: Runtime Error

Solution code:
import sys

N, M = [int(_) for _ in input().split()]
A = [int(input()) for i in range(M)]
isBroken = [False] * (N + 1)
for i in A:
    isBroken[i] = True


def solve():

    # It's impossible
    temp = A[0]
    for a in A[1:]:
        if a - 1 == temp:
            return 0
        temp = a

    # We can
    memo = [0] * (N + 1)
    print("?")
    sys.exit()

    def rec(i):
        if i == 0:
            return 1
        if i < 0:
            return 0
        if isBroken[i]:
            return 0
        if memo[i] == 0:
            count1 = rec(i - 1) % 1000000007
            count2 = rec(i - 2) % 1000000007
            memo[i] = (count1 + count2) % 1000000007
            # print(f"memo[{i}] = {count1} + {count2} -> {memo[i]}")
        return memo[i]
    return rec(N)


print(solve())

Submission status: Runtime Error

Solution code:
N, M = [int(_) for _ in input().split()]
A = [int(input()) for i in range(M)]
isBroken = [False] * (N + 1)
for i in A:
    isBroken[i] = True


def solve():

    # It's impossible
    temp = A[0]
    for a in A[1:]:
        if a - 1 == temp:
            return 0
        temp = a

    # We can
    memo = [0] * (N + 1)

    def rec(i):
        if i == 0:
            return 1
        if i < 0:
            return 0
        if isBroken[i]:
            return 0
        if memo[i] == 0:
            count1 = rec(i - 1) % 1000000007
            count2 = rec(i - 2) % 1000000007
            memo[i] = (count1 + count2) % 1000000007
            # print(f"memo[{i}] = {count1} + {count2} -> {memo[i]}")
        return memo[i]
    return rec(N)


print(solve())

Submission status: Runtime Error

Solution code:
N, M = [int(_) for _ in input().split()]
A = [int(input()) for i in range(M)]
isBroken = [False] * (N + 1)
for i in A:
    isBroken[i] = True


def solve():

    # It's impossible
    temp = A[0]
    for a in A[1:]:
        if a - 1 == temp:
            return "0"
        temp = a

    # We can
    memo = [0] * (N + 1)

    def rec(i):
        if i == 0:
            return 1
        if i < 0:
            return 0
        if isBroken[i]:
            return 0
        if memo[i] == 0:
            count1 = rec(i - 1) % 1000000007
            count2 = rec(i - 2) % 1000000007
            memo[i] = (count1 + count2) % 1000000007
            # print(f"memo[{i}] = {count1} + {count2} -> {memo[i]}")
        return memo[i]
    return rec(N)


print(solve())

Submission status: Runtime Error

Solution code:
N, M = [int(_) for _ in input().split()]
Brokens = [int(input()) for i in range(M)]
isBroken = [False] * (N + 1)
for i in Brokens:
    isBroken[i] = True


def solve():

    # It's impossible
    temp = Brokens[0]
    for a in Brokens[1:]:
        if a - 1 == temp:
            return "0"
        temp = a

    # We can
    memo = [0] * (N + 1)

    def rec(i):
        if i == 0:
            return 1
        if i < 0:
            return 0
        if isBroken[i]:
            return 0
        if memo[i] == 0:
            count1 = rec(i - 1)
            count2 = rec(i - 2)
            memo[i] = (count1 + count2) % 1000000007
            # print(f"memo[{i}] = {count1} + {count2} -> {memo[i]}")
        return memo[i]
    return rec(N)


print(solve())

Submission status: Runtime Error

Solution code:
from more_itertools import windowed

print("")

Submission status: Runtime Error

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

import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

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

if m==0:
    cnt = 0
    steps = n
    for j in range(steps//2+1):
        if j == 0:
            cnt += 1
        else:
            seat = steps - j
            cnt += combinations_count(seat,j)
    print(cnt % (10**9+7))

l = [-1]+[int(input())]
for i in range(m-1):
    a = int(input())
    if a == l[-1]+1:
        print(0)
        exit()
    l.append(a)
l.append(n+1)
# print(l)

ans = 1
for i in range(m+1):
    cnt = 0
    steps = l[i+1] - l[i] -2
    if steps == 0:
        continue
    for j in range(steps//2+1):
        if j == 0:
            cnt += 1
        else:
            seat = steps - j
            cnt += combinations_count(seat,j)
    ans *= cnt

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

Submission status: Runtime Error

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

import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

n,m = map(int,input().split())
l = [-1]+[int(input())]
for i in range(m-1):
    a = int(input())
    if a == l[-1]+1:
        print(0)
        exit()
    l.append(a)
l.append(n+1)
# print(l)

ans = 1
for i in range(m+1):
    cnt = 0
    steps = l[i+1] - l[i] -2
    for j in range(steps//2+1):
        if j == 0:
            cnt += 1
        else:
            seat = steps - j
            cnt += combinations_count(seat,j)
    ans *= cnt

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
#動的計画法(DP)
#ブログ「けんちょんの競プロ精進記録」参考
#URL: https://drken1215.hatenablog.com/entry/2019/06/10/140000


N,M = map(int,input().split())
MOD = 1000000007
issafe = [True]*N # issafe[v]: v段目が壊れていないかどうか

for _ in range(M):
    i = int(input())
    issafe[i] = False # i 段目は壊れている

#DPテーブル
dp = [0]*(N+1)

#初期条件
dp[0] = 1
if issafe[1]:dp[1] = 1

#ループ
for n in range(2,N+1):
    if issafe[n-1]: dp[n] += dp[n-1]
    if issafe[n-2]: dp[n] += dp[n-2]
    dp[n] %= MOD

print(dp[N])

Submission status: Runtime Error

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

for i in range(n+1):
    if ln[i] ==0
        pass
    elif i == 0:
        ln[i] = 1
    elif i == 1:
        ln[i] = 1
    else:
        ln.append((ln[-1] + ln[-2]) % mod_1)
print(ln[-1])

Submission status: Runtime Error

Solution code:
#dp
n,m  = map(int,input().split())
ln = [-1 for i in range(n +1)]
mod_1 = 10**9 + 7
for i in range(m):
    ln[int(input())] = 0
line = []
for i in range(n+1):
    if ln[i] ==0
        pass
    elif i == 0:
        ln[i] = 1
    elif i == 1:
        ln[i] = 1
    else:
        line.append((line[-1] + line[-2]) % mod_1)
print(line[-1])

Submission status: Runtime Error

Solution code:
n,m = map(int, input().split())
A = [int(input()) for i in range(m)]
B = [A[i+1]- A[i] for i in range(m-1)]
B.insert(0,A[0]+1)
B.append(n+1-A[m-1])

M = max(A)

Fib = [0,1]
for i in range(2,M+10):
  Fib.append(Fib[i-2]+Fib[i-1])

ans = 1
for i in range(len(B)):
  ans = (ans * Fib[B[i]-1])%1000000007
  
print(ans)

Submission status: Runtime Error

Solution code:
n,m = map(int, input().split())
A = [int(input()) for i in range(m)]
B = [A[i+1]- A[i] for i in range(m-1)]
B.insert(0,A[0]+1)
B.append(n+1-A[m-1])

M = max(A)

def Fib(n):
  L = [0,1]
  for i in range(2,n+3):
    L.append(L[i-2]+L[i-1])
  return(L)

ans = 1
for i in range(len(B)):
  ans = ans * Fib(max(A))[B[i]-1]
  ans = ans % 1000000007
  
print(ans)

Submission status: Runtime Error

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

MOD = 10**9+7

dp = [0] * (N+1)
dp[1] = 0
dp[2] = 1
dp[3] = 2
for i in range(3, N+1):
    dp[i] = dp[i-1] + dp[i-2]

res = 1
bef = -1
for a in a_list:
    res *= dp[a-bef]
    res %= MOD
    bef = a

res *= dp[N-bef+1]
res %= MOD

print(res)

Submission status: Runtime Error

Solution code:
n, m = map(int,input().split())
li = [int(input()) for i in range(m)] #壊れている段
ans = [1] #0段目にいる通り
x = 0

for i in range(1,n+1): 
    y = li[x]
    if i == y: #その段が壊れていたら
        ans.append(0)
        x += 1
    else: #そうでなければ
        if i == 1:
            ans.append(1)
        else:
            ans.append((ans[i-2]+ans[i-1])%(10**9+7))

print(ans[-1])

Submission status: Runtime Error

Solution code:
n, m = map(int,input().split())
li = [int(input()) for i in range(m)] #壊れている段
ans = [1] #0段目にいる通り
x = 0

for i in range(1,n+1):
    if li[x] == i: #その段が壊れていたら
        ans.append(0)
        x += 1
    else: #そうでなければ
        if i == 1:
            ans.append(1)
        else:
            ans.append((ans[i-2]+ans[i-1])%(10**9+7))

print(ans[-1])

Submission status: Runtime Error

Solution code:
n, m = map(int,input().split())
li = [int(input()) for i in range(m)] #壊れている段
ans = [1] #0段目にいる通り

for i in range(1,n+1): 
    if li[0] == i:
        ans.append(0)
        li.pop(0)
    else:
        if i == 1:
            ans.append(1)
        else:
            ans.append((ans[i-2]+ans[i-1])%(10**9+7))

print(ans[-1])

Submission status: Runtime Error

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

nums = [0]*(N+1)
nums[0] = 1
if 1 not in a:
    nums[1] = 1
for i in range(2, N+1):
    print(nums)
    if not i in a:
      nums[i] = nums[i-1] + nums[i-2]

print(nums[N]%(1000000007))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
route = [int(x) for x in range(N)]
a = [int(input()) for _ in range(M)]
route = [item for index, item in enumerate(route) if index not in a]

nums = [0]*(N+1)
nums[0] = 1
if 1 not in a:
    nums[1] = 1
for i in range(2, N+1):
    print(nums)
    if not i in a:
      nums[i] = nums[i-1] + nums[i-2]

print(nums[N]%(1000000007))

Submission status: Runtime Error

Solution code:
li = list(map(int,input().split()))
n,m=li[0],li[1]
_list=[int(input()) for i in range(m)]
is_safe = [True] * (n+1)
for a in _list:
  is_safe[a] = False
DP=[1, 1] if is_safe[1] == True else [1, 0]
for i in range(n-1):
  if is_safe[i+2] == False:
    DP+= [0]
  else:
    DP += [DP[i] + DP[i+1]]
print(DP[n]%=1000000007 if DP[n] != 0 else 0)

Submission status: Runtime Error

Solution code:
li = list(map(int,input().split()))
n,m=li[0],li[1]
_list=[int(input()) for i in range(m)]
is_safe = [True] * (N)
for a in _list:
  is_safe[a] = False
DP=[1, 1] if is_safe[1] == True else [1, 0]
for i in range(n-1):
  if is_safe[i+2] == False:
    DP+= [0]
  else:
    DP += [DP[i] + DP[i+1]]
print(DP[n])

Submission status: Runtime Error

Solution code:
n,m = map(int, input().split())
A = [int(input()) for i in range(m)]
for i in range(m-1):
  if A[i]+1 == A[i+1]:
    print(0)
    exit()

ANS = [A[0]-0]
for i in range(m-1):
  ANS.append(A[i+1]-A[i]-1)
ANS.append(n-A[m-1])

Fib = [1,1,2]
for i in range(3,max(ANS)+4):
  Fib.append(Fib[i-1]+Fib[i-2])

ans = 1
for i in range(len(ANS)):
  ans = (ans * Fib[ANS[i]-1])%1000000007
  
print(ans)

Submission status: Runtime Error

Solution code:
n,m = map(int, input().split())
A = [int(input()) for i in range(m)]
for i in range(m-1):
  if A[i]+1 == A[i+1]:
    print(0)
    exit()

ANS = [A[0]-0]
for i in range(m-1):
  ANS.append(A[i+1]-A[i]-1)
ANS.append(n-A[m-1])

Fib = [1,1,2]
for i in range(3,max(ANS)+4):
  Fib.append(Fib[i-1]+Fib[i-2])

print(Fib)
print(ANS)
ans = 1
for i in range(len(ANS)):
  ans = (ans * Fib[ANS[i]-1])%1000000007
  
print(ans)

Submission status: Runtime Error

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

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

def ptn_num(x): # 'x'stepまでのパターン数
    if x == 1:
        return 1
    else:
        dp = [0] * (x+1) # DP枠_including step'0'
        cnt = 0
        if broken_steps[0] == 1: # in case, step'1' broken 
            dp[:2] = 1, 0
        else:
            dp[:2] = 1, 1 # Usually

        for i in range(2, x+1):
            if i in broken_steps: # 階段が壊れている場合...
                cnt += 1
                if cnt == 2:
                    print(0)
                    exit()
            else: # 階段が壊れてない場合...
                dp[i] = (dp[i-1] + dp[i-2]) % (10**9+7)
                cnt = 0
        
        print(dp[n])

ptn_num(n)

Submission status: Runtime Error

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

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

def ptn_num(x): # 'x'stepまでのパターン数
    if x == 1:
        return 1
    else:
        dp = [0] * (x+1) # DP枠_including step'0'
        cnt = 0
        if broken_steps[0] == 1: # in case, step'1' broken 
            dp[:2] = 1, 0
        else:
            dp[:2] = 1, 1 # Usually

        for i in range(2, x+1):
            if i in broken_steps: # 階段が壊れている場合...
                cnt += 1
                if cnt == 2:
                    print(0)
                    exit()
            else: # 階段が壊れてない場合...
                tmp = (dp[i-1] + dp[i-2]) % (10**9+7)
                dp[i] = tmp
                cnt = 0
        
        return dp[-1]

print(ptn_num(n))

Submission status: Runtime Error

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

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

def ptn_num(x): # 'x'stepまでのパターン数
    if x == 1:
        return 1
    else:
        dp = [0] * (x+1) # DP枠_including step'0'
        if broken_steps[0] == 1: # in case, step'1' broken 
            dp[:2] = 1, 0
        else:
            dp[:2] = 1, 1 # Usually

        for i in range(2, x+1):
            if i not in broken_steps: # 階段が壊れてない場合...
                tmp = (dp[i-1] + dp[i-2]) % (10**9+7)
                dp[i] = tmp
            # 壊れている場合は何もしない
        return dp[-1]

print(ptn_num(n))

Submission status: Runtime Error

Solution code:
# DP_動的計画法

import sys
input = sys.stdin.readline

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

def ptn_num(x): # 'x'stepまでのパターン数
    if x == 1:
        return 1
    else:
        dp = [0] * (x+1) # DP枠_including step'0'
        if broken_steps[0] == 1: # in case, step'1' broken 
            dp[:2] = 1, 0
        else:
            dp[:2] = 1, 1 # Usually

        for i in range(2, x+1):
            if i not in broken_steps: # 階段が壊れてない場合...
                dp[i] = dp[i-1] + dp[i-2]
            # 壊れている場合は何もしない
        return dp[-1]

print(ptn_num(n) % (10**9+7))

Submission status: Runtime Error

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

def main(arg):
    #print(arg)
    input = arg.split("\n")
    N,M = list(map(int, input.pop(0).split(" ")))
    print(input)
    #return
    A = list(map(int, input))
    #print(N)
    #print(M)
    print(A)

    #return

    if len(A) > 1:
        for i in range(1,M):
            if A[i] - A[i-1] == 1:
                print(0)
                return


    dp = [0] * (N-M+1)
    dp[0] = 1

    for i in range(1,N-M+1):
        dp1 = dp[i-1]%1000000007
        dp2 = 0
        if i >= 2:
            dp2 = (dp[i-2]*2)%1000000007
        
        print("i={0}: dp1={1}, dp2={2}".format(i, dp1, dp2))
        dp[i] = max(dp1, dp2)
        
    print(dp[N-M])

#main("6 1\n3")
main(input())

Submission status: Runtime Error

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

mod = 1_000_000_007

from collections import deque

d = deque()

for _ in range(m):
    d.append(int(input()))

old = 0
new = 1

for i in range(1, n+1):
    if len(d):
        if i != d[0]:
            old, new = new, (old+new) % mod
        else:
            old, new = new, 0
            d.popleft()
    else:
        old, new = new, (old+new) % mod



print(new)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
import math
def fibnatch(n):
  if n==0:
    return 1
  a=(pow(((1+math.sqrt(5))/2),n)-pow(((1-math.sqrt(5))/2),n))/math.sqrt(5)
  c=int(a)
  if n==1:
    return 1
  elif abs(c-a)>=abs(c-a+1):
    return (c+1)%1000000007
  else:
    return c%1000000007
L=list()
N,M=map(int,input().split())
a=1
for i in range(M):
  c=int(input())
  if i==0:
    L.append(c-a)
  else:
    L.append(c-a-1)
  a=c
if 0 in L[1:]:
  print(0)
  sys.exit()
L.append(N-c)
s=1
for i in range(len(L)):
  d=L[i]
  s=(s*fibnatch(d))%1000000007
print(s)

Submission status: Runtime Error

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

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

print(dp[N])

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**6)
N,M = map(int,input().split())
A = []
MOD = 10**9+7
memo = {}
for _ in range(M):
  memo[a] = 0

def step(cur):
  if cur in memo:
    return memo[cur]
  if cur == N:
    memo[cur] = 1
    return memo[cur]
  if cur > N:
    memo[cur] = 0
    return memo[cur]
 
  memo[cur] = (step(cur+1) + step(cur+2))%MOD
  return memo[cur]
 
print(step(0)%MOD)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
A = []
MOD = 10**9+7
memo = {}
for _ in range(M):
  A.append(int(input()))
def step(cur):
  global res
  if cur in memo:
    return memo[cur]
  if cur == N:
    memo[cur] = 1
    return memo[cur]
  if cur > N or cur in A:
    memo[cur] = 0
    return memo[cur]

  memo[cur] = (step(cur+1) + step(cur+2))%MOD
  return memo[cur]

res = 0
print(step(0)%MOD)

Submission status: Runtime Error

Solution code:
def main():
	n, m = map(int, input().split())
    a = set(int(input()) for i in range(m))
    mod = 1000000007
 
    # フィボナッチ数列を作る要領で行う
    d = [0] * (n+1)
    # 2回0が続く状況aに連番があったら即座に終了する
    cnt = 0 
    # d[0]とd[1]を規定。aに1が含まれていることを考慮して場合分けしておく
    d[0] = 1
    if 1 not in a:
        d[1] = 1
    # else:
    #     d[1] = 1
    # 階段番号は2~nまでを見る必要がある
    for i in range(2, n+1):
        if i in a:
            d[i] = 0
            cnt += 1
            if cnt == 2:
                print('0')
                exit()
        else:
            d[i] = (d[i-1] + d[i-2]) % mod
            cnt = 0
    # print(d)  
    ans = d[n]        
    print(ans)
 
if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

    # フィボナッチ数列を作る要領で行う
    d = [0] * (n+1)
    # 2回0が続く状況aに連番があったら即座に終了する
    cnt = 0 
    # d[0]とd[1]を規定。aに1が含まれていることを考慮して場合分けしておく
    d[0] = 1
    if 1 not in a:
        d[1] = 1
    # else:
    #     d[1] = 1
    # 階段番号は2~nまでを見る必要がある
    for i in range(2, n+1):
        if i in a:
            d[i] = 0
            cnt += 1
            if cnt == 2:
                print('0')
                exit()
        else:
            d[i] = (d[i-1] + d[i-2]) % mod
            cnt = 0
    # print(d)  
    ans = d[n]        
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
S=[0]*100010
S[1]=1
S[2]=1
for i in range(3,100010):
    S[i]=(S[i-2]+S[i-1])%1000000007

N,M=map(int,input().split())
T=[]
for i in range(M):
    T.append(int(input()))
    if i>=1:
        if T[i]-1==T[i-1]:
            print(0)
            exit()

U=[]
U.append(T[0])
for i in range(1,M):
    U.append(T[i]-T[i-1]-1)

U.append(N-T[M-1])

ans=1
for i in range(len(U)):
    ans=(ans*S[U[i]])%1000000007
print(ans)

Submission status: Runtime Error

Solution code:
S=[0]*100010
S[1]=1
S[2]=1
for i in range(3,102):
    S[i]=(S[i-2]+S[i-1])%1000000007

N,M=map(int,input().split())
T=[]
for i in range(M):
    T.append(int(input()))
    if i>=1:
        if T[i]-1==T[i-1]:
            print(0)
            exit()

U=[]
U.append(T[0])
for i in range(1,M):
    U.append(T[i]-T[i-1]-1)

U.append(N-T[M-1])

ans=1
for i in range(len(U)):
    ans=(ans*S[U[i]])%1000000007
print(ans)

Submission status: Runtime Error

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

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

if 2 in a:
    dp[2] = 0
    del a[0]
else:
    dp[2] = dp[1] + 1

if N == 1 or N == 2:
    print(dp[N])
    exit()

for i in range(1,N-1):
    if a == [] :
        dp[i+2] = (dp[i] + dp[i+1]) % r
    elif i+2 == a[0]:
        dp[i+2] = 0
        del a[0]
    else:
        dp[i+2] = (dp[i] + dp[i+1]) % r

print(dp[N])

Submission status: Runtime Error

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

if str(1) in a:
    dp[1] = 0
else:
    dp[1] = 1

if str(2) in a:
    dp[2] = 0
else:
    dp[2] = dp[1] + 1

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

print(dp[N])

Submission status: Runtime Error

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

a = []
for _ in range(m):
    tmp = int(input())
    a.append(tmp)
a = set(a)

dp = [0] * 10**5
dp[0] = 1

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

print(dp[n]%mod)

Submission status: Runtime Error

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

from itertools import product

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

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

def fib(n):
    if n == 0:
        return 0
    else:
        F = [ [0, 1],
              [1, 1] ]
        return mat2_pow(F, n-1)[1][1]
    
    
N, M = map(int, input().split())
A = [int(input()) for i in range(M)]

x=0
L=[]
for i in range(M):
    L += [A[i] - 1 - x]
    x = A[i] + 1
L += [N - x]
L = [Fib(i+2)%1000000007 for  i in L]

X=1
for i in range(len(L)):
    X *= L[i]
    X %= 1000000007 
print(X)

Submission status: Runtime Error

Solution code:
def Fib(n, memo={}):
    if n == 1:
        return 0
    elif n == 2:
        return 1
    elif n in memo:
        return memo[n]
    else:
        memo[n] = Fib(n-1, memo) + Fib(n-2, memo)
        return memo[n]
    
N, M = map(int, input().split())
A = [int(input()) for i in range(M)]

x=0
L=[]
for i in range(M):
    L += [A[i] - 1 - x]
    x = A[i] + 1
L += [N - x]
L = [Fib(i+2)%1000000007 for  i in L]

X=1
for i in range(len(L)):
    X *= L[i]
    X %= 1000000007 
print(X)

Submission status: Runtime Error

Solution code:
def Fib(n, memo={}):
    if n == 1:
        return 0
    elif n == 2:
        return 1
    elif n in memo:
        return memo[n]
    else:
        memo[n] = Fib(n-1, memo) + Fib(n-2, memo)
        return memo[n]
    
N, M = map(int, input().split())
A = [int(input()) for i in range(M)]

x=0
L=[]
for i in range(M):
    L += [A[i] - 1 - x]
    x = A[i] + 1
L += [N - x]
L = [Fib(i+2)%1000000007 for  i in L]

X=1
for i in range(len(L)):
    X=X*L[i]%1000000007
print(X)

Submission status: Runtime Error

Solution code:
def Fib(n, memo={}):
    if n == 1:
        return 0
    elif n == 2:
        return 1
    elif n in memo:
        return memo[n]
    else:
        memo[n] = Fib(n-1, memo) + Fib(n-2, memo)
        return memo[n]
    
N, M = map(int, input().split())
A = [int(input()) for i in range(M)]

x=0
L=[]
for i in range(M):
    L += [A[i] - 1 - x]
    x = A[i] + 1
L += [N - x]
L = [Fib(i+2) for  i in L]

X=1
for i in range(len(L)):
    X=X*L[i]%1000000007
print(X)

Submission status: Runtime Error

Solution code:
import sys

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

#階段上る数求める！x段目からy段目まで上るとき
climb_method=[0]*(n+1)
climb_method[0]=1
climb_method[1]=1
climb_method[2]=2
for i in range(n-2):
    climb_method[i+3]=climb_method[i+2]+climb_method[i+1]

if m==0:
    count=climb_method[n]
    print(count)
    sys.exit()

broken_list=[0]*m
count=0
a=int(input())
broken_list[0]=a
count+=climb_method[a-1]

for i in range(m-1):
    a=int(input())
    broken_list[i+1]=a
    distance=broken_list[i+1]-broken_list[i]
    if distance==1:
        count=0
        print(count)
        sys.exit()
        break
    else:
        count*=climb_method[distance-2]
        

distance=n-broken_list[m-1]
count*=climb_method[distance-1]    


print(count%1000000007)

Submission status: Runtime Error

Solution code:
import sys

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

#階段上る数求める！x段目からy段目まで上るとき
climb_method=[0]*(n+1)
climb_method[0]=1
climb_method[1]=1
climb_method[2]=2
for i in range(n-2):
    climb_method[i+3]=climb_method[i+2]+climb_method[i+1]

if m==0:
    count=climb_method[n]
    print(count)
    sys.exit()

broken_list=[0]*m
count=0
a=int(input())
broken_list[0]=a
count+=climb_method[a-1]

for i in range(m-1):
    a=int(input())
    broken_list[i+1]=a
    distance=broken_list[i+1]-broken_list[i]
    if distance==1:
        count=0
        print(count)
        sys.exit()
        break
    else:
        count*=climb_method[distance-2]
        

distance=n-broken_list[m-1]
if distance==1:
    count=0
    print(count)
    sys.exit()
count*=climb_method[distance-1]    


print(count%1000000007)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
N,A,B,C,D = list(map(int,input().split()))
A -= 1
B -= 1
C -= 1
D -= 1
S = input()
if S[C] == '#' or S[D] == '#':
    print('No')
    exit()
if C<D:
    LA = S[A:C+1]
    LB = S[B:D+1]
    if LA.count('##') > 0 or LB.count('##') > 0:
        print('No')
        exit()
if C>D:
    LA = S[A:D+1]
    LB = S[B:C+1]
    if LA.count('##') > 0 or LB.count('##') > 0 or LA.count('...') == 0:
        print('No')
        exit()
print('Yes')

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
A = []
for i in range(M):
    A.append(int(input()))
if A[0] == 1 or A[0] == 2:
    B = [0]
else:
    B = [A[0]-1]
for j in range(M-1):
    B.append(A[j+1]-A[j]-2)
B.append(N-A[M-1]-1)
ans = 1
for p in range(M+1):
    if B[p] == -1:
        print(0)
        exit()
    elif B[p] == 0 or B[p] == 1:
        ans *= 1
    else:
        b = 0
        N = B[p]
        for v in range(N//2+1):
            a = 1
            for w in range(N-2*v+1,N-v+1):
                a *= w/(w-N+2*v)
            b += a
        ans *= b
        ans %= 1000000007
print(round(ans))

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
flag = [True] * n
cnt = [0] * n
for i in range(m):
    a = int(input())
    flag[a - 1] = False

for i in range(n - 1, -1, -1):
    if flag[i]:
        if i == n - 1 or i == n - 2:
            cnt[i] = 1
        else:
            cnt[i] = (cnt[i + 1] + cnt[i + 2]) % (10 ** 9 + 7)
    else:
        cnt[i] = 0
print (cnt[0]+ cnt[1])

Submission status: Runtime Error

Solution code:
def f(n):
    if memo[n] > 0:
        return memo[n]
    memo[n] = f(n - 1) + f(n - 2)
    return memo[n]


N, M, *A = map(int, open(0).read().split())
memo = [1, 1] + [-1] * (N + 10)
A = list(A) + [N + 1]
MOD = 10 ** 9 + 7
ans = 1
prev = 0
for a in A:
    if a == prev:
        ans = 0
        break
    ans *= f(a - 1 - prev)
    ans %= MOD
    prev = a + 1
print(ans)

Submission status: Runtime Error

Solution code:
def f(n):
    if memo[n] > 0:
        return memo[n]
    else:
        memo[n] = f(n - 1) + f(n - 2)
        return memo[n]


N, M, *A = map(int, open(0).read().split())
memo = [-1] * (N + 2)
memo[0] = 1
memo[1] = 1
A = list(A) + [N + 1]
MOD = 10 ** 9 + 7
ans = 1
prev = 0
for a in A:
    if a == prev:
        ans = 0
        break
    ans *= f(a - 1 - prev)
    ans %= MOD
    prev = a + 1
print(ans)

Submission status: Runtime Error

Solution code:
def f(n):
    if memo[n] > 0:
        return memo[n]
    else:
        return f(n - 1) + f(n - 2)


N, M, *A = map(int, open(0).read().split())
memo = [-1] * (N + 2)
memo[0] = 1
memo[1] = 1
A = list(A) + [N + 1]
MOD = 10 ** 9 + 7
ans = 1
prev = 0
for a in A:
    if a == prev:
        ans = 0
        break
    ans *= f(a - 1 - prev)
    ans %= MOD
    prev = a + 1
print(ans)