== include(page="template/taskheader" task_id="camelot") ==
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$].
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]$. Astfel se vor forma doua echipe din acesti soldati, puterea fiecarei echipei fiind suma puterilor membrilor acesteia. Intr-o astfel de lupta, echipa pierzatoare este cea cu puterea mai mica.
Regele Uther Pendragon, curios din fire, doreste sa stie cate posibilitati de a imparti echipele exista, posibilitati in care prima echipa este cea pierzatoare.
h2. Date de intrare
Î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.
Î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.
h2. Date de ieșire
Î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.
În fișierul de ieșire $camelot.out$ se va gasi un singur numar natural [$P$], reprezentand numarul de posibilitati de a alege echipele astfel incat prima echipa sa fie cea pierzatoare.
h2. Restricții
* $2 ≤ N ≤ 400$
* $1 ≤ p[i] ≤ 600$
* $Orice soldat trebuie să aparțină unei singure echipe.$
* $Nu exista doi soldati cu aceeasi putere.$
* $Orice soldat trebuie sa apartina unei singure echipe.$
h2. Exemplu
table(example).
|_. camelot.in |_. camelot.out |
| 3
1 3 5
| 3
| 4
1 3 3 4
| 1
|
h3. Explicație
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$].
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$].
== include(page="template/taskfooter" task_id="camelot") ==
