问题

在 Code Festival 2015 中，将举办一个集换式比赛。在集换式比赛中，参与某个内容后，你会得到该内容对应的一个印章。

高桥君希望收集所有内容的印章。于是他进行了以下情景并做了集换式比赛的预演。

• 场馆有 $N$ 个房间和 $N-1$ 条连接这些房间的通道。
• 任意两个房间之间可以通过若干通道移动。
• 有 $N$ 种不同的内容，第 $i$ 个房间 $(1 \leq i \leq N)$ 中会进行第 $i$ 种内容。

高桥君在预演中使用了以下伪代码算法进行集换式比赛。注意，该算法保证在每个印章都被按下一次后会停止。

进入房间 1 重复以下步骤：

• 如果当前房间的印章还没有按下，则按下印章
• X = 从当前房间出发能够经过一条通道到达的房间的集合
• 如果X中存在尚未访问的房间：
  • 移动到其中编号最小的房间
• 否则：
  • 如果当前房间是房间 1：结束集换式比赛
  • 否则：移动到X中距离房间 1 最近的房间

高桥君按下的第 $i$ 个印章是内容 $C_i$ 的印章。此时，预演使用的场馆结构有多少种可能性？场馆结构由连接了 $N-1$ 个房间的对组集合表示。注意，答案可能非常大，所以请计算除以 $10^9+7$ 的余数。

输入

输入的格式如下，从标准输入中给出。

$N$ $C_1$ $C_2$ : $C_N$

• 第 1 行是一个整数 $N (2 \leq N \leq 256)$，表示房间和内容的数量都是 $N$。
• 接下来的 $N$ 行给出了高桥君得到印章的顺序信息。其中第 $i$ 行是一个整数 $C_i (1 \leq C_i \leq N)$，表示高桥君按下的第 $i$ 个印章是内容 $C_i$ 的印章。注意，保证 $C_p \neq C_q$ 当且仅当 $p \neq q$。

输出

请输出作为场馆结构可能的数量，计算结果需要对 $10^9+7 (1,000,000,007)$ 取模，以一行输出。输出末尾要换行。

输入样例1

4
1
2
4
3

输出样例1

3

有可能的三种场馆结构如下所示。

输入样例2

2
2
1

输出样例2

0

输入样例3

30
1
28
14
7
27
17
25
4
26
2
10
19
11
12
13
23
29
20
18
3
16
24
22
5
30
9
15
6
21
8

输出样例3

348275800