「POI 2021/2022 R1」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$ 取模。

样例 1

输入

5
3 4 3 4 1

输出

2

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

数据范围与提示