AT_arc043_b [ARC043B] 難易度

[problemUrl]: https://atcoder.jp/contests/arc043/tasks/arc043_b 高橋君はプログラミングコンテストを開く仕事をしている。 高橋君はストックしている $ N $ 個の問題から $ 4 $ 問を選んでコンテストに出題する。 各問題には「難易度」という正の整数が決められており、 $ i $ 番目の問題の難易度は $ D_i $ である。 選ぶ問題は以下の $ 3 $ つの条件を満たしていなければならない。 - $ 2 $ 問目の難易度は $ 1 $ 問目の難易度の $ 2 $ 倍以上である。 - $ 3 $ 問目の難易度は $ 2 $ 問目の難易度の $ 2 $ 倍以上である。 - $ 4 $ 問目の難易度は $ 3 $ 問目の難易度の $ 2 $ 倍以上である。 上の条件のもとで $ N $ 個の問題から $ 4 $ 問選ぶとき、何通りの選び方があるか求めよ。 この値は非常に大きくなり得るので $ 1,000,000,007\ (=\ 10^9\ +\ 7) $ で割った余りを求めよ。

入力は以下の形式で標準入力から与えられる > $ N $ $ D_1 $ $ D_2 $ : $ D_N $ - $ 1 $ 行目には高橋君がストックしている問題の個数 $ N\ (4\ ≦\ N\ ≦\ 10^5) $ が与えられる。 - $ 2 $ 行目からの $ N $ 行のうち $ i $ 行目には $ i $ 番目の問題の難易度を表す整数 $ D_i\ (1\ ≦\ D_i\ ≦\ 10^5) $が与えられる。

高橋君の問題の選び方の通り数を $ 1,000,000,007(=10^9+7) $ で割った余りを1行で出力せよ。 出力の末尾に改行を入れること。

### 部分点 この問題には部分点が設定されている。 - $ 4\ ≦\ N\ ≦\ 3,000 $ を満たすデータセットに正解した場合は $ 50 $ 点が与えられる。 - $ 4\ ≦\ N\ ≦\ 10^5 $ を満たすデータセットに正解した場合はさらに $ 50 $ 点が与えられる。合計で $ 100 $ 点となる。 ### Sample Explanation 1 $ 1,\ 2,\ 3,\ 5 $ 問目もしくは $ 1,\ 2,\ 4,\ 5 $ 問目を選ぶことができます。 ### Sample Explanation 2 $ 1 $ つも条件に合う選び方がないこともあります。