最小生成树

小 $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$ 取模的结果。

3
1 2

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

5
1 2 3 5

7
1 2 4 5 7 9

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}$

NOI.AC