Cerca elegante

Points: 100 (partial)

Time limit: 0.1s

Memory limit: 32M

Author:

mdario

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$ $N$ secciones elegantes. Las secciones elegantes son rectángulos puestos uno al lado del otro en el suelo. La sección $i$ $i$ tiene una altura entera $h_i$ $h_{i}$ y un ancho entero $w_i$ $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$ $10^{9} + 7$

Subtareas

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

Entrada

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

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

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

Salida

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

Ejemplo

Entrada ejemplo 1

Copy

2
1 2
1 2

Salida ejemplo 1

Copy

Nota

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

Comments

There are no comments at the moment.