Fișierul intrare/ieșire	camelot.in, camelot.out	Sursă	Concurs Clasa a 7-a
Autor	Teodor Plop	Adăugată de	Teodor Plop • teodor94
Timp de execuție pe test	0.1 sec	Limită de memorie	2048 KB
Scorul tău	N/A	Dificultate	2.25

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

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]. 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.

Rezultatul va fi afisat modulo 900001.

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.

Date de ieșire

Î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.

Restricții

• 2 ≤ N ≤ 400
• 1 ≤ p[i] ≤ 600
• Orice soldat trebuie sa apartina unei singure echipe.

Exemplu

Explicație

Cele trei posibilitati sunt:
{1} si {2, 3};
{1, 2} si {3};
{2} si {1, 3}.