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 sys
#from scipy.special import comb
#from scipy.misc import comb

from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

sys.setrecursionlimit(100000)
nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]


def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

N,M = list(map(int, input().split()))

A = [0]*M

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

A.append(N+1)

def step_comb(L):
    c = 0
    if L==1 or L == 0:
        c = 1
    else:
        for i in range(L//2 +1):
            j = L - 2*i
            #c += comb(j+i, i, exact=True)
            c += cmb(j+i, i)
    return c

# DP version
DP = [0]*N
# １段の階段を登るやり方の数
DP[1] = 1
# 2段の階段を登るやり方の数
DP[2] = 2

def step_comb(L):
    if DP[L]>0:
        return DP[L]
    DP[L] = step_comb(L-1) + step_comb(L-2)
    return DP[L]
    
total_comb = 1
NOW = 0
for a in A:
    if NOW == a:
        print(0)
        sys.exit()
    L = a-1-NOW
    total_comb *= step_comb(L)
    NOW = a + 1
    
print(total_comb % 1000000007 )

Submission status: Runtime Error

Solution code:
import sys
#from scipy.special import comb
#from scipy.misc import comb

from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]

N,M = list(map(int, input().split()))

A = [0]*M

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

A.append(N+1)

def step_comb(L):
    c = 0
    if L==1 or L == 0:
        c = 1
    else:
        for i in range(L//2 +1):
            j = L - 2*i
            #c += comb(j+i, i, exact=True)
            c += cmb(j+i, i)
    return c

total_comb = 1
NOW = 0
for a in A:
    if NOW == a:
        print(0)
        sys.exit()
    L = a-1-NOW
    total_comb *= step_comb(L)
    NOW = a + 1
    
print(total_comb % 1000000007 )

Submission status: Runtime Error

Solution code:
import sys
from scipy.special import comb
# a = comb(n, r)
#a = comb(n, r, exact=True)

# L 段の階段を 1 or 2 段上り
# ２段を i 回 (i<L//2) 1段を j 回 (j = L - 2*i)
# L odd の場合
# i = 0~L//2

N,M = list(map(int, input().split()))

A = [0]*M

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

A.append(N+1) # goal

total_combo = 1
NOW = 0
for a in A:
    if NOW == a:
        print(0)
        sys.exit()
    L = a-1-NOW
    combo = 0
    for i in range(L//2 +1):
        j = L - 2*i
        combo += comb(j+1, i, exact=True)
    total_combo *= combo
    NOW = a + 1
    
print(total_combo)

Submission status: Runtime Error

Solution code:
# !/usr/bin/env python3
import sys
from operator import itemgetter
# gcd
# from fractions import gcd
# 切り上げ，切り捨て
# from math import ceil, floor
# リストの真のコピー（変更が伝播しない）
# from copy import deepcopy
# 累積和。list(accumulate(A))としてAの累積和
# from itertools import accumulate
# l = ['a', 'b', 'b', 'c', 'b', 'a', 'c', 'c', 'b', 'c', 'b', 'a']
# S = Counter(l)  # カウンタークラスが作られる。S=Counter({'b': 5, 'c': 4, 'a': 3})
# print(S.most_common(2))  # [('b', 5), ('c', 4)]
# print(S.keys())  # dict_keys(['a', 'b', 'c'])
# print(S.values())  # dict_values([3, 5, 4])
# print(S.items())  # dict_items([('a', 3), ('b', 5), ('c', 4)])
# from collections import Counter
# import math
# from functools import reduce
#
# input関係の定義
fin = open('in_3.txt', 'r')
sys.stdin = fin
# 提出時はコメントアウト+上のshebangを有効にする
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
def debug(*args): return print(*args, file=sys.stderr)
# template

MOD = 1000000007  # type: int

def iterate_tokens():
    for line in sys.stdin:
        for word in line.split():
            yield word

class Modint():
    '''
    自動でMODで割った余りを計算してくれる整数。MODは素数である必要があり，デフォルトは10**9+7。

    Parameters
    ----------
        n (int) : Modintの初期値
        MOD=10^9+7 (int) : 余りを計算するMOD。素数である必要がある。

    Methods
    ----------
        inverse(n: int) -> Modint
            n の逆元を返す。
    '''

    def __init__(self, n: int, mod=MOD):
        if n >= 0:
            self.n = n % mod
        else:
            self.n = (mod - (-n) % mod) % mod
        self.mod = mod

    def __eq__(self, other):
        return self.n == int(other)

    def __ne__(self, other):
        return not self == other

    def __neg__(self):
        return self.__class__(-self.n)

    def __str__(self):
        return str(self.n)

    def __int__(self):
        return self.n

    def __iadd__(self, other):
        self.n += int(other)
        self.n %= self.mod
        return self

    def __radd__(self, other):
        return self.__add__(other)

    def __isub__(self, other):
        self.n -= int(other)
        self.n %= self.mod
        return self

    def __rsub__(self, other):
        return self.__sub__(other)

    def __imul__(self, other):
        self.n = self.n * int(other) % self.mod
        return self

    def __rmul__(self, other):
        return self.__mul__(other)

    def inverse(self):
        '''
        フェルマーの小定理を考えると，MOD-2乗することでMODでの逆元を求めることができる。これは組み込み関数のpowを使うと十分に早い（O(log MOD)）。
        '''
        return self.__class__(pow(self.n, self.mod - 2, self.mod))

    def __ifloordiv__(self, other):
        self *= pow(int(other), self.mod - 2, self.mod)
        return self

    def __rfloordiv__(self, other):
        return self.__class__(other).__floordiv__(self)

    def __add__(self, other):
        return self.__class__(self.n + int(other))

    def __sub__(self, other):
        return self.__class__(self.n - int(other))

    def __mul__(self, other):
        return self.__class__(self.n * int(other))

    def __floordiv__(self, other):
        return self.__class__(self.n * Modint(int(other)).inverse())

    # def comb(self, n: int, k: int):
    #     '''
    #     コンビネーション絡みの定義。comb(n,k):特に前処理をせずnCkを求める
    #     毎回O(N)かかるので死ぬ覚悟でO(N^2)を投げるくらいしか無理

    #     ちなみにですが，これでABC132_D()を出すとPyPy3で1932msくらいですれすれセーフ
    #     '''
    #     if n < k or k < 0:
    #         return Modint(0)
    #     res = Modint(1)
    #     for i in range(int(k)):
    #         res *= Modint(n - i)
    #         res //= Modint(i + 1)
    #     return res

    # def H(self, n: int, k: int):
    #     if n < 0 or k < 0:
    #         return Modint(0)
    #     elif n == 0 and k == 0:
    #         return Modint(1)
    #     else:
    #         return self.comb(n + k - 1, n)


COMBINATION_MAX = 2 * 10**5
class Combination():
    def __init__(self, sz=COMBINATION_MAX):
        '''
        Nまでの階乗とその逆元（割り算用）を計算しておく。前処理にO(N)，P, C, Hそれぞれの計算はO(1)。N = 200000なら割と余裕で通る。
        '''
        self._fact = [Modint(0)] * (sz + 1)
        self._rfact = [Modint(0)] * (sz + 1)
        self._fact[0] = Modint(1)
        self._rfact[sz] = Modint(1)
        for i in range(1, sz + 1):
            self._fact[i] = self._fact[i - 1] * Modint(i)
        self._rfact[sz] = self._fact[sz].inverse()
        for i in range(sz - 1, -1, -1):
            self._rfact[i] = self._rfact[i + 1] * Modint(i + 1)

    def fact(self, k: int) -> int:
        """階乗の計算"""
        return self._fact[k]

    def rfact(self, k: int) -> int:
        """階乗の逆元の計算"""
        return self._rfact[k]

    def P(self, n: int, k: int) -> Modint:
        '''
        nPkの値を返す。nはあらかじめ前処理されたN以下でないとダメ

        Parameters
        ----------
            n (int) : nPkのn (0<=n<=N)
            k (int) : nPkのk （0<=k<=n）

        Returns
        ----------
            Modint : nPkをModint型で返す。Modintに依存。
        '''
        if k < 0 or n < k:
            return Modint(0)
        return self._fact[n] * self._rfact[n - k]

    def C(self, n: int, k: int) -> Modint:
        '''
        nCkの値を返す。nはあらかじめ前処理されたN以下でないとダメ

        Parameters
        ----------
            n (int) : nCkのn(0<=n<=N)
            k (int) : nCkのk（0<=k<=n）

        Returns
        ----------
            Modint : nCkをModint型で返す。Modintに依存。
        '''
        if k < 0 or n < k:
            return Modint(0)
        if n - k < k:
            k = n - k
        return self._fact[n] * self._rfact[k] * self._rfact[n - k]

    def H(self, n: int, k: int) -> Modint:
        '''
        nHkの値を返す。nはあらかじめ前処理された n+k-1 以下でないとダメ

        ちなみにnHkはn個の区別できないものをk個の箱に分けるパターンの数で，結局n+k-1Cnになる。

        Parameters
        ----------
            n (int) : nHkのn(0<=n<=N)
            k (int) : nHkのk（0<=k<=n）

        Returns
        ----------
            Modint : nHkをModint型で返す。Modintに依存。
        '''
        if n < 0 or k < 0:
            return Modint(0)
        elif k == 0:
            return Modint(1)
        return self.C(n + k - 1, k)

# END CUT HERE

if __name__ == '__main__':

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = {int(next(tokens)) for _ in range(M)}  # type: "List[int]"

    # write code
    issafe = [True for i in range(N + 10)]
    for i in a:
        issafe[i] = False
    dp = [Modint(0) for i in range(N + 10)]
    dp[0] = Modint(1)
    if issafe[1]:
        dp[1] = Modint(1)
    for n in range(2, N + 2):
        if issafe[n - 1]:
            dp[n] += dp[n - 1]
            # debug(n, "!")
        if issafe[n - 2]:
            dp[n] += dp[n - 2]
            # debug(n, "?")
    print(dp[N])

Submission status: Runtime Error

Solution code:
# !/usr/bin/env python3
import sys
from operator import itemgetter
# gcd
# from fractions import gcd
# 切り上げ，切り捨て
# from math import ceil, floor
# リストの真のコピー（変更が伝播しない）
# from copy import deepcopy
# 累積和。list(accumulate(A))としてAの累積和
# from itertools import accumulate
# l = ['a', 'b', 'b', 'c', 'b', 'a', 'c', 'c', 'b', 'c', 'b', 'a']
# S = Counter(l)  # カウンタークラスが作られる。S=Counter({'b': 5, 'c': 4, 'a': 3})
# print(S.most_common(2))  # [('b', 5), ('c', 4)]
# print(S.keys())  # dict_keys(['a', 'b', 'c'])
# print(S.values())  # dict_values([3, 5, 4])
# print(S.items())  # dict_items([('a', 3), ('b', 5), ('c', 4)])
# from collections import Counter
# import math
# from functools import reduce
#
# input関係の定義
fin = open('in_3.txt', 'r')
sys.stdin = fin
# 提出時はコメントアウト+上のshebangを有効にする
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
def debug(*args): return print(*args, file=sys.stderr)
# template

MOD = 1000000007  # type: int

def iterate_tokens():
    for line in sys.stdin:
        for word in line.split():
            yield word

class Modint():
    '''
    自動でMODで割った余りを計算してくれる整数。MODは素数である必要があり，デフォルトは10**9+7。

    Parameters
    ----------
        n (int) : Modintの初期値
        MOD=10^9+7 (int) : 余りを計算するMOD。素数である必要がある。

    Methods
    ----------
        inverse(n: int) -> Modint
            n の逆元を返す。
    '''

    def __init__(self, n: int, mod=MOD):
        if n >= 0:
            self.n = n % mod
        else:
            self.n = (mod - (-n) % mod) % mod
        self.mod = mod

    def __eq__(self, other):
        return self.n == int(other)

    def __ne__(self, other):
        return not self == other

    def __neg__(self):
        return self.__class__(-self.n)

    def __str__(self):
        return str(self.n)

    def __int__(self):
        return self.n

    def __iadd__(self, other):
        self.n += int(other)
        self.n %= self.mod
        return self

    def __radd__(self, other):
        return self.__add__(other)

    def __isub__(self, other):
        self.n -= int(other)
        self.n %= self.mod
        return self

    def __rsub__(self, other):
        return self.__sub__(other)

    def __imul__(self, other):
        self.n = self.n * int(other) % self.mod
        return self

    def __rmul__(self, other):
        return self.__mul__(other)

    def inverse(self):
        '''
        フェルマーの小定理を考えると，MOD-2乗することでMODでの逆元を求めることができる。これは組み込み関数のpowを使うと十分に早い（O(log MOD)）。
        '''
        return self.__class__(pow(self.n, self.mod - 2, self.mod))

    def __ifloordiv__(self, other):
        self *= pow(int(other), self.mod - 2, self.mod)
        return self

    def __rfloordiv__(self, other):
        return self.__class__(other).__floordiv__(self)

    def __add__(self, other):
        return self.__class__(self.n + int(other))

    def __sub__(self, other):
        return self.__class__(self.n - int(other))

    def __mul__(self, other):
        return self.__class__(self.n * int(other))

    def __floordiv__(self, other):
        return self.__class__(self.n * Modint(int(other)).inverse())

    # def comb(self, n: int, k: int):
    #     '''
    #     コンビネーション絡みの定義。comb(n,k):特に前処理をせずnCkを求める
    #     毎回O(N)かかるので死ぬ覚悟でO(N^2)を投げるくらいしか無理

    #     ちなみにですが，これでABC132_D()を出すとPyPy3で1932msくらいですれすれセーフ
    #     '''
    #     if n < k or k < 0:
    #         return Modint(0)
    #     res = Modint(1)
    #     for i in range(int(k)):
    #         res *= Modint(n - i)
    #         res //= Modint(i + 1)
    #     return res

    # def H(self, n: int, k: int):
    #     if n < 0 or k < 0:
    #         return Modint(0)
    #     elif n == 0 and k == 0:
    #         return Modint(1)
    #     else:
    #         return self.comb(n + k - 1, n)


COMBINATION_MAX = 2 * 10**5
class Combination():
    def __init__(self, sz=COMBINATION_MAX):
        '''
        Nまでの階乗とその逆元（割り算用）を計算しておく。前処理にO(N)，P, C, Hそれぞれの計算はO(1)。N = 200000なら割と余裕で通る。
        '''
        self._fact = [Modint(0)] * (sz + 1)
        self._rfact = [Modint(0)] * (sz + 1)
        self._fact[0] = Modint(1)
        self._rfact[sz] = Modint(1)
        for i in range(1, sz + 1):
            self._fact[i] = self._fact[i - 1] * Modint(i)
        self._rfact[sz] = self._fact[sz].inverse()
        for i in range(sz - 1, -1, -1):
            self._rfact[i] = self._rfact[i + 1] * Modint(i + 1)

    def fact(self, k: int) -> int:
        """階乗の計算"""
        return self._fact[k]

    def rfact(self, k: int) -> int:
        """階乗の逆元の計算"""
        return self._rfact[k]

    def P(self, n: int, k: int) -> Modint:
        '''
        nPkの値を返す。nはあらかじめ前処理されたN以下でないとダメ

        Parameters
        ----------
            n (int) : nPkのn (0<=n<=N)
            k (int) : nPkのk （0<=k<=n）

        Returns
        ----------
            Modint : nPkをModint型で返す。Modintに依存。
        '''
        if k < 0 or n < k:
            return Modint(0)
        return self._fact[n] * self._rfact[n - k]

    def C(self, n: int, k: int) -> Modint:
        '''
        nCkの値を返す。nはあらかじめ前処理されたN以下でないとダメ

        Parameters
        ----------
            n (int) : nCkのn(0<=n<=N)
            k (int) : nCkのk（0<=k<=n）

        Returns
        ----------
            Modint : nCkをModint型で返す。Modintに依存。
        '''
        if k < 0 or n < k:
            return Modint(0)
        if n - k < k:
            k = n - k
        return self._fact[n] * self._rfact[k] * self._rfact[n - k]

    def H(self, n: int, k: int) -> Modint:
        '''
        nHkの値を返す。nはあらかじめ前処理された n+k-1 以下でないとダメ

        ちなみにnHkはn個の区別できないものをk個の箱に分けるパターンの数で，結局n+k-1Cnになる。

        Parameters
        ----------
            n (int) : nHkのn(0<=n<=N)
            k (int) : nHkのk（0<=k<=n）

        Returns
        ----------
            Modint : nHkをModint型で返す。Modintに依存。
        '''
        if n < 0 or k < 0:
            return Modint(0)
        elif k == 0:
            return Modint(1)
        return self.C(n + k - 1, k)

# END CUT HERE

if __name__ == '__main__':

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = {int(next(tokens)) for _ in range(M)}  # type: "List[int]"

    # write code
    dp = [Modint(0) for i in range(N + 10)]
    dp[0] = Modint(1)
    if 1 not in a:
        dp[1] = Modint(1)
    for n in range(2, N + 2):
        if n - 1 not in a:
            dp[n] += dp[n - 1]
            debug(n, "!")
        if n - 2 not in a:
            dp[n] += dp[n - 2]
            debug(n, "?")
    debug(dp[N])

Submission status: Runtime Error

Solution code:
MOD = 10 ** 9 + 7

N, M = map(int, input().split())

broken = [False for _ in range(N+1)]
for _ in range(M):
	broken[int(input())] = True

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

for i in range(1, N+1):
	if broken[i]:
		continue
  elif i == 1:
    dp[i] = dp[i-1]
	else:
		dp[i] = dp[i-1] + dp[i-2]
		dp[i] %= MOD
print(dp[N])

Submission status: Runtime Error

Solution code:
MOD = 10 ** 9 + 7
N, M = map(int, input().split())
a = []
for i in range(M):
  a.append(int(input()))
broken = [False for _ in range(N+1)]

dp = [0 for _ in range(N + 1)]
dp[0] = 1
for _ in range(M):
	broken[int(input())] = True
for i in range(1, N+1):
	if broken[i]:
		continue
	if i == 1:
		dp[i] = dp[i-1]
	else:
		dp[i] = dp[i-1] + dp[i-2]
		dp[i] %= MOD
print(dp[N])

Submission status: Runtime Error

Solution code:
def rec(i, bs, ngs):
    if bs[i] is None:
        if ngs[i]:
            bs[i] = 0
        elif i == 0 or i == 1:
            bs[i] = 1
        else:
            bs[i] = (rec(i-1, bs, ngs) + rec(i-2, bs, ngs)) % 1000000007
    return bs[i]


N, M = map(int, input().split())
ngs = [False] * int(1e5+1)
for _ in range(M):
    ngs[int(input())] = True

bs = [None] * int(1e5+1)
ans = rec(N, bs, ngs)
print(ans)

Submission status: Runtime Error

Solution code:
N, M = list(map(int, input().split()))
a = []
for i in range(0, M):
    a.append(int(input()))
a.sort()
T = 10 ** 9 + 7

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


def fib(n):
    if r[n] > 0:
        return r[n]
    else:
        r[n] = fib(n - 1) + fib(n - 2)
        return r[n]


for i in range(0, M - 1):
    if a[i] + 1 == a[i + 1]:
        print(0)
        break
else:
    now = 0
    c = 1
    for i in range(0, M):
        c *= fib(a[i] - now - 1) % T
        c %= T
        now = a[i] + 1
    c *= fib(N - now)
    print(c % T)

Submission status: Runtime Error

Solution code:
N, M = list(map(int, input().split()))
a = []
for i in range(0, M):
    a.append(int(input()))
a.sort()
T = 10 ** 9 + 7

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


def fib(n):
    if r[n] > 0:
        return r[n]
    else:
        return fib(n - 1) + fib(n - 2)


for i in range(0, M - 1):
    if a[i] + 1 == a[i + 1]:
        print(0)
        break
else:
    now = 0
    c = 1
    for i in range(0, M):
        c *= fib(a[i] - now - 1) % T
        c %= T
        now = a[i] + 1
    c *= fib(N - now)
    print(c % T)

Submission status: Runtime Error

Solution code:
N, M = list(map(int, input().split()))
a = []
for i in range(0, M):
    a.append(int(input()))
a.sort()
T = 10 ** 9 + 7

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


def fib(n):
    if r[n] > 0:
        return r[n]
    else:
        return fib(n - 1) + fib(n - 2)


for i in range(0, M - 1):
    if a[i] + 1 == a[i + 1]:
        print(0)
        break
else:
    now = 0
    c = 1
    for i in range(0, M):
        c *= fib(a[i] - now - 1)
        c %= T
        now = a[i] + 1
    c *= fib(N - now)
    print(c % T)

Submission status: Runtime Error

Solution code:
def fibfunction(N): #各パートごとの経路の場合の数を求めるのはフィボナッチ数列
    fib=[1,1]
    if N >1:
        for i in range(N-1):
            fib.append(fib[i]+fib[i+1]) #1stepが1か2なので一つ前と二つ前の数を足せばよい
    elif N == -1:
        return 0
    else:
        return 1
    return fib[-1]

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

plist = [alist[0]-1,N-alist[-1]-1]
if M > 1:
    for j in range(M-1):
        p = alist[j+1]-alist[j]-2
        plist.append(p)

ulist = []
for l in range(len(plist)):
    q = fibfunction(plist[l])
    ulist.append(q)

ans = 1
for k in range(M+1):
    ans *= ulist[k]

ans = ans % 1000000007

print(ans)

Submission status: Runtime Error

Solution code:
def fibfunction(N): #各パートごとの経路の場合の数を求めるのはフィボナッチ数列
    fib=[1,1]
    if N >1:
        for i in range(N-1):
            fib.append(fib[i]+fib[i+1]) #1stepが1か2なので一つ前と二つ前の数を足せばよい
    elif N == -1:
        return 0
    else:
        return 1
    return fib[-1]

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

plist = [alist[0]-1,N-alist[-1]-1]
for j in range(M-1):
    p = alist[j+1]-alist[j]-2
    plist.append(p)

ulist = []
for l in range(len(plist)):
    q = fibfunction(plist[l])
    ulist.append(q)

ans = 1
for k in range(M+1):
    ans *= ulist[k]

ans = ans % 1000000007

print(ans)

Submission status: Runtime Error

Solution code:
def count(to):
    if to <= 0:
        return 0
    elif to==1:
        return 1
    elif to==2:
        return 2
    return count(to-1)+count(to-2)

N,M = [int(i) for i in input().split()]
a = [int(input()) for _ in range(M)]
res = count(max(a[0]-1, 1)) * count(max(N-1-a[-1],1))
for i in range(len(a)-1):
    res *= count(a[i+1]-1 - (a[i]+1))
print(res%1000000007)

Submission status: Runtime Error

Solution code:
def count(to):
    if to <= 0:
        return 0
    elif to==1:
        return 1
    elif to==2:
        return 2
    return count(to-1)+count(to-2)

N,M = [int(i) for i in input().split()]
a = [int(input()) for _ in range(M)]
diff_a = [a[i+1]-1 - (a[i]+1) for i in range(len(a)-1)]
res = count(max(a[0]-1, 1)) * count(max(N-1-a[-1],1))
for d in diff_a:
    res *= count(d)
print(res%1000000007)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[31]:


N, M = map(int, input().split())
As = [int(input()) for i in range(M)]
"""
100 5
1
23
45
67
89
"""


# In[32]:


import numpy as np


# In[33]:


As = np.array(As)
oAs = As[1:]-As[:-1]
if 1 in oAs:
    print(0)
    sys.exit()


# In[34]:


stairs = [0]*(N+3)
stairs[0] = 1
#stairs[1] = 1

start_stage = 0
for i in range(M):
    collapsed_stage = As[i]
    finish_stage = collapsed_stage - 1
    #print(start_stage, finish_stage)
    continuous_stairs = finish_stage - start_stage
    if continuous_stairs < 2:
        stairs[finish_stage+2] = stairs[start_stage]
        start_stage = finish_stage+2
    else:
        stairs[start_stage+1] = stairs[start_stage]
        for i in range(continuous_stairs-1):
            stairs[start_stage+i+2] = stairs[start_stage+i] + stairs[start_stage+i+1]
        stairs[finish_stage+2] = stairs[finish_stage]
        start_stage = finish_stage+2

if N-start_stage < 2:
    stairs[N] = stairs[start_stage]
else:
    continuous_stairs = N - start_stage
    stairs[start_stage+1] = stairs[start_stage]
    for i in range(continuous_stairs-1):
        stairs[start_stage+i+2] = stairs[start_stage+i] + stairs[start_stage+i+1]
        #print(stairs)
        
#print(list(range(N+1)))
#print(stairs)
print(stairs[N]%1000000007)


# In[ ]:

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
s=set([int(input()) for i in range(m)])
l=[1]+[0]*(n)
INF=1000000007
if n ==1:
    print(1)
    exit()
if len(s)!=0 and s[0]== 1:l[1]=0
else:l[1]=1

for i in range(2,n+1):
    if i in s:l[i]=0
    else:l[i] = (l[i-2]+l[i-1])%INF
print(l[-1])

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
s=[int(input()) for i in range(m)]
l=[1]
if s[0]!= 1:l.append(1)
else:l.append(0)
for i in range(2,n+1):
    if i in s:num=0
    else:num = (l[i-2]+l[i-1])%1000000007
    l.append(num)
print(l[-1])

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
l=[]
for i in range(m):
    l.append(int(input()))
if not 1 in l:
    two=1
else:
    two=0
if not 2 in l:
    if two==1:
        one=2
    else:
        one=1
lis=[two,one]
for _ in range(3,n+1):
    if not _ in l:
        lis.append((lis[_-3]+lis[_-2])%1000000007)
    else:
        lis.append(0)
print(lis[-1])

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
l=[]
for i in range(m):
    l.append(int(input()))
if not 1 in l:
    two=1
if not 2 in l:
    if two==1:
        one=2
    else:
        one=1
lis=[two,one]
for _ in range(3,n+1):
    if not _ in l:
        lis.append((lis[_-3]+lis[_-2])%1000000007)
    else:
        lis.append(0)
print(lis[-1])

Submission status: Runtime Error

Solution code:
MOD = 1000000007

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



def binet_mod(n):
    if(n==0):
        return 0
    return((int(1/5**(1/2)*((((1+5**(1/2))/2)**n)-((1-5**(1/2))/2)**n)))%MOD)
    

l = 0
ans = 1

for i in range(M):
    ans = ans * binet_mod(A[i] - l)
    l = A[i] + 1
    

ans = (ans * binet_mod(N-l+1))%MOD
print(ans)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10000)

n, m = map(int, input().split())
broken = []
for i in range(m):
    broken.append(int(input()))
    if len(broken) > 1 and broken[-2] + 1 == broken[-1]:
        print(0)
        exit()
    

dp = [-float('inf')] * (n + 1)

def rec(i):
    global dp
    if dp[i] > -float('inf'):
        return dp[i]
      
    if i in broken:
        return 0
    
    if i >= n - 1:
        return 1
    
    dp[i] = rec(i + 1) + rec(i + 2)
    
    return dp[i]
            
print(rec(0)%1000000007)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10000)

n, m = map(int, input().split())
broken = []
for i in range(m):
    broken.append(int(input()))
    if len(broken) > 1 and broken[-2] + 1 == broken[-1]:
        print(0)
        exit()
    

dp = [0] * (n + 1)

def rec(i):
    global dp
    if dp[i] > 0:
        return dp[i]
      
    if i in broken:
        return 0
    
    if i >= n - 1:
        return 1
    
    dp[i] = rec(i + 1) + rec(i + 2)
    
    return dp[i]
            
print(rec(0)%1000000007)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(2000)

n, m = map(int, input().split())
broken = []
for i in range(m):
    broken.append(int(input()))
    if len(broken) > 1 and broken[-2] + 1 == broken[-1]:
        print(0)
        exit()
    

dp = [0] * (n + 1)

def rec(i):
    global dp
    if dp[i] > 0:
        return dp[i]
    
    if i >= n - 1:
        return 1
    
    if i in broken:
        return 0
    
    dp[i] = rec(i + 1) + rec(i + 2)
    
    return dp[i]
            
print(rec(0)%1000000007)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
broken = []
for i in range(m):
    broken.append(int(input()))
    if len(broken) > 1 and broken[-2] + 1 == broken[-1]:
        print(0)
        exit()
    

dp = [0] * (n + 1)
def rec(i):
    global dp
    if dp[i] > 0:
        return dp[i]
    
    if i >= n - 1:
        return 1
    
    if i in broken:
        return 0
    
    dp[i] = rec(i + 1) + rec(i + 2)
    
    return dp[i]
            
print(rec(0)%1000000007)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
L=[0]*M
R=[0]*M
for i in range(M):
    L[i],R[i]=map(int,input().split())
def quick_sort(arr):
    left = []
    right = []
    if len(arr) <= 1:
        return arr

    # データの状態に左右されないためにrandom.choice()を用いることもある。
    # ref = random.choice(arr)
    ref = arr[0]
    ref_count = 0

    for ele in arr:
        if ele < ref:
            left.append(ele)
        elif ele > ref:
            right.append(ele)
        else:
            ref_count += 1
    left = quick_sort(left)
    right = quick_sort(right)
    return left + [ref] * ref_count + right
L=quick_sort(L)
R=quick_sort(R)
a=L[M-1]
b=R[0]
if a>b:
  print("0")
else:
  print(b-a+1)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
S = []
for _ in range(M):
    S.append(int(input()))
def fib(n):
  if n==-1:
    return 0
  elif n==0:
    return 1
  else:
    a, b = 0, 1
    for i in range(n):
        a, b = b, a + b
    return b
if S[0]==1:
  c=1
else:
  c=fib(S[0]-1)
for i in range(M-1):
  c=c*fib(S[i+1]-S[i]-2)
c=c*fib(N-S[M-1]-1)
c=c%1000000007
print(c)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
S = []
for _ in range(M):
    S.append(int(input()))
def fib(n):
  if n==0:
    return 0
  else:
    a, b = 0, 1
    for i in range(n):
        a, b = b, a + b
    return b
if S[0]==1:
  c=1
else:
  c=fib(S[0]-1)
for i in range(M-1):
  c=c*fib(S[i+1]-S[i]-2)
c=c*fib(N-S[M-1]-1)
c=c%1000000007
print(c)

Submission status: Runtime Error

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

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

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

Submission status: Runtime Error

Solution code:
n, M = map(int, input().split())
A = list(map(int, input().split()))
dp = [-1 for _ in range(n+1)]
dp[0] = 1
dp[1] = 1
if 1 in A:
    dp[1] = 0

step = 2
while True:
    if step == n+1:
        break
    
    if step in A:
        dp[step] = 0
    else:
        dp[step] = dp[step-1] + dp[step-2]
        
    step += 1
    
print(dp[n])