La hierba se ha secado en los pastos del granjero John debido a la sequía. Tras horas de desesperación y contemplación, a FJ se le ocurre la brillante idea de comprar maíz para alimentar a sus preciadas vacas.

Las ~N (1 \leq N \leq 100)~ vacas de FJ están dispuestas en una línea tal que la ~i~-ésima vaca en línea tiene un nivel de hambre entero no negativo de ~h_i~. Como las vacas de FJ son animales sociales e insisten en comer juntas, la única forma en que FJ puede disminuir los niveles de hambre de sus vacas es seleccionar dos vacas adyacentes ~i~ e ~i~+~1~ y alimentar a cada una de ellas con una bolsa de maíz, haciendo que sus niveles de hambre disminuyan en uno.

FJ quiere alimentar a sus vacas hasta que todas tengan el mismo nivel de hambre no negativo. Aunque no conoce los niveles de hambre exactos de sus vacas, sí conoce un límite superior del nivel de hambre de cada vaca; concretamente, el nivel de hambre ~h_i~ de la ~i~-ésima vaca es como máximo ~H_i (0 \leq H_i \leq 1000)~.

Tu trabajo es contar el número de ~N-tuplas~ de niveles de hambre ~[h_1,h_2,...,h_n]~ que se ajustan a estos límites superiores de manera que FJ pueda alcanzar su objetivo, módulo ~10^9~+~7~.

Entrada

• La primera línea contiene ~N~
• La segunda línea contiene ~h_1,h_2,...,h_n~

Salida

El número de ~N~ tuplas de niveles de hambre modulo ~10^9~+~7~

Ejemplo #1 de Entrada

3
9 11 7

Ejemplo #1 de Salida

241

Explicación de Ejemplo:

Hay ~(9+1)*(11+1)*(7+1) ~3-tuplas ~h~ que son consistentes con ~H~.

Una de estas tuplas es ~h=[8,10,5]~. En este caso, es posible hacer que todas las vacas tengan valores de hambre iguales: dar dos bolsas de maíz a las vacas ~2~ y ~3~, y luego dar cinco bolsas de maíz a las vacas ~1~ y ~2~, lo que hace que cada vaca tenga un nivel de hambre de ~3~.

Otra de estas tuplas es ~h=[0,1,0]~. En este caso, es imposible que los niveles de hambre de las vacas sean iguales.

Ejemplo #2 de Entrada

4

6 8 5 9

Ejemplo #2 de Salida

137