심한 가뭄 (Drought) timer 2초 memory 256MB

​가뭄으로 농부 창호의 목초지에 풀이 말라버렸다!

몇 시간 동안의 절망과 숙고 끝에 창호는 소중한 소들에게 먹일 옥수수를 사겠다는 기발한 아이디어를 낸다.

창호는 N마리의 (1≤N≤100) 젖소를 한 줄로 세웠다.

i번째 젖소의 배고픔은 h_i로 표현된다. (0\le h_i, h_i는 정수)

창호의 젖소는 사회적 동물이라 혼자서만 이기적으로 배부를 수는 없다.

창호는 두 인접한 젖소 i와 i+1을 골라 옥수수를 먹이고 h_i와 h_{i+1}을 1씩 줄일 수 있다.

창호는 모든 젖소가 배고픈 정도가 음수가 아니면서 똑같아지도록 먹이를 주고 싶다.

창호는 소의 배고픈 정도를 정확히 알지는 못하지만 각 소의 배고픔의 상한은 알고 있다.

구체적으로, i번째 젖소의 배고픔 h_i는 최대 H_i (0\le H_i \le 1000)이다.

창호가 목표를 달성할 수 있는 소의 배고픔 [h_1,h_2,…,h_N]의 경우의 수를 10^9+7​로 나눈 나머지를 구하라.