Tagy: bruteforce
Obtiažnosť: easy

Prehliadka pamiatok

Ježko Pichliač ide na dovolenku do exotickej krajiny -- Aburdistanu. V Aburdistane je nn svetovo preslávených pamiatok a Ježko by ich chcel postupne navštíviť všetky. O každej pamiatke vie, koľko radosti z výletu mu daná pamiatka pridá, keď ju navštívi. Toto číslo môže byť aj záporné.

Ježko si chce teraz naplánovať svoj výlet. Nezáleží mu, v akom poradí navštívi pamiatky, chce však každú navštíviť práve raz a chce, aby v žiadnom momente neklesla jeho radosť z výletu pod 00. Na začiatku má samozrejme radosť 00. Pomôžte mu zistiť, koľkými rôznymi spôsobmi si vie naplánovať svoj výlet.

Úloha

Na vstupe dostanete počet pamiatok nn a tiež nn čísel rir_i -- množstvo radosti, ktoré nám pridá návšteva pamiatky ii. Zistite počet rôznych spôsobov návštevy všetkých pamiatok tak, aby v žiadnom momente nebola Ježkova radosť záporná.

Vstup

Na prvom riadku je číslo nn (1n91 \leq n \leq 9) -- počet pamiatok v Aburdistane.

Na druhom riadku je nn celých čísel rir_i (1000ri1000-1000 \leq r_i \leq 1000) -- množstvo radosti získanej pri návšteve ii-tej pamiatky.

Výstup

Vypíšte jedno celé číslo -- počet rôznych možností.

Príklady

Vstup

Výstup

3
1 -2 2
3

Ježko nemôže začať návštevou druhej pamiatky, lebo jeho radosť by hneď klesla pod 00. Ak začne prvou pamiatkou, ako ďalšia musí nasledovať tretia, takže máme jednu možnosť (1,3,2)(1, 3, 2). Ak začne treťou, obe zvyšné možnosti sú prijateľné, teda (3,1,2)(3, 1, 2) a (3,2,1)(3, 2, 1). Dokopy máme 33 rôzne výlety.

Vstup

Výstup

5
-540 817 331 366 -253
50
Ak chceš riešiť túto úlohu, musíš sa najprv prihlásiť.