Problem Description

Takahashi is in charge of organizing programming contests.

He has a stock of $ N $ problems and needs to select $ 4 $ problems to be used in a contest.

Each problem has a positive integer called "difficulty", and the difficulty of the $ i $ -th problem is $ D_i $.

The selected problems must satisfy the following three conditions:

• The difficulty of the second problem is at least twice the difficulty of the first problem.
• The difficulty of the third problem is at least twice the difficulty of the second problem.
• The difficulty of the fourth problem is at least twice the difficulty of the third problem.

Under these conditions, determine the number of ways to select $ 4 $ problems from the $ N $ problems.

Since this value can be very large, output it modulo $1,000,000,007\ (=\ 10^9\ +\ 7)$.

Input Format

The input is given from the standard input in the following format:

$ N $ $ D_1 $ $ D_2 $ : $ D_N $

• The first line contains the number of problems $N\ (4\ ≦\ N\ ≦\ 10^5)$.
• The next $ N $ lines contain the difficulty of the $ i $ -th problem as an integer $D_i\ (1\ ≦\ D_i\ ≦\ 10^5)$.

Output Format

Output the number of ways to select the problems modulo $ 1,000,000,007(=10^9+7) $ in one line. Ensure a newline at the end of the output.

Sample Input and Output

Sample Input #1

5
1
2
4
5
10

Sample Output #1

2

Sample Input #2

10
11
12
13
14
15
16
17
18
19
20

Sample Output #2

0

Sample Input #3

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

Sample Output #3

94

Notes/Hints

Partial Points

This problem has partial scoring:

• If you solve the dataset where $4\ ≦\ N\ ≦\ 3,000$, you get $ 50 $ points.
• If you solve the dataset where $4\ ≦\ N\ ≦\ 10^5$, you get an additional $ 50 $ points, totaling $ 100 $ points.

Sample Explanation 1

You can choose the $ 1, 2, 3, 5 $ -th problems or the $ 1, 2, 4, 5 $ -th problems.

Sample Explanation 2

There may be no way to choose problems that satisfy the conditions.

见题面 Input 部分

见题面 Output 部分