Розподіл золота
Бессі та Канмуу знайшли мішок із 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.