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:
import sys

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

def sum(x):
    if x==1:
        return x
    if x==2:
        return x
    return sum(x-1)+sum(x-2)

if m==0:
  print(sum(n))
  sys.exit()

if m==1 and n==1:
  print('0')
  sys.exit()

if m==1 and n==2:
  print('1')
  sys.exit()

if m==1:
  print(sum(n-a[-1]-1))
  sys.exit()
  
for i in range(1,m):
  if a[i]-a[i-1]==1:
    print('0')
    sys.exit()

c=[] #1段ずつ連続して存在する階段の移動方法がそれぞれ何通りあるか

for i in range(m):
  if i==0:
    c.append(sum(a[i]-1))
  else:
    c.append(sum(a[i]-a[i-1]-2))

c.append(sum(n-a[-1]-1))


import functools
import operator

p=functools.reduce(operator.mul,c)

print(p%1000000007)

Submission status: Runtime Error

Solution code:
import sys

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

def sum(x):
    if x==1:
        return x
    if x==2:
        return x
    return sum(x-1)+sum(x-2)

if m==0:
  print(sum(n))
  sys.exit()
  
for i in range(1,m):
  if a[i]-a[i-1]==1:
    print('0')
    sys.exit()

c=[] #1段ずつ連続して存在する階段の移動方法がそれぞれ何通りあるか

for i in range(m):
  if i==0:
    c.append(sum(a[i]-1))
  else:
    c.append(sum(a[i]-a[i-1]-2))

c.append(sum(n-a[-1]-1))


import functools
import operator

p=functools.reduce(operator.mul,c)

print(p%1000000007)

Submission status: Runtime Error

Solution code:
import sys

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

for i in range(1,m):
  if a[i]-a[i-1]==1:
    print('0')
    sys.exit()


def sum(x):
    if x==1:
        return x
    if x==2:
        return x
    return sum(x-1)+sum(x-2)

c=[] #1段ずつ連続して存在する階段の移動方法がそれぞれ何通りあるか

for i in range(m):
  if i==0:
    c.append(sum(a[i]-1))
  else:
    c.append(sum(a[i]-a[i-1]-2))

c.append(sum(n-a[-1]-1))


import functools
import operator

p=functools.reduce(operator.mul,c)

print(p%1000000007)

Submission status: Runtime Error

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

def sum(x):
    if x==1:
        return x
    if x==2:
        return x
    return sum(x-1)+sum(x-2)
  
b=sum(n) #壊れた階段がない場合の移動方法が何通りあるか

c=[] #1段ずつ連続して存在する階段の移動方法がそれぞれ何通りあるか

for i in range(m):
  if i==0:
    c.append(sum(a[i]-1))
  else:
    c.append(sum(a[i]-a[i-1]-2))

c.append(sum(n-a[-1]-1))


import functools
import operator

p=functools.reduce(operator.mul,c)

print(p%1000000007)

Submission status: Runtime Error

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

def sum(x):
    if x==1:
        return x
    if x==2:
        return x
    return sum(x-1)+sum(x-2)
  
b=sum(n) #壊れた階段がない場合の移動方法が何通りあるか


c=0 #壊れた段が含めていた組合せ

for i in a:
  c+=sum(n-i)*(i-1)

d=0 #壊れた段を2段飛ばしで跨いだ組合せ

for i in a:
  d+=sum(n-i-1)*(i-1)

if (b-c-d)>0:
  print((b-c-d)%1000000007)
else:
  print('0')

Submission status: Runtime Error

Solution code:
#import math

#def f(n):
#    global memo
#    if memo[n]==0:
#        ans = 0
#        for i in range(n+1):
#            cnt_1 = n - 2*i
#            cnt_2 = 0 + 1*i
#            if cnt_1 < 0:
#                break
#            else:
#                ans += math.factorial(cnt_1+cnt_2)//(math.factorial(cnt_1)*math.factorial(cnt_2))
#        memo[n] = ans
#    return memo[n]

def kaidan(n):
    global memo
    if memo[n]==0:
        if n == 1 or n == 0:
            memo[n] = 1
        else:
            memo[n] = kaidan(n-1)+kaidan(n-2)
    return memo[n]

memo = [0] * (10**5 + 1)

n,m = map(int,input().split())
start = 0
ans = 1
for i in range(m):
    a = int(input())
    if start == a:
        ans = 0
        break
    else:
        ans = ans * kaidan((a-1)-start)
        start = a + 1
ans = ans * kaidan(n-start)
print(ans%1000000007)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
a=[int(input()) for _ in range(m)]
l=[1]+[0 for _ in range(n+5)]
c=0
for x in range(n):
    if x<a[0]:
        l[x+1]+=l[x]
        l[x+2]+=l[x]
    if x==a[0]:
        if len(a)>=2:a.pop(0)
        else:a[0]=200000
print(l[n]%(10**9+7))

Submission status: Runtime Error

Solution code:
def fib_memo(x):
  memo=[0]*(x+1)
  def fib(x):
    if x==0 or x==1:
      return 1
    elif memo[x]!=0:
      return memo[x]
    else:
      memo[x]=fib(x-1)+fib(x-2)
      return memo[x]
  return fib(x)

n,m=[int(x) for x in input().split()]
a=[-1]
for i in range(m):
  p=int(input())
  a.append(p)
a.append(n+1)
ans=1
c=1
for i in range(m+1):
  if a[i+1]-a[i]-2<0:
    print(0)
    c=0
    break
  elif a[i+1]-a[i]-2==0:
    ans*=1
  else:
    ans*=((fib_memo(a[i+1]-a[i]-2))%1000000007)
    ans=ans%1000000007
if c==1:
  print(ans)

Submission status: Runtime Error

Solution code:
def fib_memo(x):
  memo=[0]*(x+1)
  def fib(x):
    if x==0 or x==1:
      return 1
    elif memo[x]!=0:
      return memo[x]
    else:
      memo[x]=fib(x-1)+fib(x-2)
      return memo[x]
  return fib(x)

n,m=[int(x) for x in input().split()]
a=[-1]
for i in range(m):
  p=int(input())
  a.append(p)
a.append(n+1)
ans=1
c=1
for i in range(m+1):
  if a[i+1]-a[i]-2<0:
    print(0)
    c=0
    break
  elif a[i+1]-a[i]-2==0:
    ans*=1
  else:
    ans*=(fib_memo(a[i+1]-a[i]-2))
    ans=ans%1000000007
if c==1:
  print(ans)

Submission status: Runtime Error

Solution code:
n,m=list(map(int,input().split()))
stair=[0]*(n+1)
for i in range(m):
    s=list(map(int,input().split()))
    stair[s[0]]=-1
stair[-1]=1
stair[-2]=1
for i in range(n-2,-1,-1):
    if stair[i]==-1:continue
    elif stair[i+1]==-1:stair[i]=stair[i+2]
    elif stair[i+2]==-1:stair[i]=stair[i+1]
    else:stair[i]=stair[i+1]+stair[i+2]
    print(i,stair)
print(stair)

Submission status: Runtime Error

Solution code:
n,m,*L = map(int,open(0).read().split())
mod = 10**9+7

dp = [0]*(n)
if 1 in L:
    dp[0] = 0
    dp[1] = 1
elif 1 not in L:
    dp[0] = 1
    dp[1] = 2

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
A = set([]); MOD = pow(10,9)+7
for i in range(M):
  a = int(input())
  A.add(a-1)
dp = [[0]*2 for _ in range(N)] #dp[i][j] i段目(0index)にj=0最後1段でj=1最後2段できた。
if 0 not in A:
  dp[0][0] = 1
if 1 not in A:
  dp[1][0] = dp[0][0]+dp[0][1]
  dp[1][1] = 1
for i in range(2,N):
  if i in A:
    continue
  dp[i][0] = (dp[i-1][0]+dp[i-1][1])%MOD
  dp[i][1] = (dp[i-2][0]+dp[i-2][1])%MOD
ans = sum(dp[N-1])%MOD
#print(dp)
print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
broken = [int(input()) for i in range(m)]
def upstair(k):
    if k in broken:
        return 0
    if k == n-1:
        return 1
    if k == n-2:
        return 2
    return upstair(k+1)+upstair(k+2)
print(upstair(0)%(10**9 + 7))

Submission status: Runtime Error

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

a = []
for _ in range(m):
    a.append(int(input()))
a.append(n+1)

def solve(a,n,m):
    for i in range(len(a)-1):
        if a[i+1] == a[i] + 1:
            return 0

    a_diff = [a[0]-1]
    for i in range(1, m+1):
        a_diff.append(a[i] - a[i-1] - 2)
    ans = 1
    for y in a_diff:
        ans *= count_way(y)
    return ans

def count_way(n):
    memo = [0]*(n+1)
    memo[0] = 1
    memo[1] = 1
    for j in range(n+1):
        memo[j] = memo[j-1] + memo[j-2]
    return memo[n]

print(solve(a,n,m)%1000000007)

Submission status: Runtime Error

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

a = []
for _ in range(m):
    a.append(int(input()))
a.append(n+1)

def solve(a,n,m):
    for i in range(len(a)-1):
        if a[i+1] == a[i] + 1:
            return 0

    a_diff = [a[0]-1]
    for i in range(1, m+1):
        a_diff.append(a[i] - a[i-1] - 2)
    ans = 1
    for y in a_diff:
        ans *= count_way(y)
    return ans

def count_way(n):
    memo = [0]*(n+1)
    memo[0] = 1
    memo[1] = 1
    for j in range(n+1):
        memo[j] = memo[j-1] + memo[j-2]
    return memo[n]

print(solve(a,n,m)/1000000007)

Submission status: Runtime Error

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

a = []
for _ in range(m):
    a.append(int(input()))
a.append(n+1)

def solve(a,n,m):
    for i in range(len(a)-1):
        if a[i+1] == a[i] + 1:
            return 0

    a_diff = [a[0]-1]
    for i in range(1, m+1):
        a_diff.append(a[i] - a[i-1] - 2)
    ans = 1
    for y in a_diff:
        ans *= count_way(y)
    return ans

def count_way(n):
    memo = [0]*(n+1)
    memo[0] = 1
    memo[1] = 1
    for j in range(n+1):
        memo[j] = memo[j-1] + memo[j-2]
    return memo[n]

print(solve(a,n,m))

Submission status: Runtime Error

Solution code:
from scipy.special import comb
 
a = list(map(int, input().split()))
b = [int(input()) for i in range(a[1])]

count = 0
for i in range(a[1]):
  if (b[i] + 1 == b[i+1] && a[1] >= 2) :
    print("0")
    return 0;
  else :
    if i == 0:
      // x + 2y = b[i]
      if (b[i]-1) % 2 == 1: // b[i] = 2m + 1, x = 2n + 1, y = m - n
        for j in range(b[i] - b[i-1] - 1, 0, -2):
          x = j
          y = (b[i] - x)/2
          if x>=1 && y>=1 :
            count += comb(x+y, y, exact=True)
          else :
            count += 1
      else : // b[i] = 2m, y = 2n, x = b[i] - y
        for j in range((b[i] - 1)/2, -1, -1):
          y = j
          x = b[i] - 2*y
          if x>=1 && y>=1 :
            count += comb(x+y, y, exact=True)
          else :
            count += 1
    else :
      // x + 2y = b[i]
    if (b[i]-b[i-1]-1) % 2 == 1: // b[i] = 2m + 1, x = 2n + 1, y = m - n
      for j in range(b[i] - b[i-1] - 1, 0, -2):
        x = j
        y = (b[i] - x)/2
        if x>=1 && y>=1 :
          count += comb(x+y, y, exact=True)
        else :
          count += 1
    else : // b[i] = 2m, y = 2n, x = b[i] - y
      for j in range((b[i] - b[i-1] - 1)/2, -1, -1):
        y = j
        x = b[i] - 2*y
        if x>=1 && y>=1 :
          count += comb(x+y, y, exact=True)
        else :
          count += 1
  print(count%1000000007)

Submission status: Runtime Error

Solution code:
from scipy.special import comb

a = list(map(int, input().split()))
b = [int(input()) for i in range(a[1])]
b[-1] = 0
count = 0
for i in range(a[1]):
  if (b[i] + 1 == b[i+1] && a[1] >= 2) :
    print("0")
    return 0;
  else :
    // x + 2y = b[i]
    if (b[i]-b[i-1]-1) % 2 == 1: // b[i] = 2m + 1, x = 2n + 1, y = m - n
      for j in range(b[i] - b[i-1] - 1, 0, -2):
        x = j
        y = (b[i] - x)/2
        if x>=1 && y>=1 :
          count += comb(x+y, y, exact=True)
        else :
          count += 1
    else : // b[i] = 2m, y = 2n, x = b[i] - y
      for j in range((b[i] - b[i-1] - 1)/2, -1, -1):
        y = j
        x = b[i] - 2*y
        if x>=1 && y>=1 :
          count += comb(x+y, y, exact=True)
        else :
          count += 1
  print(count)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split(' '))
l = []
for i in range(m):
    l.append(int(input()))
f = True
ans = 1
a = 0

def fibonacci(n):
    if n == 0:
        return 1
    elif n == 1:
        return 1
    elif n == 2:
        return 2
    else:
        return fibonacci(n-1) + fibonacci(n-2)

if m == 0:
    print(fibonacci(n))
else:
    for i in range(1,m):
        if l[i] - l[i-1] == 1:
            f = False
            print(0)
            break
    
    if f:
        for i in range(m):
            if i == 0:
                ans *= fibonacci(l[i]-1)
            else:
                ans *= fibonacci(l[i]-l[i-1]-2)
        ans *= fibonacci(n-l[m-1]-1)
        print(ans%1000000007)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split(' '))
l = []
for i in range(m):
    l.append(int(input()))
f = True
ans = 1
a = 0

def fibonacci(n):
    if n == 0:
        return 1
    elif n == 1:
        return 1
    elif n == 2:
        return 2
    else:
        return fibonacci(n-1) + fibonacci(n-2)

for i in range(1,m):
    if l[i] - l[i-1] == 1:
        f = False
        print(0)
        break

if f:
    for i in range(m):
        if i == 0:
            ans *= fibonacci(l[i]-1)
        else:
            ans *= fibonacci(l[i]-l[i-1]-2)
    ans *= fibonacci(n-l[m-1]-1)
    print(ans%1000000007)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
 
a = []
for i in range(m):
    a.append(int(input()))
 
dp = [0] * (n + 1)
dp[0] = 1
for now in range(0, n + 1):
    for next_step in range(now + 1, min(n + 1, now + 3)):
        if not next_step in a:
            dp[next_step] += dp[now]
            dp[next_step] %= 1000000007

print(dp[n])

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
 
a = []
for i in range(m):
    a.append(int(input()))
 
dp = [0] * (n + 1)
dp[0] = 1
for now in range(0, n + 1):
    print(now, dp[now])
    for next_step in range(now + 1, min(n + 1, now + 3)):
        if not next_step in a:
            dp[next_step] += dp[now]
            dp[next_step] %= 1000000007

print(dp[n])

Submission status: Runtime Error

Solution code:
import sys

input = sys.stdin.readline

P = 10 ** 9 + 7


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

    is_ok = True
    for i in range(M - 1):
        if A[i] + 1 == A[i + 1]:
            is_ok = False
    if not is_ok:
        print(0)
        exit()

    broken = [False] * (N + 1)
    for a in A:
        broken[a] = True

    dp = [0] * (N + 1)
    dp[0] = 1
    dp[1] = 1 if A[0] != 1 else 0

    for i in range(2, N + 1):
        if broken[i]:
            dp[i] = 0
        else:
            dp[i] = (dp[i - 1] + dp[i - 2]) % P
    
    ans = dp[N]
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import time
MOD = 10**9+7

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

stime = time.time()
F=[0]*n
F[0]=1
F[1]=2
for i in range(2,n):
    F[i]=(F[i-1]+F[i-2])%MOD

etime =time.time()


a=[0]*n
ans=1
for i in range(m):
      a[int(input())-1]+=1

io=-1
for i in range(n-1):
      if 0!=a[i] :
            io=i+1
            if 0!=a[i+1]:
                  print("0")
                  exit()
      else:
            if a[i+1] and i-io>1 :
                  ans*=F[i-io-1]%MOD
                  s=0
i=n-1
ans*=F[i-io-1]%MOD
print(ans%MOD)

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict

stairs = []
steps = []
MOD = 1000000007

n, m = int(input()), int((input()))
stairs = {int(input()):True for i in range(m)}

step = defaultdict(int)
step[0] = 1

for i in range(n):
    if i in stairs.keys():
        step[i] = 0
    else:
        step[i+1] = (step[i] + step[i+1]) % MOD
        step[i+2] = (step[i] + step[i+2]) % MOD

print(step[n])

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
mod = int(1e9 + 7)
one_or_two = [0] + [1] + [2] + [-1] * n
for i in range(3, n + 3):
    one_or_two[i] = (one_or_two[i-1] + one_or_two[i-2]) % mod
ans = 1
if a[0] > 1:
    ans *= one_or_two[a[0]-1]
for i in range(1, m):
    if a[i] - a[i-1] == 2:
        continue
    if a[i] - a[i-1] == 1:
        ans = 0
        break
    ans *= one_or_two[a[i] - a[i-1] - 2]
    ans %= mod
if n - a[-1] > 1:
    ans *= one_or_two[n - a[m-1] - 1]
print(ans % mod)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
mod = int(1e9 + 7)
one_or_two = [0] + [1] + [2] + [-1] * n
for i in range(3, n + 3):
    one_or_two[i] = (one_or_two[i-1] + one_or_two[i-2]) % mod
ans = 1
if a[0] > 1:
    ans *= one_or_two[a[0]-1]
for i in range(1, m):
    if a[i] - a[i-1] == 2:
        continue
    ans *= one_or_two[a[i] - a[i-1] - 2]
    ans %= mod
if n - a[-1] > 1:
    ans *= one_or_two[n - a[m-1] - 1]
print(ans % mod)

Submission status: Runtime Error

Solution code:
# ABC129 C

MOD = 10**9 + 7
n, m = map(int, input().split())
a_l = [int(input()) for _ in range(m)]

dp = [0] * (n+1)
dp[0] = 1
k = 0
if m > 0 and a_l[0] == 1:
    k += 1
else:
    dp[1] = 1

for i in range(2, n+1):
    if m > 0 and i == a_l[k]:
        k = min(k+1, m-1)
        continue
    dp[i] = (dp[i-1] + dp[i-2]) % MOD
    
print(dp[n])

Submission status: Runtime Error

Solution code:
# ABC129 C

MOD = 10**9 + 7
n, m = map(int, input().split())
a_l = [int(input()) for _ in range(m)]

dp = [0] * (n+1)
dp[0] = 1
k = 0
if a_l[0] == 1:
    k += 1
else:
    dp[1] = 1

for i in range(2, n+1):
    if i == a_l[k]:
        k = min(k+1, m-1)
        continue
    dp[i] = (dp[i-1] + dp[i-2]) % MOD
    
print(dp[n])

Submission status: Runtime Error

Solution code:
def fib(n):
    memo = ["EMPTY"] * (n+1)
    def _fib(n):
        if n == 0:
            return 0
        elif n == 1:
            return 1
        elif memo[n] != "EMPTY":
            return memo[n]
        else:
            memo[n] = _fib(n-1) + _fib(n-2)
            return memo[n]
    return _fib(n)

def c(n, m):
  return fib(m-n-1)
  
n,m=map(int, input().split())
a=[]
a.append(-1)
for i in range(m):
  b=int(input())
  a.append(b)
a.append(n+1)
 
ans=1

for i in range(len(a)-1):
  ans=ans*c(a[i], a[i+1])
  

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
def fib(n):
  if n==0:
    return 0
  elif n==1:
    return 1
  else:
    x=fib(n-1)+fib(n-2)
    return x

n,m=map(int, input().split())
a=[]
for i in range(m):
  b=int(input())
  a.append(b)
  
d=[]
if a[0]-1==0:
  d.append(1)
else:
  d.append(a[0]-1)
d.append(n-a[m-1])
for i in range(m-1):
  d.append(a[i+1]-a[i]-1)

ans=1

for i in range(m+1):
  ans=ans*fib(d[i])


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

Submission status: Runtime Error

Solution code:
def fib(n):
  if n==0:
    return 0
  elif n==1:
    return 1
  else:
    x=fib(n-1)+fib(n-2)
    return x

n,m=map(int, input().split())
a=[]
for i in range(m):
  b=int(input())
  a.append(b)
  
d=[]
if a[0]-1==0:
  d.append(1)
else:
  d.append(a[0]-1)
d.append(n-a[m-1])
for i in range(m-1):
  d.append(a[i+1]-a[i]-1)

ans=1

for i in range(m+1):
  ans=ans*fib(d[i])
  
  print(d[i])

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

Submission status: Runtime Error

Solution code:
import sympy as sym 
def fib(n):
    x = sym.symbols('x', nonnegative=True, integer=True)
    Fib = 1 / sym.sqrt(5) * (((1+sym.sqrt(5))/2)**(n) - ((1-sym.sqrt(5))/2)**(n))
    result = Fib.subs(x, n) 
    result = sym.simplify(result) 
    return result
n,m = list(map(int, input("").split()))
a=[]
a.append(-1)
for i in range(m):   
    a.append(int(input()))
a.append(n+1)
out=1
c=10**9+7
for i in range(m+1):
    out*=int(fib(a[i+1]-a[i]-1))
out%=c
print(out)

Submission status: Runtime Error

Solution code:
import math
def fib(q):
    result = int(1 / math.sqrt(5) * (((1+math.sqrt(5))/2)**(q) - ((1-math.sqrt(5))/2)**(q)))
    return result
n,m = list(map(int, input("").split()))
a=[]
a.append(-1)
for i in range(m):   
    a.append(int(input()))
a.append(n+1)
out=1
c=10**9+7
for i in range(m+1):
    out*=int(fib(a[i+1]-a[i]-1))
out%=c
print(out)

Submission status: Runtime Error

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

dp[1] = 1

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

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

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(100000)

MOD = 1000000007


def step_state(n, broken):
    if n == 0:
        return 1
    elif n == 1:
        if broken[1]:
            return 0
        else:
            return 1
    else:
        if broken[n - 1] and broken[n - 2]:
            return 0
        elif broken[n - 1]:
            return step_state(n-2, broken) % MOD
        elif broken[n-2]:
            return step_state(n-1, broken) % MOD
        else:
            return (step_state(n-1, broken)+step_state(n-2, broken)) % MOD


if __name__ == '__main__':
    n, m = map(int, input().split())
    a = set([int(input()) for i in range(m)])
    broken = [False] * (n+1)
    for i in range(n+1):
        if i in a:
            broken[i] = True

    answer = step_state(n, broken)

    print(answer)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(100000)

MOD = 1000000007

state = [-1 for i in range(100010)]

def step_state(n, broken):
    if state[n] != -1:
        return state[n]

    if n == 0:
        state[0]=1
        return 1
    elif n == 1:
        if broken[1]:
            state[1]=0
            return 0
        else:
            state[1]=1
            return 1
    else:
        if broken[n - 1] and broken[n - 2]:
            state[n]=0
            return 0
        elif broken[n - 1]:
            state[n]=step_state(n-2, broken) % MOD
            return state[n]
        elif broken[n-2]:
            state[n] = step_state(n-1, broken) % MOD
            return state[n]
        else:
            state[n] = (step_state(n-1, broken)+step_state(n-2, broken)) % MOD
            return state[n]


if __name__ == '__main__':
    n, m = map(int, input().split())
    a = set([int(input()) for i in range(m)])
    broken = [False] * (n+1)
    for i in range(n+1):
        if i in a:
            broken[i] = True

    answer = step_state(n, broken)

    print(answer)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(100000)

MOD = 1000000007


def step_state(n, broken):
    if n == 0:
        return 1
    elif n == 1:
        if broken[1]:
            return 0
        else:
            return 1
    else:
        if broken[n - 1] and broken[n - 2]:
            return 0
        elif broken[n - 1]:
            return step_state(n-2, broken) % MOD
        elif broken[n-2]:
            return step_state(n-1, broken) % MOD
        else:
            return (step_state(n-1, broken)+step_state(n-2, broken)) % MOD


if __name__ == '__main__':
    n, m = map(int, input().split())
    a = set([int(input()) for i in range(m)])
    broken = [False] * (n+1)
    for i in range(n+1):
        if i in a:
            broken[i] = True

    answer = step_state(n, broken)

    print(answer)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

forbidden = []
for i in range(m):
  forbidden.append(int(input()))

ans = [1, 1]
if 1 in forbidden:
  ans[-1] = 0
for i in range(2,n+1):
  if i in forbbidden:
    ans.append(0)
  else:
    ans.append(ans[-1]+[ans[-2]])
  if ans[-1] == 0 and ans[-2] == 0:
    print(0)
  if i == n:
    print(ans[-1])

Submission status: Runtime Error

Solution code:
import math
def fib(q):
    result = int(1 / math.sqrt(5) * (((1+math.sqrt(5))/2)**(q) - ((1-math.sqrt(5))/2)**(q)))
    return result
n,m = list(map(int, input("").split()))
a=[]
a.append(-1)
for i in range(m):   
    a.append(int(input()))
a.append(n+1)
out=1
c=10**9+7
for i in range(m+1):
    out*=int(fib(a[i+1]-a[i]-1))
    out%=c
print(out)

Submission status: Runtime Error

Solution code:
import math
def fib(q):
    result = int(1 / math.sqrt(5) * (((1+math.sqrt(5))/2)**(q) - ((1-math.sqrt(5))/2)**(q)))
    return result
def o():
    n,m = list(map(int, input("").split()))
    a=[]
    a.append(-1)
    d=0
    for i in range(m):   
        a.append(int(input()))
    a.append(n+1)
    out=1
    c=10**9+7
    for i in range(m+1):
        d=a[i+1]-a[i]-1
        if d==0:
            return 0
        out*=int(fib(d))
        out%=c
    return int(out)
print(o())

Submission status: Runtime Error

Solution code:
import math
def fib(q):
    result = 1 / math.sqrt(5) * (((1+math.sqrt(5))/2)**(q) - ((1-math.sqrt(5))/2)**(q))
    return result
def o():
    n,m = list(map(int, input("").split()))
    a=[]
    a.append(-1)
    for i in range(m):   
        a.append(int(input()))
    a.append(n+1)
    out=1
    c=10**9+7
    for i in range(m+1):
        d=a[i+1]-a[i]-1
        if d==0:
            return 0
        out*=int(fib(d))
        out%=c
    return int(out)
print(o())

Submission status: Runtime Error

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

MOD = pow(10, 9) + 7

dp = [0] * (n+1)

dp[0] = 1

broken = int(input())
c = 1

for i in range(1, n+1):
    if i == broken:
        dp[i] = 0
        if c < m:
            broken = int(input())
            c += 1
    else:
        if i == 1:
            dp[i] = dp[i-1] % MOD
        else:
            dp[i] = (dp[i-1] + dp[i-2]) % MOD

print(dp[n] % MOD)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
lst=[int(input()) for i in range(m)]
DP=[0]*(n+1)
temp=0
DP[0]=1
for i in range(1, n+1):
  if i==1 and not in lst:
    DP[i]=1
  elif i in lst:
    DP[i]=0
  else:
    DP[i]=DP[i-1]+DP[i-2]
print(DP[n]%1000000007)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
ais = []
for _ in range(m):
    ai = int(input())
    ais.append(ai)
dp = [0]*(n+1)
dp[0]=1
if ais[0]==1:
  dp[1]=0
  ais.pop(0)
else:
  dp[1]=1
for i in range(2,n+1):
    if len(ais)>0 and ais[0]==i:
        dp[i] = 0
        ais.pop(0)
    else:
        dp[i] = dp[i-1] + dp[i-2]
print(dp[n]%1000000007)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
broken = set()
for i in range(M):
    broken.add(int(input()))
dp = [0 for i in range(N+1)]
if 1 not in broken:
    dp[1] = 1
if 2 not in broken:
    dp[2] = dp[1] + 1
for i in range(3,N+1):
    if i in broken:
        dp[i] = 0
    else:
        dp[i] = dp[i-1] + dp[i-2]
        dp[i] %= 1000000007
print(dp[N])

Submission status: Runtime Error

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

memo = [-1] * (n + 1)
memo[0] = 1
memo[1] = 1
for i in range(m):
  memo[int(input())] = 0

def fib(x):
  if memo[x] == -1:
    memo[x] = fib(x-1) + fib(x-2)
  return memo[x]

print(fib(n) % 1000000007)

Submission status: Runtime Error

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

memo = [-1] * (n + 1)
memo[0] = 1
memo[1] = 1
for i in range(m):
  memo[int(input())] = 0

def fib(x):
  if memo[x] > -1:
    return memo[x]
  else:
    memo[x] = fib(x-1) + fib(x-2)
    return memo[x]

# print(fib(n))
# print(memo)
print(fib(n) % 1000000007)

Submission status: Runtime Error

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

memo = [-1] * (n + 1)
memo[0] = 1
memo[1] = 1
for i in range(m):
  memo[int(input())] = 0

def fib(x):
  if memo[x] == 0:
    return 0
  if memo[x] > 0:
    return memo[x]
  else:
    memo[x] = fib(x-1) + fib(x-2)
    return memo[x]

# print(fib(n))
# print(memo)
print(fib(n) % 1000000007)

Submission status: Runtime Error

Solution code:
import sys
n,m=map(int,input().split())
a=[]
for i in range(m):
    a.append(int(input()))
a.append(0)
ans=[]
for i in range(m-1):
    if a[i+1]-a[i]==1:
        print(0)
        sys.exit()
ans=[0 for i in range(n+5)]
ans[1]=1
ans[2]=2
d=0
if a[0]==1:
    ans[1]=0
    ans[2]=1
    d+=1
if a[0]==2 or a[1]==2:
    ans[2]=0
    d+=1

for i in range(1,n+3):
    if i+2==a[d]:
        ans[i+2]=0
        d+=1
    else:
        ans[i+2]=ans[i+1]%1000000007+ans[i]%1000000007
   
print(ans[n]%1000000007)

Submission status: Runtime Error

Solution code:
d = {0:1, 1:1, 2:2}
def countcombi(n):
    if n in d:
        return d[n]
    else:
        d[n] = countcombi(n-1)+countcombi(n-2)
        return d[n]
N, M = list(map(int,input().rstrip().split()))
a_now = 0
a_before = 0
ans = 1
for _ in range(M):
    a_now = int(input().rstrip())
    if a_now-a_before == 0 and a_before != 0:
        print(0)
        break
    ans = (ans * countcombi(a_now-a_before-1)) % 1_000_000_007
    a_before = a_now + 1
else:
    a_now = N
    ans = (ans * countcombi(a_now-a_before)) % 1_000_000_007
    print(ans)

Submission status: Runtime Error

Solution code:
from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    else:
        return fib(n - 2) + fib(n - 1)

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

for i in range(len(a)-1):
    if a[i+1] == a[i]+1:
        print(0)
        exit()
x = []
temp=0
for i in range(m):
    x.append(a[i]-temp-1)
    temp = a[i]+1
x.append(n-temp)

temp = 1
div = 1000000007

for i in x:
    temp = (temp*fib(i+1))%div

print(temp)