FJ’s NN (1≤N≤1001≤N≤100) cows are arranged in a line such that the iith cow in line has a non-negative integer hunger level of hihi. As FJ’s cows are social animals and insist on eating together, the only way FJ can decrease the hunger levels of his cows is to select two adjacent cows ii and i+1i+1 and feed each of them a bag of corn, causing each of their hunger levels to decrease by one.

FJ wants to feed his cows until all of them have the same non-negative hunger level. Although he doesn't know his cows' exact hunger levels, he does know an upper bound on the hunger level of each cow; specifically, the hunger level hihi of the ii-th cow is at most HiHi (0≤Hi≤10000≤Hi≤1000).

Your job is to count the number of NN-tuples of hunger levels [h1,h2,…,hN][h1,h2,…,hN] that are consistent with these upper bounds such that it is possible for FJ to achieve his goal, modulo 10**9+7109+7.

SAMPLE INPUT:

3
9 11 7

SAMPLE OUTPUT:

241

There are (9+1)⋅(11+1)⋅(7+1)(9+1)⋅(11+1)⋅(7+1) 33-tuples hh that are consistent with HH.

One of these tuples is h=[8,10,5]h=[8,10,5]. In this case, it is possible to make all cows have equal hunger values: give two bags of corn to both cows 22 and 33, then give five bags of corn to both cows 11 and 22, resulting in each cow having a hunger level of 33.

Another one of these tuples is h=[0,1,0]h=[0,1,0]. In this case, it is impossible to make the hunger levels of the cows equal.

SAMPLE INPUT:

4
6 8 5 9

SAMPLE OUTPUT:

137

Problem credits: Arpan Banerjee and Benjamin Qi