Cerca elegante


Submit solution

Points: 100 (partial)
Time limit: 0.1s
Memory limit: 32M

Author:
Problem type
Allowed languages
C++

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


Comments

There are no comments at the moment.