A los jóvenes de IslaGrande les gustan mucho los dulces, tal es así que para el cumpleaños colectivo del mes de Febrero se compraron cantidades de sus ~N~ tipos de dulces favoritos. Para ser más específico, ellos compraron ~A_1~ dulces del tipo 1, ~A_2~ dulces del tipo 2,…, ~A_n~ dulces del tipo N, pero decidieron que les gustaría comerse el último dulce del tipo 1 antes de comerse el último dulce del tipo 2, comerse el último dulce del tipo 2 antes que el último dulce del tipo 3, y así sucesivamente. En otras palabras, el último dulce del tipo i debe comerse antes que el último dulce del ~tipo i+1~, para ~i~ entre ~1~ y ~N-1~.

Tarea

Hacer un programa que permita:

• Leer los ~N~ tipos de dulces favoritos comprados y la cantidad ~A_i~ de cada uno de ellos.
• Encontrar el número de maneras que pueden comerse todos los dulces cumpliendo con la restricción antes descrita si sabemos que dos dulces del mismo tipo son indistinguibles uno del otro.
• Escribir el número encontrado de maneras que pueden comerse todos los dulces.

Entrada

La entrada contiene:

• Línea 1: ~N~, representa la cantidad de tipos de dulces favoritos.
• Línea 2..N+1: en cada una de estas líneas se escribirá un entero el cual representa la cantidad de dulces del tipo ~A_i~ comprados.

Salida

La salida contiene en una sola línea el resto de dividir el número encontrado de maneras que pueden comerse todos los dulces entre ~10^9+7~.

Restricciones

• ~2 \leq N \leq 1 000~.
• ~1 \leq A_i \leq 10^6~.
• ~\sum_{i=0}^{n} A_i \leq 10^{6}~

Ejemplo de Entrada

2
2
3

Ejemplo de Salida

6