Equal Cow Hunger

Farmer John has N cows lined up, where the i-th cow has an unknown hunger level h_i, which is a non-negative integer at most H_i. Due to a severe drought, all the grass has dried up and FJ has decided to feed his cows with corn. The cows are social animals and always eat together. FJ can only lower their hunger by selecting two adjacent cows i and i+1 and feeding each one a bag of corn, which decreases both of their hunger levels by 1.

Because the feeding operation subtracts 1 from two consecutive cows, the differences between adjacent cows' hunger levels remain invariant. In other words, for any feeding operation on cows i and i+1, the value h_{i+1} − h_i does not change. Therefore, to eventually have all cows reach the same hunger level (i.e. h_1 = h_2 = ... = h_N), the initial configuration must already have all cows with an equal hunger level.

We are given the upper bounds H_1, H_2, ..., H_N for each cow’s hunger level. A valid N‐tuple [h_1, h_2, …, h_N] (with 0 ≤ h_i ≤ H_i) is one from which it is possible to achieve equal hunger levels, which implies that h_1 = h_2 = … = h_N. Let x denote this common hunger level. Then in order for the tuple to be valid we must have 0 ≤ x ≤ min(H_1, H_2, …, H_N).

Your task is to compute the number of valid N‐tuples such that FJ can eventually feed his cows to make their hunger levels equal. The answer should be given modulo (10^9+7).

Mathematically, the answer is (\min{H_1, H_2, \ldots, H_N} + 1).

inputFormat

The first line of input contains a single integer N (1 ≤ N ≤ 100) representing the number of cows. The second line contains N space-separated integers H_1, H_2, ..., H_N (0 ≤ H_i ≤ 1000), where H_i is the upper bound on the hunger level of the i-th cow.

outputFormat

Output a single integer, the number of valid N-tuples [h_1, h_2, …, h_N] for which it is possible to reach equal hunger levels, modulo (10^9+7).

sample

3
3 4 5

4