Problem:


Score : 300 points

Problem Statement

There is a staircase with N steps. Takahashi is now standing at the foot of the stairs, that is, on the 0-th step.
He can climb up one or two steps at a time.

However, the treads of the a_1-th, a_2-th, a_3-th, \ldots, a_M-th steps are broken, so it is dangerous to set foot on those steps.

How many are there to climb up to the top step, that is, the N-th step, without setting foot on the broken steps?
Find the count modulo 1\ 000\ 000\ 007.

Constraints

1 \leq N \leq 10^5

0 \leq M \leq N-1

1 \leq a_1 < a_2 <  ...  < a_M \leq N-1

Input

Input is given from Standard Input in the following format:

N M
a_1
a_2
 .
 .
 .
a_M

Output

Print the number of ways to climb up the stairs under the condition, modulo 1\ 000\ 000\ 007.

Sample Input 1

6 1
3

Sample Output 1

4

There are four ways to climb up the stairs, as follows:

0 \to 1 \to 2 \to 4 \to 5 \to 6

0 \to 1 \to 2 \to 4 \to 6

0 \to 2 \to 4 \to 5 \to 6

0 \to 2 \to 4 \to 6

Sample Input 2

10 2
4
5

Sample Output 2

0

There may be no way to climb up the stairs without setting foot on the broken steps.

Sample Input 3

100 5
1
23
45
67
89

Sample Output 3

608200469

Be sure to print the count modulo 1\ 000\ 000\ 007.



Sample input:
6 1
3


Sample output:
4

Submission status: Runtime Error

Solution code:
from math import factorial
MOD = 1_000_000_007

def calc_nCr(n, r):
    return (int(factorial(n) / (factorial(r) * factorial(n - r)))) % MOD
def count_patterns(stairs):
    if stairs == 0 or stairs == 1:
        return 1
    max_double_num = int(stairs/2)
    combs = [None]*(max_double_num+1)
    for i in range(max_double_num+1):
        double = i
        single = stairs - double*2
        n = double + single
        r = double
        nCr = calc_nCr(n, r)
        combs[i] = nCr
    return sum(combs) % MOD
  
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]

now = 0
total = 1

for broken in a:
    if broken <= now:
        print(0)
        break
    total = (total * count_patterns(broken-now-1)) % MOD
    now = broken + 1
else:
    total = (total * count_patterns(N-now)) % MOD
    print(total)

Submission status: Runtime Error

Solution code:
from math import factorial

def calc_nCr(n, r):
    return int(factorial(n) / (factorial(r) * factorial(n - r)))
def count_patterns(stairs):
    if stairs == 0 or stairs == 1:
        return 1
    max_double_num = int(stairs/2)
    combs = [None]*(max_double_num+1)
    for i in range(max_double_num+1):
        double = i
        single = stairs - double*2
        n = double + single
        r = double
        nCr = calc_nCr(n, r)
        combs[i] = nCr
    return sum(combs) % MOD
  
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]

MOD = 1_000_000_007
now = 0
total = 1

for broken in a:
    if broken <= now:
        print(0)
        break
    total = (total * count_patterns(broken-now-1)) % MOD
    now = broken + 1
else:
    total = (total * count_patterns(N-now)) % MOD
    print(total)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
a = []
mod = 10**9+7
for i in range(m):
    b = int(input())
    a.append(b)
d = [0 for i in range(n+1)]
d[0] = 1
d[1] = 1
d[2] = 2
for i in range(3,n+1):
    d[i] = d[i-1] + d[i-2]
d.append(0)
ans = 1
if a[0] == 1:
    ans = 1
else:
    ans = ans*d[a[0]-1]%mod
for i in range(m-1):
    ans = ans*d[a[i+1]-a[i]-2]%mod
ans = ans*d[n-a[m-1]-1]%mod
print(ans)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
a = []
mod = 10**9+7
for i in range(m):
    b = int(input())
    a.append(b)
d = [0 for i in range(n+1)]
d[0] = 0
d[1] = 1
d[2] = 2
for i in range(3,n+1):
    d[i] = d[i-1] + d[i-2]
d.append(0)
ans = 1
if a[0] == 1:
    ans = 1
else:
    ans = ans*d[a[0]-1]%mod
for i in range(m-1):
    ans = ans*d[a[i+1]-a[i]-2]%mod
ans = ans*d[n-a[m-1]-1]%mod
print(ans)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
a = []
mod = 10**9+7
for i in range(m):
    b = int(input())
    a.append(b)
d = [0 for i in range(n+1)]
d[0] = 0
d[1] = 1
d[2] = 2
for i in range(3,n+1):
    d[i] = d[i-1] + d[i-2]
ans = 1
if a[0] == 1:
    ans = 1
else:
    ans = ans*d[a[0]-1]%mod
for i in range(m-1):
    ans = ans*d[a[i+1]-a[i]-2]%mod
ans = ans*d[n-a[m-1]-1]%mod
print(ans)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
a = []
for i in range(m):
    b = int(input())
    a.append(b)
d = [0 for i in range(n+1)]
d[0] = 0
d[1] = 1
d[2] = 2
for i in range(3,n+1):
    d[i] = d[i-1] + d[i-2]
ans = 1
if a[0] == 1:
    ans = 1
else:
    ans = ans*d[a[0]-1]%mod
for i in range(m-1):
    ans = ans*d[a[i+1]-a[i]-2]%mod
ans = ans*d[n-a[m-1]-1]%mod
print(ans)

Submission status: Runtime Error

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

A = [int(input().strip()) for _ in range(m)]

a0 = 1
a1 = 1 if A[0] !=1 else 0
mod = 1000000007

ANS=[0]*(n+1)
ANS[0]=a0
ANS[1]=a1
Next = A if a1 !=0 else A[1:]
next = 0
for i in range(2, n+1):
    if next <= len(Next)-1:
        if i == Next[next]:
            ANS[i] = 0
            next += 1
            continue
    ANS[i] = ANS[i-2] + ANS[i-1]

print(ANS[n]%mod)

Submission status: Runtime Error

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

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

a0 = 1
a1 = 1 if A[0] !=1 else 0
mod = 1e9+7

ANS=[0]*(n+1)
ANS[0]=a0
ANS[1]=a1
Next = A if a1 !=0 else A[1:]
next = 0
for i in range(2, n+1):
    if next <= len(Next)-1:
        if i == Next[next]:
            ANS[i] = 0
            next += 1
            continue
    ANS[i] = ANS[i-2] + ANS[i-1]

print(int(ANS[n]%mod))

Submission status: Runtime Error

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

A = [int(a) for a in input().strip()]

a0 = 1 
a1 = 1 if A[0] !=1 else 0 

ANS=[0]*(n+1)
ANS[0]=a0
ANS[1]=a1
Next = A[1:] if a1 !=0 else A
next = 0
for i in range(2,n+1) :
  if i == Next[next]:
    A[i] = 0
    next += 1 
  else:
    A[i] = A[i-2] + A[i-1] 
  
print(A[n])

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
a=list(map(int,input().split()))
fib=[0,1]
for i in range(n):
  fib.append(fib[i]+fib[i+1])
b=[]
for j in range(m):
  b.append(fib[a[j]-1])
ans=0
for t in range(m-1):
  ans+=(b[t]*b[t+1])%(10**9+1)
print(ans%(10**9+1))

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
a=list(map(int,input().split()))
fib=[0,1]
for i in range(n):
  fib.append(fib[i]+fib[i+1])
b=[]
for j in range(m):
  b.append(fib[a[m]-1])
ans=0
for t in range(m-1):
  ans+=(b[t]*b[t+1])%(10**9+1)
print(ans%(10**9+1))

Submission status: Runtime Error

Solution code:
"""
N段の階段 M個の階段が壊れている
"""

N, M = map(int, input().split())
arr = [int(input()) for _ in range(M)]
no_step =[0]*N

for i in range(M):
    no_step[arr[i]-1]=1

count = [0]*N
if no_step[0]==0:
    count[0]=1

if no_step[1]==1:
    count[1]=0
elif no_step[0]==0 and no_step[1]==0:
    count[1]=2
elif no_step[0]==1 and no_step[1]==0:
    count[1]=1

for i in range(3,N+1,1):
    count[i-1] = count[i-2]+count[i-3]
    if no_step[i-1] == 1:
        count[i-1] = 0

ans =count[N-1]%1000000007
print(ans)

Submission status: Runtime Error

Solution code:
"""
N段の階段 M個の階段が壊れている
"""

N, M = map(int, input().split())
arr = [int(input()) for _ in range(M)]
no_step =[0]*N

for i in range(M):
    no_step[arr[i]-1]=1

count = [0]*N
if no_step[0]==0:
    count[0]=1

if no_step[1]==1:
    count[1]=0
elif no_step[0]==0 and no_step[1]==0:
    count[1]=2
elif no_step[0]==1 and no_step[1]==0:
    count[1]=2

for i in range(3,N+1,1):
    count[i-1] = count[i-2]+count[i-3]
    if no_step[i-1] == 1:
        count[i-1] = 0

print(count[-1]%1000000007)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9 + 7
input = sys.stdin.readline

def inp():
    return int(input())
def inpl():
    return list(map(int,input().split()))
def inpm():
    return map(int,input().split())

n,m = inpm()
dp = [0] * (n+2)
for _ in range(m):
    a = int(input())
    dp[a] = -1

# init
dp[0] = 1
# start
print(a)
for i in range(n):
    if dp[i] == -1:continue
    dp[i] %= mod
    if dp[i+1] != -1:
        dp[i+1] += dp[i]
    if dp[i+2] != -1:
        dp[i+2] += dp[i]

print(dp[n]%mod)

Submission status: Runtime Error

Solution code:
import math
N,M = list(map(int,input().split()))
A = set([-1])+set([int(input()) for _ in range(M)])+set([N+1])
cnt = 0
ans = 1
for i in range(M+1):
  cnt = 0
  d = A[i+1]-A[i]-2
  for j in range(d//2+1):
    cnt += math.factorial(d-j)//(math.factorial(d-j*2)*math.factorial(j))
  ans *= cnt
print(ans%1000000007)

Submission status: Runtime Error

Solution code:
import sys
sys.stdin.readline

def fibo(n):
    if n == 1:
        return 1
    elif n == 2:
        return 2
    else:
        if n not in stars and n-1 not in stars and n-2 not in stars:
            return fibo(n-1) + fibo(n-2)
        elif n not in stars and n-1 not in stars and n-2 in stars:
            return fibo(n-1)
        elif n not in stars and n-1 in stars and n-2 not in stars:
            return fibo(n-2)
        elif n in stars:
            return 0
        else:
            print(0)
            sys.exit()

N, M = map(int, input().split())
stars = []

for i in range(M):
    a = int(input())
    stars.append(a)

print(fibo(N) % 1000000007)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
a = [int(input()) for nesya in range(m)]
hoge = [1]*(n+1)
for i in range(m):
  hoge[a[i]] = 0
for j in range(2,n+1):
  if hoge[j] == 0:
    continue
  else:
    hoge[j] = hoge[j-1] + hoge[j-2]
  hoge[j] = hoge[j] % (10**9+7)
print(hoge[j]%(10**9+7))

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
a_list = [int(input()) 
          for nesya in range(m)]
hoge = [1]*(n+1)
for i in range(m):
  hoge[a_list[i]] = 0
for j in range(2,n+1):
  if hoge[j] == 0:
    continue
  else:
    hoge[j] = hoge[j-1] + hoge[j-2]
print(hoge[j]%(10**9+7))

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
a_list = [int(input()) 
          for nesya in range(m)]
hoge = [1]*(n+1)
for i in range(m):
  hoge[a_list[i]] = 0
for j in range(2,n+1):
  if hoge[j] == 0:
    continue
  else:
    hoge[j] = hoge[j-1] + hoge[j-2]
  hoge[j] = hoge[j] % (10**9+7)
print(hoge[j])

Submission status: Runtime Error

Solution code:
import math

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

n,m = map(int,input().split())
a_list = [int(input()) 
          for nesya in range(m)]
a_list.append(n+1)
ans = 1
mae = -1
for a in a_list:
  k = a-mae-1
  mae = a
  ans = (ans*int(fib(k)))%(10**9+7)
print(ans)

Submission status: Runtime Error

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

k = 1000000007


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

    dp[i] = dp[i-1] + dp[i-2]
    dp[i] %= k



print(n)

Submission status: Runtime Error

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

k = 1000000007


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

    dp[i] = dp[i-1] + dp[i-2]
    dp[i] /= k



print(n)

Submission status: Runtime Error

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

k = 1000000007

if dp[0] == 0 and dp[1] == 0:
    dp[0] = 1
    dp[1] = 2

if dp[0] == -1 and dp[1] == 0:
    dp[0] = 0
    dp[1] = 1


if dp[0] == 0 and dp[1] == -1:
    dp[0] = 1
    dp[1] = 0


if dp[0] == -1 and dp[1] == -1:
    dp[0] = 0
    dp[1] = 0


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

n = dp[-1] % k

print(n)

Submission status: Runtime Error

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

s = [1]*(n+1)

if 1 in a:
    s[1] = 0

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

Submission status: Runtime Error

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

if a[0] == 1:
    s[1] = 0

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

print(s[-1])

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
N,M = map(int,input().split())
lst=[int(input()) for i in range(M)]
t=0
ans=[0]*(N+1)
ans[0]=1
for j in range(N):
 if lst[t]==j+1:
  ans[j+1]=0
  t+=1
  t=min(M-1,t)
 else:
  ans[j+1]+=ans[j]
  if j!=0:
   ans[j+1]+=ans[j-1]
  ans[j+1]%=(10**9+7)
print(ans[N])

Submission status: Runtime Error

Solution code:

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

#print(a)
dp = [0] * (N+1)
dp[0]=1
if a[0]!=1:
    dp[1]=1
#dp[1]=1
j=0
for i in range(1,N+1):
    if M!=0:
        if i==a[j]:
            dp[i] = 0
            j+=1
            if j==M:
                j=0

        else:
            dp[i] = dp[i-1] + dp[i-2]
    else:
        dp[i] = dp[i-1] + dp[i-2]

print(dp[-1] % 1000000007)

Submission status: Runtime Error

Solution code:

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

#print(a)
dp = [0] * (N+1)
dp[0]=1
if a[0]!=1:
    dp[1]=1
#dp[1]=1
j=0
for i in range(1,N+1):
    if M!=0:
        if i==a[j]:
            dp[i] = 0
            j+=1
            if j==len(a):
                j=0

        else:
            dp[i] = dp[i-1] + dp[i-2]
    else:
        dp[i] = dp[i-1] + dp[i-2]

print(dp[-1] % 1000000007)

Submission status: Runtime Error

Solution code:

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

#print(a)
dp = [0] * (N+1)
dp[0]=1
if a[0]!=1:
    dp[1]=1
#dp[1]=1
j=0
for i in range(1,N+1):
    if i==a[j]:
        dp[i] = 0
        j+=1
        if j==len(a):
            j=0

    else:
        dp[i] = dp[i-1] + dp[i-2]

print(dp[-1] % 1000000007)

Submission status: Runtime Error

Solution code:
BIG = 10**9+7

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

pre = a[0]
dame = False
for i in range(1,len(a)):
    if a[i]==pre:
        dame = True
    pre=a[i]

dp = [0 for i in range(N+1)]
for item in a:
    dp[item]=-1
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] = dp[i-1]+dp[i-2]
        dp[i] = dp[i]%BIG
    else:
        dp[i]=0

print(dp)

if dame:
    print(0)
else:
    print(dp[-1])

Submission status: Runtime Error

Solution code:
BIG = 10**9+7

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

pre = a[0]
dame = False
for i in range(1,len(a)):
    if a[i]==pre:
        dame = True
    pre=a[i]

dp = [0 for i in range(N+1)]
for item in a:
    dp[item]=-1
if a[0]!=0:
    dp[0] = 1
if a[0]!=0:
    if (len(a)>1 and a[1]!=0) or a[0]!=1:
        dp[1] = 2

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

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

#print(dp)

if dame:
    print(0)
else:
    print(dp[-1])

Submission status: Runtime Error

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

mod = 1_000_000_007

dp=[0]*(n+1)

dp[0]=1
dp[1]=1

for _ in range(m):
    s = int(input())
    a.append(s)

    dp[s]=0


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

print(dp[-1]%mod)

Submission status: Runtime Error

Solution code:
# 2020/05/10
# AtCoder Beginner Contest 129 - C

# Input
n, m = map(int,input().split())
sav_a = -1
ans = 0
a = [0] * (n+1)
imp_flg = False
for i in range(m):
    ia = int(input())
    a[ia] = 1
    if sav_a + 1 == ia:
        imp_flg = True
    sav_a = ia

dp = [0] * (n+1)

if imp_flg == True:
    ans = 0
else:
    dp[1] = 1
    dp[2] = 2
    if a[1] == 1:
        dp[1] = 0
        dp[2] = 1
    if a[2] == 1:
        dp[2] = 0

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

# Output
print(dp[n])

Submission status: Runtime Error

Solution code:
#! /Library/Frameworks/Python.framework/Versions/3.7/bin/python3
D = 1000000007
n, m = map(int, input().split())
a = [0] * (10**5 + 1)
for i in range(m):
    a[int(input())] += 1

# 初期値
s0 = 1
if (a[1] == 1):
    s1 = 0
else:
    s1 = 1


def calc(l, acc1, acc2):
    # print("calc(l, acc1, acc2):" + str(l) + str(acc1) + str(acc2))
    if (l == 1):
        return acc2
    else:
        oldacc2 = acc2
        acc2 = (acc1 + acc2) % D if a[n - l + 2] == 0 else 0
        acc1 = oldacc2
        return calc(l - 1, acc1, acc2)


print(calc(n, s0, s1))

Submission status: Runtime Error

Solution code:
#! /Library/Frameworks/Python.framework/Versions/3.7/bin/python3
D = 1000000007
n, m = map(int, input().split())
a = [0] * (10**5 + 3)
for i in range(m):
    a[int(input())] += 1

# 初期値
s0 = 1
if (a[1] == 1):
    s1 = 0
else:
    s1 = 1


def calc(l, acc1, acc2):
    # print("calc(l, acc1, acc2):" + str(l) + str(acc1) + str(acc2))
    if (l == 1):
        return acc2
    else:
        oldacc2 = acc2
        acc2 = (acc1 + acc2) % D if a[n - l + 2] == 0 else 0
        acc1 = oldacc2
        return calc(l - 1, acc1, acc2)


print(calc(n, s0, s1))

Submission status: Runtime Error

Solution code:
#! /Library/Frameworks/Python.framework/Versions/3.7/bin/python3
D = 1000000007
n, m = map(int, input().split())
a = [0] * (10**6)
for i in range(m):
    a[int(input())] += 1

# 初期値
s0 = 1
if (a[1] == 1):
    s1 = 0
else:
    s1 = 1


def calc(l, acc1, acc2):
    # print("calc(l, acc1, acc2):" + str(l) + str(acc1) + str(acc2))
    if (l == 1):
        return acc2
    else:
        oldacc2 = acc2
        if (a[n - l + 2] == 1):
            acc2 = 0
        else:
            acc2 = (acc1 + acc2) % D
        acc1 = oldacc2
        return calc(l - 1, acc1, acc2)


print(calc(n, s0, s1))

Submission status: Runtime Error

Solution code:
#! /Library/Frameworks/Python.framework/Versions/3.7/bin/python3
D = 1000000007
n, m = map(int, input().split())
a = [0] * (10**5 + 4)
for i in range(m):
    a[int(input())] += 1

# 初期値
s0 = 1
if (a[1] == 1):
    s1 = 0
else:
    s1 = 1


def calc(l, acc1, acc2):
    # print("calc(l, acc1, acc2):" + str(l) + str(acc1) + str(acc2))
    if (l == 1):
        return acc2
    else:
        oldacc2 = acc2
        if (a[n - l + 2] == 1):
            acc2 = 0
        else:
            acc2 = (acc1 + acc2) % D
        acc1 = oldacc2
        return calc(l - 1, acc1, acc2)


print(calc(n, s0, s1))

Submission status: Runtime Error

Solution code:
#アキュムレータ版
D = 1000000007
n, m = map(int, input().split())
a = [0] * (10**5 + 3)
for i in range(m):
    a[int(input())] += 1

# 初期値
s0 = 1
if (a[1] == 1):
    s1 = 0
else:
    s1 = 1


def calc(l, acc1, acc2):
    # print("calc(l, acc1, acc2):" + str(l) + str(acc1) + str(acc2))
    if (l == 1):
        return acc2
    else:
        oldacc2 = acc2
        if (a[n - l + 2] == 1):
            acc2 = 0
        else:
            acc2 = (acc1 + acc2) % D
        acc1 = oldacc2
        return calc(l - 1, acc1, acc2)


print(calc(n, s0, s1))

Submission status: Runtime Error

Solution code:
# アキュムレータ版
D = 1000000007
n, m = map(int, input().split())
a = [0] * (10**5 + 2)
for i in range(m):
    a[int(input())] += 1

# 初期値
s0 = 1
if (a[1] == 1):
    s1 = 0
else:
    s1 = 1


def calc(l, acc1, acc2):
    # print("calc(l, acc1, acc2):" + str(l) + str(acc1) + str(acc2))
    if (l == 1):
        return acc2
    else:
        oldacc2 = acc2
        if (a[n - l + 2] == 1):
            acc2 = 0
        else:
            acc2 = acc1 + acc2
        acc1 = oldacc2
        return calc(l - 1, acc1, acc2) % D


print(calc(n, s0, s1))

Submission status: Runtime Error

Solution code:
# アキュムレータ版
D = 1000000007
n, m = map(int, input().split())
a = [0] * (10**5 + 1)
for i in range(m):
    a[int(input())] += 1

# 初期値
s0 = 1
if (a[1] == 1):
    s1 = 0
else:
    s1 = 1


def calc(l, acc1, acc2):
    # print("calc(l, acc1, acc2):" + str(l) + str(acc1) + str(acc2))
    if (l == 1):
        return acc2
    else:
        oldacc2 = acc2
        if (a[n - l + 2] == 1):
            acc2 = 0
        else:
            acc2 = acc1 + acc2
        acc1 = oldacc2
        return calc(l - 1, acc1, acc2) % D


print(calc(n, s0, s1))

Submission status: Runtime Error

Solution code:
# 計算量爆発パターン
D = 1000000007
n, m = map(int, input().split())
a = [0] * (10**5 + 1)
for i in range(m):
    a[int(input())] += 1

# 初期値
s0 = 1
if (a[1] == 1):
    s1 = 0
else:
    s1 = 1


def calc(n):
    if (n == 0):
        return s0
    elif (n == 1):
        return s1
    elif (a[n] == 1):
        return 0
    else:
        return (calc(n - 1) + calc(n - 2)) % D


print(calc(n))

Submission status: Runtime Error

Solution code:
#計算量爆発で死ぬパターン

D = 1000000007
n, m = map(int, input().split())
a = [0] * (10**5 + 1)
for i in range(m):
    a[int(input())] += 1

# 初期値
s0 = 1
if (a[1] == 1):
    s1 = 0
else:
    s1 = 1


def calc(n):
    if (n == 0):
        return s0
    elif (n == 1):
        return s1
    elif(a[n] == 1):
        return 0
    else:
        return (calc(n-1) + calc(n - 2) % D

print(s[n])

Submission status: Runtime Error

Solution code:
#! /Library/Frameworks/Python.framework/Versions/3.7/bin/python3
D = 1000000007
n, m = map(int, input().split())
a = [0] * (10**5)
for i in range(m):
    a[int(input())] += 1

# 初期値
s = [0] * (n + 1)
s[0] = 1
if (a[1] == 1):
    s[1] = 0
else:
    s[1] = 1


def calc(n):
    if(a[n] == 1):
        return 0
    else:
        return (s[n - 1] + s[n - 2]) % D


def solver(n):
    for i in range(2, n + 1):
        s[i] = calc(i)


solver(n)
print(s[n])

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from itertools import permutations, accumulate, combinations, combinations_with_replacement
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce
from fractions import gcd
import sys
def I(): return int(input())
def Is(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()
def LS(): return list(input())
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(10**6)
MOD = 10**9+7
INF = float('inf')


n, m = Is()
A = IR(m)
dp = [0]*(n+3)
dp[0] = 1

A.sort(reverse=True)
tmp = A.pop()
if tmp == 1:
    dp[1] = 0
    if len(A) > 0:
        tmp = A.pop()
else:
    dp[1] = 1

for i in range(n+1):
    if tmp == i+2:
        dp[i+2] = 0
        if len(A) > 0:
            tmp = A.pop()
    else:
        dp[i+2] += dp[i+1] + dp[i]

print(dp[n] % MOD)

Submission status: Runtime Error

Solution code:
import numpy as np
from math import factorial
import math, sys

N, M = map(int, input().split())
A = [None]*M

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

tmp = 0
x = []

for i, a in enumerate(A):
    x.append(a-tmp-1)
    tmp = a + 1

x.append(N - tmp)
    
x = np.array(x)
if x[1:].min()<1:
    print(0)
    sys.exit()

def calc_combi(a):
    ans = 0
    for i in range(int(a/2)+1):
        tmp_n = math.ceil(a/2)+i
        tmp_r = a - tmp_n
        ans += factorial(tmp_n) // factorial(max(tmp_r, tmp_n - tmp_r))                        
    return ans

memo =  list(map(lambda x: calc_combi(x), x))

ans = 1
for m in memo:
    ans = ans * m % 1000000007

print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
from math import factorial
import math, sys

N, M = map(int, input().split())
A = [None]*M

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

tmp = 0
x = []

for i, a in enumerate(A):
    x.append(a-tmp-1)
    tmp = a + 1

x.append(N - tmp)
    
x = np.array(x)
if x[1:].min()<1:
    print(0)
    sys.exit()

def calc_combi(a):
    ans = 0
    for i in range(int(a/2)+1):
        tmp_n = math.ceil(a/2)+i
        tmp_r = a - tmp_n
        ans += factorial(tmp_n) // factorial(max(tmp_r, tmp_n - tmp_r))                        
    return ans

memo =  list(map(lambda x: calc_combi(x), x))

ans = 1
for m in memo:
    ans = ans * m % 1000000007

Submission status: Runtime Error

Solution code:
from collections import deque

N, M = map(int, input().split())
Broken = deque()
for _ in range(M):
    broken = int(input())
    Broken.append(broken)

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

nex = Broken.popleft()

for i in range(1, N+1):
    if i == nex:
        if len(Broken) >0:
            nex = Broken.popleft()
        continue
    DP[i] = DP[i-1] + DP[i-2]
    DP[i] %= 10**9 + 7
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
memo = [-1]*(n+1)
def rec(x):
    if memo[x] != -1: pass
    elif x == 0: memo[x] = 1
    elif a and x == a[-1]:
        memo[x] = 0
        a.pop()
    elif x == 1: memo[x] = 1
    else: memo[x] = rec(x-1)+rec(x-2)
    return memo[x]%mod
print(rec(n))

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

N,M = (int(x) for x in input().split())
a = set(int(input()) for _ in range(M))
dp = [0] * N
broke = False
if 1 in a and 2 not in a:
    dp[1] = 1
elif 1 not in a and 2 in a:
    dp[0] = 1
else:
    dp[0] = 1
    dp[1] = 2
if 1 in a and 2 in a:
    print('0')
    broke = True
else:
    for i in range(3,N+1):
        if i-1 in a and i-2 in a:
            print('0')
            broke = True
            break
        elif i-1 in a:
            dp[i-1] = dp[i-3]
        elif i-2 in a:
            dp[i-1] = dp[i-2]
        else:
            dp[i-1] = (dp[i-2] + dp[i-3]) % 1000000007
if broke == False:
    print(dp[N-1])

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000000000)
input = sys.stdin.readline

N,M = (int(x) for x in input().split())
a = set(int(input()) for _ in range(M))
mem = [0] * N
def count_steps(n):
    if mem[n-1]:
        return mem[n-1]
    elif n - 1 in a and n - 2 in a:
        return 0
    elif n - 1 in a:
        if n > 2:
            mem[n-1] = count_steps(n-2)
            return mem[n-1]
        else:
            mem[1] = 1
            return 1
    elif n - 2 in a:
        mem[n-1] = count_steps(n-1)
        return mem[n-1]
    elif n == 1:
        mem[0] = 1
        return 1
    elif n == 2:
        mem[1] = 2
        return 2
    else:
        mem[n-1] = (count_steps(n-1) + count_steps(n-2)) % 1000000007
        return mem[n-1]
print(count_steps(N))

Submission status: Runtime Error

Solution code:
# C - Typical Stairs

MOD = (10 ** 9) + 7
N, M = map(int, input().split())
A = [False] * (N + 1)
for i in range(N):
    A[int(input())] = True
dp = [0] * (N + 1)
dp[0] = 1
if 1 not in A:
    dp[1] = 1

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

print(dp[N])

Submission status: Runtime Error

Solution code:
# C - Typical Stairs

import sys
sys.setrecursionlimit(10000)

MOD = (10 ** 9) + 7
INF = float('inf')
N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
dp = [INF] * (N + 1)

def f(i):
    if dp[i] != INF:
        return dp[i]
    else:
        if i in A:
            dp[i] = 0
        elif i < 2:
            dp[i] = 1
        else:
            dp[i] = (f(i - 1) + f(i - 2)) % MOD
        return dp[i]

print(f(N))

Submission status: Runtime Error

Solution code:
# C - Typical Stairs

MOD = (10 ** 9) + 7
INF = float('inf')
N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
dp = [INF] * (10 ** 5)

def f(i):
    if dp[i] != INF:
        return dp[i]
    else:
        if i in A:
            dp[i] = 0
        elif i < 2:
            dp[i] = 1
        else:
            dp[i] = (f(i - 1) + f(i - 2)) % MOD
        return dp[i]

print(f(N))

Submission status: Runtime Error

Solution code:
# C - Typical Stairs

MOD = (10 ** 9) + 7
INF = float('inf')
N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
dp = [INF] * (N + 1)

def f(i):
    if dp[i] != INF:
        return dp[i]
    else:
        if i in A:
            dp[i] = 0
        elif i < 2:
            dp[i] = 1
        else:
            dp[i] = (f(i - 1) + f(i - 2)) % MOD
        return dp[i]

print(f(N))

Submission status: Runtime Error

Solution code:
# C - Typical Stairs

MOD = (10 ** 9) + 7
N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
dp = [None] * (N + 1)

def f(i):
    if dp[i] != None:
        return dp[i]
    else:
        if i in A:
            dp[i] = 0
        elif i < 2:
            dp[i] = 1
        else:
            dp[i] = (f(i - 1) + f(i - 2)) % MOD
        return dp[i]

f(N)
print(dp[N])

Submission status: Runtime Error

Solution code:
# C - Typical Stairs

MOD = 10 ** 9 + 7
N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
dp = [None] * (N + 1)

def f(i):
    if dp[i] != None:
        return dp[i]
    else:
        if i in A:
            dp[i] = 0
        elif i < 2:
            dp[i] = 1
        else:
            dp[i] = (f(i - 1) + f(i - 2)) % MOD
        return dp[i]

f(N)
print(dp[N])

Submission status: Runtime Error

Solution code:
# C - Typical Stairs

MOD = 10 ** 9 + 7
N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
dp = [0] * (N + 1)

def f(i):
    if dp[i] != 0:
        return dp[i]
    else:
        if i in A:
            dp[i] = 0
        elif i < 2:
            dp[i] = 1
        else:
            dp[i] = (f(i - 1) + f(i - 2)) % MOD
        return dp[i]

print(f(N))