B - 難易度 Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋君はプログラミングコンテストを開く仕事をしている。

高橋君はストックしている 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) が与えられる。

部分点

この問題には部分点が設定されている。

  • 4 ≦ N ≦ 3,000 を満たすデータセットに正解した場合は 50 点が与えられる。
  • 4 ≦ N ≦ 10^5 を満たすデータセットに正解した場合はさらに 50 点が与えられる。合計で 100 点となる。

出力

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

入力例1

5
1
2
4
5
10

出力例1

2

1, 2, 3, 5 問目もしくは 1, 2, 4, 5 問目を選ぶことができます。

入力例2

10
11
12
13
14
15
16
17
18
19
20

出力例2

0

1 つも条件に合う選び方がないこともあります。

入力例3

20
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

出力例3

94