问题描述

高桥君正在进行一项开设编程竞赛的工作。

高桥君从他的题库中选择 $N$ 道问题，作为竞赛的题目。

每个问题都有一个正整数表示其"难度"，第 $i$ 道问题的难度为 $D_i$。

所选的问题必须满足以下 $3$ 个条件：

• 第二道问题的难度必须是第一道问题难度的 $2$ 倍以上。
• 第三道问题的难度必须是第二道问题难度的 $2$ 倍以上。
• 第四道问题的难度必须是第三道问题难度的 $2$ 倍以上。

在满足上述条件的情况下，从 $N$ 个问题中选择 $4$ 道问题，求共有多少种选择方式。

由于结果可能非常大，因此请输出结果除以 $1,000,000,007 (= 10^9 + 7)$ 后的余数。

---

输入

从标准输入中以以下格式给出输入：

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

• 第一行输入一个整数 $N (4 \leq N \leq 10^5)$，表示高桥君的题库中问题的数量。
• 接下来的 $N$ 行中的第 $i$ 行给出第 $i$ 道问题的难度 $D_i (1 \leq D_i \leq 10^5)$。

---

部分分

本问题有部分分。

• 若能通过满足 $4 \leq N \leq 3,000$ 的数据集，则可获得 $50$ 分。
• 若能通过满足 $4 \leq N \leq 10^5$ 的数据集，则额外可获得 $50$ 分。总计可获得 $100$ 分。

---

输出

请输出高桥君选择问题的方式数，将结果除以 $1,000,000,007(=10^9+7)$ 后，以一行输出。输出末尾需换行。

---

示例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

有可能没有符合条件的选择方式。

---

示例3

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

输出示例3

94

---