题面描述

• 给定一个长度为$n$ 的数组$a_1,a_2,\dots,a_n$，元素为正整数并满足非严格递增：$a_i\le a_{i+1}$。
• 部分位置丢失记为 $0$，保证$a_1\ne 0$ 且 $a_n\ne 0$。
• 统计把 $0$ 替换为正整数、且整体非严格递增的原数组方案数，对 $10^9+7$ 取模。

思路

• 把非零位置的下标按顺序记为$p_1<p_2<\dots<p_m$，对应值为$v_1,\dots,v_m$。若存在某对相邻非零$v_i>v_{i+1}$，答案为$0$。
• 对相邻非零之间的连续零段计数：设两端固定为$v_L$、$v_R$，中间有$k$个位置需填，且 $v_L\le v_R$，需要计数满足

题目内容

小红书算法团队为了优化用户等级历史贡献统计，记录了一个长度为 $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)$ 取模后的结果

样例1

输入

3
1 0 5

输出

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}$ 则称该数组为非严格递增数组。