Zadanie

Hodiny geometrie

Počet bodov: 50

Ivana získala vysnívanú prácu - vyučuje deti matematiku.

Keď učí geometriu, potrebuje často nakresliť nejaké mnohouholníky, s ktorými sa potom tá všakovaká geometria bude robiť. Aby to však nemusela zakaždým improvizovať, pripravila si pomôcku.

Nakreslila si pravidelný konvexný mnohouholník s \(N\) stranami. Potom na každú stranu nakreslila niekoľko bodov - na \(i\)-tu stranu ich nakreslila \(a_i\).

Keď bude potom na hodine potrebovať nejaký mnohouholník s \(N-1\) stranami, zoberie si ten pomocný, a pospája \(N-1\) z týchto bodov tak, aby jej vznikol konvexný mnohouholník s \(N-1\) stranami. Musí si pritom dávať pozor, aby vzniknutý mnohouholník mal kladný obsah, a taktiež si dá záležať, aby vnútorný uhol pri každom vrchole bol ostro menší ako 180 stupňov.

Nie je si však istá, na ako dlho jej táto pomôcka bude stačiť. Ivana ale nemá čas si to zrátať, keďže musí opravovať písomky z goniometrie…

Úloha

Daný je počet bodov, ktoré si Ivana nakreslila na strany pravidelného \(N\)-uholníka. Nie je podstatné kde presne, stačí vám vedieť, že sú navzájom rôzne a niesu vrcholmi originálneho mnohouholníka.

Zistite, koľko rôznych ostro konvexných \(N-1\) mnohouholníkov s kladným obsahom vie Ivana získať tak, že pospája \(N-1\) z týchto bodov. Dva mnohouholníky považujeme za rôzne, ak majú ako vrcholy rôzne body.

Keďže toto číslo môže byť priveľké, stačí ak vypíšete jeho zvyšok po delení \(10^9+7\).

Vstup a Výstup

V prvom riadku vstupu je číslo \(N\) - počet strán mnohouholníka. V druhom riadku vstupu je \(N\) nezáporných čísel \(a_1, a_2, \cdots, a_N\): počet nakreslených bodov na jeho stranách.

Vypíšte počet rôznych mnohouholníkov vie Ivana získať tak, ako je popísané v úlohe, mod \(10^9+7\).

Obmedzenia

Platí \(4 \leq N \leq 1000\) a \(0 \leq a_i \leq 1000\).

V prvej sade navyše \(N \leq 10\) a \(a_i \leq 2\).

V druhej sade zasa \(N \leq 10\) a \(a_i \leq 1000\).

V tretej sade \(N \leq 1000\) a \(a_i \leq 2\).

V štvrtej a piatej sade neplatia žiadne obmedzenia navyše.

Príklady

Input:

4
1 1 1 1

Output:

4

Máme v podstate štyri možnosti, ktorý bod vynecháme.

Input:

4
2 2 1 1

Output:

20

Input:

4
3 1 1 1

Output:

19

Buď posápajme body z druhej až štvrtej strany (1), alebo dva z nich s jedným z prvej strany (3 možnosti ako zvoliť dva body z tých troch strán, 3 možnosti ako zvoliť jeden bod z prvej = 9), alebo dva body z prvej strany s jedným bodom zo zvyšních (3 možnosti ako zvoliť dva body z prvej strany, 3 možnosti ako zvoliť posledný bod = 9), dokopy 19 možností.

Input:

5
47 0 7 8 9

Output:

392903