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:
from functools import lru_cache

N, M = map(int, input().split())

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

@lru_cache(1000)
def dfs(pos):
    if pos > N:
        return 0
    if pos == N:
        return 1
    s = 0
    if (pos + 1) not in A:
        s += dfs(pos + 1)
    if (pos + 2) not in A:
        s += dfs(pos + 2)
    return s

print(dfs(0) % 1000000007)

Submission status: Runtime Error

Solution code:
from functools import lru_cache

N, M = map(int, input().split())

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

# print(N, M, A)

count = 0

@lru_cache(1000)
def dfs(pos):
    if pos == N:
        return 1
    s = 0
    if (pos + 1) not in A:
        s += dfs(pos + 1)
    if (pos + 2) not in A and ((pos + 2) <= N):
        s += dfs(pos + 2)
    return s

print(dfs(0) % 1000000007)

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
d=[]
s=[0]*n
for i in range(k):
    d.append(int(input()))

if 1 in d:
    s[0]=0
else:
    s[0]=1

if 2 in d:
    s[1]=0
else:
    s[1]= s[0]+1


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

print( s[n-1] % 1000000007)

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
d=[]
s=[0]*n
for i in range(k):
    d.append(int(input()))

if 1 in d:
    s[0]=0
else:
    s[0]=1

if 2 in d:
    s[1]=0
else:
    s[1]= s[0]+1


for i in range(2,n):
    if i+1 in d:
        s[i]=0
    else:
        s[i]=s[i-1]+s[i-2]

print( s[n-1] % (1000000007))

Submission status: Runtime Error

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

A = []

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

step = [0] * (N + 1)

step[0] = 1

for s in range(1, N + 1):
    if A[s]:
        step[s] = 0
        continue
    if s == 1:
        step[s] = 1
        continue
    else:
        step[s] = step[s - 1] + step[s - 2]
        step[s] %= 1000000007

print(step[N])

Submission status: Runtime Error

Solution code:
from sys import exit

N, M = map(int, input().split())

_a = -1
A = []
ans = 0

for _ in range(M):
    a_ = int(input())
    if _a + 1 == a_:
        print(0)
        exit()
    _a = a_
    A.append(_a)

step = [] * N
step[0] = 1

for s in range(1, N + 1):
    if s in A:
        step[s] = 0
        continue
    if s == 1:
        step[s] = 1
        continue
    else:
        step[s] = (step[s - 1] + step[s - 2]) % 1000000007

print(step[N])

Submission status: Runtime Error

Solution code:
import math
def Fib(n):
  Fib=1/math.sqrt(5)*(((1+math.sqrt(5))/2)**(n+1)-((1-math.sqrt(5))/2)**(n+1))
  return int(Fib)
N,M=map(int,input().split())
if M==0:
  print(Fib(N))
  exit()
A=[]
for i in range(M):
  A.append(int(input()))
B=[0]*M
a=0
for i in range(M):
  B[i]=A[i]-1-a
  a=A[i]+1
B.append(N-a)
a=A[0]
for i in range(1,M):
  if A[i]==a+1:
    print(0)
    exit()
  else:
    a=A[i]
ans=1
for i in range(M+1):
  ans*=Fib(B[i])
print(ans%1000000007)

Submission status: Runtime Error

Solution code:
import math
def Fib(n):
  Fib=1/math.sqrt(5)*(((1+math.sqrt(5))/2)**(n+1)-((1-math.sqrt(5))/2)**(n+1))
  return int(Fib)
N,M=map(int,input().split())
A=[]
for i in range(M):
  A.append(int(input()))
B=[0]*M
a=0
for i in range(M):
  B[i]=A[i]-1-a
  a=A[i]+1
B.append(N-a)
a=A[0]
for i in range(1,M):
  if A[i]==a+1:
    print(0)
    exit()
  else:
    a=A[i]
ans=1
for i in range(M+1):
  ans*=Fib(B[i])
print(ans%1000000007)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# c ABC129
# input


def endFib(n, a1=1, a2=0):
    if (n < 1):
        return a1
    else:
        return endFib(n-1, a1 + a2, a1)


n, m = map(int, input().split())
o = 1
p = 0
if m == 0:
    if n < 3:
        o = n
    else:
        o = endFib(n)
    print(o % 1000000007)
    exit()
elif m > 0:
    ft = int(input())
    if ft < 3:
        p = ft
    elif ft == 3:
        o = 2
        p = ft
    elif ft > 3:
        o = endFib(ft-1) % 1000000007
        p = ft
    else:
        pass

    for i in range(m-1):
        t = int(input())
        if t-1-p == 0:
            print(0)
            exit()
        elif t-1-p == 1:
            p = t
        elif t-1-p == 2:
            p = t
        elif t-1-p == 3:
            o = o * 2
            p = t
        elif t-1-p > 3:
            o = (o * endFib(t-2-p)) % 1000000007
            p = t
        else:
            pass
    if n-p > 3:
        o = (o * endFib(n-p-1)) % 1000000007
    elif n-p == 3:
        o = o * 2
    else:
        pass

out = o % 1000000007
print(out)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# c ABC129
# input


def endFib(n, a1=1, a2=0):
    if (n < 1):
        return a1
    else:
        return endFib(n-1, a1 + a2, a1)


n, m = map(int, input().split())
o = 1
p = 0
if m == 0:
    if n < 3:
        o = n
    else:
        o = endFib(n)
    print(o % 1000000007)
    exit()
else:
    pass

ft = int(input())
if ft < 3:
    p = ft
elif ft == 3:
    o = 2
    p = ft
elif ft > 3:
    o = endFib(ft-1) % 1000000007
    p = ft
else:
    pass

for i in range(m):
    t = int(input())
    if t-p == 1:
        print(0)
        exit()
    elif t-p-1 == 1:
        p = t
    elif t-1-p == 2:
        p = t
    elif t-1-p == 3:
        o = o * 2
        p = t
    elif t-1-p > 3:
        o = (o * endFib(t-2-p)) % 1000000007
        p = t
    else:
        pass
if n-p > 3:
    o = o * endFib(n-p-1) % 1000000007
elif n-p == 3:
    o = o * 2
else:
    pass

out = o % 1000000007
print(out)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# c ABC129
# input


def endFib(n, a1=1, a2=0):
    if (n < 1):
        return a1
    else:
        return endFib(n-1, a1 + a2, a1)


n, m = map(int, input().split())
o = 1
p = 0
if m == 0:
    if n < 3:
        o = n
    else:
        o = endFib(n)
    print(o % 1000000007)
    exit()
else:
    pass

ft = int(input())
if ft < 3:
    p = ft
elif ft == 3:
    o = 2
    p = ft
elif ft > 3:
    o = endFib(ft-1) % 1000000007
    p = ft
else:
    pass

for i in range(m-1):
    t = int(input())
    if t-p == 1:
        print(0)
        exit()
    elif t-p-1 == 1:
        p = t
    elif t-1-p == 2:
        p = t
    elif t-1-p == 3:
        o = o * 2
        p = t
    elif t-1-p > 3:
        o = (o * endFib(t-2-p)) % 1000000007
        p = t
    else:
        pass
if n-p > 3:
    o = o * endFib(n-p-1) % 1000000007
elif n-p == 3:
    o = o * 2
else:
    pass

out = o % 1000000007
print(out)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# c ABC129
# input


def endFib(n, a1=1, a2=0):
    if (n < 1):
        return a1
    else:
        return endFib(n-1, a1 + a2, a1)


n, m = map(int, input().split())
o = 1
p = 0
if m == 0:
    if n < 3:
        o = n
    else:
        o = endFib(n)
    print(o % 1000000007)
    exit()
else:
    pass

ft = int(input())
if ft < 3:
    p = ft
elif ft == 3:
    o = 2
    p = ft
elif ft > 3:
    o = endFib(ft-1) % 1000000007
    p = ft
else:
    pass

for i in range(m-1):
    t = int(input())
    if t-p == 1:
        print(0)
        exit()
    elif t-p-1 == 1:
        p = t
    elif t-1-p == 2:
        p = t
    elif t-1-p == 3:
        o = o * 2
        p = t
    elif t-1-p > 3:
        o = o*endFib(t-2-p) % 1000000007
        p = t
    else:
        pass
if n-p > 3:
    o = o * endFib(n-p-1) % 1000000007
elif n-p == 3:
    o = o * 2
else:
    pass

out = o % 1000000007
print(out)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# c ABC129
# input


def endFib(n, a1=1, a2=0):
    if (n < 1):
        return a1
    else:
        return endFib(n-1, a1 + a2, a1)


n, m = map(int, input().split())
o = 1
p = 0
if m == 0:
    if n < 3:
        o = n
    else:
        o = endFib(n)
    print(o % 1000000007)
    exit()
ft = int(input())
if ft < 3:
    p = ft
elif ft == 3:
    o = 2
    p = ft
elif ft > 3:
    o = endFib(ft-1) % 1000000007
    p = ft

for i in range(m-1):
    t = int(input())
    if t-p == 1:
        print(0)
        exit()
    elif t-p-1 == 1:
        p = t
    elif t-1-p == 2:
        p = t
    elif t-1-p == 3:
        o = o*2
        p = t
    elif t-1-p > 3:
        o = o*endFib(t-2-p) % 1000000007
        p = t
if n-p > 3:
    o = o * endFib(n-p-1) % 1000000007
elif n-p == 3:
    o = o*2
print(o % 1000000007)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
import numpy as np

H, W = map(int, input().split())
S = np.array([list(input()) for _ in range(H)]) == '.'
ups = np.zeros((H,W), dtype=int)
downs = np.zeros((H,W), dtype=int)
lefts = np.zeros((H,W), dtype=int)
rights = np.zeros((H,W), dtype=int)

for h in range(H):
    ups[h] = (ups[h-1] + 1) * S[h-1]
    downs[H-h-1] = (downs[H-h-1] + 1) * S[H-h-1]
for w in range(W):
    lefts[:, w] = (lefts[:, w-1] + 1) * S[w-1]
    rights[:, W-w-1] = (rights[:, W-w-1] + 1) * S[W-w-1]
print(np.amax((ups+downs+lefts+rights)*S)+1)

Submission status: Runtime Error

Solution code:
def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def solve(inputs):
    [N, M] = list(map(lambda x: int(x), inputs[0].split()))
    broke_steps = list(map(lambda x: int(x), inputs[1:]))

    prev = broke_steps[0]
    for broke_step in broke_steps[1:]:
        if broke_step - prev == 1:
            return 0

    SSSS = 1000000007

    patterns = [1]
    for i, step in enumerate(range(1, N + 1)):
        if step in broke_steps:
            ap = 0
        elif i == 0:
            ap = 1
        else:
            ap = (patterns[i] + patterns[i - 1]) % SSSS
        patterns.append(ap)

    return patterns[-1]


if __name__ == "__main__":
    first = input()
    [N, M] = list(map(lambda x: int(x), first.split()))
    inputs_str = inputs(M)
    inputs_str.insert(0, first)
    ret = solve(inputs_str)
    print(ret)

Submission status: Runtime Error

Solution code:
n,m = map(int, input().split())
a = [0]*(n+1)
a[1] = 1
a[2] = 2
for i in range(m):
    a[int(input())] = "*"
if a[1] == "*":
    a[2] = 1
#階段が壊れていないならば a(n+2)=a(n+1)+a(n), a(0)=0, a(1)=1
#というフィボナッチ数列の問題になる
#ここでは、壊れている階段かどうかを逐次判定していくのが良いだろう
for i in range(1,n-1):
    if a[i+2] != "*":
        if a[i+1] != "*":
            if a[i] != "*":
                a[i+2] = a[i+1]+a[i]
            else:
                a[i+2] = a[i+1]
        else:
            if a[i] != "*":
                a[i+2] = a[i]
ans = a[-1]%1000000007
print(ans)

Submission status: Runtime Error

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

for i in range(M):
  b[int(input())] = -1
  
for i in range(N):
  if b[i] != -1:
    if b[i+1] != -1:
      b[i+1] += b[i]
      print(b[i])
      print(b[i+1])
      print(b)
    if b[i+2] != -1:
      b[i+2] += b[i]
      print(b)

Submission status: Runtime Error

Solution code:
N,M = [int(i) for i in input().split()]
A = []
for _ in range(M):
    A.append(int(input()))
def fib_memo(n):
    memo = [0]*(n+1)
    def _fib(n):
        if n <= 2:
            return n
        if memo[n] != 0:
            return memo[n]
        memo[n] = _fib(n-1) + _fib(n-2)
        return memo[n]
    return _fib(n)
cnt = 1
for a in range(len(A)+1):
    if a == 0:
        if A[a] == 1:
            width = 1
        else:
            width = A[a]-1
    elif a > 0 and a < M:
        width = A[a] - A[a-1] - 2
    elif a == (M):
        width = N-A[a-1]-1
    if width < 0:
        tmp = 0
        cnt = 0
        break
    else:
        tmp = fib_memo(width)%1000000007
    cnt = (tmp*cnt)%1000000007
print(cnt)

Submission status: Runtime Error

Solution code:
N,M = map(int, input().split())
total = 1
a = [int(input())]
total *= (((1+5**0.5)/2)**a[0] - ((1-5**0.5)/2)**a[0])/5**0.5
for i in range(M-1):
  b = int(input())
  a.append(b)
  c = a[i+1] - a[i] - 1
  total *= (((1+5**0.5)/2)**c - ((1-5**0.5)/2)**c)/5**0.5
total *= (((1+5**0.5)/2)**(N-a[M-1]) - ((1-5**0.5)/2)**(N-a[M-1]))/5**0.5
print(int(total % 1000000007))

Submission status: Runtime Error

Solution code:
N,M = [int(i) for i in input().split()]
A = []
for _ in range(M):
    A.append(int(input()))
def fibo(n):
    if n <= 2:
        return n
    return fibo(n-1) + fibo(n-2)
cnt = 1
for a in range(len(A)+1):
    if a == 0:
        if A[a] == 1:
            width = 1
        else:
            width = A[a]-1
    elif a > 0 and a < M:
        width = A[a] - A[a-1] - 2
    elif a == (M):
        width = N-A[a-1]-1
    if width < 0:
        tmp = 0
        cnt = 0
        break
    else:
        tmp = fibo(width)%1000000007
    cnt = (tmp*cnt)%1000000007
print(cnt)

Submission status: Runtime Error

Solution code:
N,M = [int(i) for i in input().split()]
A = []
for _ in range(M):
    A.append(int(input()))
def fibo(n):
    if n <= 2:
        return n
    return fibo(n-1) + fibo(n-2)
cnt = 1
for a in range(len(A)+1):
    if a == 0:
        if A[a] == 1:
            width = 1
        else:
            width = A[a]-2
    elif a > 0 and a < M:
        width = A[a] - A[a-1] - 2
    elif a == (M):
        width = N-A[a-1]-1
    if width < 0:
        tmp = 0
        cnt = 0
        break
    else:
        tmp = fibo(width)%1000000007
    cnt = (tmp*cnt)%1000000007
print(cnt)

Submission status: Runtime Error

Solution code:
N,M = [int(i) for i in input().split()]
A = []
for _ in range(M):
    A.append(int(input()))
def fibo(n):
    if n <= 2:
        return n
    return fibo(n-1) + fibo(n-2)
cnt = 1
for a in range(len(A)+1):
    if a == 0:
        if A[a] == 1:
            width = 1
        else:
            width = A[a]-2
    elif a > 0 and a < M:
        width = A[a] - A[a-1] - 2
    elif a == (M):
        width = N-A[a-1]-1
    if width < 0:
        tmp = 0
        cnt = 0
        break
    else:
        tmp = fibo(width)
    cnt = (tmp*cnt)%1000000007
print(cnt)

Submission status: Runtime Error

Solution code:
N,M = [int(i) for i in input().split()]
A = []
for _ in range(M):
    A.append(int(input()))
def fibo(n):
    if n <= 2:
        return n
    return fibo(n-1) + fibo(n-2)
cnt = 1
for a in range(len(A)+1):
    if a == 0:
        if A[a] == 1:
            width = 1
        else:
            width = A[a]-2
    elif a > 0 and a < M:
        width = A[a] - A[a-1] - 2
    elif a == (M):
        width = N-A[a-1]-1
    if width < 0:
        tmp = 0
        cnt = 0
        break
    else:
        tmp = fibo(width) % 1000000007
    cnt *= tmp
print(cnt)

Submission status: Runtime Error

Solution code:
N,M = [int(i) for i in input().split()]
A = []
for _ in range(M):
    A.append(int(input()))
def fibo(n):
    if n <= 2:
        return n
    return fibo(n-1) + fibo(n-2)
cnt = 1
for a in range(len(A)+1):
    if a == 0:
        if A[a] == 1:
            width = 1
        else:
            width = A[a]-2
    elif a > 0 and a < M:
        width = A[a] - A[a-1] - 2
    elif a == (M):
        width = N-A[a-1]-1
    if width < 0:
        tmp = 0
        cnt = 0
        break
    else:
        tmp = fibo(width) % 1000000007
    print(width,tmp)
    cnt *= tmp

Submission status: Runtime Error

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

group = []

MOD = 1000000007

if M == 0:
    group.append(N+1)
else:
    pre_a = int(input())
    group.append(pre_a)

    for i in range(M-1):
        a = int(input())
        tmp = a - pre_a - 1
        pre_a = a
        group.append(tmp)
    group.append(N - pre_a)

if 0 in group or -1 in group:
    print(0)
else:
    fiv = [1 for i in range(max(group))]
    fiv[0] = 1
    fiv[1] = 1
    for i in range(2, len(fiv)):
        fiv[i] = (fiv[i-1] + fiv[i-2]) % MOD
    ans = 1
    for g in group:
        ans *= fiv[g-1]
        ans %= MOD
    print(ans)

Submission status: Runtime Error

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

group = []

MOD = 1000000007

if M == 0:
    group.append(N+1)
else:
    pre_a = int(input())
    group.append(pre_a)

    for i in range(M-1):
        a = int(input())
        tmp = a - pre_a - 1
        pre_a = a
        group.append(tmp)
    group.append(N - pre_a)

if 0 in group:
    print(0)
else:
    fiv = [0 for i in range(max(group))]
    fiv[0] = 1
    fiv[1] = 1
    for i in range(2, len(fiv)):
        fiv[i] = (fiv[i-1] + fiv[i-2]) % MOD
    ans = 1
    for g in group:
        ans *= fiv[g-1]
    print(ans%MOD)

Submission status: Runtime Error

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

group = []

MOD = 1000000007

if M == 0:
    group.append(N)
else:
    pre_a = int(input())
    group.append(pre_a)

    for i in range(M-1):
        a = int(input())
        tmp = a - pre_a - 1
        pre_a = a
        group.append(tmp)
    group.append(N - pre_a)

if 0 in group:
    print(0)
else:
    fiv = [0 for i in range(max(group))]
    fiv[0] = 1
    fiv[1] = 1
    for i in range(2, len(fiv)):
        fiv[i] = (fiv[i-1] + fiv[i-2]) % MOD
    ans = 1
    for g in group:
        ans *= fiv[g-1]
    print(ans%MOD)

Submission status: Runtime Error

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

group = []

MOD = 1000000007

pre_a = int(input())
group.append(pre_a)

ok = True
for i in range(M-1):
    a = int(input())
    tmp = a - pre_a - 1
    pre_a = a
    group.append(tmp)
group.append(N - pre_a)

if 0 in group:
    print(0)
else:
    fiv = [0 for i in range(max(group))]
    fiv[0] = 1
    fiv[1] = 1
    for i in range(2, len(fiv)):
        fiv[i] = (fiv[i-1] + fiv[i-2]) % MOD
    ans = 1
    for g in group:
        ans *= fiv[g-1]
    print(ans%MOD)

Submission status: Runtime Error

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

group = []

MOD = 1000000007

pre_a = int(input())
group.append(pre_a)

ok = True
for i in range(M-1):
    a = int(input())
    tmp = a - pre_a - 1
    pre_a = a
    if tmp == 0:
        ok = False
    else:
        group.append(tmp)
    if not ok:
        break
group.append(N - pre_a)

if not ok:
    print(0)
elif max(group) == 1:
    print(1)
else:
    fiv = [0 for i in range(max(group))]
    fiv[0] = 1
    fiv[1] = 1
    for i in range(2, len(fiv)):
        fiv[i] = (fiv[i-1] + fiv[i-2]) % MOD
    ans = 1
    for g in group:
        ans *= fiv[g-1]
    print(ans%MOD)

Submission status: Runtime Error

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

group = []

MOD = 1000000007

pre_a = int(input())
group.append(pre_a)

ok = True
for i in range(M-1):
    a = int(input())
    tmp = a - pre_a - 1
    pre_a = a
    if tmp == 1:
        ok = False
    else:
        group.append(tmp)
    if not ok:
        break
group.append(N - pre_a)

if not ok:
    print(0)
elif max(group) == 1:
    print(1)
else:
    fiv = [0 for i in range(max(group))]
    fiv[0] = 1
    fiv[1] = 1
    for i in range(2, len(fiv)):
        fiv[i] = (fiv[i-1] + fiv[i-2]) % MOD
    ans = 1
    for g in group:
        ans *= fiv[g-1]
    print(ans%MOD)

Submission status: Runtime Error

Solution code:
import sys
def fib(a):
  if a==1:
    return 1
  elif a==0:
    return 1
  else:
    return fib(a-1)+fib(a-2)
def count(a,b):
  if a+1==b:
    return 0
  else:
    return fib(b-a-2)
n,m=map(int,input().split())
a=list(map(int,sys.stdin))
for _ in range(m+1):
  if _ == 0:
    sum = fib(a[_]-1)
  elif _ == m:
    sum = sum*fib(n-a[_-1]-1)%1000000007
  else:
    sum = sum*count(a[_-1],a[_])%1000000007
print(sum)

Submission status: Runtime Error

Solution code:
N,M = (int(i) for i in input().split())
a = [int(input()) for i in range(M)]
hoge = [0] * N
if 1 not in a:
    hoge[0] = 1
if 2 not in a:
    hoge[1] = hoge[0] + 1

for i in range(2,N):
    if i + 1 not in a:
        hoge[i] = 0
        if i in a:
            hoge[i] = hoge[i - 2]
        elif (i-1) in a:
            hoge[i] = hoge[i - 1]
        else:
            hoge[i] = hoge[i-1] + hoge[i-2]
print(hoge[N-1] % (10**9 + 7))

Submission status: Runtime Error

Solution code:
N,M = (int(i) for i in input().split())
a = [int(input()) for i in range(M)]
hoge = [0] * N
if 1 not in a:
    hoge[0] = 1
if 2 not in a:
    hoge[1] = hoge[0] + 1

for i in range(2,N):
    if i + 1 not in a:
        hoge[i] = 0
        if i in a:
            hoge[i] = hoge[i - 2]
        elif (i-1) in a:
            hoge[i] = hoge[i - 1]
        else:
            hoge[i] = hoge[i-1] + hoge[i-2]
            hoge[i] = hoge[i] % (10**9 + 7)
print(hoge[N-1] % (10**9 + 7))

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
ls=[]
for i in range(M):
    ls.append(int(input()))
ls.append(N+1)
import math 
from math import sqrt as r
p=math.pi
def A(n):
    if n==0:
        return 0
    else:
        X=(((1+r(5))/2)**n-((1-r(5))/2)**n)/r(5)
        return int(X)
k=0
ans=1
for x in ls:
    ans=ans*A(x-k)
    k=x+1
    if ans==0:
        break

print(int(ans%1000000007))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Mon Jun 10 20:26:39 2019

@author: plosi
"""
dp=[-1 for i in range(10**5+1)]


def f(x): 
    if x==0: 
        return 1 
    if x<0: 
        return 0 
    if dp[x]!=-1: 
        return dp[x] 
    val= (f(x-1)+f(x-2))%(1000000007) 
    dp[x]=val 
    return val

def main(): 
    N,M=input().split(" ") 
    N=int(N) 
    M=int(M) 

    for i in range(M): 
        dp[int(input())]=0 
    
    print((f(N-1)+f(N-2))%(1000000007)) 
    
main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
import math
from operator import mul
from functools import reduce

def cmb(n,r):
	r = min(n-r,r)
	if r == 0: return 1
	over = reduce(mul, range(n, n - r, -1))
	under = reduce(mul, range(1,r + 1))
	return over // under

def get_num(k):
	num = 0
	if k > 2:
		for idx in range(math.ceil(k/2)):
			num = num + cmb(k-1-idx,idx)
	else:
		num = 1
	return num
	

line1 = [int(i) for i in input().split()]
N = line1[0]
M = line1[1]
As = []
ans = 1

for idx in range(M):
	As.append(int(input()))
	
if As[0] > 1:
	ans = get_num(As[0]-1)
	if As[0] > 2:
		ans = ans + get_num(As[0]-2)


for idx in range(0,M):
	if idx < M-1:
		dif = As[idx+1] - As[idx] - 1
	else:
		dif = N - As[idx]
	if dif == 1 and idx < M-1:
		ans = 0
		break
	else:
		ans = ans * get_num(dif)
	
print(ans%1000000007)

Submission status: Runtime Error

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

a = [True] * (n + 1)
for i in range(m):
    a[int(input())] = False
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = dp[0] if not 1 in a else 0
for i in range(2, n + 1):
  if a[i]:
      dp[i] = (dp[i - 1] + dp[i - 2]) % mod
  else:
      dp[i]=  0
print(dp(n))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
a = [-10]
ans = -1
MOD = 10 ** 9 + 7
if N == 1:
    ans = 1
else:
    for i in range(M):
        a += [int(input())]
        if a[i + 1] - a[i] == 1:
            ans = 0
            break
a.pop(0)
if not ans in [0, 1]:
    memo = [0] * (N + 1)
    memo[0] = 1
    memo[1] = 1
    try:
        if a[0] == 1:
            a.pop(0)
            memo[1] = 0
    except:
        pass
    j = 0
    for i in range(N - 1):
        if i + 2 == a[j]:
            if j < len(a) - 1:
                j += 1
            continue
        memo[i + 2] = memo[i] + memo[i + 1]
        memo[i + 2] = memo[i + 2] % MOD
    else:
        ans = memo[i + 2]
print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Mon Jun 10 20:26:39 2019

@author: plosi
"""
dp=[-1 for i in range(10**5)]
bs=[True for i in range(10**5)]

def f(x): 
    if x==0: 
        return 1 
    if x<0: 
        return 0 
    if dp[x]!=-1: 
        return dp[x] 
    if not bs[x]: 
        dp[x]=0 
        return 0 
    val= (f(x-1)+f(x-2))%(1000000007) 
    dp[x]=val 
    return val

def main(): 
    N,M=input().split(" ") 
    N=int(N) 
    M=int(M) 

    for i in range(M): 
        bs[int(input())]=False 
    
    print((f(N-1)+f(N-2))%(1000000007)) 
    
main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Mon Jun 10 20:26:39 2019

@author: plosi
"""

def f(x): 
    if x==0: 
        return 1 
    if x<0: 
        return 0 
    if dp[x]!=-1: 
        return dp[x] 
    if not bs[x]: 
        return 0 
    val= (f(x-1)+f(x-2))%(1000000007) 
    dp[x]=val 
    return val

def main(): 
    N,M=input().split(" ") 
    N=int(N) 
    M=int(M) 
    global bs 
    global dp 
    dp=[-1 for i in range(N)]
    bs=[True for i in range(N)]
    for i in range(M): 
        bs[int(input())]=False 
    
    print((f(N-1)+f(N-2))%(1000000007)) 
    
main()

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
w = [int(input()) for _ in range(m)]
if w[0]-1 > 0 :
    ans = w[0]-1
else :
    ans = 1
    
if m > 1 :
    for i in range(0, m-1) :
        if w[i+1] - w[i] == 1 :
            print(0)
            exit()
        elif w[i+1] - w[i] > 2 :
            j = w[i+1] - w[i] - 3
            if j%4 == 0 :
                ans *= (j + 2)*(j//4)+1
            elif j%4 == 1 :
                ans *= (j + 1)*(j//4)+(j//2+1)+1
            elif j%4 == 2 :
                ans *= (j + 2)*(j//4)+(j//2+1)+1
            elif j%4 == 3 :
                ans *= (j + 1)*(j//4+1)+1

if n - w[m-1] - 2 > 0 :
    j = n - w[m-1] - 2
    if j >= 4 :
        if j%4 == 0 :
            ans *= (j + 2)*(j//4)+1
        elif j%4 == 1 :
            ans *= (j + 1)*(j//4)+(j//2+1)+1
        elif j%4 == 2 :
            ans *= (j + 2)*(j//4)+(j//2+1)+1
        elif j%4 == 3 :
            ans *= (j + 1)*(j//4+1)+1
    else :
        if j%4 == 1 :
            ans *= (j + 1)
        elif j%4 == 2 :
            ans *= (j + 1)
        elif j%4 == 3 :
            ans *= (j + 1)

    print(ans%1000000007)
else :
    print(ans%1000000007)

Submission status: Runtime Error

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

a = [int(input()) for i in range(M)]
a.reverse()
wa = (10**9) + 7

#dpを使う

dp = [0]*(N+1)
dp[0]=1
now_a = a.pop()
for i in range(1,N+1):
    if i==1:
        dp[i]=dp[i-1]
    else:
        dp[i]=dp[i-1] + dp[i-2]
    if i == now_a:
        dp[i]=0
        if len(a)!=0:
            now_a = a.pop()
        else:
            now_a = -1

print(dp[N]%wa)

Submission status: Runtime Error

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

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

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

print(dp[N])

Submission status: Runtime Error

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

def rootCount(x):
     if x == 0:
          z[x] = 1
          return 1
     elif x == 1:
          if z[x] == 0:
               return 0
          else:
               z[x] = 1
               return 1
     elif x < N+1 and z[x] != -1:
          return z[x]
     else:
          z[x] = rootCount(x-1) + rootCount(x-2)
          return z[x]
print(rootCount(N) % 1000000007)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
a = [int(input()) for i in range(M)] 
z = [0] * (N+1)
def rootCount(x):
     if x in a:
          z[x] = 0
          return 0
     elif x == 0:
          z[x] = 1
          return 1
     elif x == 1:
          z[x] = 1
          return 1
     elif x < N+1 and z[x] != 0:
          return z[x]
     else:
          z[x] = rootCount(x-1) + rootCount(x-2)
          return z[x]
print(rootCount(N) % 1000000007)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
a = [int(input()) for i in range(M)] 
z = [0] * (N+1)
for i, aa in enumerate(a):
     if 0 < i and (a[i] - a[i-1]) == 1:
          print(0)
          exit()

def rootCount(x):
     if x in a:
          z[x] = 0
          return 0
     elif x == 0:
          z[x] = 1
          return 1
     elif x == 1:
          z[x] = 1
          return 1
     elif x < N and z[x] != 0:
          return z[x]
     else:
          z[x] = rootCount(x-1) + rootCount(x-2)
          return z[x]
print(rootCount(N) % 1000000007)

Submission status: Runtime Error

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

def rootCount(x):
     if x in a:
          z[x] = 0
          return 0
     elif x == 0:
          z[x] = 1
          return 1
     elif x == 1:
          z[x] = 1
          return 1
     elif x < N and z[x] != 0:
          return z[x]
     else:
          z[x] = rootCount(x-1) + rootCount(x-2)
          return z[x]
print(rootCount(N) % 1000000007)

Submission status: Runtime Error

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

def rootCount(x):
     print(x)
     if x in a:
          z[x] = 0
          return 0
     elif x == 0:
          z[x] = 1
          return 1
     elif x == 1:
          z[x] = 1
          return 1
     elif x < N and z[x] != 0:
          print("hit " + str(x))
          print(z)
          return z[x]
     else:
          print(x,x-1,x-2)
          print(z)
          z[x] = rootCount(x-1) + rootCount(x-2)
          return z[x]
print(rootCount(N) % 1000000007)

Submission status: Runtime Error

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

num=[1,1,2]

mod=1000000007

count=0
jud=1
ans=1
for i in range(n+1):
	
	if i>2:
		num.append(1)
		num[i]=(num[i-1]+num[i-2])%mod

	if(jud==0 and a[i]==1):
		print("0")
		break
	elif(i==n):
		count+=1
		ans=(ans%mod)*(num[count-1]%mod)
		
		print(ans%mod)
	elif a[i]==1:
		
		ans=(ans%mod)*(num[count-1]%mod)
		count=0
		jud=0
	else:
		jud=1
		count+=1