Джонни недавно нашел новый отличный туториал: «Как стать гроссмейстером?». В туториале говорится много странных и неожиданных для Джонни вещей, таких как то, что он должен быть терпеливым или что очень важно решать много все более и более сложных задач.
Мальчик нашел онлайн архив с задачами, разделенными по темам. Он выбрал \(p^{k_i}\) задач из \(i\)-й категории (\(p\) — его любимое число). Он хочет решить все эти задачи за две недели (терпение еще слишком сложно для Джонни, поэтому он смотрит только на простые задачи, которые могут быть решены за такой период). Теперь наш будущий гроссмейстер должен решить, какие темы покрыть на первой неделе, а какие на второй. Помогите ему распределить темы таким образом, чтобы нагрузка была равномерной.
Формально, дано \(n\) чисел \(p^{k_i}\), мальчик хочет разделить их на два непересекающихся набора, минимизировав разность между суммами чисел в наборах. Найдите минимальное значение модуля такой разности. Выведите остаток от деления результата на \(10^{9}+7\).
Выходные данные
Выведите одно целое число — остаток от деления ответа на \(1\,000\,000\,007\).
Примечание
Вы должны минимизировать модуль разности, а не остаток модуля разности. Например, если минимальная разность равна \(2\), но существует также разбиение, при котором разность равна \(10^9 + 8\), ответ равен \(2\), а не \(1\).
В первом наборе входных данных числа равны: \(4\), \(8\), \(16\), \(16\) и \(8\). Мы можем разделить их на два набора: \({4, 8, 16}\) и \({8, 16}\). Тогда модуль разности между суммами чисел в наборах будет равен \(4\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
5 2
2 3 4 4 3
3 1
2 10 1000
4 5
0 1 1 100
1 8
89
|
4
1
146981438
747093407
|