P12917 [POI 2021/2022 R3] 小矮人派对 2 / Impreza krasnali 2

翻译来自于 [LibreOJ](https://loj.ac/p/4854)。

**题目译自 [XXIX Olimpiada Informatyczna – III etap](https://sio2.mimuw.edu.pl/c/oi29-3/dashboard/) [Impreza krasnali 2](https://szkopul.edu.pl/problemset/problem/2ZKQK-DbGaGSH4NAOY36o93L/statement/)** 小矮人们又行动了！在上一次派对之后，他们又举办了一次后续聚会。这次依然有 $n$ 个小矮人，每人戴上一顶尖帽子（共有 $n$ 顶高度从 $1$ 到 $n$ 的不同帽子）。他们照旧围坐在一张长桌的一侧大吃大喝。 本地画家又要为这次聚会作画，于是向每个小矮人询问帽子的信息。可惜，这群小矮人的记性更差了，每个小矮人只能告诉画家，自己、左边的人或右边的人的帽子高度。 请你帮助画家，编写一个程序，计算根据小矮人们的描述，可能的帽子排列有多少种。由于结果可能很大，只需输出对 $10^{9}+7$ 取模的值。如果小矮人们的描述互相矛盾，正确答案应为 $0$。

输入的第一行包含一个整数 $n$ $(n \geq 2)$，表示小矮人的数量。 第二行包含 $n$ 个整数 $h_{1}, h_{2}, \ldots, h_{n}$ $(1 \leq h_{i} \leq n)$，用空格分隔，其中 $h_{i}$ 表示从桌子左端开始数第 $i$ 个小矮人告诉画家的信息：「我、我左边的人或右边的人戴着高度为 $h_{i}$ 的帽子」。

你的程序应输出一行，包含一个整数，表示与小矮人们描述一致的帽子排列数量，结果需对 $10^{9}+7$ 取模。

**附加样例** 1. 该样例满足 $n=2, h_{i}=1$，答案为 $2$； 2. 该样例满足 $n=100000, h_{i}=i$，答案为 $F_{n+1} \bmod 10^{9}+7$，其中 $F_{i}$ 是第 $i$ 个斐波那契数。 详细子任务附加限制及分值如下表所示。 | 子任务编号 | 附加限制 | 分值 | | :---: | :--: | :---: | | $1$ | $n \leq 10$ | $12$ | | $2$ | $n \leq 20$ | $30$ | | $3$ | $n \leq 1000$ | $30$ | | $4$ | $n \leq 100000$ | $28$ |