== include(page="template/taskheader" task_id="camelot") ==
Cu ocazia venirii primaverii, maretul regat Camelot va fi gazda luptelor de echipa in The Grand Arena. In curtea regatului sunt $N$ soldati, fiecare avand o anumita putere $p[i]$. Regele Uther Pendragon, corect din fire, doreste sa formeze doua echipe, astfel incat acestea sa fie cat mai apropiate ca putere. Puterea unei echipe este determinata de suma puterilor membrilor acesteia.
Cu ocazia venirii primăverii, mărețul regat Camelot va fi gazda luptelor de echipă în The Grand Arena. În curtea regatului sunt $N$ soldați, fiecare având o anumită putere $p[i]$. Astfel se vor forma două echipe din acești soldați, puterea fiecărei echipei fiind suma puterilor membrilor acesteia. Într-o astfel de luptă, echipa pierzătoare este cea cu puterea mai mică.
Regele Uther Pendragon, curios din fire, dorește să știe câte posibilități de a împărți echipele există, posibilități în care prima echipă este cea pierzătoare.
Rezultatul va fi afișat modulo [$900001$].
h2. Date de intrare
În fișierul de intrare $camelot.in$ se gaseste pe prima linie numarul de soldati $N$ aflati in curtea regatului, iar pe cea de-a doua linie $N$ numere naturale, reprezentand puterile soldatilor.
În fișierul de intrare $camelot.in$ se găsește pe prima linie numărul de soldați $N$ aflați în curtea regatului, iar pe cea de-a doua linie $N$ numere naturale, reprezentând puterile soldaților.
h2. Date de ieșire
În fișierul de ieșire $camelot.out$ se va gasi un singur numar natural [$D$], reprezentand diferenta dintre puterea primei echipe si puterea celei de-a doua echipe in modul.
În fișierul de ieșire $camelot.out$ se va găsi un singur număr natural [$P$], reprezentând numărul de posibilități de a alege echipele astfel încât prima echipă să fie cea pierzătoare.
h2. Restricții
* $1 ≤ N ≤ 500$
* $1 ≤ p[i] ≤ 500$
* $Orice soldat trebuie sa apartina unei singure echipe.$
* $2 ≤ N ≤ 400$
* $1 ≤ p[i] ≤ 600$
* $Orice soldat trebuie să aparțină unei singure echipe.$
h2. Exemplu
table(example).
|_. camelot.in |_. camelot.out |
| 8
3 4 7 6 4 7 4 8
| 1
| 3
1 3 5
| 3
|
h3. Explicație
Prima echipa este formata din soldatii $2, 3, 4, 5$, iar cea de-a doua echipa este formata din soldatii $1, 6, 7, 8$. Puterea primei echipe este [$21$], iar puterea celei de-a doua echipe este [$22$].
Cele trei posibilități sunt:
${1} și {2, 3}$: Prima echipă are puterea [$1$], cea de-a doua echipă are puterea [$8$].
${1, 2} și {3}$: Prima echipă are puterea [$4$], cea de-a doua echipă are puterea [$5$].
${2} și {1, 3}$: Prima echipă are puterea [$3$], cea de-a doua echipă are puterea [$6$].
== include(page="template/taskfooter" task_id="camelot") ==
