#USACOC2222A. Drought

Drought

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 NN cows are arranged in a line such that the iithcow in line has a non-negative integer hunger level of hih_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 ii and i+1i+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 hih_i of the ii-th cow is at most HiH_i.

Your job is to count the number of NN-tuples of hunger levels[h1,h2,,hN][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 109+710^9+7.

  • 1N1001 \leq N \leq 100
  • 0Hi10000\le H_i\le 1000

Input Format

The first line contains NN.

The second line contains H1,H2,,HNH_1,H_2,\ldots,H_N.

Output Format

The number of NN-tuples of hunger levels modulo 109+710^9+7.

3
9 11 7
3
9 11 7

There are (9+1)(11+1)(7+1)(9+1)\cdot (11+1)\cdot (7+1) 33-tuples hh that are consistent withHH.

One of these tuples is h=[8,10,5]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 22 and 33,then give five bags of corn to both cows 11 and 22, resulting in each cowhaving a hunger level of 33.

Another one of these tuples is h=[0,1,0]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

NN is even in even-numbered tests and odd in odd-numbered tests.

  • Tests 3 and 4 satisfy N6N\le 6 and Hi10H_i \le 10.
  • Tests 5 through 10satisfy N50N\le 50 and Hi100H_i \le 100.
  • Tests 11 through 20 satisfy nofurther constraints.

Problem Credit

Problem credits: Arpan Banerjee and Benjamin Qi