Candale Silviu (silviu) X şi Y se joacă cu N biluţe, fiecare biluţă având scrisă pe ea o cifră nenulă. Inventivi din fire, aceştia au împărţit cele N biluţe în două grămezi, astfel încât valoarea medie a grămezii lui X să fie egală cu valoarea medie a grămezii lui Y. Valoarea medie a unei grămezi este egală cu suma tuturor numerelor din grămadă împărţită la numărul de elemente ale acesteia.
Cerința
Dându-se cele N valori scrise pe biluţe, aflaţi în câte moduri pot fi împărţite biluţele în două grămezi ale căror valori medii să fie egale. Cum acest număr poate fi prea mare, afişaţi doar restul împărţirii acestui număr la 666013.
Date de intrare
Fișierul de intrare bilute1.in conține pe prima linie numărul natural N, iar pe a 2-a linie se afla N numere naturale separate prin exact un spaţiu, reprezentând valorile scrise pe cele N biluţe.
Date de ieșire
Fișierul de ieșire bilute1.out va conține un singur număr, reprezentând numărul de moduri în care pot fi împărţite biluţele în grămezi, conform cerinţei de mai sus.
Restricții și precizări
2 ≤ N ≤ 750- Două configuraţii sunt considerate distincte dacă există cel puţin o biluţă care se află în grămezi diferite
- Pentru o configuraţie, ordinea de repartizare a grămezilor pentru X şi Y este semnificativă
- Fiecare grămadă trebuie să conţină cel puţin o biluţă
- Fiecare biluţă trebuie să se afle în exact una dintre cele două grămezi
- Pentru 15% dintre teste
N ≤ 20 - Pentru 25% dintre teste valoarea de pe biluţe
≤ 3
Exemplul 1
bilute1.in
6 1 2 3 4 5 6
bilute1.out
6
Explicație
GX=[1,2,5,6]; GY=[3,4], unde(1+2+5+6)/4=(3+4)/2GX=[1,3,4,6]; GY=[2,5]GX=[1,6]; GY=[2,3,4,5]GX=[2,3,4,5]; GY=[1,6]GX=[2,5]; GY=[1,3,4,6]GX=[3,4]; GY=[1,2,5,6]
Exemplu:
bilute1.in
6 1 1 2 2 3 3
bilute1.out
22