Розподіл золота#2586
Бессі та Кенмуу знайшли мішок з (1 \leq N \leq 250) золотими монетами, які вони хочуть поділити якомога рівномірніше. Монета має вартість v_i (1 \leq v_i \leq 2000). Корови прагнуть розділити монети якнайрівномірніше, але це не завжди можливо. Яка найменша можлива різниця між сумами у двох купах?
Крім того, Бессі з Кенмуу виявили, що може існувати кілька різних способів поділити монети для досягнення цієї мінімальної різниці. Вони також хотіли б знати кількість способів поділити монети якомога справедливіше. Якщо поділ навпіл неможливий, Бессі отримає купу з більшою сумою.
Наприклад, розглянемо п’ять монет номіналами , , , та . Вони поділяють монети на дві купи: в одній монета номіналом , в іншій — решта (1+2+4+8=15). Різниця складає 16-15=1. Це єдиний спосіб поділити монети з такою різницею, тож кількість оптимальних поділів дорівнює 1.
Зверніть увагу, що монети однакової вартості можна переставляти між купами, збільшуючи кількість оптимальних способів поділу. Наприклад, набір монет \{1, 1, 1, 1\} можна оптимально розділити на дві частини по дві монети у кожній шістьма різними способами.
Перший рядок містить одне ціле число .
Наступні рядків містять по одному цілому числу v_i.
У першому рядку виведіть одне ціле число — найменшу можливу різницю між сумами у двох купах.
У другому рядку виведіть одне ціле число — кількість способів поділити монети з мінімальною різницею (яка виведена у першому рядку). Оскільки це число може бути досить великим, виведіть його по модулю .
Приклад 1