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=map(int,input().split())
a=set([int(input()) for j in range(m)])
dp=[0]*(n+1)
dp[0]=1
if not a[0]==1:
    dp[1]=1
else:
    dp[1]=0
for i in range(n-1):
    if i+2 in a:
        dp[i+2]=0
    else:
        dp[i+2]=(dp[i+1]+dp[i])%(10**9+7)
print(dp[n])

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# 問題：https://atcoder.jp/contests/abc126/tasks/abc129_c

mod = 1000000007
N, M = map(int, input().strip().split())
a = [int(input()) for _ in range(M)]
a.append(N+1)

def fibonacci(x):
    if x > 2:
        return fibonacci(x-1) + fibonacci(x-2)
    else:
        return 1

res = 1
prev_a = -1
for cur_a in a:
    if  cur_a - prev_a == 1:
        res = 0
        break
    res *= fibonacci(cur_a - prev_a - 1) % mod
    res %= mod
    prev_a = cur_a
    continue

print(res)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# 問題：https://atcoder.jp/contests/abc126/tasks/abc129_c

N, M = map(int, input().strip().split())
a = [int(input()) for _ in range(M)]
a.append(N+1)

def fibonacci(x):
    if x > 2:
        return fibonacci(x-1) + fibonacci(x-2)
    else:
        return 1

res = 1
prev_a = -1
for cur_a in a:
    if  cur_a - prev_a == 1:
        res = 0
        break
    res *= fibonacci(cur_a - prev_a - 1)
    res %= 1000000007
    prev_a = cur_a
    continue

print(res)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# 問題：https://atcoder.jp/contests/abc126/tasks/abc129_c

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

def fibonacci(x):
    if x > 2:
        return fibonacci(x-1) + fibonacci(x-2)
    else:
        return 1

res = 1
count = 0
for i in range(N+1):
    if i in a:
        if count == 0:
            res = 0
            break
        res *= fibonacci(count)
        res %= 1000000007
        count = 0
        continue
    count += 1

if res != 0:
    res *= fibonacci(count)
    res %= 1000000007

print(res)

Submission status: Runtime Error

Solution code:
import itertools as it
def X (n):
    if n%2==0:
        r=n//2
    else:
        r=(n-1)//2
    S=1
    C=1
    for j in range(1,r+1):
        C=len(list(it.combinations(range(n-j),j)))
        S+=C
    return int(S)

N,M=map(int,input().split())
L=[]
a=0
for i in range(M):
    b=int(input())
    L.append(b-a-1)
    a=b
L.append(N-b-1)
A=1
mod=10**9+7
for i in range(len(L)):
    A*=(X(L[i])%mod)
    if L[i]==0 and i>0:
        A=0
        break
print(A%mod)

Submission status: Runtime Error

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

s = [-1] * N
s[0] = 1
s[1] = 1

for m in range(0, M):
    i = int(input())
    s[i] = 0

for n in range(2, N):
    if s[n] == 0:
        continue
    s[n] = s[n - 1] + s[n - 2]

print((s[N-1] + s[N-2]) % 1000000007)

Submission status: Runtime Error

Solution code:
from functools import lru_cache
MOD=10**9+7
n,m=map(int,input().split())
a=[int(input()) for _ in range(m)]
if n==1:
  print(1)
  exit()
if 1 in a and 2 in a:
  print(0)
  exit()
elif 1 in a:
  ans=[0,0,1]
elif 2 in a:
  ans=[0,1,0]
else:
  ans=[0,1,2]

@lru_cache(maxsize=None)
def cnt(x):
  if x<3:
    return ans[x]
  if x in a:
    return 0
  else:
    return (cnt(x-1)+cnt(x-2))%MOD

print(cnt(n))

Submission status: Runtime Error

Solution code:
MOD=10**9+7
n,m=map(int,input().split())
a=[int(input()) for _ in range(m)]
if 1 in a and 2 in a:
  print(0)
  exit()
elif 1 in a:
  ans=[0,1]
elif 2 in a:
  ans=[1,0]

for i in range(2,n):
  if i+1 in a:
    ans.append(0)
  else:
    s=(ans[-1]+ans[-2])%MOD
    ans.append(s)
print(ans[-1]%MOD)

Submission status: Runtime Error

Solution code:
patterns = [None] * 10**5
patterns[0] = 1
patterns[1] = 1
calcurated_until = 1
MOD = 10**9+7
def get_patterns(n):
  global calcurated_until, patterns
  if patterns[n] is None:
    for i in range(calcurated_until + 1, n + 1):
      patterns[i] = (patterns[i-1] + patterns[i-2])%MOD
    calcurated_until = n
  #print('p', n, patterns[n])
  return patterns[n]

def solve():
  N, M = map(int, input().split())
  A = [-1]
  for _ in range(M):
    A.append(int(input()))
  A.append(N+1)
  #print(A)
  
  ans = 1
  for a1, a2 in zip(A[:-1], A[1:]):
    #print(a1, a2)
    if a2 == a1+1:
      print('0')
      return
    #print('ans', ans)
    #print('get_patterns(a2 - a1 - 2)', get_patterns(a2 - a1 - 2))
    ans *= get_patterns(a2 - a1 - 2)
    #print('ans', ans)
    ans %= MOD
    #print('ans', ans)
  print(ans)
solve()

Submission status: Runtime Error

Solution code:
patterns = [None] * 10**5
patterns[0] = 1
patterns[1] = 1
MOD = 10**9+7
def get_patterns(n):
  if patterns[n] is None:
    patterns[n] = (get_patterns(n-1) + get_patterns(n-2))%MOD
  #print('p', n, patterns[n])
  return patterns[n]

def solve():
  N, M = map(int, input().split())
  A = [-1]
  for _ in range(M):
    A.append(int(input()))
  A.append(N+1)
  #print(A)
  
  ans = 1
  for a1, a2 in zip(A[:-1], A[1:]):
    #print(a1, a2)
    if a2 == a1+1:
      print('0')
      return
    #print('ans', ans)
    #print('get_patterns(a2 - a1 - 2)', get_patterns(a2 - a1 - 2))
    ans *= get_patterns(a2 - a1 - 2)
    #print('ans', ans)
    ans %= MOD
    #print('ans', ans)
  print(ans)
solve()

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
dp = [0 for _ in range(N+1)]
skip = {}

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

dp[1] = 1
dp[2] = 2

if 1 in skip:
    dp[1] = 0
    dp[2] = 1
if 2 in skip:
    dp[2] = 0

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

print(dp[N])

Submission status: Runtime Error

Solution code:
import sys

N, M = map(int, input().split())
dp = [0 for _ in range(N+1)]
skip = {}

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

dp[1] = 1
dp[2] = 2

if 1 in skip:
    dp[1] = 0
    dp[2] = 1
if 2 in skip:
    dp[2] = 0
if N in skip:
    print(0)
    sys.exit()

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

print(dp[N])

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
dp = [0 for _ in range(N+1)]
skip = {}

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

dp[1] = 1
dp[2] = 2

if 1 in skip:
    dp[1] = 0
    dp[2] = 1
if 2 in skip:
    dp[2] = 0

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

print(dp[N])

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
dp = [0 for _ in range(N+1)]
skip = []

for _ in range(M):
    skip.append(int(input()))

dp[1] = 1
dp[2] = 2

if 1 in skip:
    dp[1] = 0
    dp[2] = 1
if 2 in skip:
    dp[2] = 0

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

print(dp[N])

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
a = {int(input()) for _ in range(m)}
mod = 10**9 + 7

dp = [0]*(n+1)
dp[0] = 1
    
for i in range(1,n+1):
    if i in a:
        continue
    x = dp[i-1] 
    if i > 1:
        x += dp[i-2]
    dp[i] = x
ans = dp[n] % x
print(ans)

Submission status: Runtime Error

Solution code:
def Fib(n):
    a, b = 0, 1
    if n == 1:
        return a
    elif n == 2:
        return b
    else:
        for i in range(n-2):
            a, b = b, a + b
        return b

def solve():
    n, m = map(int, input().split())
    a = [int(input()) for _ in range(m)]

    if len(a) > 1:
        for i in range(m-1):
            if a[i+1]-a[i] <= 1:
                return 0
    
    a = a + [n]
    l = [a[0]]
    for i in range(1, m):
        l.append(a[i]-a[i-1]-1)
    l = l + [a[-1]-a[-2]]
    ans = 1
    for i in l:
        ans *= Fib(i+1)

    return ans%1000000007


print(solve())

Submission status: Runtime Error

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

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

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

print(dp[n])

Submission status: Runtime Error

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

mod = 10**9 + 7
dp = [0] * (n + 1)
dp[0] = 1
if 1 not in A:
  dp[1] = 1

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

print(dp[n])

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
am = [int(input()) for _ in range(m)]
dic2 = {}

def stairs(n):
    global dic2
    if dic2.get(n):
        return dic2[n]

    if n == 0:
        return 1
    elif n ==1:
        return 1

    if n-1 not in am:
        n1 = stairs(n-1)
    else:
        n1 = 0
    if n-2 not in am:
        n2 = stairs(n-2)
    else:
        n2 = 0

    dic2[n] = (n1+n2)%1000000007

    return (n1+n2)%1000000007

print(stairs(n))

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
am = [int(input()) for _ in range(m)]
dic = {}
def dfs(i):

    global dic
    if dic.get(i):
        return dic[i]

    if i == n:
        return 1

    k = 0
    if i+1 not in am and i+1 <= n:
        k += dfs(i+1)
    if i+2 not in am and i+2 <= n:
        k += dfs(i+2)

    k %= 1000000007
    dic[i] = k
    return k

print(dfs(0))

Submission status: Runtime Error

Solution code:
import copy

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

start = 0
stop = N

reached_ = list(range(stop - start + 1))
reached = copy.copy(reached_)
for v in a:
    reached[v] = 'x'
#print(reached)
#history = []

count = 0
def dfs(x):
    global count

    if x > N:
        return

    if x == N:
        count += 1
        #h.append(x)
        #history.append(h)
        #reached[x] = -1
        return
    
    if reached[x] == 'x':
        return
    
    #h.append(x)

    #reached[x] = -1

    dfs(x + 1)
    dfs(x + 2)

    #reached[x] = reached_[x]

dfs(0)
print(count%100000007)
#print(history)

Submission status: Runtime Error

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

stairs = []
is_continuous = False
for i in range(m):
    stairs.append(int(input()))
    if i > 0 and stairs[i] - 1 == stairs[i - 1]:
        is_continuous = True
        break

if is_continuous:
    print(0)
else:
    countup_num = [0] * (n + 1)
    countup_num[0] = 1
    countup_num[1] = 1
    for i in range(2, n + 1):
        countup_num[i] = (countup_num[i - 1] + countup_num[i - 2]) % 1000000007
    res = 1
    diff = 0
    now = 0
    for i in range(m):
        diff = stairs[i] - now - 1
        now = stairs[i] + 1
        res *= (countup_num[diff]) % 1000000007
        # print(res, now)
    diff = n - stairs[-1] - 1
    res *= (countup_num[diff]) % 1000000007

    res %= 1000000007
    # print(countup_num)
    print(res)

Submission status: Runtime Error

Solution code:
MOD=10**9+7
N,M=map(int,input().split())
A=[int(input()) for _ in range(M)]
L=[-1 for _ in range(N)]
p=0
if 1 == A[p]:
  L[0] = 0
  if p < M-1:
    p +=1
else:
  L[0] = 1
if N>1:
  if 2 == A[p]:
    L[1] = 0
    if p < M-1:
      p+=1
  else:
    L[1]=L[0]+1
for i in range(2,N):
  if i+1 == A[p]:
    L[i] = 0
    if p < M-1:
      p+=1
  else:
    L[i]=L[i-1]+L[i-2]
print(L[-1]%MOD)

Submission status: Runtime Error

Solution code:
N, M = map(int,input().split())
A_list = []
for i in range(M):
    A_list.append(int(input()))
if A_list:
    if A_list[0] == 1:
        Dp_list = [1,0]
    elif N == 1:
        print(1)
    else:
        Dp_list = [1,1]
else:
    Dp_list = [1,1]
if A_list and N != 1:
    for i in range(2, N + 1):
        if i not in A_list:
            Dp_list.append(Dp_list[i-2] + Dp_list[i-1])
        elif i in A_list and i-1 in A_list:
            Dp_list = [0] * (N + 1)
            break
        else:
            Dp_list.append(0)
        if Dp_list[i-1] > 1000000007:
            Dp_list[i-1] -= 1000000007
            Dp_list[i] -= 1000000007
	print(Dp_list[N]%1000000007)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
mod = 10**9+7
facs = [1] * n
invs = [1] * n
nfac = 1
for i in range(1, n-m+1):
    nfac = nfac * i % mod
    facs[i] = nfac
    invs[i] = pow(facs[i], mod-2, mod)

ans = 1
start = 0
def steps(start, end):
    t = end - start
    pat = 0
    for j in range(t//2+1):
        pat += (facs[t-j] * invs[j] * invs[t-j-j]) % mod
    return pat%mod

for i in range(m):
    a = int(input())
    end = a-1
    if start == end+1:
        print(0)
        break
    # startからendまで行く方法
    ans *= steps(start, end)
    ans %= mod
    start = a+1
else:
    ans *= steps(start, n)
    ans %= mod
    print(ans)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
mod = 10**9+7
facs = [1] * n
invs = [1] * n
nfac = 1
for i in range(1, n-m+1):
    nfac = nfac * i % mod
    facs[i] = nfac
    invs[i] = pow(facs[i], mod-2, mod)

ans = 1
start = 0
def steps(start, end):
    t = end - start
    pat = 0
    for j in range(-(-t//2)+1):
        pat += (facs[t-j] * invs[j] * invs[t-j-j]) % mod
    return pat

for i in range(m):
    a = int(input())
    end = a-1
    if start == end+1:
        print(0)
        break
    # startからendまで行く方法
    ans *= steps(start, end)
    ans %= mod
    start = a+1
else:
    ans *= steps(start, n)
    ans %= mod
    print(ans)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
mod = 10**9+7
facs = [1] * (n-m)
invs = [1] * (n-m)
nfac = 1
for i in range(1, n-m):
    nfac = nfac * i % mod
    facs[i] = nfac
    invs[i] = pow(facs[i], mod-2, mod)

ans = 1
start = 0
for i in range(m+1):
    try:
        a = int(input())
        end = a-1
    except:
        end = n
    if start-1 == end:
        print(0)
        break
    # startからendまで行く方法
    t = end-start
    pat = 0
    for j in range(-(-t//2)+1):
        pat += (facs[t-j] * invs[j] * invs[t-j-j]) % mod
    ans *= pat
    ans %= mod
    start = a+1
else:
    print(ans)

Submission status: Runtime Error

Solution code:
N, M = map(int,input().split())
A_list = []
for i in range(M):
    A_list.append(int(input()))
if A_list[0] == 1:
    Dp_list = [1,0]
else:
    Dp_list = [1,1]
for i in range(2, N + 1):
    if i not in A_list:
        Dp_list.append(Dp_list[i-2] + Dp_list[i-1])
    elif i in A_list and i-1 in A_list:
        Dp_list = [0] * (N + 1)
        break
    else:
        Dp_list.append(0)
    if Dp_list[i-1] > 1000000007:
        Dp_list[i-1] -= 1000000007
        Dp_list[i] -= 1000000007
print(Dp_list[N]%1000000007)

Submission status: Runtime Error

Solution code:
N, M = map(int,input().split())
A_list = []
for i in range(M):
    A_list.append(int(input()))
if A_list[0] == 1:
    Dp_list = [1,0]
else:
    Dp_list = [1,1]
for i in range(2, N + 1):
    if i not in A_list:
        Dp_list.append(Dp_list[i-2] + Dp_list[i-1])
    elif i in A_list and i-1 in A_list:
        Dp_list = [0] * (N + 1)
        break
    else:
        Dp_list.append(0)
print(Dp_list[N]%1000000007)

Submission status: Runtime Error

Solution code:
n, m = (int(xi) for xi in input().split())

a = []
diff = []
a0 = 0
a1 = int(input())
a.append(a1)
diff.append(a1+1)

if m>1:
    for xi in range(m-1):
        a0 = a1
        a1 = int(input())
        a.append(a1)
        diff.append(a1-a0)

if a1==n-1:
    diff.append(n-a1+1)
else:
    diff.append(n-a1+1)

# print(diff)
# print(a)

p = [0]
p.append(1)
p.append(1)
for xi in range(3,max(diff)+2):
    add = (p[xi-1]+p[xi-2])%1_000_000_007
    p.append(add)

# print(p)

# print(len(diff))
out = 1
for xi in range(len(diff)):
    out *= p[diff[xi]-1]

print(out% 1_000_000_007 )

Submission status: Runtime Error

Solution code:
n, m = (int(xi) for xi in input().split())

a = []
diff = []
a0 = 0
a1 = int(input())
a.append(a1)
diff.append(a1+1)

if m>1:
    for xi in range(m-1):
        a0 = a1
        a1 = int(input())
        a.append(a1)
        diff.append(a1-a0)

if a1==n-1:
    diff.append(n-a1+1)
else:
    diff.append(n-a1+1)

# print(diff)
# print(a)

p = [0]
p.append(1)
p.append(1)
for xi in range(3,max(diff)):
    add = (p[xi-1]+p[xi-2])%1_000_000_007
    p.append(add)

# print(p)

# print(len(diff))
out = 1
for xi in range(len(diff)+2):
    out *= p[diff[xi]-1]

print(out% 1_000_000_007 )

Submission status: Runtime Error

Solution code:
n, m = (int(xi) for xi in input().split())

a = []
diff = []
a0 = 0
a1 = int(input())
a.append(a1)
diff.append(a1+1)

if m>1:
    for xi in range(m-1):
        a0 = a1
        a1 = int(input())
        a.append(a1)
        diff.append(a1-a0)

if a1==n-1:
    diff.append(n-a1+1)
else:
    diff.append(n-a1+1)

# print(diff)
# print(a)

p = [0]
p.append(1)
p.append(1)
for xi in range(3,max(diff)):
    add = (p[xi-1]+p[xi-2])%1_000_000_007
    p.append(add)

# print(p)

# print(len(diff))
out = 1
for xi in range(len(diff)):
    out *= p[diff[xi]-1]

print(out% 1_000_000_007 )

Submission status: Runtime Error

Solution code:
n, m = (int(xi) for xi in input().split())

a = []
diff = []
a0 = 0
a1 = int(input())
a.append(a1)
diff.append(a1+1)

if m>1:
    for xi in range(m-1):
        a0 = a1
        a1 = int(input())
        a.append(a1)
        diff.append(a1-a0)

if a1==n-1:
    diff.append(n-a1+1)
else:
    diff.append(n-a1+1)

# print(diff)
# print(a)

p = [0]
p.append(1)
p.append(1)
for xi in range(3,n-m):
    p.append(p[xi-1]+p[xi-2])

# print(p)

# print(len(diff))
out = 1
for xi in range(len(diff)):
    out *= p[diff[xi]-1]

print(out% 1_000_000_007 )

Submission status: Runtime Error

Solution code:
n, m = (int(xi) for xi in input().split())

a = []
diff = []
a0 = 0
a1 = int(input())
a.append(a1)
diff.append(a1+1)

for xi in range(m-1):
    a0 = a1
    a1 = int(input())
    a.append(a1)
    diff.append(a1-a0)

if a1==n-1:
    diff.append(n-a1+1)
else:
    diff.append(n-a1+1)

# print(diff)
# print(a)

p = [0]
p.append(1)
p.append(1)
for xi in range(3,n-m):
    p.append(p[xi-1]+p[xi-2])

# print(p)

# print(len(diff))
out = 1
for xi in range(len(diff)):
    out *= p[diff[xi]-1]

print(out% 1_000_000_007 )

Submission status: Runtime Error

Solution code:
import math

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

n, m = (int(xi) for xi in input().split())

a = []
diff = 0
a0 = 0
a1 = 0
for xi in range(m):
    a0 = a1
    a1 = int(input())
    a.append(a1)
    if a1-a0>diff :
        diff=a1-a0

print(comb(n,diff))
print(diff)
print(a)

p = [1]
for xi in range(1,diff+1):
    p[xi] = 1
    for j in range(1, int(xi/2)):
        p[xi] += comb(xi-j,j)

Submission status: Runtime Error

Solution code:
def resolve():
    '''
    code here
    '''
    from functools import lru_cache

    N, M = [int(item) for item in input().split()]
    As = [int(input()) for _ in range(M)]
    memo = [False for _ in range(N+1)]

    for item in As:
        memo[item] = True

    res_list = []

    prev = 0
    for i in range(1,N+1):
        if memo[i] == True:
            res_list.append(i-1 - prev)
            prev = i+1
    else:
        if memo[N] == False and memo[N] == False:
            res_list.append(N - prev)

    @lru_cache
    def cal(num):
        if 0 <= num <= 1:
            return 1
        elif num == -1:
            return 0
        else:
            return cal(num-1) + cal(num-2)
    # print(res_list)
    res = 1
    for item in res_list:
        res *= cal(item)% (10**9 + 7)

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



if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
def resolve():
    '''
    code here
    '''
    from functools import lru_cache

    N, M = [int(item) for item in input().split()]
    As = [int(input()) for _ in range(M)]
    memo = [False for _ in range(N+1)]

    for item in As:
        memo[item] = True

    res_list = []

    prev = 0
    for i in range(1,N+1):
        if memo[i] == True:
            res_list.append(i-1 - prev)
            prev = i+1
    else:
        if memo[N] == False and memo[N] == False:
            res_list.append(N - prev)

    @lru_cache
    def cal(num):
        if 0 <= num <= 1:
            return 1
        elif num == -1:
            return 0
        else:
            return cal(num-1) + cal(num-2)
    # print(res_list)
    res = 1
    for item in res_list:
        res *= cal(item)

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



if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
def resolve():
    '''
    code here
    '''
    from functools import lru_cache

    N, M = [int(item) for item in input().split()]
    As = [int(input()) for _ in range(M)]
    memo = [1 for _ in range(N+1)]

    for item in As:
        memo[item] = 0

    res_list = []
    for i in range(1,N+1):
        if i == 1 and memo[i] == 0:
            memo[i] = 0
            res_list.append(2)
        elif memo[i] == 0:
            memo[i] = 0
            res_list.append(memo[i-1])
        else:
            memo[i] += memo[i-1]
    else:
        res_list.append(memo[N])

    
    @lru_cache
    def cal(num):
        if num <= 1:
            return 0
        elif num == 2:
            return 1
        elif num == 3:
            return 2
        else:
            return cal(num-1) + cal(num-2)
    
    res = 1
    for item in res_list:
        res *= cal(item)
    print(res % (10**9 + 7))



if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**5)
N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
MOD = 1000000007
def Fib(n, A, MOD, memo={}):
    if n in A:
        return 0
    elif n == 0:
        return 1
    elif n == 1:
        return 1
    elif n in memo:
        return memo[n]
    else:
        memo[n] = ( Fib(n-1, A, MOD, memo) + Fib(n-2, A, MOD, memo) ) % MOD
        return memo[n]
print(Fib(N, A, MOD))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**10)
N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
MOD = 1000000007
def Fib(n, A, MOD, memo={}):
    if n in A:
        return 0
    elif n == 0:
        return 1
    elif n == 1:
        return 1
    elif n in memo:
        return memo[n]
    else:
        memo[n] = ( Fib(n-1, A, MOD, memo) + Fib(n-2, A, MOD, memo) ) % MOD
        return memo[n]
print(Fib(N, A, MOD))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10*10)
N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
MOD = 1000000007
def Fib(n, A, MOD, memo={}):
    if n in A:
        return 0
    elif n == 0:
        return 1
    elif n == 1:
        return 1
    elif n in memo:
        return memo[n]
    else:
        memo[n] = ( Fib(n-1, A, MOD, memo) + Fib(n-2, A, MOD, memo) ) % MOD
        return memo[n]

print(Fib(N, A, MOD))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10*20)
N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
MOD = 1000000007
def Fib(n, A, MOD, memo={}):
    if n in A:
        return 0
    elif n == 0:
        return 1
    elif n == 1:
        return 1
    elif n in memo:
        return memo[n]
    else:
        memo[n] = ( Fib(n-1, A, MOD, memo) + Fib(n-2, A, MOD, memo) ) % MOD
        return memo[n]

print(Fib(N, A, MOD))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10*50)
N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
MOD = 1000000007
def Fib(n, A, MOD, memo={}):
    if n in A:
        return 0
    elif n == 1:
        return 1
    elif n == 2:
        if 1 in A:
            return 1
        else:
            return 2
    elif n in memo:
        return memo[n]
    else:
        memo[n] = ( Fib(n-1, A, MOD, memo) + Fib(n-2, A, MOD, memo) ) % MOD
        return memo[n]

print(Fib(N, A, MOD))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10*20)
N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
MOD = 1000000007
def Fib(n, A, MOD, memo={}):
    if n in A:
        return 0
    elif n == 1:
        return 1
    elif n == 2:
        if 1 in A:
            return 1
        else:
            return 2
    elif n in memo:
        return memo[n]
    else:
        memo[n] = ( Fib(n-1, A, MOD, memo) + Fib(n-2, A, MOD, memo) ) % MOD
        return memo[n]

print(Fib(N, A, MOD))

Submission status: Runtime Error

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

print(Fib(N, A, MOD))

Submission status: Runtime Error

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

print(Fib(N, A))

Submission status: Runtime Error

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

def main():
    n, m = map(int,input().split())
    mlis = []
    for _ in range(m):
        a = int(input())
        mlis.append(a)
    ans = 1
    mae = 0

   infi = 10 **9 + 7
   for num in mlis:
       ans *= fibona(num-mae)
       ans %= infi
       mae = num + 1

    nobori = n - mae + 1
    ans *= fibona(nobori) 
    ans %= infi
    print(int(ans))
    



if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
def Fib(n):
  seq = []
  a,b = 0,1
  for i in range(1,n+1):
    if i == 1:
      seq.append(0)
    elif i == 2:
      seq.append(1)
    else:
      a, b = b, a + b
      seq.append(b)
  return seq
table = Fib(n)
temp = -1
route = 1
mod = 10**9+7
for _ in range(m):
  a = int(input())
  dif = a-temp-1
  temp = a
  route = route*table[dif]%mod
print(route*table[n-temp]%mod)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
def fibona(x):
    import math
    from decimal import Decimal
    return Decimal(((1/2+math.sqrt(5)/2)**(x+1))-((1/2-math.sqrt(5)/2)**(x+1))) // Decimal(math.sqrt(5))

def main():
    n, m = map(int,input().split())
    mlis = []
    for _ in range(m):
        a = int(input())
        mlis.append(a)
    ans = 1
    mae = -1

    for i in range(m):

        broken = mlis[i]
        if mae == broken - 1:
            print(0)
            exit()

        nobori = (broken-1) - (mae+1)
        if nobori == 0:
            ans *= 1
            mae = broken
        else:
            ans *= fibona(nobori)
            ans %= (10 ** 9 + 7)
            mae = broken

    nobori = n - (mae+1)
    ans *= fibona(nobori) 
    ans %= (10 ** 9 + 7)
    print(int(ans))



if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
a=[int(input()) for i in range(M)]
b=0
c=0
while b<N:
  if b+2 in A:
    b+=1
    c+=1
  else:
    b+=2
    c+=1
print(c)

Submission status: Runtime Error

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

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 fb(n):
    if n == 0:
        return 0
    else:
        F = [ [0, 1],
              [1, 1] ]
        return mat2_pow(F, n-1)[1][1]
l=[]
for _ in range(m):  
  l.append(int(input()))
ans=fb(l[0])
#print(ans)
for i in range(m-1):
  if l[i]+1==l[i+1]:
    print(0)
    exit()
  elif l[i+1]-l[i]>2:
    ans=ans*(fb(l[i+1]-l[i]-1))
print(ans*fb(n-l[m-1])%1000000007)

Submission status: Runtime Error

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

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 fb(n):
    if n == 0:
        return 0
    else:
        F = [ [0, 1],
              [1, 1] ]
        return mat2_pow(F, n-1)[1][1]


l=[]
for _ in range(m):  
  l.append(int(input()))
ans=fb(l[0])
#print(ans)
for i in range(m-1):
  if l[i]+1==l[i+1]:
    print(0)
    exit()
  elif l[i+1]-l[i]>2:
    ans=ans*(fb(l[i+1]-l[i]-1))
print(ans*fb(n-l[m-1])%1000000007)

Submission status: Runtime Error

Solution code:
n, m=map(int, input().split())
def fb(n):    
  if n == 1:
    return 1
  elif n == 2:
    return 2
  else:
    return fb(n-1) + fb(n-2)
#print(fb(4))
l=[]
for _ in range(m):  
  l.append(int(input()))
ans=fb(l[0]-1)
#print(ans)

for i in range(m-1):
  if l[i]+1==l[i+1]:
    print(0)
    exit()
  elif l[i+1]-l[i]>2:
    ans=ans*(fb(l[i+1]-l[i]-1))
print(ans*fb(n-l[m-1]-1)%1000000007)