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