题目描述

题目译自 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$ 取模。

---

样例 1

输入

4
2 4 2 1

输出

3

解释
第一个和第三个小矮人都提到高度 $2$ 的帽子，因此第二个小矮人一定戴着高度为 $2$ 的帽子。若第四个小矮人指的是他右邻居（即第三个小矮人）的帽子，则第二个小矮人指的是第一个小矮人的帽子，排列为 $4\ 2\ 1\ 3$。若第四个小矮人指的是自己的帽子，则可能有两种排列：$4\ 2\ 3\ 1$ 或 $3\ 2\ 4\ 1$。总共有 $3$ 种可能。

---

样例 2

见附加文件下 imp1ocen.in 和 imp1ocen.out。

该样例满足 $n=2$, $h_{i}=1$，答案为 $2$。

---

样例 3

见附加文件下 imp2ocen.in 和 imp2ocen.out。

该样例满足 $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$
4	$n \leq 100000$	$28$