P8096 [USACO22JAN] Drought G

All the grass in Farmer John’s pasture has dried up in a severe drought. After hours of despair and thinking, FJ comes up with a brilliant idea: buy corn to feed his precious cows. FJ’s $N$ cows ($1 \leq N \leq 100$) are standing in a line. The hunger level of the $i$-th cow in the line is a non-negative integer $h_i$. Since FJ’s cows are social animals, they insist on eating together. The only way for FJ to decrease the cows’ hunger levels is to choose two adjacent cows $i$ and $i+1$ and feed each of them one bag of corn, which decreases both of their hunger levels by 1. FJ wants to feed his cows until all cows have the same non-negative hunger level. Although he does not know the exact hunger levels of his cows, he knows an upper bound for each cow; specifically, the hunger level $h_i$ of the $i$-th cow is at most $H_i$ ($0 \le H_i \le 1000$). Your task is to compute the number of $N$-tuples $[h_1,h_2,\ldots,h_N]$ that satisfy the above upper bounds and for which it is possible for FJ to achieve his goal. Output the answer modulo $10^9+7$.

The first line of input contains $N$. The second line contains $H_1, H_2, \ldots, H_N$.

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

[Sample Explanation] There are $(9+1)\cdot (11+1)\cdot (7+1)$ different 3-tuples $h$ that are consistent with $H$. $h = [8,10,5]$ is one such tuple. In this case, it is possible to make all cows have the same hunger level: feed cows $2$ and $3$ two bags of corn each, then feed cows $1$ and $2$ five bags of corn each, and all cows will end up with hunger level $3$. $h = [0,1,0]$ is another tuple. In this case, it is not possible to make the cows’ hunger levels equal. [Constraints] - In test points with even indices, $N$ is even. In test points with odd indices, $N$ is odd. - Test points 3-4 satisfy $N \le 6$ and $H_i \le 10$. - Test points 5-10 satisfy $N \le 50$ and $H_i \le 100$. - Test points 11-20 have no additional constraints. Translated by ChatGPT 5