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

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.

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.

Restricții

• 2 ≤ N ≤ 400
• 1 ≤ p[i] ≤ 600
• Orice soldat trebuie să aparțină unei singure echipe.

Exemplu

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.