D - 全域木 Editorial /

Time Limit: 5 sec / Memory Limit: 256 MB

問題文

各辺はに 1 から N(N-1)/2 までの相異なる重みがついているような N 頂点の無向完全グラフであり、 最小全域木で使われる辺の重みが小さいほうから順に A_1,A_2,...,A_{N-1} であるようなものの個数を 10^9+7 で割ったあまりを求めてください。

ただし、頂点の入れ替えでうつりあうようなグラフも異なるものとして数えます。

制約

  • 1 ≦ N ≦ 30
  • 1 ≦ A_1 < A_2 < ... < A_{N-1} ≦ N(N-1)/2
  • 入力はすべて整数である

入力

入力は以下の形式で標準入力から与えられる。

N
A_1
:
A_{N-1}

出力

条件を満たすグラフの個数を 10^9+7 で割ったあまりを 1 行に出力せよ。

入力例1

3
1
2

出力例1

6

3 頂点のすべてのグラフが条件を満たします。

入力例2

5
1
2
4
6

出力例2

69120

入力例3

5
2
3
4
5

出力例3

0

入力例4

10
1
2
4
6
8
10
11
12
14

出力例4

837872061