問題文

AliceとBobはNN枚のカードをそれぞれ持っています.カードにはそれぞれ11以上99以下の数値が書かれています.Aliceが持っているカードの値と,Bobが持っているカードの値は同じです.

22人は次のようなゲームを行います.

  1. それぞれ自分の持っているカードをすべて伏せて置きます.
  2. 22人同時に,自分の持っているカードの中からランダムに11枚を選びそれを表にします.
  3. 自分が表にしたカードの値が,相手が表にしたカードの値以上だったプレイヤーは11ポイントを得ます.22人が表にしたカードの値が同じだった場合は22人ともポイントを得ます.
  4. 伏せられたカードがまだある場合は,2に戻ります.一度表にしたカードはもう使うことができません.

それぞれNN枚のカードを表にしたのち,より多くのポイントを持っているプレイヤーの勝ちです.22人が持っているポイントが同じ場合は引き分けです.

カードの値の集合AAが与えられるので,これを使ってこのゲームを行った場合,Aliceが勝つ場合が何通りあるかを求めてください.ただし,同じ値が書かれたカードも別のカードとして区別します. また,答えは非常に大きくなることがあるため,答えを109+710^9+7で割ったあまりを出力してください.

制約

  • 1N91 \leq N \leq 9
  • 1Ai91 \leq A_i \leq 9 (1iN)(1 \leq i \leq N)
  • 入力はすべて整数

入力

NN
A1ANA_1 \dots A_N

出力

入力で与えられたカードの値の集合でゲームを行った場合,Aliceが勝つ場合が何通りあるかを出力してください.ただし,答えは非常に大きくなることがあるため,答えを109+710^9+7で割ったあまりを出力してください.

サンプル

入力例1
5
4 4 4 4 4
出力例1
0

ゲームは必ず引き分けになるため,Aliceが勝つことはありません.

入力例2
3
2 1 3
出力例2
6

例えばAliceが11 22 33の順,Bobが33 11 22の順で表にした場合,Aliceが得るポイントは22,Bobが得るポイントは11ポイントなのでAliceの勝ちです.このサンプルでAliceが勝つのは以下の66通りです.

| Alice |  Bob  |
| 1 2 3 | 3 1 2 |
| 1 3 2 | 3 2 1 |
| 2 1 3 | 1 3 2 |
| 2 3 1 | 1 2 3 |
| 3 1 2 | 2 3 1 |
| 3 2 1 | 2 1 3 |
入力例3
4
9 6 3 6
出力例3
96

提出


Go (1.21)