Bessie и Canmuu нашли мешок с $N$ ($1 \leq N \leq 250$) золотыми монетами и хотят разделить их как можно поровну. Монета $i$ стоит $v_i$ ($1 \leq V_i \leq 2{,}000$). Равенство стоимости двух куч не всегда возможно. Какова минимальная разница между их стоимостями?

Способов достичь минимальной разницы может быть несколько. Коровы также хотят знать число наиболее справедливых разделений. Если разделить поровну нельзя, Bessie получает более дорогую кучу.

Например, пять монет стоят $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,000,000$.

Примеры

Входные данные 1

5
2
1
8
4
16

Выходные данные 1

1
1

Автор задачи: Sherry Wu, классическая задача, 2010