Uolevilla on pussi, jossa on n palloa, jotka on väritetty k:lla eri värillä. Värit on indeksoitu luvuilla 1, 2, \ldots, k. Samanväriset pallot ovat täysin samanlaisia. Uolevi otti kaikki pallot pussista jossain järjestyksessä. Hän huomasi että hän otti viimeisen värin i pallon ennen viimeistä värin i+1 palloa kaikille 1 \le i < k. Kuinka monella eri tavalla tämä voi tapahtua?

Syöte

Ensimmäisellä rivillä on luku k, värien määrä. Seuraavalla rivillä on k lukua, c_1, c_2, \ldots, c_k, jossa c_i on värin i pallojen määrä.

Tuloste

Tulosta eri järjestysten määrä modulo 10^9+7.

Rajat

• 1 \le k \le 1000
• 1 \le c_i \le 1000
• 1 \le n \le 1000, eli pallojen yhteismäärä on korkeintaan 1000.

Esimerkki

Syöte:

3
2 2 1

Tuloste:

3

Eri järjestykset ovat (1, 2, 1, 2, 3), (1, 1, 2, 2, 3) ja (2, 1, 1, 2, 3).

Syöte:

4
1 2 3 4

Tuloste:

1680