题目描述

题目译自 XXIX Olimpiada Informatyczna – I etap Impreza krasnali

小矮人又举办了一次派对。他们还是有 $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)$，表示每个小矮人的回答。从左数第 $i$ 个小矮人告诉画家：「我桌子上的一个邻居戴的帽子高度是 $h_{i}$」。

输出格式

输出一行一个整数，表示符合小矮人们的回答的帽子排列的数量。你的答案应该对 $10^{9}+7$ 取模。

5
3 4 3 4 1

2

第一个小矮人描述的肯定是第二个小矮人的帽子（所以第二个小矮人的帽子是 $3$），第五个小矮人描述的肯定是第四个小矮人的帽子（所以第四个小矮人的帽子是 $1$）。另外，第二个和第四个小矮人都记得有一顶 $4$ 号的帽子，所以那肯定是第三个小矮人的帽子。剩下的就是两种可能的排列方式，把 $2$ 号和 $5$ 号的帽子分别放在第一个和第五个小矮人的头上，或者反过来。

样例 2

见附加文件下 [imp1.in](file:imp1.in) 和 [imp1.out](file:imp1.out)。

该样例满足 $n=99999, h_{i}=i$。答案是 $0$。

样例 3

见附加文件下 [imp2.in](file:imp2.in) 和 [imp2.out](file:imp2.out)。

该样例满足 $n=10^5, h_{i}=i$。答案是 $1$。

数据范围与提示

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

子任务编号	附加限制	分值
$1$	$n \leq 10$	$12$
$2$	$n \leq 20$	$30$
$3$	$n \leq 1000$	$30$
$4$	$n \leq 10^5$	$28$