- Time limit: 1.00 s
- Memory limit: 512 MB
Sinulla on joukko punnuksia, joilla on tietyt painot. Haluat jakaa kaikki punnukset vaa'an vasempaan ja oikeaan kuppiin niin, että vaaka on tasapainossa.
Montako eri tapaa tähän on olemassa? Kaksi tapaa ovat erilaiset, jos jokin punnus on eri kupissa.
Syöte
Syötteen ensimmäisellä rivillä on kokonaisluku n: punnusten määrä.
Seuraavalla rivillä on n kokonaislukua p_1,p_2,\dots,p_n: punnusten painot.
Tuloste
Tulosta yksi kokonaisluku: mahdollisten tapojen määrä modulo 10^9+7.
Rajat
- 1 \le n \le 100
- 1 \le p_i \le 1000
Esimerkki
Syöte:
4 2 2 3 3
Tuloste:
4
Selitys: Merkitään punnuksia 2_1,2_2,3_1,3_2, jotta samanpainoiset punnukset erottuvat. Mahdolliset jaot ovat: [2_1,3_1] ja [2_2,3_2], [2_2,3_1] ja [2_1,3_2], [2_1,3_2] ja [2_2,3_1], [2_2,3_2] ja [2_1,3_1].