Description

The grass has dried up in Farmer John's pasture due to a drought. After hours ofdespair and contemplation, FJ comes up with the brilliant idea of purchasingcorn to feed his precious cows.

FJ’s $N$ cows are arranged in a line such that the $i$thcow in line has a non-negative integer hunger level of $h_i$. As FJ’s cows aresocial animals and insist on eating together, the only way FJ can decrease thehunger levels of his cows is to select two adjacent cows $i$ and $i+1$ and feedeach of them a bag of corn, causing each of their hunger levels to decrease byone.

FJ wants to feed his cows until all of them have the same non-negative hungerlevel. Although he doesn't know his cows' exact hunger levels, hedoes know an upper bound on the hunger level of each cow; specifically, thehunger level $h_i$ of the $i$-th cow is at most $H_i$.

Your job is to count the number of $N$-tuples of hunger levels$[h_1,h_2,\ldots,h_N]$ that are consistent with these upper bounds such that itis possible for FJ to achieve his goal, modulo $10^9+7$.

• $1 \leq N \leq 100$
• $0\le H_i\le 1000$

Input Format

The first line contains $N$.

The second line contains $H_1,H_2,\ldots,H_N$.

Output Format

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

3
9 11 7

3
9 11 7

There are $(9+1)\cdot (11+1)\cdot (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 allcows 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 cowhaving 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.

4
6 8 5 9

4
6 8 5 9

Scoring

$N$ is even in even-numbered tests and odd in odd-numbered tests.

• Tests 3 and 4 satisfy $N\le 6$ and $H_i \le 10$.
• Tests 5 through 10satisfy $N\le 50$ and $H_i \le 100$.
• Tests 11 through 20 satisfy nofurther constraints.

Problem Credit

Problem credits: Arpan Banerjee and Benjamin Qi