The grass has dried up in Farmer John's pasture due to a drought. After hours of despair and contemplation, FJ comes up with the brilliant idea of purchasing corn to feed his precious cows.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 109**+**7109+7.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains NN.The second line contains H1**,H2**,…,HNH1,H2,…,HN.

OUTPUT FORMAT (print output to the terminal / stdout):

The number of NN-tuples of hunger levels modulo 109**+**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

SCORING:

NN is even in even-numbered tests and odd in odd-numbered tests.

• Tests 3 and 4 satisfy N≤6N≤6 and Hi≤10Hi≤10.
• Tests 5 through 10 satisfy N≤50N≤50 and Hi≤100Hi≤100.
• Tests 11 through 20 satisfy no further constraints.