Drought

Time limit1sMemory limit1024 MB

Summary

Count N-tuples of hunger levels within given upper bounds for which adjacent-pair feedings can make all cows equal, modulo 1e9+7.

Level: Hard8 of 10
Topics: Dynamic programming, Combinatorics, Math, Greedy
Solved: No attempts yet

Problem

The grass in Farmer John's pasture has dried up because of a drought. After hours of despair and contemplation, FJ comes up with the idea of buying corn to feed his precious cows.

FJ's $N$ cows ( $1 \leq N \leq 100$ ) stand in a line, and the $i$ -th cow in line has a non-negative integer hunger level $h\_i$ . Because FJ's cows are social animals and insist on eating together, the only way FJ can decrease their hunger levels is to pick two adjacent cows $i$ and $i+1$ and feed each of them a bag of corn, which decreases each of their hunger levels by one.

FJ wants to feed his cows until all of them have the same non-negative hunger level. He does not know his cows' exact hunger levels, but he does know an upper bound on each cow's hunger level: the hunger level $h\_i$ of the $i$ -th cow is at most $H\_i$ ( $0\le H\_i\le 1000$ ).

Among the $N$ -tuples of hunger levels $\[h\_1,h\_2,\ldots,h\_N]$ that are consistent with these upper bounds, count those for which FJ can achieve his goal, modulo $10^9+7$ .

Input

The first line contains $N$ .

The second line contains $H\_1,H\_2,\ldots,H\_N$ .

Output

Print the number of $N$ -tuples of hunger levels modulo $10^9+7$ .

Examples2

Example 1
Input
```
3
9 11 7
```
Expected output
```
241
```
Example 2
Input
```
4
6 8 5 9
```
Expected output
```
137
```