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

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 a single number — the answer modulo $ 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 $ .