Las jóvenes de IslaGrande encontraron una caja con perlas de sus antepasados. En la caja habían ~N~ perlas coloreadas con ~K~ colores. Ellas decidieron poner todas las perlas sobre un cordel para formar un collar. Los únicos objetos en el collar serían las ~N~ perlas pues ellas no piensan poner ningún otro elemento ornamental. No conformes, quieren saber cuántos collares diferentes pueden obtenerse utilizando todas las perlas. Dos collares se consideran idénticos si, puestos sobre una superficie plana, después de un número de rotaciones y reflexiones de uno de los collares este resulta ser igual al otro.

Tarea

Hacer un programa que permita:

• Leer desde la entrada el número ~K~ de colores de perlas y la cantidad de perlas de cada color ~A_1, A_2,..., A_k~.

• Encontrar cuántos collares diferentes se pueden formar si ellas ordenan las perlas sobre una cuerda.

• Escribir hacia la salida la cantidad de collares diferentes encontrados.

Entrada

La entrada contiene:

Linea 1: ~K~, el número de colores de las perlas.

Linea 2: ~A_1, A_2,.., A_k~, la cantidad de las perlas de cada color disponibles, separadas entre sí por un espacio en blanco.

Salida

La salida contiene en una sola línea el número de collares diferentes los cuales pueden ser formados de la manera descrita anteriormente, modulo 1000000007:

Restricciones

• ~N = A_1 + A_2 +...+ A_k~.

• ~1 \le N \le 1 000 000~.

• ~1 \le K \le 100 000~.

• En el 10% de los casos de prueba, ~N \le 8~.

• En otro 20% de los casos de prueba, ~3 \le K, A_1 = 1, A_2~ y \(А_3\) son impares.

• En otro 30% de los casos de prueba, ~A_1 = 1~.

Ejemplo #1 de Entrada

3
1 1 1

Ejemplo #1 de Salida

1

Ejemplo #2 de Entrada

2
2 2

Ejemplo #2 de Salida

2

Explicación del Ejemplo # 1: Dos collares con tres perlas de diferentes colores son el mismo. Sean los colores blanco, verde y rojo. Dos collares puestos sobre una mesa, el primero con las perlas en el orden (blanca, verde, roja) y el segundo con las perlas (blanca, roja, verde). No es suficiente rotar un collar entonces levantamos un collar y lo reflejamos para hacer que ellos sean el mismo.

Explicación del Ejemplo # 2: Tenemos dos perlas blancas y dos rojas. En este caso, las perlas pueden alternar (blanca, roja, blanca, roja) o estar adyacentes (blanca, blanca, roja, roja). No hay manera de que los dos collares parezcan el mismo a través de rotaciones o reflexiones.