El Granjero Nauj dejó a Bessie en el medio de la nada. En el tiempo ~t=0~, Bessie está ubicada en ~x=0~ en una línea numérica infinita. Ella busca freneticamente una salida moviéndose a la izquierda o a la derecha 1 unidad cada segundo. Sin embargo, realmente no hay salida y después de ~T~ segundos, Bessie está de vuelta en ~x=0~, cansada y resignada.

El Granjero Nauj trata de rastrear a Bessie pero solamente sabe cuántas veces Bessie cruza ~x=.5,1.5,2.5,...,(N-1).5~, dadas en un arreglo ~A_0,A_1,...,A_{N-1}~. Bessie nunca llega a ~x>N~ tampoco a ~x<0~.

En particular, la ruta de Bessie puede ser representada por una cadena de ~T = \sum_{i=0}^{N-1} A_i~ ~Ls~ y ~Rs~ donde el caracter i-ésimo representa la dirección en que Bessie se mueve en el segundo i-ésimo. El número de cambios de direcciones está definido como el número de ocurrencias de ~LRs~ más el número de ocurrencias de ~RLs~. Por favor, ayude al Granjero Nauj a contar el número de rutas que Bessie podría haber tomado que son consistentes con ~A~ y minimice el número de cambios de dirección. Se garantia que al menos hay una ruta válida.

Entrada

• La primera línea contiene ~N~.
• La segunda línea contiene ~A_0,A_1,...,A_{N-1}~.

Salida

El número de rutas que Bessie podría haber tomado, modulo ~10^9+7~.

Restricciones

• ~1 \leq N \leq 10^5~
• ~1 \leq A_i \leq 10^6~

Ejemplo de Entrada

2
4 6

Ejemplo de Salida

2

Bessie debe cambiar dirección al menos 5 veces. Hay dos ruts correspondiendo al cambio de dirección exactamente 5 veces:

RRLRLLRRLL
RRLLRRLRLL

Calificaciones

Entradas	Restricciones adicionales
2-4	~N \leq 2~ y ~\max(A_i) \leq 10^3~
5-7	~N \leq 2~
8-11	~\max(A_i) \leq 10^3~
12-21	Sin restricciones adicionales

USACO 2023 January Contest, Gold Problem 3. Moo Route.