CF1805F1.Survival of the Weakest (easy version)

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 \lt 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$.

这是该问题的简单版本。它与困难版本的唯一区别在于对 $n$ 的约束条件。你只有在同时锁定两个版本的情况下才能进行 hack。

设 $a_1, a_2, \ldots, a_n$ 是一个非负整数数组。令 $F(a_1, a_2, \ldots, a_n)$ 表示所有形如 $a_i + a_j$（其中 $1 \le i \lt j \le n$）的 $n - 1$ 个最小数值按非递减顺序排列所得的数组。换言之，$F(a_1, a_2, \ldots, a_n)$ 是数组 $a_1, a_2, \ldots, a_n$ 中所有可能元素对之和中最小的 $n - 1$ 个和，按非递减顺序排列所得的数组。例如，$F(1, 2, 5, 7) = [1 + 2, 1 + 5, 2 + 5] = [3, 6, 7]$。

给定一个非负整数数组 $a_1, a_2, \ldots, a_n$，求经过 $n-1$ 次嵌套应用函数 $F$ 后所得数组的唯一元素，即 $\underbrace{F(F(F\ldots F}_{n-1}(a_1, a_2, \ldots, a_n)\ldots))$。由于答案可能非常大，请输出其对 $10^9+7$ 取模的结果。

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.

第一行包含一个整数 $n$（$2 \le n \le 3000$）—— 数组的初始长度。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \le a_i \le 10^9$）—— 数组的元素。

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

输出一个整数——答案对 $10^9 + 7$ 取模的结果。

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$.

在第一次测试中，数组的变换过程如下：$[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$ 的数构成。

在第四次测试中，数组的变换过程如下：$[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$。