問題文

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

高橋君はストックしている $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