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())
use=[0]
ans=1
for i in range(m):
    use.append(int(input()))
use.append(n)

if N>=2:        
    lists=[1,2]

    for i in range(n-2):
        lists.append((lists[-1]+lists[-2])%1000000007)

    
    for i in range(m+1):
    
        if use[i+1]-use[i]==1 and i>=1:
            ans=0
            break
        else:
            ans=(ans*lists[int(use[i+1]-use[i]-2)])%1000000007
            
            
    print(ans)
elif N==1:
    print(1)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
use=[0]
ans=1
for i in range(m):
    use.append(int(input()))
use.append(n)
print(use)
if N>=2:        
    lists=[1,2]

    for i in range(n-2):
        lists.append((lists[-1]+lists[-2])%1000000007)

    
    for i in range(m+1):
    
        if use[i+1]-use[i]==1 and i>=1:
            ans=0
            break
        else:
            ans=(ans*lists[int(use[i+1]-use[i]-2)])%1000000007
            
            
    print(ans)
elif N==1:
    print(1)

Submission status: Runtime Error

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

print(dp[-1])

Submission status: Runtime Error

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

print(dp[-1])

Submission status: Runtime Error

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

print(dp[-1])

Submission status: Runtime Error

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

print(dp[-1])

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
aL = [int(input()) for _ in range(m)]
mod = 10**9+7
dp = [0]*(n+1)
dp[0] = 1
dp[1] = 0 if aL[0] == 1 else 1
pos = 1 if aL[0] == 1 else 0
for i in range(n-1):
    if pos < len(aL):
        if i+2 == aL[pos]:
            dp[i+2] = 0
            pos += 1
        else:
            dp[i+2] = (dp[i] + dp[i+1]) % mod
    else:
        dp[i+2] = (dp[i] + dp[i+1]) % mod

print(dp[-1])

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
aL = [int(input()) for _ in range(m)]
mod = 10**9+7
cant = 0
dp = [0]*(n+1)
dp[0] = 1
dp[1] = 0 if aL[0] == 1 else 1
pos = 1 if aL[0] == 1 else 0
for i in range(n-1):
    if pos < len(aL):
        if i+2 == aL[pos]:
            dp[i+2] = 0
            pos += 1
        else:
            dp[i+2] += (dp[i] + dp[i+1]) % mod
    else:
        dp[i+2] += (dp[i] + dp[i+1]) % mod

print(dp[-1])

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
aL = [int(input()) for _ in range(m)]
mod = 10**9+7
cant = 0
dp = [0]*(n+1)
dp[0] = 1
dp[1] = 0 if aL[0] == 1 else 1
for i in range(n-1):
    if i+2 in aL:
        if dp[i+1] > 0:
            dp[i+2] = 0
        else:
            cant = 1
            break
    else:
        dp[i+2] += (dp[i] + dp[i+1]) % mod
if cant == 1:
    print(0)
else:
    print(dp[n])

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
aL = [int(input()) for _ in range(m)]
mod = 10**9+7
cant = 0
dp = [0]*(n+1)
dp[0] = 1
dp[1] = 0 if aL[0] == 1 else 1
pos = 1 if aL[0] == 1 else 0
for i in range(n-1):
    if pos < len(aL):
        if i+2 == aL[pos]:
            if dp[i+1] > 0:
                dp[i+2] = 0
                pos += 1
            else:
                cant = 1
                break
        else:
            dp[i+2] += (dp[i] + dp[i+1]) % mod
    else:
        dp[i+2] += (dp[i] + dp[i+1]) % mod
if cant == 1:
    print(0)
else:
    print(dp[n])

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
aL = [int(input()) for _ in range(m)]
mod = 10**9+7
cant = 0
dp = [0]*(n+1)
dp[0] = 1
dp[1] = 0 if aL[0] == 1 else 1
if dp[1] == 0:
    pos = 1
else:
    pos = 0
for i in range(n-1):
    if pos < len(aL):
        if i+2 == aL[pos]:
            if dp[i+1] > 0:
                dp[i+2] = 0
                pos += 1
            else:
                cant = 1
                break
        else:
            dp[i+2] += (dp[i] + dp[i+1]) % mod
    else:
        dp[i+2] += (dp[i] + dp[i+1]) % mod
if cant == 1:
    print(0)
else:
    print(dp[n])

Submission status: Runtime Error

Solution code:
import numpy as np
nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]
N, M = map(int,input().split())
dv = 1000000007
a = [-1]
for i in range(M):
    a.append(int(input()))
# 不可能チェック
if M!=1:
    for i in range(M-1):
        if a[i+1]-a[i] == 1:
            print(0)
            exit()
b = []
amari = 1
dic = {}
for i in range(M):
    b.append(a[i+1]-a[i]-2)
b.append(N-a[M]-1)
for dist in b:
    if dist%2==0:
        dist = dist//2
        tmp = sum([cmb(dist+x,dist-x) for x in range(dist+1)])
        amari *= tmp % dv
        amari = amari % dv
    else:
        dist = dist//2
        tmp = sum([cmb(dist+x,dist-x-1) for x in range(dist)])
        amari *= tmp % dv
        amari = amari % dv
print(amari)

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
A=[]
B=[]
a=[]
a.append(0)
x=0
d=1
A.append(1)
A.append(2)
B.append(1)
B.append(1)
for j in range(2,N):
    A.append(A[j-1]+A[j-2])
    B.append(B[j-1]+B[j-2])
for i in range(1,M+1):
    a.append(int(input()))
    if a[i-1]==0:
        if a[i]==1:
            d=1
        else:
            x=A[a[i]-a[i-1]-2]
            d=d*x%(10**9+7)
    else:
        x=B[a[i]-a[i-1]-2]
        d=d*x%(10**9+7)
    if i>1:
        if a[i]-a[i-1]==1:
            d=0
            break
c=N-a[M]
if c==1:
    print(d)
else:
    x=A[N-a[M]-2]
    d=d*x%(10**9+7)
    print(d)

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
A=[]
a=[]
a.append(0)
x=0
d=1
A.append(1)
A.append(2)
for j in range(2,N):
    A.append(A[j-1]+A[j-2])
for i in range(1,M+1):
    a.append(int(input()))
    x=A[a[i]-a[i-1]-2]
    d=d*x
    if i>1:
        if a[i]-a[i-1]==1:
            d=0
x=A[N-a[M]-2]
d=d*x
print(A[21],A[11])
print(d%(10**9+7))

Submission status: Runtime Error

Solution code:
import sys
n,m=map(int,input().split())
if m==0:
    x=1
    y=2
    for i in range(n-2):
        if x<y:
            x+=y%1000000007
        else:
            y+=x%1000000007
    print(max(x,y)%1000000007)
    sys.exit()
a=list(int(input()) for i in range (m))

x=['']*n
if a[0]==1:
    x[0]=0
else:
    x[0]=1

if m>=2:
	if a[0]!=2 and a[1]!=2:
		x[1]=x[0]+1
    else:
        x[1]=0
    

if m==1:
    if a[0]!=2:
	       x[1]=x[0]+1
    elif a[0]==2:
        x[1]=0


for z in range(m):
    x[a[z]-1]=0
        
if n>=3:
    for k in range(2,n):
        if x[k]!=0:
            x[k]=x[k-2]%1000000007+x[k-1]%1000000007
            
elif n==1:
    print(1)
    sys.exit()
    
elif n==2:
    print(x[0]+1)
    sys.exit()
    
print(x[n-1]%1000000007)

Submission status: Runtime Error

Solution code:
import sys
n,m=map(int,input().split())
if m==0:
    x=1
    y=2
    for i in range(n-2):
        if x<y:
            x+=y%1000000007
        else:
            y+=x%1000000007
    print(max(x%1000000007,y%1000000007))
    sys.exit()
a=list(int(input()) for i in range (m))

x=['']*n
if a[0]==1:
    x[0]=0
else:
    x[0]=1

if m>=2:
	if a[0]!=2 and a[1]!=2:
		x[1]=x[0]+1
    

else:
    if a[0]!=2:
	       x[1]=x[0]+1
    elif a[0]==2:
        x[1]=0


for z in range(m):
    x[a[z]-1]=0
        
if n>=4:
    for k in range(2,n):
        if x[k]!=0:
            x[k]=x[k-2]%1000000007+x[k-1]%1000000007
            
else:
    x[2]=x[1]+x[0]
print(x[n-1]%1000000007)

Submission status: Runtime Error

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

if m>=2:
	if a[0]!=2 and a[1]!=2:
		x[1]=x[0]+1

if m==1:
    if a[0]!=2:
	       x[1]=x[0]+1

if n>3:
    for k in range(2,n):
        for z in range(m):
            x[a[z]-1]=0
        x[k]=x[k-2]+x[k-1]
else:
    x[2]=x[1]+x[0]
print(x[n-1]%1000000007)

Submission status: Runtime Error

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

if m>=2:
	if a[0]!=2 and a[1]!=2:
		x[1]=x[0]+1

if m==1:
    if a[0]!=2:
	       x[1]=x[0]+1

if n>3:
    for k in range(2,n):
        for z in range(m):
            x[a[z]-1]=0
        x[k]=x[k-2]+x[k-1]
else:
    x[2]=x[1]+x[0]
print(x[n-1]%1000000

Submission status: Runtime Error

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

if m>=2:
	if a[0]!=2 and a[1]!=2:
		x[1]=x[0]+1

if m==1:
    if a[0]!=2:
	       x[1]=x[0]+1

if n>=3:
    for k in range(2,n):
        for z in range(m):
            x[a[z]-1]=0
        x[k]=x[k-2]+x[k-1]
else:
    x[2]=x[1]+x[0]
print(x[n-1]%1000000007)

Submission status: Runtime Error

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

if m>=2:
	if a[0]!=2 and a[1]!=2:
		x[1]=x[0]+1

if m==1:
    if a[0]!=2:
	       x[1]=x[0]+1


for k in range(2,n):
    for z in range(m):
        x[a[z]-1]=0
    x[k]=x[k-2]+x[k-1]

print(x[n-1]%1000000007)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
n,m=map(int,input().split())

a=[int(input()) for i in range(m)]

def fib(n):
    if n==0:
        return 1
    if n==1:
        return 1
    if n==2:
        return 2
    return fib(n-1)+fib(n-2)

ans=1
check=0
for i in a:
    if i-check==1 and i!=1:
        print(0)
        exit()
    if i-check==1 and i==1:
        check=1
    else:
      ans*= fib(i-check-2)
      check=i
ans*=fib(n-a[-1]-1)
print(ans%((10**9)+7))

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
n,m=map(int,input().split())

a=[int(input()) for i in range(m)]

def fib(n):
    if n==1:
        return 1
    if n==2:
        return 2
    return fib(n-1)+fib(n-2)

ans=1
check=0
for i in a:
    if i-check==1 and i!=1:
        print(0)
        exit()
    if i-check==1 and i==1:
        check=2
    else:
      ans*= fib(i-check-1)
      check=i+1
ans*=fib(n-a[-1]-1)
print(ans%((10**9)+7))

Submission status: Runtime Error

Solution code:
import sys
#input = sys.stdin.readline
sys.setrecursionlimit(10**9)
n,m=map(int,input().split())

a=[int(input()) for i in range(m)]

def fib(n):
    if n==1:
        return 1
    if n==2:
        return 2
    return fib(n-1)+fib(n-2)

ans=1
check=0
for i in a:
    if i-check==1 and i!=1:
        print(0)
        exit()
    if i-check==1 and i==1:
        check=2
    else:
      ans*= fib(i-check-1)
      check=i+1
ans*=fib(n-a[-1]-1)
print(ans%((10**9)+7))

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
n,m=map(int,input().split())

a=[int(input()) for i in range(m)]

def fib(n):
    if n==1:
        return 1
    if n==2:
        return 2
    return fib(n-1)+fib(n-2)

ans=0
check=0
for i in a:
    if i-check==1:
        print(0)
        exit()
    ans+= fib(i-check-1)
    check=i
ans+=fib(n-check-1)
print(ans%(10**9+7))

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
n,m=map(int,input().split())

a=[int(input()) for i in range(m)]

def fib(n):
    if n==1:
        return 1
    if n==2:
        return 2
    return fib(n-1)+fib(n-2)

ans=0
check=0
for i in a:
    if i-check==1:
        ans=0
        exit()
    ans+= fib(i-check-1)
    check=i
ans+=fib(n-check-1)
print(ans%(10**9+7))

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
n,m=map(int,input().split())

a=[int(input()) for i in range(m)]

def fib(n):
    if n==1:
        return 1
    if n==2:
        return 2
    return fib(n-1)+fib(n-2)

ans=0
check=0
for i in a:
    if i-check==1:
        ans=0
        break
    ans+= fib(i-check-1)
    check=i
if ans!=0:
    ans+=fib(n-check-1)
print(ans%(10**+7))

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
n,m=map(int,input().split())

a=[int(input()) for i in range(m)]

def fib(n):
    if n==1:
        return 1
    if n==2:
        return 2
    return fib(n-1)+fib(n-2)

ans=0
check=0
for i in a:
    if i-check==1:
        ans=0
        break
    ans+= fib(i-check-1)
    check=i
if ans!=0:
    ans+=fib(n-check-1)
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np

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

ans = np.zeros(N + 1)
ans[N] = 1
broken_a = np.zeros(N)
for a_ in a:
    broken_a[a_] = 1
if broken_a[N-1] != 1:
    ans[N - 1] = 1


for i in range(2, N + 1):
    if broken_a[N - i] != 1:
        ans[N - i] = (ans[N - i + 1] + ans[N - i + 2])
    else:
        ans[N - i] = 0
print(int(ans[0] % (10 ** 9 + 7)))

Submission status: Runtime Error

Solution code:
import numpy as np

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

ans = np.zeros(N + 1)
ans[N] = 1

if N - 1 not in a:
    ans[N - 1] = 1

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

Submission status: Runtime Error

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

n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
a.append(n+1)
seq = [a[0]]

for i in range(m):
    d = a[i+1] - a[i] - 1
    if d == 0:
        print(0)
        sys.exit()
    seq.append(d)

memo = [-1] * 10**5
def fib(i):
    if i == 0: return 0
    elif i == 1: return 1
    elif memo[i] != -1: return memo[i]
    else:
        memo[i] = fib(i-1) + fib(i-2)
        return memo[i]

ans = 1
for s in seq:
    ans *= fib(s)
print(ans % 1000000007)

Submission status: Runtime Error

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

print(count[-1])

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import numpy as np

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

ans = np.zeros(N + 1)
ans[N] = 1

if N - 1 not in a:
    ans[N - 1] = 1

print(ans[N])

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

Submission status: Runtime Error

Solution code:
N, M = [int(nm) for nm in input().split()]
if M != 0:
  a = int(input())
  M -= 1

C = [1, 0] # [-2段目, -1段目]
C += [0]*(N+10) # C = [-2段目, -1段目, 0段目, 1段目, 2段目, ...]
for n in range(0, N+1):
  if n != a or M == 0:
    C[n+2] = (C[n] + C[n+1]) % 1000000007
  else: # n == a and M != 0:
    C[n+2] = 0
    a = int(input())
    M -= 1

ans = C[N+2]  % 1000000007
print(ans)

Submission status: Runtime Error

Solution code:
from math import *

def fib(n):
    return ((1+sqrt(5))**(n+1)  -  (1-sqrt(5))**(n+1)) // (2**(n+1)*sqrt(5))


def how_many_ways(lst_of_broken_steps,goal):

    
    if len(lst_of_broken_steps)==0:#brokenstepがない場合
        return fib(goal)%1000000007

    for i in range(len(lst_of_broken_steps)-1):#連続しているbrokenステップがあった時
        if lst_of_broken_steps[i]+1==lst_of_broken_steps[i+1]:
            return 0


    #1回目のbrokenステップの処理
    ans = fib(lst_of_broken_steps[0]-1)
    ans = ans % 1000000007

    for i in range(1,len(lst_of_broken_steps)):#2回目以降のbrokenステップの処理
        ans *= fib((lst_of_broken_steps[i]-1)-(lst_of_broken_steps[i-1]+1))
        ans = ans%1000000007
    

    #最後のbrokenステップの処理の後からゴールまで
    ans *= fib(goal-(lst_of_broken_steps[-1]+1))

    return ans % 1000000007



goal,n = map(int,input().split())
lst_of_broken_steps = []
for _ in range(n):
    lst_of_broken_steps.append(int(input()))

print(int(how_many_ways(lst_of_broken_steps,goal)))

Submission status: Runtime Error

Solution code:
from math import *

def fib(n):
    return ((1+sqrt(5))**(n+1)  -  (1-sqrt(5))**(n+1)) // (2**(n+1)*sqrt(5))


def how_many_ways(lst_of_broken_steps,goal):

    for i in range(len(lst_of_broken_steps)-1):#連続しているbrokenステップがあった時
        if lst_of_broken_steps[i]+1==lst_of_broken_steps[i+1]:
            return 0
    if len(lst_of_broken_steps)==0:#brokenstepがない場合
        return fib(goal)%1000000007
    #1回目のbrokenステップの処理
    ans = fib(lst_of_broken_steps[0]-1)
    ans = ans % 1000000007

    for i in range(1,len(lst_of_broken_steps)):#2回目以降のbrokenステップの処理
        ans *= fib((lst_of_broken_steps[i]-1)-(lst_of_broken_steps[i-1]+1))
        ans = ans%1000000007
    

    #最後のbrokenステップの処理の後からゴールまで
    ans *= fib(goal-(lst_of_broken_steps[-1]+1))

    return ans % 1000000007



goal,n = map(int,input().split())
lst_of_broken_steps = []
for i in range(n):
    lst_of_broken_steps.append(int(input()))

print(int(how_many_ways(lst_of_broken_steps,goal)))

Submission status: Runtime Error

Solution code:
from math import *

def fib(n):
    return ((1+sqrt(5))**(n+1)  -  (1-sqrt(5))**(n+1)) // (2**(n+1)*sqrt(5))


def how_many_ways(lst_of_broken_steps,goal):

    for i in range(len(lst_of_broken_steps)-1):#連続しているbrokenステップがあった時
        if lst_of_broken_steps[i]+1==lst_of_broken_steps[i+1]:
            return 0
    
    #1回目のbrokenステップの処理
    ans = fib(lst_of_broken_steps[0]-1)
    print(ans)
  

    for i in range(1,len(lst_of_broken_steps)):#2回目以降のbrokenステップの処理
        ans *= fib((lst_of_broken_steps[i]-1)-(lst_of_broken_steps[i-1]+1))
        ans = ans%1000000007
        print(ans)#けす
    

    #最後のbrokenステップの処理の後からゴールまで
    ans *= fib(goal-(lst_of_broken_steps[-1]+1))

    return ans % 1000000007


    
goal,n = map(int,input().split())
lst_of_broken_steps = []
for i in range(n):
    lst_of_broken_steps.append(int(input()))

print(int(how_many_ways(lst_of_broken_steps,goal)))

Submission status: Runtime Error

Solution code:
import math

N,M = (int(i) for i in input().split())
a = [0] * M
mod = 1000000007
for i in range(M):
    a[i] = int(input())

def calc(f,t):
    tmp = t - f
    i = 1
    ans = 1
    if tmp == 1:
        return 1
    if tmp == 0:
        return 1
    while(tmp >= 2*i):
        ans += math.factorial(tmp - i) // math.factorial(i) // math.factorial(tmp - 2*i)
        i += 1
    return ans

flag = 0
A = 1
A *= calc(0,a[0]-1)

for i in range(M-1):
    if a[i] + 1 == a[i+1]:
        flag = 1
        break
    A *= calc(a[i]+1,a[i+1]-1)
    A %= mod

A *= calc(a[M-1]+1,N)
A %= mod

if flag == 1:
    print(0)
elif M == 0:
    print(calc(0,N))
else:
    print(A)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = [0] * M
B = [0] * N

if M ==0:
  B[0] = 1
  B[1] = 2
  for i in range(2,N):
    B[i] = B[i-1]+B[i-2]
  print(B[N-1])
  exit()
#elif M == 1:
#  A[0] = int(input())
#  if A[0] == 1:
#    B[0] = 0
#    B[1] = 1
#  elif A[0] == 2:
#    B[0] = 1
#    B[1] = 0
#  else:
#    B[0] = 1
#    B[1] = 2
#    
#  for i in range(2,N-2):
#    B[i] = B[i-1]+B[i-2]
#  print(B[N-3])
#  print(B)
#  exit()
  


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


count = [0] * N
dame = M-1
if A[M-1] == N-1 and A[M-2] == N-2:
  count[N-1] = 0
  count[N-2] = 0
  dame -= 2
elif A[M-1] == N-1:
  count[N-1] = 0
  count[N-2] = 1
  dame -= 1
elif A[M-1] == N-2:
  count[N-1] = 1
  count[N-2] = 0
  dame -= 1
else:
  count[N-1] = 1
  count[N-2] = 2

#print(count[N-1])
#print(count[N-2])

for i in range(N-3, -1, -1):
  if A[dame] == i:
#    print('dame_' + str(dame))
#    print(A[dame])
    count[i] = 0
    dame -= 1
  else:
    count[i] = (count[i+1] + count[i+2] ) % 1000000007
#    print(count[i])

#  if i % 10 == 0:
#    print(count[i])
#  print('i_ ' + str(i))
#  print(count[i])
result = count[0] % 1000000007
print(result)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = [0] * M
B = [0] * N

if M ==0:
  B[0] = 1
  B[1] = 2
  for i in range(2,N):
    B[i] = B[i-1]+B[i-2]
  print(B[N-1])
  exit()
elif M == 1:
  A[0] = int(input())
  if A[0] == 1:
    B[0] = 0
    B[1] = 1
  elif A[0] == 2:
    B[0] = 1
    B[1] = 0
  else:
    B[0] = 1
    B[1] = 2
    
  for i in range(2,N-2):
    B[i] = B[i-1]+B[i-2]
  print(B[N-3])
#  print(B)
  exit()
  


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


count = [0] * N
dame = M-1
if A[M-1] == N-1 and A[M-2] == N-2:
  count[N-1] = 0
  count[N-2] = 0
  dame -= 2
elif A[M-1] == N-1:
  count[N-1] = 0
  count[N-2] = 1
  dame -= 1
elif A[M-1] == N-2:
  count[N-1] = 1
  count[N-2] = 0
  dame -= 1
else:
  count[N-1] = 1
  count[N-2] = 2

#print(count[N-1])
#print(count[N-2])

for i in range(N-3, -1, -1):
  if A[dame] == i:
#    print('dame_' + str(dame))
#    print(A[dame])
    count[i] = 0
    dame -= 1
  else:
    count[i] = (count[i+1] + count[i+2] ) % 1000000007
#    print(count[i])

#  if i % 10 == 0:
#    print(count[i])
#  print('i_ ' + str(i))
#  print(count[i])
result = count[0] % 1000000007
print(result)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = [0] * M
B = [0] * N

if M ==0:
  B[0] = 1
  B[1] = 2
  for i in range(2,N):
    B[i] = B[i-1]+B[i-2]
  print(B[N-1])
  exit()
elif M == 1:
  A[0] = int(input())
  if A[0] == 1:
    B[0] = 0
    B[1] = 1
  elif A[0] == 2:
    B[0] = 1
    B[1] = 0

  for i in range(2,N-1):
    B[i] = B[i-1]+B[i-2]
  print(B[N-2])
  exit()
  


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


count = [0] * N
dame = M-1
if A[M-1] == N-1 and A[M-2] == N-2:
  count[N-1] = 0
  count[N-2] = 0
  dame -= 2
elif A[M-1] == N-1:
  count[N-1] = 0
  count[N-2] = 1
  dame -= 1
elif A[M-1] == N-2:
  count[N-1] = 1
  count[N-2] = 0
  dame -= 1
else:
  count[N-1] = 1
  count[N-2] = 2

#print(count[N-1])
#print(count[N-2])

for i in range(N-3, -1, -1):
  if A[dame] == i:
#    print('dame_' + str(dame))
#    print(A[dame])
    count[i] = 0
    dame -= 1
  else:
    count[i] = (count[i+1] + count[i+2] ) % 1000000007
#    print(count[i])

#  if i % 10 == 0:
#    print(count[i])
#  print('i_ ' + str(i))
#  print(count[i])
result = count[0] % 1000000007
print(result)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = [0] * M

if M ==0:
  B = [0] * N
  B[0] = 1
  B[1] = 2
  for i in range(2,N):
    B[i] = B[i-1]+B[i-2]
  print(B[N-1])
  exit()
elif M == 1:
  B = [0] * N
  B[0] = 1
  B[1] = 2
  for i in range(2,N-1):
    B[i] = B[i-1]+B[i-2]
  print(B[N-2])
  exit()
  


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


count = [0] * N
dame = M-1
if A[M-1] == N-1 and A[M-2] == N-2:
  count[N-1] = 0
  count[N-2] = 0
  dame -= 2
elif A[M-1] == N-1:
  count[N-1] = 0
  count[N-2] = 1
  dame -= 1
elif A[M-1] == N-2:
  count[N-1] = 1
  count[N-2] = 0
  dame -= 1
else:
  count[N-1] = 1
  count[N-2] = 2

#print(count[N-1])
#print(count[N-2])

for i in range(N-3, -1, -1):
  if A[dame] == i:
#    print('dame_' + str(dame))
#    print(A[dame])
    count[i] = 0
    dame -= 1
  else:
    count[i] = (count[i+1] + count[i+2] ) % 1000000007
#    print(count[i])

#  if i % 10 == 0:
#    print(count[i])
#  print('i_ ' + str(i))
#  print(count[i])
result = count[0] % 1000000007
print(result)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = [0] * M

if M ==0:
  B = [0] * N
  B[0] = 1
  B[1] = 2
  for i in range(2,N):
    B[i] = B[i-1]+B[i-2]
  print(B[N-1])
  exit()
elif M == 1:
  B = [0] * N
  B[0] = 1
  B[1] = 2
  for i in range(2,N-1):
    B[i] = B[i-1]+B[i-2]
  print(B[N-2])
  exit()
  


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


count = [0] * N
dame = M-1
if A[M-1] == N-1 and A[M-2] == N-2:
  count[N-1] = 0
  count[N-2] = 0
  dame -= 2
elif A[M-1] == N-1:
  count[N-1] = 0
  count[N-2] = 1
  dame -= 1
elif A[M-1] == N-2:
  count[N-1] = 1
  count[N-2] = 0
  dame -= 1
else:
  count[N-1] = 1
  count[N-2] = 2

#print(count[N-1])
#print(count[N-2])

for i in range(N-3, -1, -1):
  if A[dame] == i:
    print('dame_' + str(dame))
    print(A[dame])
    count[i] = 0
    dame -= 1
  else:
    count[i] = (count[i+1] + count[i+2] ) % 1000000007
    print(count[i])

#  if i % 10 == 0:
#    print(count[i])
#  print('i_ ' + str(i))
#  print(count[i])
result = count[0] % 1000000007
print(result)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = [0] * M
for i in range(M):
  A[i] = int(input())
  
#print(A)
count = [0] * N
dame = M-1
if A[M-1] == N-1 and A[M-2] == N-2:
  count[N-1] = 0
  count[N-2] = 0
  dame -= 2
elif A[M-1] == N-1:
  count[N-1] = 0
  count[N-2] = 1
  dame -= 1
elif A[M-1] == N-2:
  count[N-1] = 1
  count[N-2] = 0
  dame -= 1
else:
  count[N-1] = 1
  count[N-2] = 2

#print(count[N-1])
#print(count[N-2])

for i in range(N-3, -1, -1):
  if A[dame] == i:
#    print('dame_' + str(dame))
#    print(A[dame])
    count[i] = 0
    dame -= 1
  else:
    count[i] = (count[i+1] + count[i+2] ) % 1000000007
#  if i % 10 == 0:
#    print(count[i])
#  print('i_ ' + str(i))
#  print(count[i])
result = count[0] % 1000000007
print(result)

Submission status: Runtime Error

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

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

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
#!/home/ryo/.pyenv/versions/anaconda3-2019.03/envs/hoge/bin/python
import sys
def fib(n):
    memo = [0] * (n+1)
    memo[0:2] = [0, 1]
    for i in range(2, n+1):
        memo[i] = memo[i - 1] + memo[i - 2]
    return memo

lim=10**9+7

N,M = map(int,input().split())
A=[]
for i in range(0,M):
    A.append(int(input()))
diff=[]
for i in range(0,len(A)-1):
    diff.append(A[i+1]-A[i]-1)
if 0 in diff:
    print(0)
    sys.exit()
else:
    max_n=diff.copy()
    max_n.append(A[0])
    max_n.append(N-A[-1])
    memo_fib=fib(max(max_n))
    #print(memo_fib)
    ans=memo_fib[A[0]]
    #print(ans)
    for i in diff:
        ans= ans * memo_fib[i] % lim
        #print(i, ans)
ans=ans*memo_fib[N-A[-1]] % lim
print(ans)

Submission status: Runtime Error

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

def fib(n):  
    if (n==0 or n==1):return 1
    if n in a:
      return 0
    elif fib(n-1) + fib(n-2) < 1000000007:
      return (fib(n-1) + fib(n-2))
    else:
      return (fib(n-1) + fib(n-2)) % 1000000007

print(fib(N))

Submission status: Runtime Error

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

def f(x):
    if x == 1 or x == 0:
        return 1
    else:
        return f(x-1) + f(x-2)

def sol(a):
    for i in range(m - 1):
        if a[i+1] - a[i] == 1:
            print(0)
            return
    mod = 10 ** 9 + 7
    stairs = []
    now = 0
    for i in range(m):
        stairs.append(a[i] - 1 - now)
        now = a[i] + 1
    stairs.append(n - now)

    ans = 1
    for ele in stairs:
        ans *= f(ele)

    print(ans % mod)


sol(a)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
INFTY = 10**9+7
N,M = map(int,input().split())
A = [int(input()) for _ in range(M)]
dp = [0 for _ in range(N+1)]
dp[0] = 1
dp[1] = 1
cur = 0
if A[0]==1:
    dp[1] = 0
    cur = 1
for i in range(2,N+1):
    if cur<M and i==A[cur]:
        cur += 1
    else:
        dp[i] = (dp[i-1]+dp[i-2])%INFTY
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
step=[0]*(N+1)
step[1]=0 if 1 in A else 0
step[2]=0 if 2 in A else 1 if 1 in A else 0
for i in range(3, N+1):
  if i in A:
    continue
  step[i]=(step[i-1]+step[i-2])%mod
print(step[-1])

Submission status: Runtime Error

Solution code:
n,m = map(int, input().split())
div = 1000000007
ok [True] * (n + 1)
for _ in range(m):
  a = int(input())
  ok[a] = False
dp = [0] * (n + 1)
dp[0] = 1
if ok[1]:
  dp[1] = 1
else:
  dp[1] = 0

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

print(dp[n])

Submission status: Runtime Error

Solution code:
n,m = map(int, input().split())
div = 1000000007
ok [True] * n + 1
for _ in range(m):
  a = int(input())
  ok[a] = False
dp = [0] * (n + 1)
dp[0] = 1
if ok[1]:
  dp[1] = 1
else:
  dp[1] = 0

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

print(dp[n])