UOJ Logo

NOI.AC

#31. MST

统计

最小生成树

题目描述

小 $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}$。以下为每个测试点的数据范围及性质:

测试数据编号 $n\le$ 特殊性质 $\ast$ 测试数据编号 $n\le$ 特殊性质 $\ast$
$1$ $4$ $\surd$ $11$ $20$ $\surd$
$2$ $4$ $\times$ $12$ $20$ $\times$
$3$ $5$ $\surd$ $13$ $25$ $\surd$
$4$ $5$ $\times$ $14$ $25$ $\times$
$5$ $6$ $\surd$ $15$ $30$ $\surd$
$6$ $6$ $\times$ $16$ $30$ $\times$
$7$ $7$ $\surd$ $17$ $35$ $\times$
$8$ $7$ $\times$ $18$ $35$ $\times$
$9$ $15$ $\surd$ $19$ $40$ $\times$
$10$ $15$ $\times$ $20$ $40$ $\times$

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

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

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