Note el límite de tiempo y memoria inusual para este problema

Todo el mundo sabe que Alicia tiene la cerca más elegante en toda la ciudad. Está construida a partir de ~N~ secciones elegantes. Las secciones elegantes son rectángulos puestos uno al lado del otro en el suelo. La sección ~i~ tiene una altura entera ~h_i~ y un ancho entero ~w_i~.

Estamos buscando rectángulos elegantes en esta cerca elegante. Un rectángulo es elegante si:

• sus lados son horizontales o verticales y tienen longitudes enteras.
• la distancia entre el rectángulo y el suelo es entera.
• la distancia entre el rectángulo y el lado izquierdo de la primera sección es entera.
• está completamente dentro de las secciones.

¿Cuál es el número de rectángulos elegantes?

Este número puede ser muy grande, así que estamos interesados en su módulo ~10^9+7~

Subtareas

• Subtarea 1 (12 puntos): ~N \leq 50~ y ~h_i \leq 50~ y ~w_i = 1~ para todo ~i~.
• Subtarea 2 (13 puntos): ~h_i \leq 2~ para todo ~i~.
• Subtarea 3 (15 puntos): ~h_i = h_j~ para todo ~i, j~.
• Subtarea 4 (15 puntos): ~h_i \leq h_{i+1}~ para todo ~i \leq N-1~.
• Subtarea 5 (18 puntos): ~N \leq 1000~.
• Subtarea 6 (27 puntos): Sin restricciones adicionales.

Entrada

La primera línea contiene un entero ~N~ (~1 \leq N \leq 10^5~), el número de secciones.

La segunda línea contiene ~N~ enteros separados por espacios, el ~i~-ésimo es ~h_i~ (~1 \leq h_i \leq 10^9~).

La tercera línea contiene ~N~ enteros separados por espacios, el ~i~-ésimo es ~w_i~ (~1 \leq h_i \leq 10^9~).

Salida

Imprima un solo entero, el número de rectángulos elegantes módulo ~10^9+7~. Por tanto el rango de la salida es ~0, 1, 2, ..., 10^9+6~

Ejemplo

Entrada ejemplo 1

2
1 2
1 2

Salida ejemplo 1

12

Nota

La cerca tiene ~2~ secciones, una sección de ~1~ de altura ~1~ de ancho, y otra de ~2~ de altura y ~2~ de ancho, respectivamente. Hay ~5~ rectángulos elegantes de dimensiones: ~1x1~ Hay ~3~ rectángulos elegantes de dimensiones: ~1x2~ Hay ~1~ rectángulos elegantes de dimensiones: ~1x3~ Hay ~2~ rectángulos elegantes de dimensiones: ~2x1~ Hay ~1~ rectángulos elegantes de dimensiones: ~2x2~