题目描述

Anon 有一个关于数字 1 到 N 的秘密排列 P。他写了一个程序，把这个排列编码成一个序列 Q，满足对于每个 i（1 <= i <= N），都有：

• Q_i = P_{i-1}，或
• Q_i = P_{i+1}。

由于不存在 P_0 和 P_{N+1}，所以必然有：

• Q_1 = P_2
• Q_N = P_{N-1}

问题在于，Anon 不太聪明，把排列 P 删掉了，因为他原以为总会存在一个唯一的排列与序列 Q 对应。而且他也不确定自己在生成 Q 的程序里有没有写错，因此这个序列 Q 甚至可能对任何排列都不合法。

现在他想知道：有多少个排列与给定序列 Q 对应。但在犯下这一连串错误之后，他陷入了存在主义危机，再也不敢写代码了。请你帮助他，编写程序 permutation.cpp，对于给定序列 Q，求出有多少个排列使得 Q 是其合法序列。

由于答案可能非常大，请输出答案对 1000000007（10^9 + 7）取模后的结果。

输入格式

第一行输入一个整数 N。
第二行输入 N 个整数，表示序列 Q 的各个元素。

输出格式

输出一个整数，表示满足条件的排列个数，对 10^9 + 7 取模。

数据范围

• 2 <= N <= 10^6
• 1 <= Q_i <= N

子任务

样例 1

输入

5
1 3 1 4 2

输出

3

说明

可能的排列为：

3 1 4 2 5
3 1 5 2 4
5 1 3 2 4

样例 2

输入

4
3 1 2 3

输出

0

说明

不存在满足条件的排列。