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 N (1≤N≤100) cows are arranged in a line such that the ith cow in line has a non-negative integer hunger level of hi. 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 i and i+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 hi of the i-th cow is at most Hi (0≤Hi≤1000).
Your job is to count the number of N-tuples of hunger levels [h1,h2,…,hN] that are consistent with these upper bounds such that it is possible for FJ to achieve his goal, modulo 10^9+7.
INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains N.
The second line contains H1,H2,…,HN.
OUTPUT FORMAT (print output to the terminal / stdout):
The number of N-tuples of hunger levels modulo 10^9+7.
SAMPLE INPUT:
3
9 11 7
SAMPLE OUTPUT:
241
There are (9+1)⋅ (11+1)⋅ (7+1) 3-tuples h that are consistent with H.
One of these tuples is 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 2 and 3, then give five bags of corn to both cows 1 and 2, resulting in each cow having a hunger level of 3.
Another one of these tuples is 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:
N is even in even-numbered tests and odd in odd-numbered tests.
Tests 3 and 4 satisfy N≤6 and Hi≤10.
Tests 5 through 10 satisfy N≤50 and Hi≤100.
Tests 11 through 20 satisfy no further constraints.