44444

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

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

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

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

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

• 入力はすべて整数

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

5
4 4 4 4 4

0

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

3
2 1 3

6

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

| 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