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 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 109+7.
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.
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.
Problem credits: Arpan Banerjee and Benjamin Qi
Source: USA Computing Olympiad.
Input Format
The first line contains N.
The second line contains H1,H2,…,HN.
Output Format
The number of N-tuples of hunger levels modulo 109+7.