Problem Description

At the Code Festival 2015, a stamp rally was held. In the stamp rally, participating in a certain content allows you to get a stamp corresponding to that content.

Takahashi wants to collect stamps from all contents. Therefore, Takahashi conducted a rehearsal of the stamp rally assuming the following situation:

• The venue consists of $ N $ rooms and $ N-1 $ corridors connecting pairs of rooms.
• Any two rooms can be reached by traversing some corridors.
• There are $ N $ types of contents, and content $i\ (1\ ≦\ i\ ≦\ N)$ is held in room $ i $.

Takahashi proceeded with the stamp rally using an algorithm similar to the following pseudocode. It is guaranteed that this algorithm always stops after getting all stamps once.

Enter room 1 Repeat the following: If the stamp of the current room has not been collected yet: Collect the stamp X = Set of rooms that can be reached by exactly one corridor from the current room If there is an unvisited room in X: Move to the room with the smallest number otherwise: If the current room is room 1: End the stamp rally otherwise: Move to the room closest to room 1 in X

The $i\ (1\ ≦\ i\ ≦\ N)$ stamp collected by Takahashi was the stamp of content $ C_i $. How many possible structures of the venue can be considered for this rehearsal? The structure of the venue is represented by the set of pairs of rooms connected by $ N-1 $ corridors. Since the answer can be a very large number, find it modulo $ 10^9+7 $.

Input Format

The input is given from the standard input in the following format:

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

• The first line contains an integer $N\ (2\ ≦\ N\ ≦\ 256)$, indicating that there are $ N $ rooms and $ N $ contents.
• The next $ N $ lines contain the information about the order of stamps collected by Takahashi. The $i\ (1\ ≦\ i\ ≦\ N)$ line contains an integer $C_i\ (1\ ≦\ C_i\ ≦\ N)$, indicating that the $ i $ stamp collected was the stamp of content $ C_i $. It is guaranteed that $C_p\ \neq\ C_q$ when $p\ \neq\ q$.

Output Format

Output the number of possible structures of the venue modulo $10^9+7\ (1,000,000,007)$ in one line. Ensure a newline at the end of the output.

Sample Input and Output

Sample Input #1

4
1
2
4
3

Sample Output #1

3

Sample Input #2

2
2
1

Sample Output #2

0

Sample Input #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

Sample Output #3

348275800

Notes/Hints

Sample Explanation 1

The following three structures are possible:

见题面 Input 部分

见题面 Output 部分