Problem:


Score : 300 points

Problem Statement

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

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

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

Constraints

1 \leq N \leq 10^5

0 \leq M \leq N-1

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

Input

Input is given from Standard Input in the following format:

N M
a_1
a_2
 .
 .
 .
a_M

Output

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

Sample Input 1

6 1
3

Sample Output 1

4

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

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

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

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

0 \to 2 \to 4 \to 6

Sample Input 2

10 2
4
5

Sample Output 2

0

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

Sample Input 3

100 5
1
23
45
67
89

Sample Output 3

608200469

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



Sample input:
6 1
3


Sample output:
4

Submission status: Runtime Error

Solution code:
import math
import string
import collections
from collections import Counter
from collections import deque
import sys
sys.setrecursionlimit(2*10**5)
INF = 2**60


def readints():
    return list(map(int, input().split()))


def nCr(n, r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))


def has_duplicates2(seq):
    seen = []
    for item in seq:
        if not(item in seen):
            seen.append(item)
    return len(seq) != len(seen)


def divisor(n):
    divisor = []
    for i in range(1, n+1):
        if n % i == 0:
            divisor.append(i)
    return divisor


# coordinates
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]

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

safe = [True]*(N+1)
for i in range(M):
    safe[(a[i])] = False

# print(a)
dp = [0]*(2*N)
#print('safe', safe)
dp[0] = 1
for i in range(0, N):
    if safe[i]:
        dp[i+1] = dp[i+1]+dp[i]
        dp[i+2] = dp[i+2]+dp[i]

    if not(safe[i]):
        dp[i] = 0
#print('dp', dp)
print(dp[N] % 1000000007)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
danger = list(int(input()) for _ in range(m))
danger = [0] + danger + [n]
def fibo(n):
    memo = [-1]*(n+1)
    def _fibo(n):
        if memo[n] != -1:
            return memo[n]
        else:
            if n <= 1:
                memo[n] = n
                return memo[n]
            else:
                memo[n] = _fibo(n-1) + _fibo(n-2)
                return memo[n]
    return _fibo(n)
ans = 1
for j in range(m+1):
    if danger[j+1] - danger[j] ==1:
        ans *= 0
    else:
        ans *= fibo(danger[j+1] - danger[j] )
print(ans)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
danger = list(int(input()) for _ in range(m))
danger = [0] + danger + [n]
def fibo(n):
    memo = [-1]*(n+1)
    def _fibo(n):
        if memo[n] != -1:
            return memo[n]
        else:
            if n <= 1:
                memo[n] = n
                return memo[n]
            else:
                memo[n] = _fibo(n-1) + _fibo(n-2)
                return memo[n]
    return _fibo(n)
ans = 1
for j in range(m+1):
    ans *= fibo(danger[j+1] - danger[j] )
print(ans)

Submission status: Runtime Error

Solution code:
import math
import string
import collections
from collections import Counter
from collections import deque


def readints():
    return list(map(int, input().split()))


def nCr(n, r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))


def has_duplicates2(seq):
    seen = []
    for item in seq:
        if not(item in seen):
            seen.append(item)
    return len(seq) != len(seen)


def divisor(n):
    divisor = []
    for i in range(1, n+1):
        if n % i == 0:
            divisor.append(i)
    return divisor


# coordinates
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]

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

safe = [True]*(N+1)
for i in range(M):
    safe[(a[i])] = False


def func(i):
    global safe

    if not(safe[i]):
        return 0
    if i == 0:
        return 1
    if i == 1:
        return 1
    if i >= 2:
        return func(i-1)+func(i-2)


print(func(N) % 1000000007)

# print(a)
# dp = [0]*(N+1)
# print('safe', safe)
# dp[0] = 1
# if safe[1]:
#    dp[1] = 1
# for i in range(2, N+1):
#    if safe[i]:
#        dp[i] = dp[i-1]+dp[i-2]
#    if not(safe[i]):
#        dp[i] = 0
# print('dp', dp)
# print(dp[N] % 1000000007)

Submission status: Runtime Error

Solution code:
import sys
IS = lambda: sys.stdin.readline().rstrip()
II = lambda: int(IS())
MII = lambda: list(map(int, IS().split()))

def main():
    n, m = MII()
    a_lst = [II() for _ in range(m)]
    DIV = 10**9+7
    stairs = [1]*2 + [0]*(n-1)
    for a in a_lst:
        stairs[a] = 'NG'
    cnt = 0
    for i in range(2, n+1):
        if cnt == 2:
            print(0)
            exit(1)
        if stairs[i] == 'NG': cnt += 1; continue
        cnt = 0
        a = stairs[i-1] if stairs[i-1] != 'NG' else 0
        b = stairs[i-2] if stairs[i-2] != 'NG' else 0
        stairs[i] = a + b
    print(stairs[n]%DIV)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
n, m = [int(i) for i in input().split()]
fibo_l = [1, 1] + [None] * (n + 100)
a = [int(input()) for i in range(m)]

def fibo(x):
    if x not in a and x >= 0:
            if fibo_l[x] is None:
                fibo_l[x] = fibo(x - 1) + fibo(x - 2)
            return fibo_l[x]
    else: return 0
    
print(fibo(n) % 1000000007)

Submission status: Runtime Error

Solution code:
n, m = [int(i) for i in input().split()]
fibo_l = [1, 1] + [None] * (n + 1)
a = [int(input()) for i in range(m)]

def fibo(x):
    if x not in a and x >= 0:
            if fibo_l[x] is None:
                fibo_l[x] = fibo(x - 1) + fibo(x - 2)
            return fibo_l[x]
    else: return 0
    
print(fibo(n) % 1000000007)

Submission status: Runtime Error

Solution code:
n, m = [int(i) for i in input().split()]
fibo_l = [1, 1] + [None] * (n - 1)
a = [int(input()) for i in range(m)]

def fibo(x):
    if x not in a and x >= 0:
            if fibo_l[x] is None:
                fibo_l[x] = fibo(x - 1) + fibo(x - 2)
            return fibo_l[x]
    else: return 0
    
print(fibo(n) % 1000000007)

Submission status: Runtime Error

Solution code:
n, m = [int(i) for i in input().split()]
fibo_l = [1, 1] + [None] * (n - 2)
a = [int(input()) for i in range(m)]

def fibo(x):
    if x not in a and x >= 0:
            if fibo_l[x] is None:
                fibo_l[x] = fibo(x - 1) + fibo(x - 2)
            return fibo_l[x]
    else: return 0
    
print(fibo(n) % 1000000007)

Submission status: Runtime Error

Solution code:
n, m = [int(i) for i in input().split()]
fibo_l = [1, 1] + [None] * n
a = [int(input()) for i in range(m)]

def fibo(x):
    if x not in a and x >= 0:
            if fibo_l[x] is None:
                fibo_l[x] = fibo(x - 1) + fibo(x - 2)
                return fibo_l[x]
            else: return fibo_l[x]
    else: return 0
    
print(fibo(n) % 1000000007)

Submission status: Runtime Error

Solution code:
n, m = [int(i) for i in input().split()]
fibo_l = [1, 1] + [None] * n
a = [int(input()) for i in range(m)]

def fibo(x):
    if x not in a and x >= 0:
            if fibo_l[x] is None:
                fibo_l[x] = fibo(x - 1) + fibo(x - 2)
                return fibo_l[x]
            else: return fibo_l[x]
    else: return 0
    
print(fibo(n) % 1_000_000_007)

Submission status: Runtime Error

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

dp = [1]
for _ in range(N+1):
  dp.append(0)
 
#N段目まで行くのにdp[N]通り
s = 0
for i in range(N):
  if A[s] != i:
    dp[i+1] += dp[i]
    dp[i+2] += dp[i]
  else:
    dp[i] = 0
    s += 1
 
print(dp[N]%(10**9+7))

Submission status: Runtime Error

Solution code:
N, M  = map(int, input().split())
A = [int(input()) for i in range(M)]
 
dp = [1]
for _ in range(N+1):
  dp.append(0)
 
#N段目まで行くのにdp[N]通り
s = 0
for i in range(N):
  if A[s] != i:
    dp[i+1] += dp[i]
    dp[i+2] += dp[i]
  else:
    dp[i] = 0
    s += 1
 
print(dp[N]%(10**9+7))

Submission status: Runtime Error

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



N, M  = map(int, input().split())
A = [int(input()) for i in range(M)]
 
dp = [1]
for _ in range(N+1):
  dp.append(0)
 
#N段目まで行くのにdp[N]通り
s = 0
for i in range(N):
  if A[s] != i:
    dp[i+1] += dp[i]
    dp[i+2] += dp[i]
  else:
    dp[i] = 0
    s += 1
 
print(dp[N]%(10**9+7))

Submission status: Runtime Error

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

from collections import deque
N, M  = map(int, input().split())

#A = [int(input()) for i in range(M)]
A = deque()
for i in range(M):
  A.append(int(input()))


A.append(10005)

dp = [1]
for _ in range(N+1):
  dp.append(0)

#N段目まで行くのにdp[N]通り

s = 0
for i in range(N):
  if A[s] != i:
    dp[i+1] += dp[i]
    dp[i+2] += dp[i]
  else:
    dp[i] = 0
    s += 1

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

Submission status: Runtime Error

Solution code:
from collections import deque
N, M  = map(int, input().split())

#A = [int(input()) for i in range(M)]
A = deque()
for i in range(M):
  A.append(int(input()))


A.append(10005)

dp = [1]
dp.append(1)
for _ in range(N):
  dp.append(0)

#N段目まで行くのにdp[N]通り

s = 0
for i in range(N):
  if A[s] != i:
    dp[i+1] += dp[i]
    dp[i+2] += dp[i]
  else:
    dp[i] = 0
    s += 1

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

Submission status: Runtime Error

Solution code:
from collections import deque
N, M  = map(int, input().split())

#A = [int(input()) for i in range(M)]
A = deque()
for i in range(M):
  A.append(int(input()))


A.append(10005)

dp = [1]
for _ in range(N+1):
  dp.append(0)

#N段目まで行くのにdp[N]通り

s = 0
for i in range(N):
  if A[s] != i:
    dp[i+1] += dp[i]
    dp[i+2] += dp[i]
  else:
    dp[i] = 0
    s += 1

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

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(2147483647)

from collections import deque
N, M  = map(int, input().split())

#A = [int(input()) for i in range(M)]
A = deque()
for i in range(M):
  A.append(int(input()))


A.append(10005)

dp = [1]
for _ in range(N+1):
  dp.append(0)

#N段目まで行くのにdp[N]通り

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

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

Submission status: Runtime Error

Solution code:
from collections import deque
N, M  = map(int, input().split())

#A = [int(input()) for i in range(M)]
A = deque()
for i in range(M):
  A.append(int(input()))


A.append(10005)

dp = [1]
for _ in range(N+1):
  dp.append(0)

#N段目まで行くのにdp[N]通り

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

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

Submission status: Runtime Error

Solution code:
from collections import deque
N, M  = map(int, input().split())

#A = [int(input()) for i in range(M)]
A = deque()
if M != 0:
  for i in range(M):
    A.append(int(input()))


A.append(10005)

dp = [1]
for _ in range(N+1):
  dp.append(0)

#N段目まで行くのにdp[N]通り

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

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

Submission status: Runtime Error

Solution code:
from collections import deque
N, M  = map(int, input().split())

#A = [int(input()) for i in range(M)]
A = deque()
for i in range(M):
  A.append(int(input()))
A.append(10005)

dp = [1]
for _ in range(N+1):
  dp.append(0)

#N段目まで行くのにdp[N]通り

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

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

Submission status: Runtime Error

Solution code:
from collections import deque
N, M  = map(int, input().split())

A = [int(input()) for i in range(M)]
A = deque(A)
A.append(10005)

dp = [1]
for _ in range(N+1):
  dp.append(0)

#N段目まで行くのにdp[N]通り

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

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

Submission status: Runtime Error

Solution code:
from collections import deque
N, M  = map(int, input().split())

A = [int(input()) for i in range(M)]
A = deque(A)
A.append(0)

dp = [1]
for _ in range(N+1):
  dp.append(0)

#N段目まで行くのにdp[N]通り

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

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
broken = [0] * n
dp = [0] * (n+1)
in_memo = [0] * (n+1)
for i in range(m):
    broken[int(input())] = 1

def solve(i):
    if(not in_memo[i]):
        if i == n:
            dp[i] = 1
        elif i == n-1:
            dp[i] = 0 if broken[i] else 1
        else:
            dp[i] = 0 if broken[i] else (solve(i+1)+solve(i+2)) % 1000000007
        in_memo[i] = 1
    return dp[i]

print(solve(0))

Submission status: Runtime Error

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

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,M = map(int,readline().split())
A = [True] * (N+10)
MOD = 10 ** 9 + 7
for _ in range(M):
  x = int(readline())
  A[x] = False


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

for i in range(N):
  if not A[i]:
    continue
  
  if A[i+1]:
    DP[i+1] += DP[i]
    DP[i+1] %= MOD
  if A[i+2]:
    DP[i+2] += DP[i]
    DP[i+2]: %= MOD
       
print(DP[N]%MOD)

Submission status: Runtime Error

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

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,M = map(int,readline().split())
A = [True] * (N+10)
MOD = 10 ** 9 + 7
for _ in range(M):
  x = int(readline())
  A[x] = False


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

for i in range(N):
  if not A[i]:
    continue
  
  if A[i+1]:
    DP[i+1] += DP[i]
    DP[i+1] %= MOD
  if A[i+2]:
    DP[i+2] += DP[i]
    DP[i+2]: %= MOD
       
print(DP[N]%MOD)

Submission status: Runtime Error

Solution code:
def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))
def ism():return map(str,input().split())
def isl():return list(map(str,input().split()))

n,m = iim()
broke = []
for j in range(m):
    broke.append(ii())

num = [1]
if broke[0] == 1:
    num.append(0)
    broke.pop(0)
else:
    num.append(1)

for i in range(2,n+1):
    if len(broke) and broke[0] == i:
        num.append(0)
        broke.pop(0)
    else:
        num.append((num[-1]+num[-2])%1000000007)

print(num[-1])

Submission status: Runtime Error

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


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
import math

from collections import defaultdict
from collections import deque
def load(vtype=int):
    return vtype(input().strip())
def load_list(seplator=" ", vtype=int):
    return [vtype(v) for v in input().strip().split(seplator)]
def exit():
    import sys
    sys.exit(0)
def perm_sub(li, used):
    if len(li) == len(used):
        return [deque()]
    k = []
    for i in range(len(li)):
        if i in used:
            continue
        used.add(i)
        sub_list = perm_sub(li, used)
        for sub in sub_list:
            sub.appendleft(li[i])
        k.extend(sub_list)
        used.discard(i)
    return k
def perm_li(li):
    return perm_sub(li, set())
def perm_n(n):
    return perm_sub(list(range(n)), set())
def join_i(li, sep=""):
    return sep.join([str(e) for e in li])
def li2n(li):
    n, base = 0, 1
    for i in range(len(li)-1, -1, -1):
        n += li[i] * base
        base *= 10
    return n
def sli2ili(li):
    return [int(s) for s in li] 
def prime_list(n):
    li = [i for i in range(2, n+1)]
    for i in range(len(li)):
        if li[i] >= int(math.sqrt(n)):
            break
        if li[i] == -1:
            continue
        for j in range(i+1, len(li)):
            if li[j] % li[i] == 0:
                li[j] = -1
    return [n for n in li if n != -1]
def gcd(a, b):
    a, b = max(a, b), min(a, b)
    while True:
        r = a % b
        if r == 0: return b
        a, b = b, r
def lcm(a, b):
    return int(a * b / gcd(a,b))
def all_subset(li):
    s = []
    n = len(li)
    for bit in range(0, (1<<(n+1))):
        ss = set()
        for i in range(0, n):
            if (bit & (1 << i)):
                ss.add(li[i])
        s.append(ss)
    return s
def factorial(n):
    if n == 1:
        return 1
    return n * factorial(n-1)
def mCn(m, n):
    def factorial_ntimes(m, n):
        r = 1
        while n:
            r *= m
            m -= 1
            n -= 1
        return r
    return int(factorial_ntimes(m, n) / factorial(n))


n, m = load_list()
A = []
for _ in range(m):
    A.append(load())
A = set(A)

dp = dict()
def f(now, goal, A):
    if now > goal:
        return 0
    if now == goal:
        return 1
    
    cnt = 0
    if now + 1 in A:
        pass
    elif now + 1 in dp:
        cnt += dp[now+1]
    else: 
        dp[now+1] = f(now+1, goal, A) 
        cnt += dp[now+1]

    if now + 2 in A:
        pass
    elif now + 2 in dp:
        cnt += dp[now+2]
    else:
        dp[now+2] = f(now+2, goal, A) 
        cnt += dp[now+2]
    return cnt
   
cnt = f(0, n, A)
print(cnt % 1000000007)

Submission status: Runtime Error

Solution code:
from functools import lru_cache
n,m=map(int,input().split())
a=[int(input()) for _ in range(m)]
a=sorted(a)
@lru_cache(maxsize=None) 
def fib(n): 
    if n <= 1:
        return 1
    else:
        return fib(n - 2) + fib(n - 1)
ans=fib(a[0])*fib(n-a[-1])
for i in range(1,m):
  if a[i]-a[i-1]==1:
    print(0)
    exit()
  elif m==1:
    print(ans)
    exit()
  ans=ans*fib(a[i]-a[i-1]-1)
print(ans%1000000007)

Submission status: Runtime Error

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

mod = 10**9+7

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

for i in range(1,n+1):
    #print(i)
    if i == ai[num]:
        dp[i] = 0
        num += 1
        num = min(num,len(ai)-1)
    else:
        if i == 1:
            dp[i] = dp[i-1] % mod
        else:
            dp[i] = (dp[i-1] + dp[i-2])%mod
#    dp[i+1] = dp[i-1] + dp[i]
            
print(dp[n]%mod)

Submission status: Runtime Error

Solution code:
from collections import deque
from collections import Counter
from itertools import product, permutations,combinations
from operator import itemgetter
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right, bisect
#pypyではscipy, numpyは使えない
#from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, minimum_spanning_tree
#from scipy.sparse import csr_matrix, coo_matrix, lil_matrix
#import numpy as np
from fractions import gcd
from math import ceil,floor, sqrt, cos, sin, pi, factorial
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7

def main():
  n, m = map(int, readline().split())
  A = list(int(readline()) for i in range(m))
  A.append(INF)
  dp = [0]*(n+1)
  dp[0] = 0
  j = 0
  if A[j] == 1:
    dp[1] = 0
    j += 1
  else:
    dp[1] = 1
  
  if A[j] == 2:
    dp[2] = 0
    j += 1
  else:
    dp[2] = dp[1] + 1
  
  for i in range(3, n+1):
    if A[j] == i:
      dp[i] = 0
      j += 1
    else:
      dp[i] = (dp[i-1]+dp[i-2])%MOD
  print(dp[n])
  
if __name__ == '__main__':
  main()

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
m = [int(input()) for k in range(M)]
ndic = {0:1}
for n in range(N):
    if not dic[n][0]:
        if n+1 in ndic.keys():
            ndic[n+1] += ndic[n]
        else:
            ndic[n+1] = ndic[n]
#         print("add {} to {}".format(ndic[n], n+1))
    else:
        if not n+1 in ndic.keys():
            ndic[n+1] = 0
    if not dic[n][1]:
        if n+2  in ndic.keys():
            ndic[n+2]+= ndic[n]
        else:
            ndic[n+2]= ndic[n]
    else:
        if not n+2 in ndic.keys():
            ndic[n+2] = 0
#         print("add {} to {}".format(ndic[n],n+2 ))

print(ndic[N]%1000000007)

Submission status: Runtime Error

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

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

print(dp[0])

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
m = [int(input()) for k in range(M)]
dic = {}
for n in range(N):
    dic[n]=[n+1 in m, n+2 in m]
ndic = {0:1}
for n in range(N):
    if not dic[n][0]:
        if n+1 in ndic.keys():
            ndic[n+1] += ndic[n]
        else:
            ndic[n+1] = ndic[n]
        #print("add {} to {}".format(ndic[n], n+1))
    else:
        if not n+1 in ndic.keys():
            ndic[n+1] = 0
    if not dic[n][1]:
        if n+2  in ndic.keys():
            ndic[n+2]+= ndic[n]
        else:
            ndic[n+2]= ndic[n]
    else:
        if not n+2 in ndic.keys():
            ndic[n+2] = 0
        #print("add {} to {}".format(ndic[n],n+2 ))
        
print(ndic[N]%10000000070

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
n, m = map(int,input().split())
hole = [int(input()) for _ in range(m)]
k = 0
a, b = 0, 0
x = (10 ** 9 + 7)
for i in range(n):
    if i + 1 == hole[k]:
        a, b = 0, a
    else:
        if i == 0:
            a = 1
        elif i == 1:
            a, b = (a + 1) % x, a % x
        else:
            a, b = (a + b) % x, a % x
    if i + 1 >= hole[k] and k < m - 1:
        k += 1

    
print(a)

Submission status: Runtime Error

Solution code:
import math
import sys
sys.setrecursionlimit(100000)
f = math.factorial
n, m = map(int, input().split())
a = [-1] + [int(input()) for i in range(m)] + [n+1]
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10 ** 9 + 7
N = 10 ** 4  # N は必要分だけ用意する
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]
 
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)


count = 1
for i in range(m+1):
    k = a[i+1] - a[i] - 2
    if k == -1:
        count = 0
        break
    else:
        work = 0
        for b in range(k//2+1):
            work += cmb(k-b, b, p)
        count *= work
print(count%p)

Submission status: Runtime Error

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

ans=1
if min(b)==-1:
  ans=0
else:
  for i in range(m):
    ans=(ans*x[b[i]])%p
print(ans)

Submission status: Runtime Error

Solution code:
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
dp[2] = 2
if m == 0:
    for i in range(2,n+1):
        dp[i] = dp[i-1] + dp[i-2]
    print(dp[n]%(10**9+7))
else:
    c = 0
    for i in range(1,n+1):
        if i == a[c]:
            dp[i] = 0
            if c < m-1:
                c += 1
        else:
            dp[i] = dp[i-1] + dp[i-2]

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

Submission status: Runtime Error

Solution code:
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
dp[2] = 2
c = 0
for i in range(1,n+1):
    if i == a[c]:
        dp[i] = 0
        if c < m-1:
            c += 1
    else:
        dp[i] = dp[i-1] + dp[i-2]

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

Submission status: Runtime Error

Solution code:
import sys


input = sys.stdin.readline

N, M = map(int, input().split())
has_broken = [False]*(N+3)
prev_a = int(input())
has_broken[prev_a+2] = True
for _ in range(M-1):
    a = int(input())
    has_broken[a+2] = True

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

print(dp[N+2])

Submission status: Runtime Error

Solution code:
import sys


sys.setrecursionlimit(10**6)
N, M = map(int, input().split())
has_broken = [True, True, False] + [False for _ in range(N)]
prev_a = int(input())
has_broken[prev_a+2] = True
for _ in range(M-1):
    a = int(input())
    has_broken[a+2] = True


# dp[i] := i段目にたどり着く移動方法の総数
# 一歩で1段か2段上れるのだから、dp[i]は前段と前々段へたどり着く方法の和
# dp[i] = dp[i-1] + dp[i-2]
# dp配列は-1段目と-2段目の分大きくなっています
dp = [0 for _ in range(N+3)]
# 一段目初期化
dp[2] = 1

for i in range(2, N+3):
    if not has_broken[i]:
        dp[i] += dp[i-1] + dp[i-2]

print(dp[N+2]%1000000007)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
has_broken = [True, True, False] + [False for _ in range(N)]
prev_a = int(input())
has_broken[prev_a+2] = True
for _ in range(M-1):
    a = int(input())
    has_broken[a+2] = True


# dp[i] := i段目にたどり着く移動方法の総数
# 一歩で1段か2段上れるのだから、dp[i]は前段と前々段へたどり着く方法の和
# dp[i] = dp[i-1] + dp[i-2]
# dp配列は-1段目と-2段目の分大きくなっています
dp = [0 for _ in range(N+3)]
# 一段目初期化
dp[2] = 1

for i in range(2, N+3):
    if not has_broken[i]:
        dp[i] += dp[i-1] + dp[i-2]

print(dp[N+2]%1000000007)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
has_broken = [True, True, False] + [False for _ in range(N)]
prev_a = int(input())
has_broken[prev_a+2] = True
for _ in range(M-1):
    a = int(input())
    # 壊れているのが連続していたら上がれない
    if prev_a == a+1:
        print(0)
        exit(0)
    has_broken[a+2] = True


# dp[i] := i段目にたどり着く移動方法の総数
# 一歩で1段か2段上れるのだから、dp[i]は前段と前々段へたどり着く方法の和
# dp[i] = dp[i-1] + dp[i-2]
# dp配列は-1段目と-2段目の分大きくなっています
dp = [0 for _ in range(N+3)]
# 一段目初期化
dp[2] = 1

for i in range(2, N+3):
    if not has_broken[i]:
        dp[i] += dp[i-1] + dp[i-2]

print(dp[N+2]%1000000007)

Submission status: Runtime Error

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

lst=[0]*(N+1)
def func(n):
    if n in a:
        return 0
    if n<=1:
        return 1
    else:
        if lst[n]:
            return lst[n]
        else:
            temp=(func(n-1)+func(n-2))%(10**9+7)
            lst[n]=temp
            return temp

print(func(N))

Submission status: Runtime Error

Solution code:
def func(n):
    if n>=3:
        return (func(n-1)+func(n-2))%(10**9+7)
    elif n==2:
        return 2
    else:
        return 1

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

    a=[-1]+a+[N+1]
    answer=1
    for i in range(M+1):
        if a[i+1]-a[i]==1:
            print(0)
            break
        answer=( func(a[i+1]-a[i]-2)*answer )%(10**9+7)
    else:
        print(answer)

else:
    print(func(N))

Submission status: Runtime Error

Solution code:
def func(n):
    if n>=3:
        return (func(n-1)%(10**9+7)+func(n-2)%(10**9+7))%(10**9+7)
    elif n==2:
        return 2
    else:
        return 1

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



    a=[-1]+a+[N+1]
    answer=1
    for i in range(M+1):
        if a[i+1]-a[i]==1:
            print(0)
            break
        answer=( func(a[i+1]-a[i]-2)*answer )%(10**9+7)
    else:
        print(answer)

else:
    print(func(N))

Submission status: Runtime Error

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

def func(n):
    if n>=3:
        return (func(n-1)%(10**9+7)+func(n-2)%(10**9+7))%(10**9+7)
    elif n==2:
        return 2
    else:
        return 1

a=[-1]+a+[N+1]
answer=1
for i in range(M+1):
    if a[i+1]-a[i]==1:
        print(0)
        break
    answer=( func(a[i+1]-a[i]-2)*answer )%(10**9+7)
else:
    print(answer)

Submission status: Runtime Error

Solution code:
inputs = input().split(' ')
n = int(inputs[0])+1
a = [-1]
while True:
    try:
        a.append(int(input()))
    except:
        break

a_next = a[1:] + [n]
margins = []
for i, j in zip(a, a_next):
    margins.append(j-i-1)

mod = 1000000007
N_max = pow(10,5)
fibo_list = [0 for i in range(N_max+1)]
fibo_list[0] = 0
fibo_list[1] = 1
fibo_list[2] = 1
for i in range(3,N_max+1):
    fibo_list[i] = (fibo_list[i-1] + fibo_list[i-2])%mod

result = 1
for i in margins:
    result = (result*fibo_list[i])%mod

print(result)

Submission status: Runtime Error

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

#n = int(input())
#l = list(map(int, input().split()))

'''
A=[]
B=[]
for i in range():
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)'''


n,m=map(int, input().split())
fibo = [1, 1]
for i in range(1, 10**5+1):
    fibo.append(fibo[i]+fibo[i-1])
#print(fibo)
a=[]
for i in range(m):
    a.append(int(input()))

flg=True
for i in range(m-1):
    if a[i]+1==a[i+1]:
        flg=False
        break
#print(a[0]==a[1],flg)
if not flg:
    print(0)
else:
    ans=1
    if m==1:
        #print(fibo[a[0]-1],fibo[n-a[0]-1])
        print(fibo[a[0]-1]*fibo[n-a[0]-1] % (10**9+7))
    else:
        for i in range(1,m):
            #print(a[i],a[i-1])
            #print(fibo[21])
            #print(fibo[a[i]-a[i-1]-1])
            ans*=fibo[a[i]-a[i-1]-2]
            print(ans % (10**9+7))

        #print(fibo[a[0]-1],fibo[n-a[m-1]-1],fibo[10])
        print(ans*fibo[a[0]-1]*fibo[n-a[m-1]-1]%(10**9+7))