P3366.第3题-历史贡献

1000ms

Difficulty: 7

所属公司 : 小红书

算法与标签>组合数学

题目内容

小红书算法团队为了优化用户等级历史贡献统计，记录了一个长度为 $n$ 的数组 $(a_1,a_2,…,a_n)$ 。该数组中的元素均为正整数，并满足非严格递增关系: $a_1≤a_2≤...≤a_n$ 。

但由于网络波动，小红书后台日志中部分位置的值丢失，用 $a_i=0$ 表示丢失数据;题目保证 $a_1,a_n$ 不为 $0$ .

请统计符合上述要求的原始数组的可能方案数。由于方案数可能非常大，请将结果对 $(10^9+7)$ 取模后输出。

在一行上输入一个整数 $n(1≤n≤2*10^5)$ ,表示数组长度。

在第二行输入 $n$ 个整数 $a_1,a_2,a_n(0≤a_i≤10^9)$ ,其中 $a=0$ 表示丢失数据，其余位置满足非严格通增关系。

在一行上输出一个整数,表示符合条件的原始数组的方案数对 $(10^9+7)$ 取模后的结果

输入

3
1 0 5

输出

说明

本题中，如果您需要使用到除法的取模，即计算 $(p*q^{-1}$ $mod$ $M)$ 时， $q^{-1}$ 需要使用公式 $(q^{M-1}$ $mod$ $M)$ 得到。例如，计算 $5/4$ $mod$ $M$ :

$\frac {4^{-1}}{(\frac {5}{4} mod M) }$

$4^{-1}=(4^{M-2}$ $mod$ $M$ ) $=250$ $000$ $002$

$(\frac {5}{4}$ $mod$ $M)= 5×4^{-1}$ $mod$ $M$ $=5×250$ $000$ $002$ $mod$ $M$ $=250$ $000$ $003$

非严格递增:对于数组 $(a_1,a_2,...,a_n)$ ,若对任意 $1≤i<n$ 都有 $a_i≤a_{i+1}$ 则称该数组为非严格递增数组。

输入

预期输出（选填）