Problem Statement

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

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

Constraints

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

Input

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

N
A_1
:
A_{N-1}

Output

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