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:
# C - Typical Stairs

MOD = 1000000007
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] % MOD
    else:
        if i in A:
            dp[i] = 0
        elif i < 2:
            dp[i] = 1
        else:
            dp[i] = f(i - 1) + f(i - 2)
        return dp[i] % MOD

print(f(N))

Submission status: Runtime Error

Solution code:
# C - Typical Stairs

MOD = 1000000007
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)
        return dp[i] % MOD

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)
        return dp[i] % MOD

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]

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 == 1 or i == 0:
            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 == 1 or i == 0:
            dp[i] = 1
        else:
            dp[i] = f(i - 1) + f(i - 2)
        return dp[i]

print(f(N) % MOD)

Submission status: Runtime Error

Solution code:
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,M = LI()
a = set([I() for _ in range(M)])
dp = [0]*(N+1) #1_indexed
dp[1] = 0 if 1 in a else 1
dp[2] = 0 if 2 in a else (1+dp[1])
for i in range(3,N+1):
    if i in a:
        dp[i] = 0
        continue
    dp[i] = (dp[i-2]+dp[i-1])%1000000007
print(dp[-1])

Submission status: Runtime Error

Solution code:
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,M = LI()
a = set([I() for _ in range(M)])
dp = [0]*(N+1) #1_indexed
dp[1] = 0 if 1 in a else 1
dp[2] = 0 if 2 in a else 1 +dp[1]
for i in range(3,N+1):
    if i in a:
        dp[i] = 0
        continue
    dp[i] = (dp[i-2]+dp[i-1])%1000000007
print(dp[-1])

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
a = list(int(input()) for i in range(M))
DP = [0]*(N+1)
pointer = 0
for i in range(N+1):
    if i in a[pointer]:
        DP[i] = 0
        pointer += 1
    elif i == 0 or i == 1:
        DP[i] = 1
    else:
        DP[i] = (DP[i-1]+DP[i-2])
print(DP[-1]%1000000007)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
def main():
    N, M = map(int, input().split())
    A = deque([int(input()) for i in range(M)])
    dp = [0]*N
    # 一段目と二段目への行き方
    if len(A) != 0:
        out = A.popleft() 
    else:
        out = 0

    if out != 1:
        dp[0] = 1
    else:
        dp[0] = 0
        if len(A) != 0:
            out = A.popleft()
    if out != 2:
        dp[1] = 1+dp[0]
    else:
        dp[1] = 0
        if len(A) != 0:
            out = A.popleft()

    for i in range(2,N):
        if i+1 == out:
            dp[i] = 0
            if len(A) != 0:
                out = A.popleft()
        else:
            if dp[i-2] != 0 or dp[i-1] != 0:
                dp[i] = dp[i-2] + dp[i-1]

    if dp[N-1] != 0:
        print(dp[N-1]%(10**9 + 7))
    else:
        print(0)
    
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
def main():
    N, M = map(int, input().split())
    A = deque([int(input()) for i in range(M)])
    dp = [0]*N
    # 一段目と二段目への行き方
    if len(A) != 0:
        out = A.popleft 
    else:
        out = 0
        
    if out != 1:
        dp[0] = 1
    else:
        dp[0] = 0
        if len(A) != 0:
            out = A.popleft 
    if out != 2:
        dp[1] = 1+dp[0]
    else:
        dp[1] = 0
        if len(A) != 0:
            out = A.popleft 

    for i in range(2,N):
        if i+1 == out:
            dp[i] = 0
            if len(A) != 0:
                out = A.popleft()
        else:
            if dp[i-2] != 0 or dp[i-1] != 0:
                dp[i] = dp[i-2] + dp[i-1]

    if dp[N-1] != 0:
        print(dp[N-1]%(10**9 + 7))
    else:
        print(0)
    
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
def main():
    N, M = map(int, input().split())
    A = deque([int(input()) for i in range(M)])
    dp = [0]*N
    # 一段目と二段目への行き方
    dp[0] = 1
    dp[1] = 2
    out = A.popleft()
    for i in range(2,N):
        if i+1 == out:
            dp[i] = 0
            if len(A) != 0:
                out = A.popleft()
        else:
            if dp[i-2] != 0 or dp[i-1] != 0:
                dp[i] = dp[i-2] + dp[i-1]
    if dp[N-1] != 0:
        print(dp[N-1]%(10**9 + 7))
    else:
        print(0)
    
if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

stair = []
for i in range(N):
    if i+1 in a:
        stair.append(False)
    else:
        stair.append(True)

# DP
dp = [0] * N
if stair[0]:
    dp[0] = 1
if stair[1]:
    dp[1] = dp[0] + 1
else:
    dp[1] = 0

for i in range(2, N):
    if not stair[i]:
        dp[i] = 0
        continue
    if stair[i-1] and stair[i-2]:
        dp[i] = dp[i-1] + dp[i-2]
    elif stair[i-1]:
        dp[i] = dp[i-1]
    elif stair[i-2]:
        dp[i] = dp[i-2]
        
print(dp[N-1] % MOD)

Submission status: Runtime Error

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

for i in range(m):
    if m == 1:
        break
    if a[i+1] - a[i] == 1:
        print(0)
        exit()

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

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

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

print(dp[n])

Submission status: Runtime Error

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

for i in range(m):
    if a[i+1] - a[i] == 1:
        print(0)
        exit()

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

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

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

print(dp[n])

Submission status: Runtime Error

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

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

mod = (10**9)+7
ans = 0

def steps(now):
    if now == n:
        global ans
        ans += 1
        ans %= mod
    else:
        if s[now+1] == 0:
            steps(now+1)
        if now+2 <= n:
            if s[now+2] == 0:
                steps(now+2)
            
steps(0)
print(ans)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
dp = [0]*(N+1)
last_step= 0
for i in range(N+1):
    if i == 0:
        dp[0] = 1
    elif i == 1:
        if 1 == a[last_step]:
            dp[1] = 0
            if last_step +1 < M:
                last_step += 1
        else:
            dp[1] = 1
    else:
        if i  == a[last_step]:
            dp[i] = 0
            if last_step +1 < M:
                last_step += 1
        else:
            dp[i] = dp[i-1] + dp[i-2]
print(dp[-1]%1000000007)

Submission status: Runtime Error

Solution code:
import sys
N, M = map(int, input().split())
ok = [True] * (N + 1)
for _ in range(M):
    a = int(sys.stdin.readline())
    ok[a] = False

dp = [0] * (N + 1)
if ok[1]:
    dp[1] = 1
if ok[2]:
    dp[2] = 2
for s in range(3, N + 1):
    if ok[s]:
        dp[s] = dp[s-1] + dp[s-2]
        dp[s] %= 1000000007
    else:
        dp[s] = 0

print(dp[N])

Submission status: Runtime Error

Solution code:
import sys
N, M = map(int, input().split())
ok = [True] * (N + 1)
for _ in range(M):
    a = int(sys.stdin.readline())
    ok[a] = False

dp = [0] * (N + 1)
dp[1] = 1
dp[2] = 2
for s in range(3, N + 1):
    if ok[s]:
        dp[s] = dp[s-1] + dp[s-2]
        dp[s] %= 1000000007
    else:
        dp[s] = 0

print(dp[N])

Submission status: Runtime Error

Solution code:
import sys
from functools import lru_cache
N, M = map(int, input().split())
ok = [True] * (N + 1)
for _ in range(M):
    a = int(sys.stdin.readline())
    ok[a] = False
sys.setrecursionlimit(N + 10000)
@lru_cache(maxsize=None)
def f(s):
    if not ok[s]:
        return 0
    if s in (0, 1, 2):
        return s
    count = f(s - 1) + f(s - 2)
    count %= 1000000007
    return count

ans = f(N)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
from functools import lru_cache
N, M = map(int, input().split())
ok = [True] * (N + 1)
for _ in range(M):
    a = int(sys.stdin.readline())
    ok[a] = False
sys.setrecursionlimit(N + 100)
@lru_cache(maxsize=None)
def f(s):
    if not ok[s]:
        return 0
    if s in (0, 1, 2):
        return s
    count = f(s - 1) + f(s - 2)
    count %= 1000000007
    return count

ans = f(N)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
from functools import lru_cache
N, M = map(int, input().split())
ok = [True] * (N + 1)
for _ in range(M):
    a = int(sys.stdin.readline())
    ok[a] = False

@lru_cache(maxsize=None)
def f(s):
    if not ok[s]:
        return 0
    if s in (0, 1, 2):
        return s
    count = f(s - 1) + f(s - 2)
    count %= 1000000007
    return count

ans = f(N)
print(ans)

Submission status: Runtime Error

Solution code:

n,m = map(int,input().split())
b = [True] * n
for i in range(m):
    x = int(input())
    b[x-1] = False

dp = [0] * n
if(n == 1):
    print(1)
if(b[0]):
    dp[0] = 1
    if(b[1]):dp[1] = 2
else:
    if(b[1]):dp[1] = 1

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

Submission status: Runtime Error

Solution code:

n,m = map(int,input().split())
b = [True] * n
for i in range(m):
    x = int(input())
    b[x-1] = False

dp = [0] * n

if(b[0]):
    dp[0] = 1
    if(b[1]):dp[1] = 2
else:
    if(b[1]):dp[1] = 1

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

Submission status: Runtime Error

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

mod = pow(10, 9)+7
point = [0]*(n+1)
point[0] = 1
j = 0
if 1 in a:
    point[1] = 0
    j += 1
else:
    point[1] = 1

if m == 0:
    a = [0]

for i in range(2, n+1):
    if i == a[j]:
        if j < m-1:
            j += 1
    else:
        point[i] = point[i-1]+point[i-2]
        point[i] %= mod

print(point[-1] % mod)

Submission status: Runtime Error

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

mod = pow(10, 9)+7
point = [0]*(n+1)
point[0] = 1
j = 0
if 1 in a:
    point[1] = 0
    j += 1
else:
    point[1] = 1

for i in range(2, n+1):
    if i == a[j]:
        if j < m-1:
            j += 1
    else:
        point[i] = point[i-1]+point[i-2]
        point[i] %= mod

print(point[-1] % mod)

Submission status: Runtime Error

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

mod = pow(10, 9)+7
point = [0]*(n+1)
point[0] = 1
if a[0] != 1:
    point[1] = 1

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

# print(point)
print(point[-1] % mod)

Submission status: Runtime Error

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

for i in range(1, m):
    if a[i]-a[i-1] == 1:
        print(0)
        exit()
mod = pow(10, 9)+7
point = [0]*(n+1)
point[0] = 1
if a[0] != 1:
    point[1] = 1

for i in range(2, n+1):
    if not(i in a):
        point[i] = point[i-1]+point[i-2]
        point[i] %= mod


print(point[-1] % mod)

Submission status: Runtime Error

Solution code:

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

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

print(dp[n])

Submission status: Runtime Error

Solution code:

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

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

print(dp[n])

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
n, m = map(int, input().split())
a = eval("int(input()),"*m)
f = lambda j: j not in a

mod = 10**9+7

dp = [0] * -~n
dp[0] = 1
dp[1] = f(1)

for i in range(2, -~n):
    dp[i] += (dp[i - 1] + dp[i - 2]) * f(i) % mod

print(dp[n])

Submission status: Runtime Error

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

dp = [0] * (n+1)
dp[0] = 1
if 1 not in a:
    dp[1] = 1
else:
    dp[1] = 0
    
for i in range(2,n+1):
    if i in a:
        pass
    else:
        dp[i] = dp[i-1] + dp[i-2]
        
print(dp[n]%MOD)

Submission status: Runtime Error

Solution code:
#### C
from functools import reduce
from operator import mul
n,m = map(int,input().split())
a = [int(input()) for _ in range(m)]
MOD = 10 ** 9 + 7
def fib(n):
    if n == 1:
        return 0
    elif n == 2:
        return 1
    else:
        return fib(n-1) + fib(n-2)
   
a.append(n+1)
cnt = []
prev = 0
for i in a:
    tmp = fib(i+1-prev)
    cnt.append(tmp)
    prev = i+1
    
print(reduce(mul,cnt)%MOD)

Submission status: Runtime Error

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

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

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

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

Submission status: Runtime Error

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

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

Submission status: Runtime Error

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

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

Submission status: Runtime Error

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

#初期状態定義
dp[0] = 1
if 1 not in a:
  dp[1] = 1
else:
  dp[1] = 0

for i in range(2,n+1):
    if i-1 not in a :
      dp[i] += dp[i-1] #n-1 段目が安全なら
    if i-2 not in a :
      dp[i] += dp[i-2] #n-2 段目が安全なら
dp[i] %= INF

print(dp[n])

Submission status: Runtime Error

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

Submission status: Runtime Error

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

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

for i in range(2,n+1):
    if i not in a :
      dp[i] += dp[i-1] #n-1 段目が安全なら
      dp[i] += dp[i-2] #n-2 段目が安全なら
dp[i] %= INF

print(dp[n])

Submission status: Runtime Error

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

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

for i in range(2,n+1):
    if i not in a :
      dp[i] += dp[i-1] #n-1 段目が安全なら
      dp[i] += dp[i-2] #n-2 段目が安全なら
dp[i] %= INF

print(dp[n])

Submission status: Runtime Error

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

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

for i in range(2,n+1):
    if i not in a :
      dp[i] += dp[i-1] #n-1 段目が安全なら
      dp[i] += dp[i-2] #n-2 段目が安全なら
dp[i] %= INF

print(dp[n])

Submission status: Runtime Error

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

stair = [0]*n
s = 1
s_tmp = 2
for i in range(n):
    stair[i] = s
    s_tmp_tmp = s_tmp
    s_tmp = s_tmp+s
    s= s_tmp_tmp
    
#print(stair)

ans = 1
muri = 0
tmp = -1
for i in range(m):
    
    a = int(input())
    
    # 前の欠陥から連続の場合fail
    if a-1 == tmp:
        muri = 1
        break
    
    # 1段目スキップ
    elif a == 1:
        tmp = a
        continue
    # そうでないとき、まえの欠陥から正常な段数だけパターンがある
    else:
        ans *= stair[a-tmp-3]
        ans %= (10**9)+7

    # 1段前を記録
    tmp = a

# 最後の階段
ans *= stair[n-tmp-2]

if muri == 1:
    print(0)
else:
    if m == 0:
        print(stair[n+1]%10**9+7)
    else:
        print(ans%(10**9+7))

Submission status: Runtime Error

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

total=1
cannot=0
s=-1
for i in range(m):
    t=int(input())
    if t-s == 1:
        cannot+=1
        break
    else:
        total*=fib[t-s-2]
        total%=10**9+7
    s=t



if n+1-t <= 1:
    cannot+=1
else:
    total*=fib[n-t-1]
    total%=10**9+7

if cannot != 0:
    print(0)
else:
    print(total)

Submission status: Runtime Error

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

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

Submission status: Runtime Error

Solution code:

n,m=map(int,input().split())
a=[1]*(n+1)
for i in range(m):
    a[int(input())]=0
memo={}

def count(p):
    if p in memo:
        return memo[p]
    if p==0:
        return 1
    if p==1:
        return a[p]
    if a[p]==1:
        x=count(p-1)+count(p-2)
        memo[p]=x
        return x
    else:
        memo[p]=0
        return 0
print(count(n)%1000000007)

Submission status: Runtime Error

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

    for i in a:
        dp[i] = 0

    print(i_step(n, a, dp) % 1000000007)

# i段目にたどり着くまでの移動方法の総数
def i_step(i, a, dp):
    if i < 0:
        return 0

    if i == 0:
        return 1

    ret = 0
    if dp[i - 1] != -1:
        ret += dp[i - 1]
    else:
        ret += i_step(i - 1, a, dp)

    if i == 1:
        return ret

    if dp[i - 2] != -1:
        ret += dp[i - 2]
    else:
        ret += i_step(i - 2, a, dp)

    dp[i] = ret
    return ret
  
resolve()

Submission status: Runtime Error

Solution code:
from collections import deque

n,m=map(int,input().split())
step=list(range(2,n+1))
broken=[]
for i in range(m):
    broken+=[int(input())]
mod=10**9+7
dp=[0]*(n+1)
dp[0]=1
if m==0:
    dp[1]=1
elif not broken[0]==1:
    dp[1]=1
b=deque(broken)
if len(broken) != 0:
    bad_one = b.popleft()
    if bad_one==1:
        bad_one=b.popleft()
else:
    bad_one = -1
for i in step:
    if i != bad_one:
        dp[i]=(dp[i-1]+dp[i-2])%mod
    elif i == bad_one and len(b) != 0:
        bad_one = b.popleft()
print(dp[n])

Submission status: Runtime Error

Solution code:
from collections import deque

n,m = map(int,input().split())
step = [i for i in range(2, n+1)]
broken = []
for i in range(m):
    broken += [int(input())]

mod = pow(10,9) + 7 #10**9+7
dp = [0 for _ in range(n+1)]
dp[0] = 1

if m == 0:
    dp[1] = 1
    for i in step:
        dp[i] = dp[i-1] + dp[i-2]
else:
    b = deque(broken)
    if not broken[0] == 1:
        dp[1] = 1
    else:
        b.popleft()
    if len(broken) != 0:
        bad_one = b.popleft()
    for i in step:
        if i != bad_one:
            dp[i] = (dp[i-1]+dp[i-2]) % mod
        elif i == bad_one and len(b) != 0:
            bad_one = b.popleft()
print(dp[n] % mod)

Submission status: Runtime Error

Solution code:
from collections import deque

n,m=map(int,input().split())
step=list(range(2,n+1))
broken=[]
for i in range(m):
    broken+=[int(input())]
mod=10**9+7
dp=[0]*(n+1)
dp[0]=1
if m==0:
    dp[1]=1
elif not broken[0]==1:
    dp[1]=1
b=deque(broken)
if len(broken) != 0:
    bad_one = b.popleft()
for i in step:
    if i != bad_one:
        dp[i]=(dp[i-1]+dp[i-2])%mod
    elif i == bad_one and len(b) != 0:
        bad_one = b.popleft()
print(dp[n])

Submission status: Runtime Error

Solution code:
from collections import deque

n,m=map(int,input().split())
step=list(range(2,n+1))
broken=[]
for i in range(m):
    broken+=[int(input())]
mod=10**9+7
dp=[0]*(n+1)
dp[0]=1
if m==0:
    dp[1]=1
elif not broken[0]==1:
    dp[1]=1
b=deque(broken)
bad_one = b.popleft()
for i in step:
    if i != bad_one:
        dp[i]=(dp[i-1]+dp[i-2])%mod
    elif i == bad_one and len(b) != 0:
        bad_one = b.popleft()
print(dp[n])

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
# import sys
# sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]


def Fibo(n, memo={}):
    if n == 1:
        return 0
    elif n == 2:
        return 1
    elif n in memo:
        return memo[n]
    else:
        memo[n] = Fibo(n-1,memo)+Fibo(n-2,memo)
        return memo[n]

def solve():
    n, m = MI()
    s = 0
    mod = 1000000007
    ans = 1
    for _ in range(m):
        t = II() - 1
        d = t - s
        if d < 0:
            ans = 0
        else:
            keiro = Fibo(d + 2)
        # print(s, t, d, keiro)
        ans = ans * keiro % mod
        s = t + 2
    d = n - s
    if d < 0:
        keiro = 0
    else:
        keiro = Fibo(d + 2)

    ans = ans * keiro % mod
    print(ans % mod)


if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
# import sys
# sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]


def Fibo(n, memo={}):
    if n == 1:
        return 0
    elif n == 2:
        return 1
    elif n in memo:
        return memo[n]
    else:
        memo[n] = Fibo(n-1,memo)+Fibo(n-2,memo)
        return memo[n]

def solve():
    n, m = MI()
    s = 0
    mod = 1000000007
    ans = 1
    for _ in range(m):
        t = II() - 1
        d = t - s
        if d < 0:
            ans = 0
            break
        else:
            keiro = Fibo(d + 2)
        # print(s, t, d, keiro)
        ans = ans * keiro % mod
        s = t + 2
    d = n - s
    if d < 0:
        keiro = 0
    else:
        keiro = Fibo(d + 2)

    ans = ans * keiro % mod
    print(ans % mod)


if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
# import sys
# sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]


def Fibo(n, memo={}):
    if n == 1:
        return 0
    elif n == 2:
        return 1
    elif n in memo:
        return memo[n]
    else:
        memo[n] = Fibo(n-1,memo)+Fibo(n-2,memo)
        return memo[n]

def solve():
    n, m = MI()
    s = 0
    mod = 1000000007
    ans = 1
    for _ in range(m):
        t = II() - 1
        d = t - s
        if d < 0:
            ans = 0
            break
        else:
            keiro = Fibo(d + 2)
        # print(s, t, d, keiro)
        ans = ans * keiro
        s = t + 2
    d = n - s
    if d < 0:
        keiro = 0
    else:
        keiro = Fibo(d + 2)

    ans = ans * keiro
    print(ans % mod)


if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
# import sys
# sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]


def Fibo(n, memo={}):
    if n == 1:
        return 0
    elif n == 2:
        return 1
    elif n in memo:
        return memo[n]
    else:
        memo[n] = Fibo(n-1,memo)+Fibo(n-2,memo)
        return memo[n]

def solve():
    n, m = MI()
    A = []
    s = 0
    mod = 1000000007
    ans = 1
    for _ in range(m):
        t = II() - 1
        d = t - s
        if d < 0:
            keiro = -1
        else:
            keiro = Fibo(d + 2)
        # print(s, t, d, keiro)
        ans = ans * keiro
        s = t + 2
    d = n - s
    keiro = Fibo(d + 2)
    ans = ans * keiro
    if ans < 0:
        print(0)
    else:
        print(ans % mod)



if __name__ == '__main__':
    solve()

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

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

Submission status: Runtime Error

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

def get_number(s):
	if s==0:
		return 1
	else:
		DP=[0]*s
		DP[0]=1
		DP[1]=1
		for i in range(2,s):
			DP[i]=DP[i-1]+DP[i-2]
    
		return DP[s-1]
Cnt = get_number(A[0]-1)
for i in range(M-1):
	Cnt = Cnt*get_number(A[i+1]-A[i]-1)
    
Cnt = Cnt*get_number(N-A[M-1])
print(Cnt%1000000007)