题目内容

小M获得了一份古老的年降水量记录，记录了某地区连续 $n$ 年的年降水量。由于时间久远，部分年份的记录已无法辨认，仅留下 $0$ 标记。已知该地区的年降水量具有非递减的特征，即每一年的降水量都不低于上一年。记录的首尾年份数据完好（不为 $0$）。

现在小M想知道，在所有可能补全缺失数据的方式中，有多少种符合非递减条件的原始序列。答案可能很大，请输出对 $10^9+7$ 取模后的结果。

【约束条件】

• 年份数 $n$ 满足 $1 \le n \le 2 \times 10^5$。
• 对于每个数据 $a_i$，若为完整记录，则其值为正整数且不超过 $10^9$；若缺失则为 $0$。
• 序列的第一个数据 $a_1$ 和最后一个数据 $a_n$ 保证不是 $0$。

输入描述

第一行输入一个整数 $n$，表示序列的长度。 第二行输入 $n$ 个整数，依次表示 $a_1, a_2, \dots, a_n$，其中 $0$ 代表缺失数据。

输出描述

输出一个整数，表示满足条件的原始序列方案数对 $10^9+7$ 取模后的结果。

样例1

输入

4
2 0 0 5

输出

10

说明

非零位置为 $a_1=2$ 和 $a_4=5$，中间缺失 2 个值。设 $k=2$，差值 $d=5-2=3$。问题等价于在 $[2,5]$ 中选择 2 个非递减整数。根据隔板法，方案数为组合数 $C(d+k, k) = C(3+2, 2) = C(5,2) = 10$。所以总方案数为 10。

样例2

输入

5
2 0 3 0 5

输出

6

说明

非零值依次为 $a_1=2$, $a_3=3$, $a_5=5$。第一段 $2$ 到 $3$ 之间缺失 $k=1$ 个值，$d=1$，方案数 $C(1+1, 1)=2$（可填 2 或 3）。第二段 $3$ 到 $5$ 之间缺失 $k=1$ 个值，$d=2$，方案数 $C(2+1, 1)=3$（可填 3、4 或 5）。总方案数为 $2 \times 3 = 6$。

样例3

输入

4
5 0 0 3

输出

0

说明

已知非零值 $a_1=5$ 和 $a_4=3$，但 $5 > 3$，不满足非递减条件，因此无法补全任何合法序列，方案数为 0。

样例4

输入

3
1 2 3

输出

1

说明

所有值均已给出且满足非递减，没有缺失值需要补全，因此只有 1 种方案，即序列本身。