問題文

AliceとBobは$N$枚のカードをそれぞれ持っています．カードにはそれぞれ$1$以上$9$以下の数値が書かれています．Aliceが持っているカードの値と，Bobが持っているカードの値は同じです．

$2$人は次のようなゲームを行います．

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

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

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

制約

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

入力

出力

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

サンプル

5
4 4 4 4 4

0

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

3
2 1 3

6

例えばAliceが$1$ $2$ $3$の順，Bobが$3$ $1$ $2$の順で表にした場合，Aliceが得るポイントは$2$，Bobが得るポイントは$1$ポイントなのでAliceの勝ちです．このサンプルでAliceが勝つのは以下の$6$通りです．

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

4
9 6 3 6

96