题目背景

翻译来自于 LibreOJ。

题目描述

题目译自 XXIX Olimpiada Informatyczna – III etap Impreza krasnali 2

小矮人们又行动了！在上一次派对之后，他们又举办了一次后续聚会。这次依然有 $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$ 取模。

4
2 4 2 1

3

提示

附加样例

1. 该样例满足 $n=2, h_{i}=1$，答案为 $2$；
2. 该样例满足 $n=100000, h_{i}=i$，答案为 $F_{n+1} \bmod 10^{9}+7$，其中 $F_{i}$ 是第 $i$ 个斐波那契数。

详细子任务附加限制及分值如下表所示。