Problem Description

Consider an undirected complete graph with $N$ vertices where each edge has a distinct weight ranging from $1$ to $N(N-1)/2$. Find the number of such graphs where the weights of the edges used in the minimum spanning tree are, in ascending order, $A_1, A_2, ..., A_{N-1}$, modulo $10^9+7$.

Note that graphs that can be transformed into each other by swapping vertices are counted as distinct.

Input Format

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

$ N $ $ A_1 $ : $ A_{N-1} $

Output Format

Output the number of graphs satisfying the conditions, modulo $10^9+7$, in one line.

Sample Input and Output

Sample Input #1

3
1
2

Sample Output #1

6

Sample Input #2

5
1
2
4
6

Sample Output #2

69120

Sample Input #3

5
2
3
4
5

Sample Output #3

0

Sample Input #4

10
1
2
4
6
8
10
11
12
14

Sample Output #4

837872061

Notes/Hints

Constraints

• $1 \leq N \leq 30$
• $1 \leq A_1$
• All inputs are integers

见题面 Input 部分

见题面 Output 部分