Это простая версия задачи. Она отличается от сложной только ограничением на \(n\). Вы можете делать взломы, только если заблокируете обе версии задачи.
Пусть \(a_1, a_2, \ldots, a_n\) — массив, состоящий из целых неотрицательных чисел. Определим \(F(a_1, a_2, \ldots, a_n)\) как отсортированный по неубыванию массив, состоящий из \(n - 1\) минимальных чисел вида \(a_i + a_j\), где \(1 \le i < j \le n\). Другими словами, \(F(a_1, a_2, \ldots, a_n)\) — это отсортированный по неубыванию массив из \(n - 1\) минимальных сумм всевозможных пар элементов массива \(a_1, a_2, \ldots, a_n\). Например, \(F(1, 2, 5, 7) = [1 + 2, 1 + 5, 2 + 5] = [3, 6, 7]\).
Вам дан массив, состоящий из целых неотрицательных чисел \(a_1, a_2, \ldots, a_n\). Определите, чему равен единственный элемент массива \(\underbrace{F(F(F\ldots F}_{n-1}(a_1, a_2, \ldots, a_n)\ldots))\). Так как ответ может быть достаточно большим, выведите его по модулю \(10^9+7\).
Примечание
В первом тесте массив трансформируется следующим образом: \([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\).