Adam 即将乘坐公共汽车进行一次长途旅行。他可以选择购买 20 分钟的票（价格为 2 PLN）或 75 分钟的票（价格为 6 PLN）。车票可以在任何整分钟购买，并会自动生效。例如，在 9:14:00 购买的 20 分钟车票有效期至 9:33:59。即使 Adam 手中还有有效的车票，他也可以购买新票。

公交车共有 $N$ 个停靠站，第 $i$ 个停靠站在第 $t_i$ 分钟。在每个停靠站，可能会有检票员等待。他们会上车立即检查所有乘客，然后下车（此过程仅需几秒钟）。

在旅程开始时，Adam 会收到关于哪些停靠站有检票员的信息。他随后会规划购票方案，以最小化总支出，并确保在每次检查时都持有有效的车票。

考虑所有 $2^N$ 种检票员分布的情况，计算 Adam 的最优支出总和（单位为 PLN）。输出该总和除以 $10^9 + 7$ 的余数。

输入格式

第一行包含一个整数 $N$ ($1 \le N \le 1000$)，表示停靠站的数量。

第二行包含一个递增的整数序列 $t_1, t_2, \dots, t_N$ ($1 \le t_i \le 10^9, t_i < t_{i+1}$)，表示公交车停靠的分钟数。

输出格式

输出一个整数，即结果除以 $10^9 + 7$ 的余数。

样例

样例输入 1

3
1 8 20

样例输出 1

14

样例输入 2

5
25 45 65 85 1000000000

样例输出 2

156

说明

在第一个样例中，共有 3 个停靠站，需要考虑 8 种情况。如果 Adam 收到信息显示没有任何停靠站有检票员，他将不会购买任何车票。在其余 7 种情况中，他只需要一张 20 分钟的车票，花费 2 PLN。答案为 $0 + 7 \cdot 2 = 14$ PLN。

让我们考虑第二个样例中 32 种情况里的 2 种：

• 所有 5 个停靠站（25, 45, 65, 85, 1 000 000 000）都有检票员 —— Adam 花费 8 PLN：购买一张 75 分钟的车票（6 PLN）和一张 20 分钟的车票（2 PLN），例如分别在第 25 分钟和第 1 000 000 000 分钟购买。
• 有 2 个停靠站（25, 45）有检票员 —— Adam 花费 4 PLN 购买两张 20 分钟的车票，例如分别在第 25 分钟和第 45 分钟购买，或者在第 17 分钟和第 26 分钟购买。

*华沙的实际票价为 20 分钟 3.40 PLN，75 分钟或全程票 4.40 PLN。通常购买长时效车票更划算。