Drought

문제

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\le N\le 1001\; \backslash leq\; N\; \backslash leq\; 100$) cows are arranged in a line such that the $ii$th cow in line has a non-negative integer hunger level of $h_{i}h\_i$. 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 $h_{i}h\_i$ of the $ii$-th cow is at most $H_{i}H\_i$ ($0\le H_i\le 10000\backslash le\; H\_i\backslash le\; 1000$).

Your job is to count the number of $NN$-tuples of hunger levels $[h_1,h_2,\dots ,h_N][h\_1,h\_2,\backslash ldots,h\_N]$ that are consistent with these upper bounds such that it is possible for FJ to achieve his goal, modulo ${10}^9+710^9+7$.

입력

The first line contains $NN$.

The second line contains $H_1,H_2,\dots ,H_{N}H\_1,H\_2,\backslash ldots,H\_N$.

출력

The number of $NN$-tuples of hunger levels modulo ${10}^9+710^9+7$.

3
9 11 7

241

4
6 8 5 9

137