它们又来了！小矮人们在上次聚会后又举办了一场余兴派对。这次依然有 $n$ 个小矮人，每个人都得到了一顶尖顶帽子（共有 $n$ 顶高度各不相同的帽子，高度从 $1$ 到 $n$）。他们依然坐在长桌的一侧用餐。

当地的画家又要将这次聚会画下来，因此他询问了每个小矮人关于帽子高度的信息。然而，这次小矮人们记得更少了，每个人只能说出他左边的邻居、右边的邻居或者他自己的帽子高度。

请帮助画家编写一个程序，根据小矮人们的陈述，计算出可能的帽子排列方案数。结果对 $10^9 + 7$ 取模。如果小矮人们记错了，导致提供的信息相互矛盾，则正确结果为 $0$。

输入格式

第一行包含一个整数 $n$ ($n \ge 2$)，表示小矮人的数量。

第二行包含一个由 $n$ 个整数组成的序列 $h_1, h_2, \dots, h_n$ ($1 \le h_i \le n$)；数字 $h_i$ 表示第 $i$ 个小矮人（从桌子左端开始计数）告诉画家：“我或者我身边的邻居戴着高度为 $h_i$ 的帽子”。

输出格式

输出一行，包含一个整数，表示符合小矮人陈述的帽子排列方案数。结果需对 $10^9 + 7$ 取模。

样例

样例输入 1

4
2 4 2 1

样例输出 1

3

说明

第一个和第三个小矮人记得帽子高度为 $2$，因此这顶帽子一定是第二个小矮人的。如果第四个小矮人记得的是他邻居（即第三个小矮人）的帽子，那么第二个小矮人一定记得的是第一个小矮人的帽子，因此帽子顺序为 $4\ 2\ 1\ 3$。

如果第四个小矮人记得的是他自己的帽子高度，那么有两种可能：$4\ 2\ 3\ 1$ 或 $3\ 2\ 4\ 1$。

子任务

测试集分为以下子任务。每个子任务的测试由一组或多组独立的测试用例组成。