Laiko ribojimas: 1s

Atminties ribojimas: 256MB

Duomenų failas: antimaterija.in

Rezultatų failas: antimaterija.out

Jei norite pateikti savo sprendimą - prisijunkite.

Antimaterija

Gustas netikėtai atrado slaptą laboratoriją. Laboratorijoje jis rado n eilėje išrikiuotų įrenginių sunumeruotų nuo 1 iki n iš kairės į dešinę. Kiekvienas įrenginys gali sukurti a_i vienetų materijos arba antimaterijos.

Gustas nori pasirinkti kurią nors iš eilės einančių įrenginių seką, kiekvienam sekos įrenginiui nustatyti, kad gamintų materiją arba antimateriją ir nufotografuoti rezultatą. Vis dėlto, jam pavyks tik tuo atveju, jeigu antimaterijos bei materijos pagamintų kiekių suma sekoje bus vienoda.

Gustas prašo jūsų išsiaiškinti, kiek skirtingų nuotraukų jis gali padaryti. Nuotrauka skiriasi nuo kitos, jei jo pasirinktų įrenginių seka nuotraukoje skiriasi arba bent vienas jo pasirinktos sekos įrenginys vienoje nuotraukoje gamina materiją, o kitoje antimateriją.

Pradiniai duomenys

Pirmoje eilutėje yra skaičius n (1\\leqn\\leq1000).

Antroje eilutėje yra n sveikųjų skaičių a_i (1\\leqa_i\\leq1000).

(a_1+a_2+...+a_n\\leq10000)

Rezultatai

Išveskite vieną skaičių - kiek skirtingų nuotraukų gali padaryti Gustas moduliu 1000000007.

Pavyzdžiai

Pradiniai duomenys Rezultatai Paaiškinimas 
4
1 1 1 1
 
12
 
Skirtingos nuotraukos: [1+, 2-], [1-, 2+], [2+, 3-], [2-, 3+], [3+, 4-], [3-, 4+], [1+, 2+, 3-, 4-], [1+, 2-, 3+, 4-],
[1+, 2-, 3-, 4+], [1-, 2+, 3+, 4-], [1-, 2+, 3-, 4+] bei [1-, 2-, 3+, 4+]. i+ reiškia, jog i-tasis įrenginys gamina materiją, i- - antimateriją.