题目描述

John 把所有积蓄都投入了加密货币。现在他想靠“冠军饮食”——奶酪——来回血。

他有一个圆形盒子，里面有 $N$ 块奶酪。每块奶酪有一种类型，类型用整数表示。John 每天从盒子里拿走一块奶酪。拿走之前以及拿走之后，盒子中任意两块相邻的剩余奶酪都必须是不同类型。

形式化地说，给定一个环形数组：

我们要不断删除其中一个元素，直到数组为空。要求在每次删除之后，以及第一次删除之前，都不能存在两个相邻位置的值相同。

一次删除方案由离开数组的原始下标顺序定义。例如 $N=4$ 时共有 $4!=24$ 种删除顺序，但并非所有顺序都满足要求。

题目要求计算满足要求的删除顺序数量，结果对 $1\,000\,000\,007$ 取模。

题面示意图如下。图中位置 $A$ 和 $B$ 已经被取走，此时只有 $E$ 或 $G$ 可以被删除；如果删除 $C$，则 $D$ 和 $H$ 会变成相邻且类型相同；如果删除 $D$，则 $C$ 和 $E$ 会变成相邻且类型相同。

输入格式

第一行包含一个整数 $N$，表示环形数组长度。

第二行包含 $N$ 个整数：

表示数组中每个位置的类型。

输出格式

输出一个整数，表示满足要求的删除顺序数量。

本题有两种计分方式：

• 若输出等于环形数组答案，则该测试点得满分；
• 否则会继续与普通线性数组答案比较，即不认为 $v_1$ 和 $v_N$ 相邻；若相等，则该测试点得 $80\%$ 分数。

数据范围

• $1\le N\le 500$；
• $1\le v_i\le N$。

子任务

样例

样例 1

4
1 2 1 2

0

若按线性数组处理，答案为 $8$。可行删除序列包括：

1,2,3,4
1,2,4,3
1,4,2,3
1,4,3,2
4,1,2,3
4,1,3,2
4,3,1,2
4,3,2,1

样例 2

8
1 2 1 3 1 2 1 3

1728

若按线性数组处理，答案为 $6912$。

样例 3

4
1 2 3 4

24

所有元素两两不同，因此任意删除顺序均合法。

样例 4

6
1 2 3 1 3 2

96

若按线性数组处理，答案为 $312$。

样例 5

1
1

1

只有一个元素，因此只有一种删除方式。