小矮人们又举办了一场派对。这次共有 $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

5
3 4 3 4 1

输出格式 1

2

说明

第一个小矮人描述的肯定是第二个人的帽子（因此第二个人的帽子高度为 $3$），第五个小矮人描述的是第四个人的帽子（因此第四个人的帽子高度为 $1$）。此外，第二个和第四个小矮人都记得帽子高度为 $4$，因此这肯定是第三个小矮人的帽子。剩下的帽子高度 $2$ 和 $5$ 有两种可能的排列方式。

子任务

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