题目内容

某实验室记录了一个长度为 $n$ 的非递减整数序列 $(a_1,a_2,\dots,a_n)$，即对于任意 $1 \le i < n$ 满足 $a_i \le a_{i+1}$。由于仪器故障，序列中部分记录丢失，丢失的位置用 $0$ 表示。已知首项 $a_1$ 与末项 $a_n$ 均未丢失。

请你计算在所有可能恢复丢失值的情况下，能够满足原始非递减规律的序列共有多少种。答案可能很大，请输出对 $10^9+7$ 取模后的结果。

约束条件

• 数组长度 $n$ 满足 $1 \le n \le 2 \times 10^5$。
• 序列元素为整数，已知的非零值满足 $1 \le a_i \le 10^9$（丢失位置用 $0$ 表示），且给出的非零值保持非递减顺序。
• 保证 $a_1 eq 0$ 且 $a_n eq 0$。

输入描述

第一行输入一个整数 $n$，表示序列的长度。 第二行输入 $n$ 个整数 $a_1,a_2,\dots,a_n$，用空格分隔，其中 $0$ 表示该位置数据丢失。

输出描述

输出一个整数，表示所有可能的原始序列数目对 $10^9+7$ 取模的结果。

样例1

输入

4
2 0 0 6

输出

15

说明

已知 $a_1=2$，$a_4=6$，中间有 2 个缺失值，值域跨度 $d=6-2=4$。需要填入 $x_1,x_2$ 满足 $2 \le x_1 \le x_2 \le 6$，这是从 $d+1=5$ 个可用值（2,3,4,5,6）中可重复地选取 2 个的组合问题。方案数为 $\binom{d+k}{k}=\binom{4+2}{2}=15$。

样例2

输入

6
1 0 2 0 3 4

输出

4

说明

序列中的已知值为 $1,2,3,4$。第一段从 $1$ 到 $2$：中间有 $k=1$ 个缺失位，跨度 $d=1$，填法数为 $\binom{1+1}{1}=2$。第二段从 $2$ 到 $3$：同样 $k=1,d=1$，填法数也为 2。第三段 $3$ 与 $4$ 相邻，无缺失位。总方案数为 $2 \times 2 = 4$，分别为 $1,2,2,3,3,4$；$1,2,2,3,4,4$；$1,1,2,3,3,4$；$1,1,2,3,4,4$。

样例3

输入

2
10 20

输出

1

说明

当 $n=2$ 且没有任何缺失值时，原始序列完全确定，只有 1 种可能。

样例4

输入

5
1 0 0 0 5

输出

35

说明

$a_1=1$，$a_5=5$，中间有 $k=3$ 个缺失值，跨度 $d=4$。满足非递减的填法数为 $\binom{d+k}{k}=\binom{7}{3}=35$。