CSES - Tasapaino
  • 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 nn: punnusten määrä.

Seuraavalla rivillä on nn kokonaislukua p1,p2,,pnp_1,p_2,\dots,p_n: punnusten painot.

Tuloste

Tulosta yksi kokonaisluku: mahdollisten tapojen määrä modulo 109+710^9+7.

Rajat

  • 1n1001 \le n \le 100
  • 1pi10001 \le p_i \le 1000

Esimerkki

Syöte:

4
2 2 3 3

Tuloste:

4

Selitys: Merkitään punnuksia 21,22,31,322_1,2_2,3_1,3_2, jotta samanpainoiset punnukset erottuvat. Mahdolliset jaot ovat: [21,31][2_1,3_1] ja [22,32][2_2,3_2], [22,31][2_2,3_1] ja [21,32][2_1,3_2], [21,32][2_1,3_2] ja [22,31][2_2,3_1], [22,32][2_2,3_2] ja [21,31][2_1,3_1].