F1. 最弱者的生存（简单版）
每个测试点的时间限制：3 秒
每个测试点的内存限制：256 兆字节

本题为简单版本，与困难版本的区别仅在于 $n$ 的数据范围。你可以锁定两个版本后再进行 $Hack$ 操作。

---

给定一个由非负整数组成的数组 $a_1, a_2, \dots, a_n$。
定义 $F(a_1, a_2, \dots, a_n)$ 为所有形如 $a_i + a_j$（其中 $1 \le i < j \le n$）的和中，最小的 $n-1$ 个和按非降序排列后得到的数组。

换句话说，$F(a_1, a_2, \dots, a_n)$ 是从所有可能的数对和里选出最小的 $n-1$ 个值，并从小到大排序。

例如：$F(1,2,5,7) = [1+2,\ 1+5,\ 2+5] = [3,6,7]$。

---

现在，给你一个数组 $a_1, a_2, \dots, a_n$。
考虑如下反复应用 $F$ 的过程：

$$F(F(F \dots F(a_1, a_2, \dots, a_n) \dots))$$

总共应用 $n-1$ 次 $F$。
最终我们会得到一个只包含一个元素的数组。
请你求出这个元素的值，并对 $10^9 + 7$ 取模后输出。

---

输入格式
第一行包含一个整数 $n$（$2 \le n \le 3000$），表示数组的初始长度。
第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \le a_i \le 10^9$），表示数组元素。

---

输出格式
输出一个整数 —— 最终的单元素值对 $10^9+7$ 取模的结果。

---

样例

样例 1
输入

5
1 2 4 5 6

输出

34

样例 2
输入

9
1 1 1 7 7 7 9 9 9

输出

256

样例 3
输入

7
1 7 9 2 0 0 9

输出

20

样例 4
输入

3
1000000000 1000000000 777

输出

1540

---

样例解释

• 样例 1
  变化过程：
  $[1,2,4,5,6] \rightarrow [3,5,6,6] \rightarrow [8,9,9] \rightarrow [17,17] \rightarrow [34]$
  最终唯一元素为 $34$。

• 样例 2
  $F(a_1,\dots,a_n) = [2,2,2,8,8,8,8,8]$
  这个数组由 $3$ 个 $1+1$ 和 $5$ 个 $1+7$ 组成。

• 样例 4
  变化过程：
  $[10^9,10^9,777] \rightarrow [10^9+777, 10^9+777] \rightarrow [2\cdot 10^9 + 1554]$
  $2\cdot 10^9 + 1554$ 对 $10^9+7$ 取模等于 $1540$。