write a go solution for Description:
This is the easy version of the problem. It differs from the hard one only in constraints on n. You can make hacks only if you lock both versions.

Let a_1,a_2,ldots,a_n be an array of non-negative integers. Let F(a_1,a_2,ldots,a_n) be the sorted in the non-decreasing order array of n-1 smallest numbers of the form a_i+a_j, where 1<=i<j<=n. In other words, F(a_1,a_2,ldots,a_n) is the sorted in the non-decreasing order array of n-1 smallest sums of all possible pairs of elements of the array a_1,a_2,ldots,a_n. For example, F(1,2,5,7)=[1+2,1+5,2+5]=[3,6,7].

You are given an array of non-negative integers a_1,a_2,ldots,a_n. Determine the single element of the array underbraceF(F(FldotsF_n-1(a_1,a_2,ldots,a_n)ldots)). Since the answer can be quite large, output it modulo 10^9+7.

Input Format:
The first line contains one integer n (2<=n<=3000) — the initial length of the array.

The second line contains n integers a_1,a_2,ldots,a_n (0<=a_i<=10^9) — the array elements.

Output Format:
Output a single number — the answer modulo 10^9+7.

Note:
In the first test, the array is transformed as follows: [1,2,4,5,6]to[3,5,6,6]to[8,9,9]to[17,17]to[34]. The only element of the final array is 34.

In the second test, F(a_1,a_2,ldots,a_n) is [2,2,2,8,8,8,8,8]. This array is made up of 3 numbers of the form 1+1 and 5 numbers of the form 1+7.

In the fourth test, the array is transformed as follows: [10^9,10^9,777]to[10^9+777,10^9+777]to[2*10^9+1554]. 2*10^9+1554 modulo 10^9+7 equals 1540.. Output only the code with no comments, explanation, or additional text.