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 = []
for i in range(M):
    a.append(int(input()))

def fibo(n):
    a, b = 1, 1
    if (n == 0) or (n == 1) or (n == 2):
        return 1
    else:
        for _ in range(n-2):
            a, b = b, a + b
        return b

aa = [] #aの差を取ったもののリスト
for k in range(M-1):
    aa.append(a[k+1] - a[k] - 1)
#print(aa)
#aa.append(N - a(M))

if 0 in aa:
    ans = 0

else:
    ans = 1
    ans_list = []
    for i in range(M-1):
        ans_list.append(fibo(aa[i]))

    ans_list.append(fibo(a[0]))
    ans_list.append(fibo(N - a[M-1]))
    #print(ans_list)
    
    for i in range (len(ans_list)):
        ans = (ans * ans_list[i]) % (10**9 + 7)

print(ans)

Submission status: Runtime Error

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

def fibo(x2):
    if (x2 == 1) or (x2 == 2):
        return (1)
    else:
        return((fibo(x2-1) + fibo(x2-2)) % (10**9 + 7))

aa = [] #aの差を取ったもののリスト
for k in range(M-1):
    aa.append(a[k+1] - a[k] - 1)
#print(aa)
#aa.append(N - a(M))

if 0 in aa:
    ans = 0

else:
    ans = 1
    ans_list = []
    for i in range(M-1):
        if aa[i] >= 1:
            ans_list.append(fibo(aa[i]))

    ans_list.append(fibo(a[0]))
    ans_list.append(fibo(N - a[M-1]))
    #print(ans_list)
    
    for i in range (len(ans_list)):
        ans = (ans * ans_list[i]) % (10**9 + 7)

print(ans)

Submission status: Runtime Error

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

def fibo(x2):
    if (x2 == 1) or (x2 == 2):
        return (1)
    else:
        return((fibo(x2-1) + fibo(x2-2)) % (10**9 + 7))

aa = [] #aの差を取ったもののリスト
for k in range(M-1):
    aa.append(a[k+1] - a[k] - 1)
print(aa)
#aa.append(N - a(M))

if 0 in aa:
    ans = 0

else:
    ans = 1
    ans_list = []
    for i in range(M-1):
        if aa[i] >= 1:
            ans_list.append(fibo(aa[i]))

    ans_list.append(fibo(a[0]))
    ans_list.append(fibo(N - a[M-1]))
    print(ans_list)
    
    for i in range (len(ans_list)):
        ans = (ans * ans_list[i]) % (10**9 + 7)

print(ans)

Submission status: Runtime Error

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

    s[0] = 1
    s[1] = 1 if 1 not in a else 0

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

    print(s[n])

main()

Submission status: Runtime Error

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

s[0] = 1
s[1] = 1 if 1 not in a else 0

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

print(s[n])

Submission status: Runtime Error

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

s[0] = 1
s[1] = 1 if n-1 not in a else 0

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


print(s[n])

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

a1=int(input())
a2=a1
data=[a1]
ans_data=[]
for i in range(M-1):
  a1=a2
  a2=int(input())
  #print("a",a2-a1-1)
  data.append(a2-a1-1)
  
data.append(N-a2-1)
  
data=sorted(data)
#print(data)
if  data[0]==0:
  print(0)
  
elif data[M]==1:
  print(1)
else:
  mm=data.count(1)
  ma=2
  #print("mm=",mm)
  f1=1
  f2=2
  for i in range(0,data[M]+len(data)-2-mm):  
      
    if ma==data[mm]:
      ans_data.append(f2)
      #print("data[mm]",data[mm],"f2",f2,"i",i)
      mm=mm+1
     
    else:
      ma=ma+1
      f11=f1
      f1=f2
      f2=f1+f11
      #print("data[mm]",data[mm],"f2",f2,"ma",ma)
        
        
  ans=1
  #print("ans_data",ans_data)
  for i in range(0,len(ans_data)):
    ans=ans*ans_data[i]
    
  mod=10**9+7
  print(ans%mod)

Submission status: Runtime Error

Solution code:
import math
 
N, M = list(map(int, input().split()))
a = []

for i in range(M):
  a.append(int(input()))
  
answer = 0
# a = [3]
for i in range(len(a) + 1):
	if i == 0:
		dif = a[i] - 1
	elif i == len(a):
		dif = N - a[-1] - 1
	else:
		dif = a[i] - a[i - 1] - 2
	if dif >= 2:
		b = dif // 2
		tmp_sum = 0
		for j in range(b + 1):
			tmp_sum += math.factorial(j + dif - j * 2) / (math.factorial(j) * math.factorial(dif - j * 2))
			# print(tmp_sum)
		if tmp_sum != 0 and answer == 0:
			answer += 1
		answer *= tmp_sum
    
print(int(answer % 1000000007))

Submission status: Runtime Error

Solution code:
import math
 
N, M = list(map(int, input().split()))
a = []

for i in range(M):
  a.append(int(input()))
  
answer = 0
# a = [3]
for i in range(len(a) + 1):
	if i == 0:
		dif = a[i] - 1
	elif i == len(a):
		dif = N - a[-1] - 1
	else:
		dif = a[i] - a[i - 1] - 2
	if dif >= 2:
		b = dif // 2
		tmp_sum = 0
		for j in range(b + 1):
			tmp_sum += math.factorial(j + dif - j * 2) / (math.factorial(j) * math.factorial(dif - j * 2))
			# print(tmp_sum)
		if tmp_sum != 0 and answer == 0:
			answer += 1
		answer *= tmp_sum
    
print(answer % 1000000007)

Submission status: Runtime Error

Solution code:
import math
 
N, M = list(map(int, input().split()))
a = []

for i in range(M):
  a.append(int(input()))
  
answer = 0
# a = [3]
for i in range(len(a) + 1):
	if i == 0:
		dif = a[i] - 1
	elif i == len(a):
		dif = N - a[-1] - 1
	else:
		dif = a[i] - a[i - 1] - 2
	if dif >= 2:
		b = dif // 2
		tmp_sum = 0
		for j in range(b + 1):
			tmp_sum += math.factorial(j + dif - j * 2) / (math.factorial(j) * math.factorial(dif - j * 2))
			# print(tmp_sum)
		if tmp_sum != 0 and answer == 0:
			answer += 1
		answer *= tmp_sum
    
print(answer)

Submission status: Runtime Error

Solution code:
import math
 
N, M = list(map(int, input().split()))
a = []

for i in range(M):
  a.append(int(input()))
  
answer = 0
# a = [3]
for i in range(len(a) + 1):
	if i == 0:
		dif = a[i] - 1
	elif i == len(a):
		dif = N - a[-1] - 1
	else:
		dif = a[i] - a[i - 1] - 2
	if dif >= 2:
		b = dif // 2
		tmp_sum = 0
		for j in range(b + 1):
			tmp_sum += math.factorial(j + dif - j * 2) / (math.factorial(j) * math.factorial(dif - j * 2))
			print(tmp_sum)
		if tmp_sum != 0 and answer == 0:
			answer += 1
		answer *= tmp_sum
    
print(answer)

Submission status: Runtime Error

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

# DP
dp = [1] * (N )
for A in AL:
    dp[A] = 0

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

Submission status: Runtime Error

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

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

for i in A:
    dp[i] = 0

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

print (step[-1] % 1000000007)

Submission status: Runtime Error

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

    S =[0]*(N + 1)
    S[0] = 1
    if A[0] == 1:
        S[1] = 0
    else:
        S[1] = 1

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

Submission status: Runtime Error

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

S =[0]*(N + 1)
S[0] = 1
if A[0] == 1:
    S[1] = 0
else:
    S[1] = 1

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

Submission status: Runtime Error

Solution code:
from sys import stdin
N, M = [int(_) for _ in stdin.readline().rstrip().split()]
dp = [1 for i in range(N+1)]
MOD = 1000000007
for _ in range(M):
  a = int(stdin.readline().rstrip())
  dp[a] = 0
for i in range(2, n+1):
    if dp[i] == 0:
        continue
    dp[i] = dp[i-1]+dp[i-2]
print(dp[N] % MOD)

Submission status: Runtime Error

Solution code:
from sys import stdin
N, M = [int(_) for _ in stdin.readline().rstrip().split()]
dp = [1 for i in range(N+1)]
MOD = 1000000007
for _ in range(M):
  a = int(stdin.readline().rstrip())
  dp[a] = 0
for i in range(2, n+1):
    if dp[i] == 0:
        continue
    dp[i] = dp[i-1]+dp[i-2]
print(dp[n] % MOD)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
ana = [0] * M
ans = [0] * N
mod = 10 ** 9 + 7
if M != 0:
    for i in range(M):
      ans[int(input())-1] = -1

if ans[0] == -1:
    ans[0] = 0
    ans[1] = 1
elif ans[1] == -1:
    ans[0] = 1
    ans[1] = 0
else:
    ans[0] = 1
    ans[1] = 2

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

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
ana = [0] * M
ans = [0] * N
mod = 10 ** 9 + 7
if M != 0:
    for i in range(M):
      ans[int(input())-1] = -1

if ans[0] == -1:
    ans[0] = 0
    ans[1] = 1
elif ans[1] == -1:
    ans[0] = 1
    ans[1] = 0
else:
    ans[0] = 1
    ans[1] = 2

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

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
ana = [0] * M
ans = [0] * N
mod = 10 ** 9 + 7
for i in range(M):
  ans[int(input())-1] = -1

if ans[0] == -1:
    ans[0] = 0
    ans[1] = 1
elif ans[1] == -1:
    ans[0] = 1
    ans[1] = 0
else:
    ans[0] = 1
    ans[1] = 2

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

Submission status: Runtime Error

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

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

for _ in range(M):
  i = int(input()) + 1
  step[i] = -1

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

print (ans % 1000000007)

Submission status: Runtime Error

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

ans = 0

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

for _ in range(M):
  i = int(input()) + 1
  step[i] = -1

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

print (step[N] % 1000000007)

Submission status: Runtime Error

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

ans = 0

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

for _ in range(M):
  i = int(input()) + 1
  step[i] = -1

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

print (ans % 1000000007)

Submission status: Runtime Error

Solution code:
import math
mod = 10**9+7

def stairs(n):
    a = 1/math.sqrt(5)
    b = (1+math.sqrt(5))/2
    c = (1-math.sqrt(5))/2
    return int(a*(b**(n+1)-c**(n+1)))%mod

def main():
    n,m = map(int,input().split(' '))
    a=[-1]
    a_list=[]
    ans = 1
    if m !=0:
        for i in range(m):
            a.append(int(input()))
        a.append(n+1)
        for i in range(m+1):
            a_list.append(a[i+1]-a[i]-2)
        for i in a_list:
            if i <0:
                ans = 0
                break
            ans *= stairs(i)
            ans %= mod
        print(ans)
    else:
        print(stairs(n)%mod)

main()

Submission status: Runtime Error

Solution code:
n,m = [int(i) for i in input().split()]
a = {int(input()) for i in range(m)}
dp = {}
def stairs(step):
  if step in a:
    return 0
  if step == 1:
    return 1
  if step == 2:
    return stairs(step-1) + 1
  if step in dp.keys():
    return dp[step]
  else:
    dp[step] = stairs(step-1) + stairs(step-2)
    return dp[step]
print(int(stairs(n)%1000000007))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
a = int(input())
P = [0]*(N+1)
P[0] = 1
if a == 1:
  P[1] = 0
  try:
    a = int(input())
  except EOFError:
    pass
    
else:
  P[1] = 1

for i in range(2,N+1):
  if i == a:
    P[i] = 0
    try:
      a = int(input())
    except EOFError:
      continue
  else:
    P[i] = P[i-1] + P[i-2]
print(P[-1]%1000000007)

Submission status: Runtime Error

Solution code:
import math
mod = 10**9+7

def stairs(n):
    a = 1/math.sqrt(5)
    b = (1+math.sqrt(5))/2
    c = (1-math.sqrt(5))/2
    return int(a*(b**(n+1)-c**(n+1)))%mod

def main():
    n,m = map(int,input().split(' '))
    a=[-1]
    a_list=[]
    ans = 1
    for i in range(m):
        a.append(int(input()))
    a.append(n+1)
    for i in range(m+1):
        a_list.append(a[i+1]-a[i]-2)
    for i in a_list:
        if i <0:
            ans = 0
            break
        ans *= stairs(i)
        ans %= mod
    print(ans)

main()

Submission status: Runtime Error

Solution code:
import math
mod = 10**9+7

def stairs(n):
    a = 1/math.sqrt(5)
    b = (1+math.sqrt(5))/2
    c = (1-math.sqrt(5))/2
    return int(a*(b**(n+1)-c**(n+1)))%mod

def main():
    n,m = map(int,input().split(' '))
    a=[-1]
    a_list=[]
    ans = 1
    for i in range(m):
        a.append(int(input()))
    a.append(n+1)
    for i in range(m+1):
        a_list.append(a[i+1]-a[i]-2)
    print(a_list)
    for i in a_list:
        if i <0:
            ans = 0
            break
        ans *= stairs(i)
        ans %= mod
    print(ans)

main()

Submission status: Runtime Error

Solution code:
mod = 10**9+7

def stairs(n):
    if n == 0:
        return 1
    elif n == 1:
        return 1
    else:
        return stairs(n-1)%mod+stairs(n-2)%mod

def main():
    n,m = map(int,input().split(' '))
    a=[-1]
    a_list=[]
    ans = 1
    for i in range(m):
        a.append(int(input()))
    a.append(n+1)
    for i in range(m+1):
        a_list.append(a[i+1]-a[i]-2)
    for i in a_list:
        if i <0:
            ans = 0
            break
        ans *= stairs(i)
        ans %= mod
    print(ans)

main()

Submission status: Runtime Error

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

for i in range(2,N+1):
  if i == a:
    P[i] = 0
    try:
      a = int(input())
    except EOFError:
      continue
  else:
    P[i] = P[i-1] + P[i-2]
print(P[-1]%1000000007)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
using namespace std;
typedef long long int ll;
#define dame { puts("-1"); return 0;}
#define yn {puts("Yes");}else{puts("No");}


int main() {
    int n,m;
    cin >> n >> m;
    int no[m+1];
    rep(i,m){
        cin >> no[i];
    }
    no[m] = 99999999;
    int count = 0;

    ll dp[n+1] = {};

    ll ans = 0;

    dp[0] = 1;
    dp[1] = 1;
    if(no[count]==1){
        dp[1] = 0;
        count++;
    }

    srep(i,2,n+1){
        dp[i] = dp[i-1] + dp[i-2];
        if(no[count]==i){
            dp[i] = 0;
            count++;
        }
    }

    cout << dp[n] << endl;
    return 0;
}

Submission status: Runtime Error

Solution code:
import sys

n1, n2 = [int(i) for i in input().split()]

na1 = []

for i1 in range(n2):
    na1.append(int(input()))

for i3 in range(n2):
    if i3 == 0:
        continue
    else:
        if na1[i3] == na1[i3 - 1] + 1:
            print("0")
            sys.exit()

if na1[n2 -1] == n1:
    print("0")
    sys.exit()
    

n3 = 0
n4 = 0
n5 = 0
n6 = 0
n7 = 0
r1 = 0
r2 = []
f1 = False
for i2 in range(n1 ):
    if len(na1) > n7 and (na1[n7] == i2 + 1 ):
        n3 = 0
        n4 = 0
        n6 = 0
        n7 += 1
        if r1 == 0:
            r1 = 1
        r2.append(r1)
        f1 = True

    else:
        if f1 == True:
            f1 = False
            continue
        if n4 == 0 :
            n4 = 1
            r1 = 1
        elif n3 == 0 :
            n3 = 1
            n4 = 2
            r1 = 2
        else:
            n6 = n3 + n4
            r1 = n6
            n3 = n4
            n4 = n6
    if i2 == (n1 - 1) :
        r2.append(r1)

r3 = 1
for i6 in range(len(r2)):
    r3 *= r2[i6]

print(r3 % 1000000007)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
steps = [True] * (N + 1)
for _ in range(M):
    steps[int(input())] = False
dp = [0] * (N + 1)
dp[0] = 1
for prev in range(N):
    for now in range(prev + 1, min(N, prev + 2) + 1):
        if steps[now]:
            dp[now] += dp[prev]
            dp[now] %= 1_000_000_007
print(dp[N])

Submission status: Runtime Error

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

S = [0] * (N+1)
for n in range(N+1):
    if str(n) in a:
        S[n] = 0
    elif n<=1:
        S[n] = 1
    else:
        S[n] = S[n-1] + S[n-2]

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
a = set(int(i) for i in input().split())

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

for i in range(1,N+1):
    if i in a:
        dp[i] = 0
        continue
    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 = set(int(i) for i in input().split())

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

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

print(dp[N])

Submission status: Runtime Error

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

b = []
start = 0
for x in a:
    b += [-start+x]
    start = x+1
b  += [-start+n+1]

from functools import lru_cache
@lru_cache(maxsize=None)
def steps(N):
    if N in [1,2]:
        return 1
    else:
        return steps(N-1)+steps(N-2)

if 0 in b:
    print(0)

else:
    ans = 1
    for z in b:
        ans *= steps(z)

    print(ans%full)

Submission status: Runtime Error

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

if a[1] == 0:
    a[2] = 1
else:
    a[1] = 1
    if a[2] != 0:
        a[2] = 2
        
for i in range(3,n+1):
    if a[i] != 0:
        a[i] = a[i-1] + a[i-2]
#print(a)
print(a[n] % mod)

Submission status: Runtime Error

Solution code:
from functools import lru_cache

def main(N, M, a_list):
    div = 10**9 + 7
    @lru_cache(maxsize=None)
    def fib(n):
        if n in a_list:
            return 0
        else:
            if n == -1:
                return 0
            elif n == 0 or n == 1:
                return 1
            else:
                return fib(n-1) % div + fib(n-2) % div
    
    
    print(fib(N) % div )




if __name__ == "__main__":
    N, M = [int(x) for x in input().split()]
    a_list = []
    for _ in range(M):
        a_list.append(int(input()))

    main(N, M, a_list)

Submission status: Runtime Error

Solution code:
# 2019 6/9
# ABC129 C Typical Stairs
# fn: ways from 0 to n
# f(n) = f(n-1) + f(n-2)
# DP

import sys
import numpy as np


def fib(n):
    a = (1 + np.sqrt(5)) / 2
    b = (1 - np.sqrt(5)) / 2
    ans = (a**n - b**n) / np.sqrt(5)
    return int(ans)


def check_hole(M, broken_stairs):
    if len(broken_stairs) <= 1:
        return True
    for i in range(M - 1):
        if broken_stairs[i + 1] - broken_stairs[i] == 1:
            return False
    return True


if __name__ == '__main__':
    N, M = list(map(int, input().split()))
    broken_stairs = []
    for i in range(M):
        broken_stairs.append(int(input()))

    length = len(broken_stairs)
    if length == 0:
        print(fib(N) % 1000000007)
        sys.exit()

    able = check_hole(M, broken_stairs)
    if not able:
        print(0)
    else:
        ans = fib(N - 2 * length)
        print(ans % 1000000007)

Submission status: Runtime Error

Solution code:
from functools import lru_cache

def main(N, M, a_list):
    @lru_cache(maxsize=None)
    def fib(n):
        if n in a_list:
            return 0
        else:
            if n == -1:
                return 0
            elif n == 0 or n == 1:
                return 1
            else:
                return fib(n-1) + fib(n-2)
    
    div = 10**9 + 7
    print(fib(N) % int(div))




if __name__ == "__main__":
    N, M = [int(x) for x in input().split()]
    a_list = []
    for _ in range(M):
        a_list.append(int(input()))

    main(N, M, a_list)

Submission status: Runtime Error

Solution code:
import math
 
N, M = map(int, input().split())
a = []
for i in range(M):
  a.append(int(input()))
  
answer = 0
for i in range(len(a) - 1):
  dif = a[i + 1] - a[i]
  if dif >= 4:
    b = dif // 2
    tmp_sum = 0
    for j in range(b):
      tmp_sum += math.factorial(j + dif - j * 2) / (math.factorial(j) * math.factorial(dif - j * 2))
    if tmp_sum != 0 and answer = 1:
      answer += 1
    answer *= tmp_sum
    
print(answer)

Submission status: Runtime Error

Solution code:
import math
print(math.factorial(5))

N, M = map(int, input().split())
a = []
for i in range(M):
  a.append(int(input()))
  
answer = 0
for i in range(len(a) - 1):
  dif = a[i + 1] - a[i]
  if dif >= 4:
    b = dif // 2
    tmp_sum = 0
    for j in range(b):
      tmp_sum += math.factorial(j + dif - j * 2) / (math.factorial(j) * math.factorial(dif - j * 2))
    if tmp_sum != 0 and answer = 1:
      answer += 1
    answer *= tmp_sum
    
print(answer)

Submission status: Runtime Error

Solution code:
# 2019 6/9
# ABC129 C Typical Stairs
# fn: ways from 0 to n
# f(n) = f(n-1) + f(n-2)
# DP

import sys
sys.setrecursionlimit(100000)

dp = [-1] * 10005




CNT = 0
dp_list = [-1] * (100000 + 5)


def check_hole(M, broken_stairs):
    if len(broken_stairs) <= 1:
        return True
    for i in range(M - 1):
        if broken_stairs[i + 1] - broken_stairs[i] == 1:
            return False
    return True


def fib(n):
    global dp_list
    if n == 0 or n == 1 or n == 2:
        dp_list[0] = 0
        dp_list[1] = 1
        dp_list[2] = 2
        return dp_list[n]
    if dp_list[n] != -1:
        return dp_list[n]
    else:
        dp_list[n] = fib(n-1) + fib(n-2)
        return dp_list[n]


def count(broken_stairs, top_N, M):
    head = -1
    count_list = []
    if M == 1:
        count_list.append(broken_stairs[0] - 1)
        count_list.append(top_N - broken_stairs[0] - 1)
        return count_list
    else:
        for i in range(M):
            count_list.append(broken_stairs[i] - head - 2)
            head = broken_stairs[i]
        count_list.append(top_N - broken_stairs[-1] - 1)
        return count_list


def find_ans(broken_stairs, top_N, M):
    global CNT
    tmp = 1
    holes = count(broken_stairs, top_N, M)
    print('holes', holes)
    for i in holes:
        if i == 0:
            i = 1
        tmp *= fib(i)
    return tmp


if __name__ == '__main__':
    N, M = list(map(int, input().split()))
    broken_stairs = []
    for i in range(M):
        broken_stairs.append(int(input()))

    if M == 0:
        print(fib(N) % 1000000007)
        sys.exit()
    able = check_hole(M, broken_stairs)
    if not able:
        print(0)
    else:
        ans = find_ans(broken_stairs, N, M)
        print(dp_list[:10])
        print(ans % 1000000007)

Submission status: Runtime Error

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

hole_count = 0
pattern = [0,1]

a = int(input())
hole_count += 1

for i in range(n):
    index = i + 1
    if index == a:
        pattern.append(0)
        if hole_count < m:
            a = int(input())
            hole_count += 1
    else:
        pattern.append(pattern[-1] + pattern[-2])

print(pattern[-1] % 1000000007)

Submission status: Runtime Error

Solution code:
# 2019 6/9
# ABC129 C Typical Stairs
# fn: ways from 0 to n
# f(n) = f(n-1) + f(n-2)
# DP

import sys
sys.setrecursionlimit(100000)

dp = [-1] * 10005




CNT = 0
dp_list = [-1] * (100000 + 5)


def check_hole(M, broken_stairs):
    if len(broken_stairs) <= 1:
        return True
    for i in range(M - 1):
        if broken_stairs[i + 1] - broken_stairs[i] == 1:
            return False
    return True


def fib(n):
    global dp_list
    if n == 0 or n == 1 or n == 2:
        dp_list[0] = 0
        dp_list[1] = 1
        dp_list[2] = 2
        return dp_list[n]
    if dp_list[n] != -1:
        return dp_list[n]
    else:
        dp_list[n] = fib(n-1) + fib(n-2)
        return dp_list[n]


def count(broken_stairs, top_N, M):
    head = -1
    count_list = []
    if M == 1:
        count_list.append(broken_stairs[0] - 1)
        count_list.append(top_N - broken_stairs[0] - 1)
        return count_list
    else:
        for i in range(M):
            count_list.append(broken_stairs[i] - head - 2)
            head = broken_stairs[i]
        count_list.append(top_N - broken_stairs[-1] - 1)
        return count_list


def find_ans(broken_stairs, top_N, M):
    global CNT
    tmp = 1
    holes = count(broken_stairs, top_N, M)
    print('holes', holes)
    for i in holes:
        if i == 0:
            i = 1
        tmp *= fib(i)
    return tmp


if __name__ == '__main__':
    N, M = list(map(int, input().split()))
    broken_stairs = []
    for i in range(M):
        broken_stairs.append(int(input()))

    if M == 0:
        print(fib(N) / 1000000007)
        sys.exit()
    able = check_hole(M, broken_stairs)
    if not able:
        print(0)
    else:
        ans = find_ans(broken_stairs, N, M)
        print(dp_list[:10])
        print(ans % 1000000007)

Submission status: Runtime Error

Solution code:
from functools import lru_cache


@lru_cache(maxsize=10000000)
def get_ways(n):
    if n == 1 or n == 2:
        return n
    elif n == 0:
        return 1
    elif n == -1:
        return 0
    else:
        return get_ways(n - 2) + get_ways(n - 1)


N, M = map(int, input().split())
ans = 1
tmp = 0
for i in range(M):
    a = int(input())
    ans *= get_ways(a - tmp - 1)
    tmp = a + 1
ans *= get_ways(N - tmp)
print(ans % 1000000007)

Submission status: Runtime Error

Solution code:
from functools import lru_cache


@lru_cache(maxsize=100000)
def get_ways(n):
    if n == 1 or n == 2:
        return n
    elif n == 0:
        return 1
    elif n == -1:
        return 0
    else:
        return get_ways(n - 2) + get_ways(n - 1)


N, M = map(int, input().split())
ans = 1
tmp = 0
for i in range(M):
    a = int(input())
    ans *= get_ways(a - tmp - 1)
    tmp = a + 1
ans *= get_ways(N - tmp)
print(ans % 1000000007)

Submission status: Runtime Error

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

dp =[0]*(n+1)
if 0 in a:
    dp[0] =0
else:
    dp[0]=1

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

for i in range(2,n+1):

    if dp[i-1]==dp[i-2]==0:break

    dp[i] = (dp[i-2]+dp[i-1])

    if i in a[i]:
        dp[i] = 0

print(dp[-1]%1000000007)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
b = [] 
for i in range(n+1):
  if i == 0 or i == 1:
    b.appned(1)
  else:
    b.append(b[i-2]+b[i-1])

ans = 1
if m != 0:
  a = list(range(m))
  for i in range(m):
    a[i] = int(input())
    if i == 0:
      ans = ans*b[a[i]-1]%1000000007
    else:   
      ans = ans*b[a[i]-a[i-1]-2]%1000000007
  ans = ans*b[n-a[m-10]-1]%1000000007
  print(ans)
else:
  print(b[n]%1000000007)