310255: CF1805F1. Survival of the Weakest (easy version)

F1. Survival of the Weakest (easy version)time limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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 \le i < j \le 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 $\underbrace{F(F(F\ldots F}_{n-1}(a_1, a_2, \ldots, a_n)\ldots))$. Since the answer can be quite large, output it modulo $10^9+7$.

Input

The first line contains one integer $n$ ($2 \le n \le 3000$) — the initial length of the array.

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

Output

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

ExamplesInput

5
1 2 4 5 6

Output

34

Input

9
1 1 1 7 7 7 9 9 9

Output

256

Input

7
1 7 9 2 0 0 9

Output

20

Input

3
1000000000 1000000000 777

Output

1540

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 \cdot 10^9 + 1554]$. $2 \cdot 10^9 + 1554$ modulo $10^9+7$ equals $1540$.

题目大意：
这是一个关于数组的问题。给定一个非负整数数组 $a_1, a_2, \ldots, a_n$，定义函数 $F(a_1, a_2, \ldots, a_n)$ 为数组中所有可能的两元素之和（$a_i + a_j$，其中 $1 \le i < j \le n$）按非递减顺序排序后的前 $n - 1$ 个最小值组成的数组。重复应用 $F$ 函数 $n-1$ 次后，求最终数组中唯一的元素，结果对 $10^9+7$ 取模输出。

输入输出数据格式：
输入：
- 第一行包含一个整数 $n$ ($2 \le n \le 3000$) —— 数组的初始长度。
- 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$) —— 数组元素。

输出：
- 输出一个数字 —— 经过 $n-1$ 次函数 $F$ 处理后数组中唯一的元素，对 $10^9 + 7$ 取模的结果。

示例：
输入：
```
5
1 2 4 5 6
```
输出：
```
34
```

输入：
```
9
1 1 1 7 7 7 9 9 9
```
输出：
```
256
```

输入：
```
3
1000000000 1000000000 777
```
输出：
```
1540
```

注意：
- 在第一个示例中，数组经过 $F$ 函数处理的过程是：$$ [1, 2, 4, 5, 6] \to [3, 5, 6, 6] \to [8, 9, 9] \to [17, 17] \to [34] $$。最终数组中唯一的元素是 $34$。
- 在第二个示例中，$F(a_1, a_2, \ldots, a_n)$ 的结果是 $$ [2, 2, 2, 8, 8, 8, 8, 8] $$。这个数组由 $3$ 个 $1 + 1$ 形式的数字和 $5$ 个 $1 + 7$ 形式的数字组成。
- 在第四个示例中，数组经过 $F$ 函数处理的过程是：$$ [10^9, 10^9, 777] \to [10^9+777, 10^9+777] \to [2 \cdot 10^9 + 1554] $$。$2 \cdot 10^9 + 1554$ 对 $10^9+7$ 取模等于 $1540$。题目大意： 这是一个关于数组的问题。给定一个非负整数数组 $a_1, a_2, \ldots, a_n$，定义函数 $F(a_1, a_2, \ldots, a_n)$ 为数组中所有可能的两元素之和（$a_i + a_j$，其中 $1 \le i < j \le n$）按非递减顺序排序后的前 $n - 1$ 个最小值组成的数组。重复应用 $F$ 函数 $n-1$ 次后，求最终数组中唯一的元素，结果对 $10^9+7$ 取模输出。 输入输出数据格式： 输入： - 第一行包含一个整数 $n$ ($2 \le n \le 3000$) —— 数组的初始长度。 - 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$) —— 数组元素。 输出： - 输出一个数字 —— 经过 $n-1$ 次函数 $F$ 处理后数组中唯一的元素，对 $10^9 + 7$ 取模的结果。 示例： 输入： ``` 5 1 2 4 5 6 ``` 输出： ``` 34 ``` 输入： ``` 9 1 1 1 7 7 7 9 9 9 ``` 输出： ``` 256 ``` 输入： ``` 3 1000000000 1000000000 777 ``` 输出： ``` 1540 ``` 注意： - 在第一个示例中，数组经过 $F$ 函数处理的过程是：$$ [1, 2, 4, 5, 6] \to [3, 5, 6, 6] \to [8, 9, 9] \to [17, 17] \to [34] $$。最终数组中唯一的元素是 $34$。 - 在第二个示例中，$F(a_1, a_2, \ldots, a_n)$ 的结果是 $$ [2, 2, 2, 8, 8, 8, 8, 8] $$。这个数组由 $3$ 个 $1 + 1$ 形式的数字和 $5$ 个 $1 + 7$ 形式的数字组成。 - 在第四个示例中，数组经过 $F$ 函数处理的过程是：$$ [10^9, 10^9, 777] \to [10^9+777, 10^9+777] \to [2 \cdot 10^9 + 1554] $$。$2 \cdot 10^9 + 1554$ 对 $10^9+7$ 取模等于 $1540$。