最小生成树

题目描述

小 $D$ 最近学习了最小生成树的有关知识。为了更好地学习求最小生成树的流程，他造了一张 $n$ 个点的带权无向完全图（即任意两个不同的点之间均有且仅有一条无向边的图），并求出了这个图的最小生成树。

为了简单起见，小 $D$ 造的无向图的边权为 $[1,\frac{n(n-1)}{2}]$ 之间的整数，且任意两条边的边权均不一样。

若干天后，小 $D$ 突然发现自己不会求最小生成树了。于是他找出了当时求出的最小生成树，但是原图却怎么也找不到了。于是小 $D$ 想要求出，有多少种可能的原图。但是小 $D$ 连最小生成树都不会求了，自然也不会这个问题。请你帮帮他。

形式化地，你会得到 $n-1$ 个递增的正整数 $a_1,a_2,\cdots,a_{n-1}$，依次表示最小生成树上的边的边权。你要求出，有多少张 $n$ 个点的带权无向完全图，满足：

• 每条边的边权为 $[1,\frac{n(n-1)}{2}]$ 之间的整数；
• 任意两条不同的边的边权也不同；
• 至少存在一种最小生成树，满足树上的边权按照从小到大的顺序排列即为 $a_1,a_2,\cdots,a_{n-1}$（事实上，可以证明任意一张无向图的任意两棵最小生成树上的边权集合相同）。

因为答案可能很大，所以你只要求出答案对 $10^9+7=1,000,000,007$（一个质数）取模的结果即可。

输入格式

第一行一个整数 $n$。

第二行 $n-1$ 个空格隔开的整数 $a_1,a_2,\cdots,a_{n-1}$，表示最小生成树上的边权。

输出格式

一行一个整数表示可能的无向图个数对 $10^9+7$ 取模的结果。

输入样例 1

3
1 2

输出样例 1

6

样例解释 1

任意一张三个点的完全图均符合题意，所以答案为 $3\times 2\times 1=6$。

输入样例 2

5
1 2 3 5

输出样例 2

820800

输入样例 3

7
1 2 4 5 7 9

输出样例 3

616898266

数据规模与约定

本题共 $20$ 个测试数据，每个测试数据 $5$ 分。对于所有测试数据，保证 $1\le n\le 40$，$1\le a_i\le \frac{n(n-1)}{2}$。且对于任意 $1\le i\lt n-1$，有 $a_i\lt a_{i+1}$。以下为每个测试点的数据范围及性质：

其中，若 “特殊性质 $\ast$” 一栏为 “$\surd$”，则保证对于任意 $1\le i\le n-1$，有 $a_i=i$ 成立。否则不保证这一点成立。

时间限制：$2\mathtt{s}$

空间限制：$512\mathtt{MB}$