Problem Statement

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

高橋君はストックしている $N$ 個の問題から $4$ 問を選んでコンテストに出題する。

各問題には「難易度」という正の整数が決められており、 $i$ 番目の問題の難易度は $D_i$ である。

選ぶ問題は以下の $3$ つの条件を満たしていなければならない。

• $2$ 問目の難易度は $1$ 問目の難易度の $2$ 倍以上である。
• $3$ 問目の難易度は $2$ 問目の難易度の $2$ 倍以上である。
• $4$ 問目の難易度は $3$ 問目の難易度の $2$ 倍以上である。

上の条件のもとで $N$ 個の問題から $4$ 問選ぶとき、何通りの選び方があるか求めよ。

この値は非常に大きくなり得るので $1,000,000,007 (= 10^9 + 7)$ で割った余りを求めよ。

Input

入力は以下の形式で標準入力から与えられる

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$ 点となる。

Output

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