组合数学（Python）

参考：https://blog.nowcoder.net/n/524adc66d6b04d149d89b0ce79b93c0b

思路：组合数学结论。本题主要就是这个结论，如果你不知道的话，基本上写不出来了。这个结论其实是隔板法的推论：对于m个数中可重复的选取n个数，方案数有comb(m + n - 1, n)个。因此，我们就去记录一下连续0的[l, r]，那么此时的m就是a[l - 1] - a[r + 1] + 1，此时的n就是r - l + 1，这些区间相互独立，用乘法原理不断累乘方案数并取模，最终输出结果即可

当然，我们这里还可以用一些方法来优化下代码。第一个就是预处理出取模的阶乘数组；第二个就是在头尾添加哨兵，防止数组越界；第三个就是除法取模，算乘法逆元，需要使用小费马定理。总之，这题还是挺不错的，融合了一些数学结论和优化技巧

代码：

import sys
input = lambda: sys.stdin.readline().strip()

import math
inf = 10 ** 18

def I():
    return input()

def II():
    return int(input())

def MII():
    return map(int, input().split())

def GMI():
    return map(lambda x: int(x) - 1, input().split())

def LI():
    return input().split()

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

def LFI():
    return list(map(float, input().split()))

fmax = lambda x, y: x if x > y else y
fmin = lambda x, y: x if x < y else y
isqrt = lambda x: int(math.sqrt(x))

'''

'''

mod = 10 ** 9 + 7

MAXN = 10 ** 6
fac = [1] * (MAXN + 1)
for i in range(1, MAXN + 1):
    fac[i] = fac[i - 1] * i % mod # 记得取mod，不然会爆

def inv(x):
    return pow(x, mod - 2, mod)

def comb(a, b):
    if a < b:
        return 0
    return fac[a] * inv(fac[b]) * inv(fac[a - b]) % mod

def solve():
    n = II()
    a = [1000] + LII() + [1] # 方便边界处理
    n += 2

    # 分组循环找连续0的[l, r]
    tmp = []
    i = 0
    while i < n:
        if a[i] != 0:
            i += 1
            continue
        st = i
        i += 1
        while i < n and a[i] == 0:
            i += 1
        tmp.append((st, i - 1))

    # 隔板法结论求ans
    ans = 1
    for l, r in tmp:
        w = a[l - 1] - a[r + 1] + 1
        h = r - l + 1
        ans = ans * comb(w + h - 1, h) % mod

    print(ans)

t = 1
# t = II()
for _ in range(t):
    solve()