Деление золота
Бесси и Канмуу нашли мешок с N (1 ≤ N ≤ 250) золотыми монетами, которые они хотят разделить как можно более равномерно. Монета i имеет стоимость v_i (1 ≤ V_i ≤ 2,000). Коровы стремятся разделить монеты так, чтобы разница в стоимости между двумя кучами была минимальной, хотя это не всегда возможно. Какова минимальная разница между суммами двух куч?
Кроме того, Бесси и Канмуу обнаружили, что может существовать несколько способов разделить монеты с этой минимальной разницей. Они также хотят узнать количество способов, которыми можно разделить монеты наиболее справедливо. Если невозможно разделить кучи поровну, Бесси получит кучу с большей стоимостью.
Например, рассмотрим мешок из пяти монет со значениями: 2, 1, 8, 4 и 16. Бесси и Канмуу разделяют монеты на две кучи: одна куча с одной монетой стоимостью 16, а другая куча с оставшимися монетами стоимостью 1+2+4+8=15. Таким образом, разница составляет 16-15 = 1. Это единственный способ разделить монеты таким образом, поэтому количество способов разделить их поровну равно 1.
Заметьте, что монеты с одинаковой стоимостью могут быть перемещены между кучами, чтобы увеличить количество способов выполнить оптимальное разделение. Таким образом, набор монет {1, 1, 1, 1} имеет шесть различных способов разделить на две оптимальные части, каждая из которых содержит по две монеты.
Входные данные
Строка 1: Одно целое число: N.
Строки 2..N+1: Строка i+1 содержит одно целое число: V_i.
Выходные данные
Строка 1: Одно целое число, которое является наименьшей разницей двух частей.
Строка 2: Одно целое число, которое является количеством способов разделить монеты с минимальной разницей, напечатанной в строке 1. Поскольку это число может быть довольно большим, напечатайте остаток от деления на 1,000,000.